Abstract: The crossed cube proposed by Efe 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(n2) 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)|Pi|≤the distance between u and v+3. Therefore, the algorithm works efficiently in communication.

Key words: Crossed cube, Hypercube, Internally node-disjoint paths, Path length, Routing algorithm

摘要： Efe提出的交叉立方体是超立方体的一种变型，其某些性质优于超立方体。在高性能的并行计算机系统中，信息通过若干条内结点互不交叉的路径并行传输，这些路径的长度将直接影响并行计算的性能。该文提出了一种时间复杂度为o(n2)的交叉立方体网络并行路由算法，可输出源点u到目的点v的3条并行路径P0,P1,P2，并且满足：(1)|P0|= u到v的距离；(2)|Pi|≤u到v的距离+3(i=1,2)。这说明该算法是通信高效的。

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