A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh

Research output: Contribution to journalArticleResearchpeer-review

33 Citations (Scopus)

Abstract

We propose a new fault block model, Minimal-Connected-Component (MCC), for fault-tolerant adaptive routing in mesh-connected multiprocessor systems. This model refines the widely used rectangular model by including fewer nonfaulty nodes in fault blocks. The positions of source/destination nodes relative to faulty nodes are taken into consideration when constructing fault blocks. The main idea behind it is that a node will be included in a fault block only if using it in a routing will definitely make the route nonminimal. The resulting fault blocks are of the rectilinear-monotone polygonal shapes. A sufficient and necessary condition is proposed for the existence of the minimal "Manhattan" routes in the presence of such fault blocks. Based on the condition, an algorithm is proposed to determine the existence of Manhattan routes. Since MCC is designed to facilitate minimal route finding, if there exists no minimal route under MCC fault model, then there will be absolutely no minimal route whatsoever. We will also present two adaptive routing algorithms that construct a Manhattan route avoiding all fault blocks, should such routes exist.

Original languageEnglish
Pages (from-to)310-320
Number of pages11
JournalIEEE Transactions on Computers
Volume52
Issue number3
DOIs
StatePublished - 1 Mar 2003

Fingerprint

Fault-tolerant
Monotone
Routing
Fault
Mesh
Connected Components
Adaptive Routing
Routing algorithms
Vertex of a graph
Adaptive algorithms
Model
Fault-tolerant Routing
Minimal Model
Multiprocessor Systems
Routing Algorithm
Adaptive Algorithm
Necessary Conditions
Sufficient Conditions

Keywords

  • Adaptive routing
  • Fault model
  • Fault tolerance
  • Interconnection network
  • Mesh

Cite this

@article{424eba2a55ec409da69f6876e89c0e0c,
title = "A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh",
abstract = "We propose a new fault block model, Minimal-Connected-Component (MCC), for fault-tolerant adaptive routing in mesh-connected multiprocessor systems. This model refines the widely used rectangular model by including fewer nonfaulty nodes in fault blocks. The positions of source/destination nodes relative to faulty nodes are taken into consideration when constructing fault blocks. The main idea behind it is that a node will be included in a fault block only if using it in a routing will definitely make the route nonminimal. The resulting fault blocks are of the rectilinear-monotone polygonal shapes. A sufficient and necessary condition is proposed for the existence of the minimal {"}Manhattan{"} routes in the presence of such fault blocks. Based on the condition, an algorithm is proposed to determine the existence of Manhattan routes. Since MCC is designed to facilitate minimal route finding, if there exists no minimal route under MCC fault model, then there will be absolutely no minimal route whatsoever. We will also present two adaptive routing algorithms that construct a Manhattan route avoiding all fault blocks, should such routes exist.",
keywords = "Adaptive routing, Fault model, Fault tolerance, Interconnection network, Mesh",
author = "Dajin Wang",
year = "2003",
month = "3",
day = "1",
doi = "10.1109/TC.2003.1183946",
language = "English",
volume = "52",
pages = "310--320",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "3",

}

A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh. / Wang, Dajin.

In: IEEE Transactions on Computers, Vol. 52, No. 3, 01.03.2003, p. 310-320.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh

AU - Wang, Dajin

PY - 2003/3/1

Y1 - 2003/3/1

N2 - We propose a new fault block model, Minimal-Connected-Component (MCC), for fault-tolerant adaptive routing in mesh-connected multiprocessor systems. This model refines the widely used rectangular model by including fewer nonfaulty nodes in fault blocks. The positions of source/destination nodes relative to faulty nodes are taken into consideration when constructing fault blocks. The main idea behind it is that a node will be included in a fault block only if using it in a routing will definitely make the route nonminimal. The resulting fault blocks are of the rectilinear-monotone polygonal shapes. A sufficient and necessary condition is proposed for the existence of the minimal "Manhattan" routes in the presence of such fault blocks. Based on the condition, an algorithm is proposed to determine the existence of Manhattan routes. Since MCC is designed to facilitate minimal route finding, if there exists no minimal route under MCC fault model, then there will be absolutely no minimal route whatsoever. We will also present two adaptive routing algorithms that construct a Manhattan route avoiding all fault blocks, should such routes exist.

AB - We propose a new fault block model, Minimal-Connected-Component (MCC), for fault-tolerant adaptive routing in mesh-connected multiprocessor systems. This model refines the widely used rectangular model by including fewer nonfaulty nodes in fault blocks. The positions of source/destination nodes relative to faulty nodes are taken into consideration when constructing fault blocks. The main idea behind it is that a node will be included in a fault block only if using it in a routing will definitely make the route nonminimal. The resulting fault blocks are of the rectilinear-monotone polygonal shapes. A sufficient and necessary condition is proposed for the existence of the minimal "Manhattan" routes in the presence of such fault blocks. Based on the condition, an algorithm is proposed to determine the existence of Manhattan routes. Since MCC is designed to facilitate minimal route finding, if there exists no minimal route under MCC fault model, then there will be absolutely no minimal route whatsoever. We will also present two adaptive routing algorithms that construct a Manhattan route avoiding all fault blocks, should such routes exist.

KW - Adaptive routing

KW - Fault model

KW - Fault tolerance

KW - Interconnection network

KW - Mesh

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

U2 - 10.1109/TC.2003.1183946

DO - 10.1109/TC.2003.1183946

M3 - Article

VL - 52

SP - 310

EP - 320

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 3

ER -