Adaptive deadlock- and livelock-free routing with all minimal paths in Torus networks
- 1 June 1992
- proceedings article
- Published by Association for Computing Machinery (ACM)
Abstract
This paper consists of two parts. In the first part, a newalgorithm for deadlock- and livelock-free routing for then-dimensional torus network is presented. This algo-rithm, called *-Channels, is fully-adaptive minimal, i.e.all paths with a minimal number of hops from source todestination are available for routing. *-Channels worksfor messages of unknown size, thus yielding new rout-ing techniques for both packet-switched and worm-holemodels. *.Channels differs radically from the...Keywords
This publication has 13 references indexed in Scilit:
- Deadlock-free adaptive routing algorithms for multicomputers: evaluation of a new algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Requirements for deadlock-free, adaptive packet routingPublished by Association for Computing Machinery (ACM) ,1992
- An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubesIEEE Transactions on Computers, 1991
- Chaos routerPublished by Association for Computing Machinery (ACM) ,1991
- The chaos router: a practical application of randomization in network routingPublished by Association for Computing Machinery (ACM) ,1990
- Average case analysis of greedy routing algorithms on arraysPublished by Association for Computing Machinery (ACM) ,1990
- Virtual-channel flow controlPublished by Association for Computing Machinery (ACM) ,1990
- An O(logN) deterministic packet routing schemePublished by Association for Computing Machinery (ACM) ,1989
- Expanders might be practical: fast algorithms for routing around faults on multibutterfliesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Deadlock-Free Message Routing in Multiprocessor Interconnection NetworksIEEE Transactions on Computers, 1987