Adaptive deadlock- and livelock-free routing with all minimal paths in torus networks
- 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
- https://doi.org/10.1109/71.334898
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 25 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
- An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubesIEEE Transactions on Computers, 1991
- Fully-adaptive routingPublished by Association for Computing Machinery (ACM) ,1991
- Average case analysis of greedy routing algorithms on arraysPublished by Association for Computing Machinery (ACM) ,1990
- Expanders might be practical: fast algorithms for routing around faults on multibutterfliesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Universal packet routing algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- A Framework for Adaptive RoutingPublished by Defense Technical Information Center (DTIC) ,1987
- 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