基于消息传递的并行计算.ppt

并行计算ParallelComputing 基于消息传递的并行计算 消息传递库 消息传递软件中最流行的是MPI和PVM 它们能运行在所有的并行平台上 包括SMP和PVP 二者已经在Windows和各种Unix平台上实现 程序设计语言支持C Fortran 在国产的三大并行机系列神威 银河和曙光上都实现了对MPI和PVM和支持 消息传递库 PVM 开发时间 始于1989年开发单位 美国Tennessee大学 OakRidge国家实验室和Emory大学联合研制特点 具有较好的适应性 可扩展性 可移植性和易使用性等特点 源代码可以免费获取 现已被用户广泛采纳 现状 目前对它的研究和开发工作仍在各大学和研究机构进行 尽管已经有越来越多的人开始使用MPI 但PVM仍然是做并行处理最流行的软件之一 随着它的不断流行 已经被移植到PVP SMP MPP 工作站和PC组成的机群系统 消息传递库 MPI 目标 提供一个实际可用的 可移植的 高效的和灵活的消息传递接口标准 MPI以语言独立的形式来定义这个接口库 并提供了与C Fortran语言的绑定 这个定义不包含任何专用于某个特别的制造商 操作系统或硬件的特性 MPI在并行计算界被广泛地接受 消息传递库 MPI MPI的实现建立在厂家专用的环境之上IBMSP2的POE MPL IntelParagon的OSF Nx公共的MPI环境 CHIMPEdinburg大学LAM LocalAreaMulticomputer Ohio超级计算中心MPICHArgonne国家实验室与Mississippi州立大学MPICH是MPI在各种机器上的可移植实现 可以安装在几乎所有的平台上 PC工作站SMPMPPCOW 消息传递模式 关于通信模式 用户需要理解的有三个方面 共有多少个进程 进程间如何同步 如何管理通信缓冲区 现在的消息传递系统多使用三种通信模式 同步的消息传递 SynchronousMessagePassing 阻塞的消息传递 BlockingMessagePassing 非阻塞的消息传递 NonblockingMessagePassing SynchronousMessagePassing BlockingandNonblockingMessagePassing BlockingIthasbeenusedtodescriberoutinesthatdonotreturnuntilthetransferiscompleted Theroutinesare blocked fromcontinuing Inthatsense thetermssynchronousandblockingweresynonymous Non blockingIthasbeenusedtodescriberoutinesthatreturnwhetherornotthemessagehadbeenreceived Send Receivebuffer ProcessP M 10 L1 sendMtoQ L2 M 20 gotoL1 ProcessQ L1 S 100 L2 receiveSfromP X S 1 Send Receivebuffer M sendmessagebuffer orsendbufferS receivemessagebuffer orreceivebuffer BlockingBufferedSend Receive Forsendroutine oncethelocalactionshavebeencompletedandthemessageissafelyonitsway theprocesscancontinuewithsubsequentwork Bufferscanonlybeoffinitelengthandapointcouldbereachedwhenthesendroutineisheldupbecausealltheavailablebufferspacehasbeenexhausted Generally amessagebufferneededbetweensourceanddestinationtoholdmessage Non BlockingMessagePassing Itreturnsfromthesendorreceiveoperationbeforeitissemanticllysafe Theyaregenerallyaccompaniedbyacheck statusoperation Onemustbecarefulusingnon blockingprotocolssinceerrorscanresultfromunsafeaccesstodatathatbeingcommunicated 非阻塞模式的安全 ProcessP M 10 sendMtoQ dosomecomputationwhichdoesnotchangeM waitforMtobesent M 20 ProcessQ S 100 receiveSfromP dosomecomputationwhichdoesnotuseS waitforStobereceived X S 1 非阻塞模式下 强制进程等待直到安全时再继续执行 非阻塞模式本身也会带来一些额外开销 作为临时缓冲区用的内存空间分配缓冲区的操作将消息拷入和拷出临时缓冲区执行一个额外的检测和等待函数 消息传递方式 消息传递方式 消息传递 消息传递的特点 在消息传递模型中 一个并行应用由一组进程组成 每个进程的代码是本地的 只能访问私有数据 进程之间通过传递消息实现数据共享和进程同步 优点 用户可以对并行性的开发 数据分布和通信实现完全控制 缺点 要求程序员显式地处理通信问题 如 消息传递调用的位置 数据移动 数据复制 数据操作 数据的一致性等等 对大多数科学计算程序来说 消息传递模型的真正困难还在于显式的域分解 也就是说 将对相应数据的操作限定在指定的处理器上进行 在每个处理器上只能看见整个分布数据的一部分 无法以渐进的方式 通过逐步将串行代码转换成并行代码而开发出来 大量的散布在程序各处的域分解要求整个程序由串行到并行的转换一次性实现 而共享存储方法允许在现有的串行代码中插入并行说明从而实现逐步转换 与之相比 这是消息传递的一个明显的缺点 PVM ParallelVirtualMachine PVM ParallelVirtualMachine isapackageoflibrariesandruntimedaemonsthatenablesbuildingparallelappseasilyandefficientlyAllowsacollectionofheterogeneousmachinestobeviewedandusedasasingle virtual parallelmachine KeyattributesofPVM RunsoneveryUNIX LinuxandWNT W95Runsovermostphysicalnetworks ethernet FDDI Myrinet ATM Shared Memory AheterogeneouscollectionofmachinescanbeassembledandusedasaSuperComputerProgrammingiscompletelyportableTheunderlyingmachineandnetworkistransparenttotheprogrammer userEachuserhashis hersownprivateVM HeterogeneousNetworkComputingModelforPVM Nodesmaybeheterogeneousintermsofarchitecture dataformat speed andload Performancecanbeoptimizedbyassigningeachindividualtasktomostappropriatearchitecture PVMComputingModel ApplicationprogramiswrittenasacollectingofinteractingPVMtasks ThesetaskscanaccessPVMresourcesthroughalibraryofstandardinterfaceroutines Theseroutinesprovideprocesscontrol communication andsynchronizationmechanismacrossanetworkofheterogeneousmachines PVMComponents daemon calledpvmd3orpvmd residesonallthecomputersmakingupthevirtualmachine PVMlibrary containsuser callableroutinesformessagepassing spawningprocesses coordinatingtasks andmodifyingthevirtualmachine PVMComponents pvmd pvmdisresponsiblefor providinginter hostpointofcontacttaskauthenticationexecutingprocessesonmachinesmessageroutingtransmittingmessagesfromitsapplicationtoadestinationreceivingandbufferingmessagesfromotherpvmd suntilthedestinationapplicationcandealwiththem StartingPVM Typepvmpvm addhostnamepvm deletehostnamepvm confpvm ps aquit quittheconsoleprompt pvm halt PVMconsole Theavailablecommandsareadd followedbyoneormorehostnames addsthesehoststothevirtualmachine alias definesorlistscommandaliases conf liststheconfigurationofthevirtualmachineincludinghostname pvmdtaskID architecturetype andarelativespeedrating delete followedbyoneormorehostnames deletesthesehostsfromthevirtualmachine PVMprocessesstillrunningonthesehostsarelost echo echoarguments halt killsallPVMprocessesincludingconsole andthenshutsdownPVM Alldaemonsexit help PVMconsole cont jobs listsrunningjobs kill canbeusedtoterminateanyPVMprocess mstat showsthestatusofspecifiedhosts ps a listsallprocessescurrentlyonthevirtualmachine theirlocations theirtaskid s andtheirparents taskid s pstat showsthestatusofasinglePVMprocess quit exitstheconsole leavingdaemonsandPVMjobsrunning reset killsallPVMprocessesexceptconsoles andresetsalltheinternalPVMtablesandmessagequeues Thedaemonsareleftinanidlestate setenv displaysorsetsenvironmentvariables PVMconsole cont sig followedbyasignalnumberandTID sendsthesignaltothetask spawn startsaPVMapplication Optionsincludethefollowing count numberoftasks defaultis1 host spawnonhost defaultisany ARCH spawnofhostsoftypeARCH enabledebugging redirecttaskoutputtoconsole file redirecttaskoutputtofile file redirecttaskoutputappendtofile PVMconsole cont tracejob displayoutputonconsole file tracejob outputtofiletrace setsordisplaysthetraceeventmask unalias undefinescommandalias version printsversionofPVMbeingused sampleapplication Basichelloworldsampleprogram Spawnsaslaveandreceivesastringfromit include includemain intcc tid charbuf 100 printf i mt x n pvm mytid spawn1copyofhello otheronanymachine cc pvm spawn hello other char 0 PvmTaskDefault 1 pvm mytid intpvm mytid pvm mytid returnsthetidofthecallingtask EachPVMtaskhasaunique tid TaskIDwhichisassignedtoitwhenitiscreated Eachhosthasarangeof0 x40000tidsavailable Thusatidwilllooklike0 x40003or0 xC001a pvm parent intpvm parent pvm parent returnsthetidofthecallingtasksparent thetaskwhichspawnedit Inthecasewherethetaskwasn tspawnedPvmNoParent 1 isreturned pvm spawn intpvm spawn char task char argv intflag char where intntask int tids Spawnsataskwhichisaexecutablewithoptionalcommandlinearguments Canspawnseveralcopiesonseveralmachinesdependingontheflagargument Thetidsofspawnedtasksarereturnedintidsandthenumberofspawnedtasksisreturnedbythefunction Thecombinationflagandwheredefinewherethetaskswillbespawned PvmTaskDefault spawnonanymachinePvmTaskHost spawnonthemachinenamedinwherePvmTaskArch spawnonthearchitecturenamedinwherePvmTaskDebug spawnthetaskinadebuggerPvmHostCompl spawnonanymachineexceptwhere Receivingamessage intpvm recv intsource inttag Blockuntilamessagesentbysourcewithtagarrives 1isawildcardvaluethatreceivesfromanysourceortag Returnstheidofthemessagebufferused intpvm upkstr char str Unpackastringfromthemessagebuffer intpvm upkint char ip intsize intsize Unpacksizeintegers insertthemineveryotherstrideplaceinip intpvm bufinfo intbuf int bytes int tag int tid Usingbufthebufferidreceivedfrompvm recv getthesizebytes tagandtidofthereceivedmessage spawnedapp Slavepartofhelloworldsampleprogram Sendsastringtothetaskthatspawnedit include defineHELLO TAG100main intptid charbuf 100 ptid pvm parent strcpy buf hello worldfrom gethostname buf strlen buf 64 sendstringtoparent pvm initsend PvmDataDefault pvm pkstr buf pvm send ptid HELLO TAG pvm exit exit 0 Sendingamessage intpvm initsend intencoding Initabufferforsendingamessage Encodingdefineshowthedataispacked usePvmDataDefaultforXDRencoding intpvm pkstr char str Packastringintothebuffer intpvm pkint int ip intsize intstride Packanarrayofsizeintegers packeveryotherstrideinteger intpvm send inttarget inttag Sendthebuffertotidtarget Identifythemessagebytag XPVM AGraphicalConsoleandMonitorforPVM ConsoleCommands NetworkView Space TimeView UtilizationView CallTraceandTaskOutputViews MPI Messagepassinginterface MPI是一个库 而不是一门语言 许多人认为MPI就是一种并行语言 这是不准确的 但是按照并行语言的分类 可以把FORTRAN MPI或C MPI看作是一种在原来串行语言基础之上扩展后得到的并行语言 MPI库可以被FORTRAN77 C Fortran90 C 调用 从语法上说它遵守所有对库函数 过程的调用规则 和一般的函数 过程没有什么区别 MPI Messagepassinginterface MPI是一种标准或规范的代表 而不特指某一个对它的具体实现 迄今为止所有的并行计算机制造商都提供对MPI的支持 可以在网上免费得到MPI在不同并行计算机上的实现 一个正确的MPI程序可以不加修改地在所有的并行机上运行 MPI Messagepassinginterface MPI是一种消息传递编程模型 并成为这种编程模型的代表和事实上的标准 MPI虽然很庞大 但是它的最终目的是服务于进程间通信这一目标的 MPI Messagepassinginterface BasicMPIConceptsAsetofprocessesexecutinginparallel Theseprocesseshaveseparateaddressspace Communicationbetweenprocessesiscooperative Oneprocessexecuteasendandtheotherexecuteareceiveoperation Message Data Envelope HowMPIWorks ImplementedasalibraryInstructionsanddataarepassedbetweeneachcomputerintheclusterviatheMPIlibraries WhatisIncludedinMPI Point to pointcommunicationCollectiveoperationsProcessgroupsCommunicationdomainsProcesstopologiesEnvironmentalmanagementandinquiryProfilinginterfaceBindingsforFortranandC C WhatisNotIncludedinMPI Explicitshared memoryoperationsOperationsthatrequiremoreoperatingsystemsupportthanwasstandardduringtheadoptionofMPI forexample interrupt drivenreceives remoteexecution ProgramconstructiontoolsDebuggingfacilitiesExplicitsupportforthreadsSupportfortaskmanagementI Ofunctions Advantages Reliable message orientatedcommunicationWidelyusedPortableimplementationsManyvendorimplementations Disadvantages NofaulttoleranceRestrictedtoeitherCorFortranPerformanceissues BasicFeaturesofMPIPrograms AnMPIprogramconsistsofmultipleinstancesofaserialprogramthatcommunicatebylibrarycall Callsmayberoughlydividedintofourclasses Callsusedtoinitialize manage andterminatecommunicationsCallsusedtocommunicatebetweenpairsofprocessors Paircommunication Callsusedtocommunicateamonggroupsofprocessors Collectivecommunication Callstocreatedatatypes AFirstProgram HelloWorld C include includevoidmain intargc char argv interr err MPI Init FortranPROGRAMhelloINCLUDE mpif h INTEGERerrCALLMPI INIT err PRINT helloworld CALLMPI FINALIZE err END ASampleMPIProgram include include include mpi h main intargc char argv intmy rank processrank intp no ofprocesses intsource rankofsender intdest rankofreceiver inttag 0 messagetag like emailsubject charmessage 100 buffer MPI Statusstatus functionreturnstatus StartupMPI MPI Init master workers Hello ASampleMPIProgram if my rank 0 MasterProcess for source 1 source p source MPI Recv message 100 MPI CHAR source tag MPI COM WORLD Execution cc ohellohello c lmpi mpirun p2helloHello Iamprocess1 mpirun p4helloHello Iamprocess1 Hello Iamprocess2 Hello Iamprocess3 mpirunhello nooutput therearenoworkers nogreetings 初始化MPI环境 得到每个进程在组中的编号 发送消息 接收消息 终止MPI环境 BasicStructuresofMPIPrograms HeaderfilesMPICommunicatorMPIFunctionformatCommunicatorSizeandProcessRankInitializingandExitingMPI MPIBasics Awiderangeofproblemscanbesolvedbyusingjustsixofitsfunctions StartingandFinishingMPI INITMPI FINALIZEIdentifyingyourselfMPI COMM SIZEMPI COMM RANKSendingandReceivingmessagesMPI SENDMPI RECV MPIstartingandfinishing StatementneededineveryprogrambeforeanyotherMPIcodeMPI Init Programwillnotterminatewithoutthisstatement Communicator CollectionofprocessesInitially allprocessesenrolledina universe calledMPI COMM WORLDMPI COMM SIZE comm size canbeusedtoknowitssizeDeterminesscopetowhichmessagesarerelativeIdentityofprocess rank isrelativetocommunicatoreachprocessisgivenauniquerank anumberfrom0ton 1 wheretherearenprocesses MPI COMM RANK comm rank canbeusedtofindprocessrank Determinetheidentifierofthecurrentprocess Scopeofglobalcommunications broadcast etc TypesofMPICommunication PointtoPointcommunicationGroup Collective communicationOnetomanyMPI BCASTManytooneMPI GATHERManytomanyMPI ALLTOALL Point to PointCommunication Thegeneralformatsofparametersofthesend receiveare MPI Send 例子 MPI Send 第一个参数指明消息缓存的起始地址 即存放要发送的数据信息 第二个参数指明消息中给定的数据类型有多少项 这个数据类型由第三个参数给定 数据类型要么是基本数据类型 要么是导出数据类型 后者由用户生成指定一个可能是由混合数据类型组成的非连续数据项 第四个参数是目的进程的标识符 进程编号 第五个是消息标签第六个参数标识进程组和上下文 即 通信子 通常 消息只在同组的进程间传送 但是 MPI允许通过intercommunicators在组间通信 MPI Receive 例 MPI Recv tmp 1 MPI INT i i PI COMM WORLD Status 第一个参数指明接收消息缓冲的起始地址 即存放接收消息的内存地址第二个参数指明给定数据类型的最大项数 它存放在第三个参数内 可以被接收 接收到的实际项数可能少一些第四个参数是源进程标识符 编号 第五个是消息标签第六个参数标识一个通信子第七个参数是一个指针 指向一个结构MPI StatusStatus存放了各种有关接收消息的各种信息 Status MPI SOURCE实际的源进程编号Status MPI TAG实际的消息标签实际接收到的数据项数由MPI例程MPI Get count Status MPI INT C 读出 这个例程使用Status中的信息来决定给定数据类型 在这里是MPI INT 中的实际项数 将这个数放在变量C中 标签的使用 为什么要使用消息标签 Tag 未使用标签 使用了标签 为了说明为什么要用标签 我们先来看右面一段没有使用标签的代码 这段代码打算传送A的前32个字节进入X 传送B的前16个字节进入Y 但是 如果消息B尽管后发送但先到达进程Q 就会被第一个recv 接收在X中 使用标签可以避免这个错误 标签的使用 使用标签的另一个原因是可以简化对下列情形的处理 假定有两个客户进程P和R 每个发送一个服务请求消息给服务进程Q MessagePassingExample include include include mpi h includesMPIlibrarycodespecs defineMAXSIZE100intmain intargc char argv intmyRank rank identity ofprocess intnumProc numberofprocessors intsource rankofsender intdest rankofdestination inttag 0 tagtodistinguishmessages charmess MAXSIZE message othertypespossible intcount numberofitemsinmessage MPI Statusstatus statusofmessagereceived MessagePassingExample Cont MPI Init shutdownMPI MessagePassingExample Cont if myRank 0 allprocessessendtoroot createmessage sprintf message Hellofrom d myRank dest 0 destinationisroot count strlen mess 1 include 0 inmessage MPI Send mess count MPI CHAR dest tag MPI COMM WORLD else root 0 processreceivesandprintsmessages fromeachprocessorinrankorder for source 1 source numProc source MPI Recv mess MAXSIZE MPI CHAR source tag MPICOMM WORLD CollectiveCommunications OnetoMany Broadcast Scatter ManytoOne Reduce Gather ManytoMany Allreduce Allgather MPI Bcast BroadcastfromroottoallotherprocessesMPI Gather GathervaluesforgroupofprocessesMPI Scatter ScattersbufferinpartstogroupofprocessesMPI Alltoall SendsdatafromallprocessestoallprocessesMPI Reduce CombinevaluesonallprocessestosinglevalueMPI Reduce scatter CombinevaluesandscatterresultsMPI Scan Computeprefixreductionsofdataonprocesses Broadcast MPI Bcast Address Count Datatype Root Comm 在下列broadcast操作中 标号为Root的进程发送相同的消息给标记为Comm的通信子中的所有进程 消息的内容如同点对点通信一样由三元组 Address Count Datatype 标识 对Root进程来说 这个三元组既定义了发送缓冲也定义了接收缓冲 对其它进程来说 这个三元组只定义了接收缓冲 MPI Bcast Syntax MPI Bcast mess count MPI INT root MPI COMM WORLD messpointertomessagebuffercountnumberofitemssentMPI INTtypeo