Practical Interconnection Network RPC(k) and its Routing Algorithms
Lin Yang · 2010
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.