摘要
Pertersen图由于具有短直径和正则性等特性,在并行计算与分布式计算中具有良好的性能。基于环结构,提出了一种Pertersen图的新扩展方法,构造了互联网络RPC(k)。分析了该互联网络的性质,它具有连接度小、网络直径短、拓扑结构简单以及易于扩展等特点。同时给出了RPC(k)优于二维Torus以及RP(k)互联网络的直径和节点可分组性的条件。最后,分别设计了RPC(k)上的单播路由、置换路由、广播路由和多对多路由,它们的通信效率分别为「k/2」+5,k+9,「k/2」+5和k+9。特别是随着k的增大,RPC(k)网络路由算法的通信效率近似于RP(k)网络上的对应算法通信效率的1/3倍。
Petersen graph has good performance in parallel and distributed computation because of its characteristics such as short diameter and regularity. Based on ring structure, a new extension of Petersen graph was proposed, and a new interconnection network, the RPC（k） network was developed. Additionally, the properties of the RPC（k） network were investigated. It was proved that RPC（k） has lower-degree connectivity, smaller network diameter, simple topology and good extensibility. On the basis of these analysis, the conditions satisfying that the network diameter and grouping ability of RPC（k） are better than the diameter and grouping ability of 2-D Torus and RP（k） interconnection networks were presented. Finally, based on the RPC（k） network we designed a set of routing algorithms which are point-to-point routing, permutation routing, one-to-all routing and all-to-all routing. Their communication efficiencies are [ k/2 ] ＋5, k ＋9,[ k/2 ]＋5 and k ＋9 respectively. Especially as the k increasing, the efficiencies of these routing algorithms based on RPC（k） approximate to 1/3 of which based on RP（k） network.
出处
《计算机科学》
CSCD
北大核心
2010年第6期131-135,175,共6页
Computer Science
基金
国家自然科学基金项目(60373063
90612003)
山东省自然科学基金项目(Y2007G11)资助
