Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks
- 1 June 2005
- journal article
- research article
- Published by Informa UK Limited in International Journal of Parallel, Emergent and Distributed Systems
- Vol. 20 (2), 99-111
- https://doi.org/10.1080/17445760500033341
Abstract
We propose a deterministic fault-tolerant and deadlock-free routing protocol in 2-dimensional (2-D) meshes based on Wu's fault-tolerant odd–even turn model and Wang's rectilinear-monotone polygonal fault block model. The fault-tolerant odd–even turn protocol, also called extended X–Y routing, was originally proposed to achieve fault-tolerant and deadlock-free routing among traditional, rectangular fault blocks. It uses no virtual channels. The number of faults to be tolerated is unbounded as long as nodes outside fault blocks are connected in the mesh network. The recently proposed rectilinear-monotone polygonal fault blocks (also called minimal-connected-components or MCCs) are of the polygonal shapes, and are a refinement of rectangular fault blocks. The formation of MCCs depends on the relative locations of source and destination, and MCCs include far fewer healthy nodes in resultant fault blocks. In this paper, we show that with a simple modification, the extended X–Y routing can also be applied to 2-D meshes using extended MCCs.Keywords
This publication has 11 references indexed in Scilit:
- A new approach to fault-tolerant wormhole routing for mesh-connected parallel computersIEEE Transactions on Computers, 2004
- Fault-Tolerant Routing in Wormhole MeshesJournal of Interconnection Networks, 2003
- Adaptive fault-tolerant wormhole routing algorithms for hypercube and mesh interconnection networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The odd-even turn model for adaptive routingIEEE Transactions on Parallel and Distributed Systems, 2000
- Adaptive and deadlock-free routing for irregular faulty patterns in mesh multicomputerIEEE Transactions on Parallel and Distributed Systems, 2000
- Fault-tolerant wormhole routing in mesh with overlapped solid fault regionsParallel Computing, 1997
- Fault-tolerant wormhole routing algorithms for mesh networksIEEE Transactions on Computers, 1995
- The turn model for adaptive routingJournal of the ACM, 1994
- A survey of wormhole routing techniques in direct networksComputer, 1993
- Deadlock-Free Message Routing in Multiprocessor Interconnection NetworksIEEE Transactions on Computers, 1987