首页 | 本学科首页   官方微博 | 高级检索  
     

一个针对洗牌交换网的最优路由算法
引用本文:陈贵海,刘智满,顾庆,谢立.一个针对洗牌交换网的最优路由算法[J].计算机学报,2001,24(1):25-31.
作者姓名:陈贵海  刘智满  顾庆  谢立
作者单位:1. 南京大学
2. 香港大学计算机科学与信息系统系,
基金项目:国家自然科学基金!(6 0 0 730 2 9,6 980 30 0 5 )资助
摘    要:洗牌交换网是最流行的互连网之一,然而,它的缺点之一便是最短路由算法,最短路由算法,通常也称为最优路由算法,能保证报文在任意一对结点之间沿着最短路径传送。针对包含2^n个结点的洗牌交换网,文中给出了一个O(n^2)时间复杂度的最短路由算法。该算法还可以很容易地适用于立方体连接圈(CCC),且所得到的算法比已有的CCC路由算法要简单得多。

关 键 词:互连网络  多处理器  洗牌交换网  最优路由算法  并行计算
修稿时间:2000年3月1日

An Optimal Routing Algorithm for Shuffle-Exchange Networks
CHEN Gui Hai,Francis C M Lau,GU Qing,XIE Li.An Optimal Routing Algorithm for Shuffle-Exchange Networks[J].Chinese Journal of Computers,2001,24(1):25-31.
Authors:CHEN Gui Hai  Francis C M Lau  GU Qing  XIE Li
Affiliation:CHEN Gui Hai 1) Francis C M Lau 2) GU Qing 1) XIE Li 1) 1)
Abstract:The shuffle-exchange network is among the most interestinginterconnection 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 2n 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 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(n2)-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.
Keywords:interconnection network  multiprocessor  routing  shuffle  exchange network
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号