A Necessary and Sufficient Condition for Deadlock-Free Adaptive Routing in Wormhole Networks
Author:
- 1 August 1994
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (01903918) , 142-149
Abstract
Deadlock avoidance is a key issue in wormhole networks. A first approach [8] consists of removing the cyclic dependencies between channels. Although this is a necessary and sufficient condition for deadlock-free deterministic routing, it is only a sufficient condition for deadlock-free adaptive routing. A more powerful approach [12] only requires the absence of cyclic dependencies on a connected channel subset. The remaining channels can be used in almost any way. In this paper, we propose a necessary and sufficient condition for deadlock-free adaptive routing. This condition is the key for the design of maximally adaptive routing algorithms with minimum restrictions. Some examples are given, showing the application of the new theory. In particular, we propose a partially adaptive routing algorithm for k-ary n-cubes which doubles the throughput without increasing the hardware complexity significantly.Keywords
This publication has 13 references indexed in Scilit:
- A THEORY TO INCREASE THE EFFECTIVE REDUNDANCY IN WORMHOLE NETWORKSParallel Processing Letters, 1994
- The Message Flow Model for Routing in Wormhole-Routed Networks1993
- Adaptive routing protocols for hypercube interconnection networksComputer, 1993
- Deadlock-free adaptive routing in multicomputer networks using virtual channelsIEEE Transactions on Parallel and Distributed Systems, 1993
- A new theory of deadlock-free adaptive routing in wormhole networksIEEE Transactions on Parallel and Distributed Systems, 1993
- Requirements for deadlock-free, adaptive packet routing1992
- An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubesIEEE Transactions on Computers, 1991
- On the design of deadlock-free adaptive routing algorithms for multicomputers: Theoretical aspects1991
- Multicomputers: message-passing concurrent computersComputer, 1988
- The torus routing chipDistributed Computing, 1986