Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks

Jie Wu, Dajin Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

We propose a deterministic fault-tolerant and deadlock-free routing protocol in 2D meshes based on Wu's fault-tolerant odd-even turn model (2000) 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 does not use any 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 is a refinement of rectangular fault blocks. The formation of MCCs depends on the relative locations of source and destination, and they include much 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 2D meshes using extended MCCs.

Original languageEnglish
Title of host publicationProceedings - International Conference on Parallel Processing, ICPP 2002
EditorsTarek S. Abdelrahman
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages247-254
Number of pages8
ISBN (Electronic)0769516777
DOIs
StatePublished - 1 Jan 2002
EventInternational Conference on Parallel Processing, ICPP 2002 - Vancouver, Canada
Duration: 18 Aug 200221 Aug 2002

Publication series

NameProceedings of the International Conference on Parallel Processing
Volume2002-January
ISSN (Print)0190-3918

Other

OtherInternational Conference on Parallel Processing, ICPP 2002
CountryCanada
CityVancouver
Period18/08/0221/08/02

Keywords

  • Computer architecture
  • Computer science
  • Fault tolerance
  • Mesh networks
  • Multiprocessor interconnection networks
  • Network topology
  • Packet switching
  • Routing protocols
  • Shape
  • System recovery

Fingerprint Dive into the research topics of 'Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks'. Together they form a unique fingerprint.

  • Cite this

    Wu, J., & Wang, D. (2002). Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks. In T. S. Abdelrahman (Ed.), Proceedings - International Conference on Parallel Processing, ICPP 2002 (pp. 247-254). [1040880] (Proceedings of the International Conference on Parallel Processing; Vol. 2002-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICPP.2002.1040880