摘要
Efe提出的交叉立方体是超立方体的一种变型,其某些性质优于超立方体。在高性能的并行计算机系统中,信息通过若干条内结点互不交叉的路径并行传输,这些路径的长度将直接影响并行计算的性能。该文提出了一种时间复杂度为o(n2)的交叉立方体网络并行路由算法,可输出源点u到目的点v的3条并行路径P0,P1,P2,并且满足:(1)|P0|=u到v的距离;(2)|Pi|≤u到v的距离+3(i=1,2)。这说明该算法是通信高效的。
The crossed cube proposed by Ere is a variation of hypercube, but some properties of the former are superior to those of the latter. The messages are simultaneously transmitted on some internally node-disjoint paths in the high performance parallel computing system, thus the lengths of those paths directly affect the performance of parallel computing. This paper proposes a parallel routing algorithm with time complexity of o（n^2） for crossed cube networks, which can output three paths P0,P1,P2 between the source node u and the destination node v, such that： （1）｜P0｜=the distance between u and v; （2）｜P1｜〈the distance between u and v＋3. Therefore, the algorithm works efficiently in communication.
出处
《计算机工程》
CAS
CSCD
北大核心
2007年第3期12-14,共3页
Computer Engineering
基金
国家杰出青年科学基金资助项目(60425310)
教育部青年教师奖励计划项目(教人[2002]5号)
