RCP(n)网络的并行路由算法  

A Parallel Routing Algorithm for RCP(n) Networks

作　　者：刘宏英[1] 高太平[2,3] 卢永红[1] 

机构地区：[1]山西大同大学数学与计算机科学学院,山西大同037009 [2]山西大学计算机科学与信息技术学院,山西太原030006 [3]山西大学计算智能与中文信息处理省部共建教育部重点实验室,山西太原030006

出　　处：《山西师范大学学报（自然科学版）》2011年第2期38-40,共3页Journal of Shanxi Normal University(Natural Science Edition)

基　　金：国家自然科学基金项目(60803034)

摘　　要：基于交叉立方体环连接的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.

关 键 词：RCP(n) 交叉立方体 并行路径 路由算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]