摘要
基于交叉立方体环连接的Peterson图互联网络RCP(n)具有优良的特性.在高性能并行计算机系统中,信息通过若干内结点不交叉的路径并行传输,这些路径的长度将直接影响并行计算的性能.本文提出了一种时间复杂度为o(n2)的RCP(n)网络并行路由算法,可输出源点u到目标点v的两条并行路径P0,P1,并证明Pi≤u到v距离+4(i=0,1),说明该算法是通信高效的.
The topological structure on interconnection network RCP（n） has many attractive properties.The message 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.In this paper we propose a parallel routing algorithm with time complexity of o（n2） for RCP（n） networks.The algorithm can generate two paths for any pair of vertices and the length of paths is equal or less the sum of 4 and the shortest length of u and v,so the algorithm is effective in communications.
出处
《山西师范大学学报（自然科学版）》
2011年第2期38-40,共3页
Journal of Shanxi Normal University(Natural Science Edition)
基金
国家自然科学基金项目(60803034)
