一个针对洗牌交换网的最优路由算法  

An Optimal Routing Algorithm for Shuffle-Exchange Networks

作　　者：陈贵海[1] 刘智满[2] 顾庆[1] 谢立[1] 

机构地区：[1]南京大学软件新技术国家重点实验室,南京210093 [2]香港大学计算机科学与信息系统系

出　　处：《计算机学报》2001年第1期25-31,共7页Chinese Journal of Computers

基　　金：国家自然科学基金!(6 0 0 730 2 9;6 980 30 0 5 )资助

摘　　要：洗牌交换网是最流行的互连网络之一 ,然而 ,它的缺点之一便是缺少最短路由算法 .最短路由算法 ,通常也称为最优路由算法 ,能保证报文在任意一对结点之间沿着最短路径传送 .针对包含 2 n个结点的洗牌交换网 ,文中给出了一个 O(n2 )时间复杂度的最短路由算法 .该算法还可以很容易地适用于立方体连接圈 (CCC) ,且所得到的算法比已有的 CCC路由算法要简单得多 .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 f

关 键 词：互连网络 多处理器 洗牌交换网 最优路由算法 并行计算 

分 类 号：TP393.03[自动化与计算机技术—计算机应用技术] TN915[自动化与计算机技术—计算机科学与技术]