移位交换网的最优路由算法

An Optimal Routing Algorithm for Shuffle-Exchange Networks

移位交换网是重要的互联网络之一 ,在并行计算中有着广泛应用 .然而 ,它缺少任意点对间的最短路由算法 .已有的路由算法都不能保证其任意节点对间都是最短路由 .文中给出了一个最短路由算法 ,也是最优路由算法 ,它使得从源节点到目的节点的任何信息都是沿最短路由传输 .同时 。

The shuffle\|exchange network is 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 uniquebinary address, and two nodes are linked by an edge if either (1) their addressesdiffer in the last bit, or (2) one is a cyclic shift (by one bit) of the other. Edgesof type (1) are called exchange edges, and those of type (2) are shuffle edges. Such a simple structure admits a simple routing algorithm: cycle through all the bits of the source address by traversing the right\|shuffle/left\|shuffle edges, changing a bit whenever necessary by traversing an exchange edge. This algorithm takes at most 2n-1 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 2n-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 pair, it is not necessary to cycle through all the bits because of the existence of some common substring in their adresses. The simple routing algorithm insists on traversing st least n-1 right\|shuffle/left\|shuffle edges in order to cycle through all the bits, and the result is often a non\|optimal route. An optimal algorithm always directs a message along the shortest path between any two nodes. In this paper, we propose an algorithm for the optimal routing in a shuffle\|exchange network, which guarantee the message can be directed along the shortest path between any two nodes; in particular, it would avoid cycling through a common substring of the source and destination adresses. Meanwhile we obtain the distance formula between any two nodes.