The Turn Model for Adaptive Routing
- 24 August 2005
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 278-287
- https://doi.org/10.1109/isca.1992.753324
Abstract
We present a model for designing wormhole routing algorithms that are deadlock free, livelock free, minimal or nonminimal, and maximally adaptive. A unique feature of this model is that it is not based on adding physical or virtual channels to network topologies (though it can be applied to networks with extra channels). Instead, the model is based on analyzing the directions in which packets can turn in a network and the cycles that the turns can form. Prohibiting just enough turns to break all of the cycles produces routing algorithms that are deadlock free, livelock free, minimal or nonminimal, and maximally adaptive for the network. In this paper, we focus on the two most common network topologies for wormhole routing, n-dimensional meshes and k-ary n-cubes, without extra channels. In an n-dimensional mesh, just a quarter of the turns must be prohibited to prevent deadlock. The remaining three quarters of the turns permit partial adaptiveness in routing. Partially adaptive routing algorithms are described for 2D meshes, n-dimensional meshes, k-ary n-cubes, and hypercubes. Simulations of partially adaptive and nonadaptive routing algorithms for 2D meshes and hypercubes show that which algorithm has the lowest latencies and highest sustainable throughput depends on the pattern of message traffic. For nonuniform traffic, partially adaptive routing algorithms perform better than nonadaptive ones.Keywords
This publication has 12 references indexed in Scilit:
- iWarp: an integrated solution to high-speed parallel computingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Adaptive routing in mesh-connected networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- APRIL: a processor architecture for multiprocessingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The directory-based cache coherence protocol for the DASH multiprocessorPublished 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
- Adaptive, low latency, deadlock-free packet routing for networks of processorsIEE Proceedings E Computers and Digital Techniques, 1989
- The architecture and programming of the Ametek series 2010 multicomputerPublished by Association for Computing Machinery (ACM) ,1988
- Deadlock-Free Message Routing in Multiprocessor Interconnection NetworksIEEE Transactions on Computers, 1987
- The torus routing chipDistributed Computing, 1986
- A large scale, homogeneous, fully distributed parallel machine, IPublished by Association for Computing Machinery (ACM) ,1977