Planar-adaptive routing
- 1 April 1992
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGARCH Computer Architecture News
- Vol. 20 (2), 268-277
- https://doi.org/10.1145/146628.140383
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 k-ary n-cubes require an exponential number of virtual channels, independent of network 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 k-ary n-cubes of more than two dimensions (with 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.Keywords
This publication has 16 references indexed in Scilit:
- Deadlock-free adaptive routing in multicomputer networks using virtual channelsIEEE Transactions on Parallel and Distributed Systems, 1993
- Chaos routerPublished by Association for Computing Machinery (ACM) ,1991
- Limits on interconnection network performanceIEEE Transactions on Parallel and Distributed Systems, 1991
- Performance analysis of k-ary n-cube interconnection networksIEEE Transactions on Computers, 1990
- Directory-based cache coherence in large-scale multiprocessorsComputer, 1990
- Virtual-channel flow controlPublished by Association for Computing Machinery (ACM) ,1990
- Synchronization, coherence, and event ordering in multiprocessorsComputer, 1988
- Deadlock-Free Message Routing in Multiprocessor Interconnection NetworksIEEE Transactions on Computers, 1987
- A DAG-Based Algorithm for Prevention of Store-and-Forward Deadlock in Packet NetworksIEEE Transactions on Computers, 1981
- Prevention of Deadlocks in Packet-Switched Data Transport SystemsIEEE Transactions on Communications, 1981