An Optimal Routing Algorithm for Shuffle-Exchange Networks
Guohua Chen, Fcm Lau, Qian Ping Gu, Lifang Xie · Chinese Journal of Computers · 2001
The shuffle exchange network is among the most interesting interconnection networks that have been subject to much research in the field of parallel computing. However, one of its drawbacks is the lack of the optimal routing algorithm. In a shuffle exchange network, each node is identified by a unique binary address, and two nodes are linked by an edge if either (a) their addresses differ in the last bit, or (b) one is a cyclic shift (by one bit) of the other. Edges of type (a) are called exchange edges, and those of type (b) are shuffle or unshuffle edges. Such a simple structure admits a simple routing algorithm: cycle through all the bits of the source address by traversing the shuffle/unshuffle edges, changing a bit whenever necessary by traversing an exchange edge. This algorithm takes at most 2 n steps for an n dimensional shuffle exchange network (whose node addresses have n bits). Considering the fact that any route from 00…0 to 11…1 must have 2 n -1 edges, this algorithm seems to be just good enough. A simple inspection, however, would reveal that many of the routes thus generated are not at all the shortest possible. It turns out that for some source destination address pairs, it is not necessary to cycle through all the bits because of the existence of some common substring in their addresses. The simple routing algorithm insists on traversing at least n -1 shuffle/unshuffle edges in order to cycle through all the bits, and the result is often a non optimal route. An optimal routing algorithm always directs a message along the shortest path between any two nodes. In this paper, we propose an O(n 2) time algorithm for the optimal routing in a shuffle exchange network having 2n nodes; in particular, it would avoid cycling through a common substring of the source and destination addresses if it is deemed profitable. The algorithm can be easily adapted to routing in the cube connected cycles (CCC)——the result is a much simpler algorithm than a previous algorithm for the CCC.