虫蚀算法论文

《虫蚀算法论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、全端口虫蚀寻径超立方体上的优化广播摘要：广播是大规模并行计算机中基本的通信模式之一。在全端口虫蚀寻径的超立方体上给出了一个采用E-立方体寻径的优化广播算法。该算法充分利用了虫蚀寻径的距离不敏感性以及多端口结构的特性，其性能比目前已有的各种全端口广播算法都要好，而且该算法避免了通道冲突。关键词：全端口；虫蚀寻径；超立方体；广播算法；通道冲突OptimalBroadcastinAll-portWormho1e-routedHypercubeslAbstractJBroadcastisaprimarycommunicationpatterninmassi

2、velyparallelcomputers.Thispaperpresentsanoptima1broadcastalgorithmforall-portwormhole-routedhypercubes.Byexploitingthedislance-insensitivecharacteristicofwormhole-routingandthepropertiesofal1-portnetworks,theproposedalgorithmoutperformstheexistingall-portbroadcastalgorithmssig

3、nificantly,andavoidschannel-conflictaswel1・IKeywordslAl1-port;Wormhole-route;Hypercubes;Broadcastalgorithm;Channel-conf1ict1引言广播是大规模并行计算机(MPC)中基木的通信模式之一。有效的广播算法对提高系统的性能是非常重耍的，许多优秀的综述文章［1］对此都作了详细的介绍。许多数值计算算法［2,3］,包括矩阵一向量乘、矩阵一矩阵乘、高斯消元、LU-分解等的性能都依赖于广播算法的好坏。在实现广播通信时，通信时延是一个亜要的考虑因素

4、。为了减少通信时延，通常都采用虫蚀寻径［4］的交换策略。在虫蚀寻径下，一条消息被分割成许多的小片(flit)o消息的头片控制整个消息的路山，其余的片则跟在头片后而以流水线的方式传送。虫蚀寻径的一个重要特征是当没有通道冲突时网络时延与消息所经过的距离儿乎无关。传统上，超立方体上的广播通信是通过生成二叉树(spanningbinomialtree,SBT)［5］来实现的。这种方法仅仅使用相邻结点间的通信。因此，在旷立方体上，从源结点到达最远结点需要n个消息传递步。2立方体上的广播算法理论上，在4-立方体上进行广播需要的最少步数为2。这里给出一个采川E-

5、立方体寻径的4-立方体上的最少步数广播算法,HPMB4(MinimumBroadcaston4-Cube)算法。下而给出实现MB4算法的伪代码，其中s为源结点编号，n为超立方体的维数，pid为当前处理机的编号，s表示将结点编号s按位取反，'㊉'表示异或。包含在关键字cobegin和coend之间的send语句将被同时执行。事实上，由于该算法对3-立方体也同样有效，因此没有将n定为4。图1给出了MB4算法的广播过程。b第一步广播图1MB4算法的广播过程算法1MB4算法ProcedureMB4(s,n)beginifpid=sthen/*ifcurre

6、ntnodeisthesourcenode*/cobegin/*step1*/fori=1ton-1dosend(msg,s㊉2i)/*sendthebroadcastmessagetoanode*/endforsend(msg,s)coendsend(msg,s㊉1)/*step2*/else/*ifcurrentnodeisadestinationnode*/receive(msg,s)/*receivethebroadcastmessage*/ifpid=sthencobcginfori=0ton-1dosend(msg,pid©2i)end

7、forcoendelsefori=1ton-1doifpid=s®2ithenbreakendifendforcobeginforj=0toi-1dosend(msg,pid©2i)cndforcoendendifendifend/*endofMB4algorithm*/3超立方体上的优化广播算法利用第1节的购4算法，可以得到一个优化的任意维超立方体上的广播算法。山于该广播算法是基于低维子立方体上的广播算法而得到的，且其最底层的子立方体广播算法为皿4算法,因此称该算法为SB4算法(Subcube-basedBroadcastingAlgorithm

8、)。SB4算法的基本思想是:根据结点编号的最高k位将一个n维的超立方体划分成2k个n-k维的子立方体，从而就将n维超立方体