The embedding of rings and meshes into RP(k) networks

Copyright by Science in China Press 2004 Interconnection networks, as an important means in parallel processing systems, are investigated widely[1,2]. Recently a class of lower-degree networks is proposed[2—4]. In ref. [3] we have investigated a constant degree network, called RP(k) network. Com-pared with rings and 2-D mesh networks, the RP(k) network has many good properties. The RP(k) network has a much smaller diameter than that of 2-D meshes when the number of network nodes is less …

The embedding of rings and meshes into RP(k) networks

This paper first investigates the topological properties of RP(k) networks. Then focusing on the embedding of rings and 2-D meshes into the RP(k) network, it is proved that the RP(k) network is a Hamiltonian graph and the ring with 10*k nodes can be embedded into the RP(k) network with load, expansion, dilation and congestion all equal to 1. If there exists a faulty node on each slice in the RP(k) network, throwing off the faulty nodes, the RP-1(k) network is obtained. It is also proved that there exists a Hamiltonain cycle in the RP-1(k) network. So the ring with 9*k nodes can be embedded into the RP- 1(k) network. After that, we discuss the embedding of a 2-D mesh, M1(a, b), into the RP(k) network. By defining the sequence-column-order mapping, the snake-like-column-order mapping and the shortest path mapping, we obtain two ways of embedding a 2-D mesh into the RP(k) network. The performances of the embedding are as follows. In the snake-like-column-order mapping, the dilations are 1, 2, 3, 3 and 2 and the congestion are 1, 3, 4, 5 and 3 respectively when a is equal to 1, 2, 3, 4 and 5. In the sequence- column-order mapping, the dilation is equal to 3 and the congestion is equal to 6 when a is between 6 and 9. The dilation is equal to a/10+2 and the congestion is equal to max{ a/10+1, 6} when a >10. As a special case, the four parameters are also equal to 1 when a is equal to 10.