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 contributionResearchpeer-review

13 Citations (Scopus)

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

Fingerprint

Deadlock
Fault-tolerant
Monotone
Routing
Fault
Mesh
Routing protocols
Network protocols
Odd
Virtual Channel
Mesh Networks
Vertex of a graph
Routing Protocol
Connected Components
Refinement
Model

Keywords

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

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
Wu, Jie ; Wang, Dajin. / Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks. Proceedings - International Conference on Parallel Processing, ICPP 2002. editor / Tarek S. Abdelrahman. Institute of Electrical and Electronics Engineers Inc., 2002. pp. 247-254 (Proceedings of the International Conference on Parallel Processing).
@inproceedings{9bcdf65b5f7b4adea88b4b3cc3271934,
title = "Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks",
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.",
keywords = "Computer architecture, Computer science, Fault tolerance, Mesh networks, Multiprocessor interconnection networks, Network topology, Packet switching, Routing protocols, Shape, System recovery",
author = "Jie Wu and Dajin Wang",
year = "2002",
month = "1",
day = "1",
doi = "10.1109/ICPP.2002.1040880",
language = "English",
series = "Proceedings of the International Conference on Parallel Processing",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "247--254",
editor = "Abdelrahman, {Tarek S.}",
booktitle = "Proceedings - International Conference on Parallel Processing, ICPP 2002",

}

Wu, J & Wang, D 2002, Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks. in TS Abdelrahman (ed.), Proceedings - International Conference on Parallel Processing, ICPP 2002., 1040880, Proceedings of the International Conference on Parallel Processing, vol. 2002-January, Institute of Electrical and Electronics Engineers Inc., pp. 247-254, International Conference on Parallel Processing, ICPP 2002, Vancouver, Canada, 18/08/02. https://doi.org/10.1109/ICPP.2002.1040880

Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks. / Wu, Jie; Wang, Dajin.

Proceedings - International Conference on Parallel Processing, ICPP 2002. ed. / Tarek S. Abdelrahman. Institute of Electrical and Electronics Engineers Inc., 2002. p. 247-254 1040880 (Proceedings of the International Conference on Parallel Processing; Vol. 2002-January).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

TY - GEN

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

AU - Wu, Jie

AU - Wang, Dajin

PY - 2002/1/1

Y1 - 2002/1/1

N2 - 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.

AB - 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.

KW - Computer architecture

KW - Computer science

KW - Fault tolerance

KW - Mesh networks

KW - Multiprocessor interconnection networks

KW - Network topology

KW - Packet switching

KW - Routing protocols

KW - Shape

KW - System recovery

UR - http://www.scopus.com/inward/record.url?scp=84948448877&partnerID=8YFLogxK

U2 - 10.1109/ICPP.2002.1040880

DO - 10.1109/ICPP.2002.1040880

M3 - Conference contribution

T3 - Proceedings of the International Conference on Parallel Processing

SP - 247

EP - 254

BT - Proceedings - International Conference on Parallel Processing, ICPP 2002

A2 - Abdelrahman, Tarek S.

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Wu J, Wang D. Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks. In Abdelrahman TS, editor, Proceedings - International Conference on Parallel Processing, ICPP 2002. Institute of Electrical and Electronics Engineers Inc. 2002. p. 247-254. 1040880. (Proceedings of the International Conference on Parallel Processing). https://doi.org/10.1109/ICPP.2002.1040880