Thumbnail
Access Restriction
Subscribed

Author Chien, Andrew A. ♦ Kim, Jae H.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1995
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Adaptive routing ♦ Fault tolerance ♦ Interconnection networks ♦ Multicomputers ♦ Packet routing ♦ Parallel processing ♦ Transmission-order preservation
Abstract Network throughput can be increased by allowing multipath, adaptive routing. Adaptive routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of adaptive routing introduces new possibilities of deadlock. Previous deadlock avoidance schemes in $\textit{k}-ary$ $\textit{n}-cubes$ require an exponential number of virtual channels. We describe a family of deadlock-free routing algorithms, called planar-adaptive routing algorithms, that require only a constant number of virtual channels, independent of networks size and dimension. Planar-adaptive routing algorithms reduce the complexity of deadlock prevention by reducing the number of choices at each routing step. In the fault-free case, planar-adaptive networks are guaranteed to be deadlock-free. In the presence of network faults, the planar-adaptive router can be extended with misrouting to produce a working network which remains provably deadlock free and is provably livelock free. In addition, planar-adaptive networks can simultaneously support both in-order and adaptive, out-of-order packet delivery.Planar-adaptive routing is of practical significance. It provides the simplest known support for deadlock-free adaptive routing in $\textit{k}-ary$ $\textit{n}-cubes$ of more than two dimensions (with $\textit{k}>2).$ Restricting adaptivity reduces the hardware complexity, improving router speed or allowing additional performance-enhancing network features. The structure of planar-adaptive routers is amenable to efficient implementation.Simulation studies show that planar-adaptive routers can increase the robustness of network throughput for nonuniform communication patterns. Planar-adaptive routers outperform deterministic routers with equal hardware resources. Further, adding virtual lanes to planar-adaptive routers increases this advantage. Comparisons with fully adaptive routers show that planar-adaptive routers, limited adaptive routers, can give superior performance. These results indicate the best way to allocate router resources to combine adaptivity and virtual lanes.Planar-adaptive routers are a special case of limited adaptivity routers. We define a class of adaptive routers with $\textit{f}$ degrees of routing freedom. This class, termed f-flat adaptive routers, allows a direct cost-performance tradeoff between implementation cost (speed and silicon area) and routing freedom (channel utilization). For a network of a particular dimension, the cost of adaptivity grows linearly with the routing freedom. However, the rate of growth is a much larger constant for high-dimensional networks. All of the properties proven for planar-adaptive routers, such as deadlock and livelock freedom, also apply to $\textit{f}-flat$ adaptive routers.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1995-01-03
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 42
Issue Number 1
Page Count 33
Starting Page 91
Ending Page 123


Open content in new tab

   Open content in new tab
Source: ACM Digital Library