并行程序设计 中文课件 09 并行程序通信开销.pptVIP

All-to-AllPersonalizedCommunicationonaHypercubeAll-to-AllPersonalizedCommunicationonaHypercube:CostWehavelogpiterationsandmp/2wordsarecommunicatedineachiteration.Therefore,thecostis:Thisisnotoptimal!All-to-AllPersonalizedCommunicationonaHypercube:OptimalAlgorithmEachnodesimplyperformsp–1communicationsteps,exchangingmwordsofdatawithadifferentnodeineverystep.Anodemustchooseitscommunicationpartnerineachstepsothatthehypercubelinksdonotsuffercongestion.Inthejthcommunicationstep,nodeiexchangesdatawithnode(iXORj).Inthisschedule,allpathsineverycommunicationsteparecongestion-free,andnoneofthebidirectionallinkscarrymorethanonemessageinthesamedirection.All-to-AllPersonalizedCommunicationonaHypercube:OptimalAlgorithm每个节点简单地执行p-1通信步骤，在每个步骤中与不同节点交换m个数据字。节点必须在每个步骤中选择其通信伙伴，以便超立方体链路不会拥塞。在第j个通信步骤中，节点i与节点（iXORj）交换数据。在该时间表中，每个通信步骤中的所有路径都是无拥塞的，并且没有一个双向链路在同一个方向上携带多个消息。All-to-AllPersonalizedCommunicationonaHypercube:OptimalAlgorithmAll-to-AllPersonalizedCommunicationonaHypercube:OptimalAlgorithmAproceduretoperformall-to-allpersonalizedcommunicationonad-dimensionalhypercube.ThemessageMi,jinitiallyresidesonnodeiandisdestinedfornodej.All-to-AllPersonalizedCommunicationonaHypercube:CostAnalysisofOptimalAlgorithmTherearep–1stepsandeachstepinvolvesnon-congestingmessagetransferofmwords.有p-1个步骤，每个步骤涉及m个词的非拥塞消息传递。Wehave:CircularShiftAspecialpermutationinwhichnodeisendsadatapackettonode(i+q)modpinap-nodeensemble (0≤q≤p).节点i在p节点集合中向节点（i+q）modp发送数据分组的特殊排列（0≤q≤p）。CircularShiftonaMeshTheimplementationonaringisratherintuitive.Itcanbeperformedinmin{q,p–q}neighborcommunications.Meshalgorithmsfollowfromthisaswell.Weshiftinonedirection(allprocessors)followedbythenextdirection.Theassociatedtimehasanu