Deadlock-Free Adaptive Routing in Meshes with Fault-Tolerance Ability Based on Channel Overlapping
- 19 January 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Dependable and Secure Computing
- Vol. 8 (1), 74-88
- https://doi.org/10.1109/TDSC.2009.3
Abstract
A new deadlock-free routing scheme for meshes is proposed based on a new virtual network partitioning scheme, called channel overlapping. Two virtual networks can share some common virtual channels based on the new virtual network partitioning scheme. The deadlock-free adaptive routing method is then extended to deadlock-free adaptive fault-tolerant routing in 3D meshes still with two virtual channels. A few faulty nodes can make a higher dimensional mesh unsafe for fault-tolerant routing methods based on the block fault model, where the whole system (n-dimensional space) forms a fault block. Planar safety information in meshes is proposed to guide fault-tolerant routing and classifies fault-free nodes inside 2D planes. Many nodes globally marked as unsafe in the whole system become locally enabled inside 2D planes. This fault-tolerant deadlock-free adaptive routing algorithm is also extended to the one in an n-dimensional meshes with two virtual channels. Extensive simulation results are presented and compared to previous methods.Keywords
This publication has 21 references indexed in Scilit:
- Practical Deadlock-Free Fault-Tolerant Routing in Meshes Based on the Planar Network Fault ModelIEEE Transactions on Computers, 2008
- Deadlock-Free Adaptive Routing in Meshes Based on Cost-Effective Deadlock Avoidance Schemes2007 International Conference on Parallel Processing (ICPP 2007), 2007
- A fault-tolerant and deadlock-free routing protocol in 2D meshes based on odd-even turn modelIEEE Transactions on Computers, 2003
- Fault-tolerant routing in hypercube multicomputers using local safety informationIEEE Transactions on Parallel and Distributed Systems, 2001
- The odd-even turn model for adaptive routingIEEE Transactions on Parallel and Distributed Systems, 2000
- Adaptive fault-tolerant deadlock-free routing in meshes and hypercubesIEEE Transactions on Computers, 1996
- Planar-adaptive routingJournal of the ACM, 1995
- Deadlock-free adaptive routing in multicomputer networks using virtual channelsIEEE Transactions on Parallel and Distributed Systems, 1993
- A new theory of deadlock-free adaptive routing in wormhole networksIEEE Transactions on Parallel and Distributed Systems, 1993
- Deadlock-Free Message Routing in Multiprocessor Interconnection NetworksIEEE Transactions on Computers, 1987