Adaptive deadlock- and livelock-free routing with all minimal paths in torus networks
Authors:
- G.D. PifarreGPG.D. Pifarre
- P.E. BermanPBP.E. Berman
- J.L.C. SanzJSJ.L.C. Sanz
- 1 December 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 5 (12) , 1233-1251
Abstract
This paper consists of two parts. In the first part, two new algorithms for deadlock- and livelock-free wormhole routing in the torus network are presented. The first algorithm, called Channels, is for the n-dimensional torus network. This technique is fully-adaptive minimal, that is, all paths with a minimal number of hops from source to destination are available for routing, and needs only five virtual channels per bidirectional link, the lowest channel requirement known in the literature for fully-adaptive minimal worm-hole routing. In addition, this result also yields the lowest buffer requirement known in the literature for packet-switched fully-adaptive minimal routing. The second algorithm, called 4-Classes, is for the bidimensional torus network. This technique is fully-adaptive minimal and requires only eight virtual channels per bidirectional link. Also, it allows for a highly parallel implementation of its associated routing node. In the second part of this paper, four worm-hole routing techniques for the two-dimensional torus are experimentally evaluated using a dynamic message injection model and different traffic patterns and message lengths.Keywords
This publication has 21 references indexed in Scilit:
- Routing techniques for massively parallel communicationProceedings of the IEEE, 1991
- An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubesIEEE Transactions on Computers, 1991
- Fully-adaptive routing1991
- Average case analysis of greedy routing algorithms on arrays1990
- Expanders might be practical: fast algorithms for routing around faults on multibutterflies1989
- Universal packet routing algorithms1988
- A Framework for Adaptive Routing1987
- Deadlock-Free Message Routing in Multiprocessor Interconnection NetworksIEEE Transactions on Computers, 1987
- The torus routing chipDistributed Computing, 1986
- Deadlock Avoidance in Store-and-Forward Networks--I: Store-and-Forward DeadlockIEEE Transactions on Communications, 1980