一种交叉立方体网络的并行路由算法  

A Parallel Routing Algorithm for Crossed Cube Networks

作　　者：喻昕[1] 吴敏[1] 王国军[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机工程》2007年第3期12-14,共3页Computer Engineering

基　　金：国家杰出青年科学基金资助项目(60425310);教育部青年教师奖励计划项目(教人[2002]5号)

摘　　要：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.

关 键 词：交叉立方体 超立方体 内结点不交叉路径 路径长度 路由算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]