A traffic-balanced adaptive wormhole routing scheme for two-dimensional meshes
- 1 February 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 46 (2) , 190-197
- https://doi.org/10.1109/12.565594
Abstract
In this paper, we analyze several issues involved in developing low latency adaptive wormhole routing schemes for two-dimensional meshes. It is observed that along with adaptivity, balanced distribution of traffic has a significant impact on the system performance. Motivated by this observation, we develop a new fully adaptive routing algorithm called positive-first-negative-first for two-dimensional meshes. The algorithm uses only two virtual channels per physical channel creating two virtual networks. The messages are routed positive-first in one virtual network and negative-first in the other. Because of this combination, the algorithm distributes the system load uniformly throughout the network and is also fully adaptive. It is shown that the proposed algorithm results in providing better performance in terms of the average network latency and throughput when compared with the previously proposed routing algorithms.Keywords
This publication has 16 references indexed in Scilit:
- Adaptive routing in mesh-connected networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Planar-adaptive routingJournal of the ACM, 1995
- The turn model for adaptive routingJournal of the ACM, 1994
- A Class of Partially Adaptive Routing Algorithms for n_dimensional MeshesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1993
- Adaptive Deadlock-Free Routing in Multicomputers Using Only One Extra Virtual ChannelPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1993
- A survey of wormhole routing techniques in direct networksComputer, 1993
- A new theory of deadlock-free adaptive routing in wormhole networksIEEE Transactions on Parallel and Distributed Systems, 1993
- Virtual-channel flow controlIEEE Transactions on Parallel and Distributed Systems, 1992
- An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubesIEEE Transactions on Computers, 1991
- Performance analysis of k-ary n-cube interconnection networksIEEE Transactions on Computers, 1990