A heuristic fault-tolerant routing algorithm in mesh using rectilinear-monotone polygonal fault blocks

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

A new, rectilinear-monotone polygonally shaped fault block model, called Minimal-Connected-Component (MCC), was proposed in [D. Wang, A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh, IEEE Trans. Comput. 52 (3) (2003) 310-320] for minimal adaptive routing in mesh-connected multiprocessor systems. This model refines the widely used rectangular model by including fewer non-faulty nodes in fault blocks. The positions of source/destination nodes relative to faulty nodes are taken into consideration when constructing fault blocks. Adaptive routing algorithm was given in Wang (2003), that constructs a minimal "Manhattan" route avoiding all fault blocks, should such routes exist. However, if there are no minimal routes, we still need to find a route, preferably as short as possible. In this paper, we propose a heuristic algorithm that takes a greedy approach, and can compute a nearly shortest route without much overhead. The significance of this algorithm lies in the fact that routing is a frequently performed task, and messages need to get to their destinations as soon as possible. Therefore one would prefer to have a fast answer about which route to take (and then take it), rather than spend too much time working out an absolutely shortest route.

Original languageEnglish
Pages (from-to)619-628
Number of pages10
JournalJournal of Systems Architecture
Volume53
Issue number9
DOIs
StatePublished - Sep 1 2007

Fingerprint

Routing algorithms
Heuristic algorithms
Adaptive algorithms

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture

Keywords

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

Cite this

@article{2ed64f6e59da4a2faa398ef4e7af9081,
title = "A heuristic fault-tolerant routing algorithm in mesh using rectilinear-monotone polygonal fault blocks",
abstract = "A new, rectilinear-monotone polygonally shaped fault block model, called Minimal-Connected-Component (MCC), was proposed in [D. Wang, A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh, IEEE Trans. Comput. 52 (3) (2003) 310-320] for minimal adaptive routing in mesh-connected multiprocessor systems. This model refines the widely used rectangular model by including fewer non-faulty nodes in fault blocks. The positions of source/destination nodes relative to faulty nodes are taken into consideration when constructing fault blocks. Adaptive routing algorithm was given in Wang (2003), that constructs a minimal {"}Manhattan{"} route avoiding all fault blocks, should such routes exist. However, if there are no minimal routes, we still need to find a route, preferably as short as possible. In this paper, we propose a heuristic algorithm that takes a greedy approach, and can compute a nearly shortest route without much overhead. The significance of this algorithm lies in the fact that routing is a frequently performed task, and messages need to get to their destinations as soon as possible. Therefore one would prefer to have a fast answer about which route to take (and then take it), rather than spend too much time working out an absolutely shortest route.",
keywords = "Adaptive routing, Fault block model, Fault tolerance, Interconnection network, Mesh",
author = "Dajin Wang",
year = "2007",
month = "9",
day = "1",
doi = "https://doi.org/10.1016/j.sysarc.2006.12.005",
language = "English",
volume = "53",
pages = "619--628",
journal = "Journal of Systems Architecture",
issn = "1383-7621",
publisher = "Elsevier",
number = "9",

}

A heuristic fault-tolerant routing algorithm in mesh using rectilinear-monotone polygonal fault blocks. / Wang, Dajin.

In: Journal of Systems Architecture, Vol. 53, No. 9, 01.09.2007, p. 619-628.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A heuristic fault-tolerant routing algorithm in mesh using rectilinear-monotone polygonal fault blocks

AU - Wang, Dajin

PY - 2007/9/1

Y1 - 2007/9/1

N2 - A new, rectilinear-monotone polygonally shaped fault block model, called Minimal-Connected-Component (MCC), was proposed in [D. Wang, A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh, IEEE Trans. Comput. 52 (3) (2003) 310-320] for minimal adaptive routing in mesh-connected multiprocessor systems. This model refines the widely used rectangular model by including fewer non-faulty nodes in fault blocks. The positions of source/destination nodes relative to faulty nodes are taken into consideration when constructing fault blocks. Adaptive routing algorithm was given in Wang (2003), that constructs a minimal "Manhattan" route avoiding all fault blocks, should such routes exist. However, if there are no minimal routes, we still need to find a route, preferably as short as possible. In this paper, we propose a heuristic algorithm that takes a greedy approach, and can compute a nearly shortest route without much overhead. The significance of this algorithm lies in the fact that routing is a frequently performed task, and messages need to get to their destinations as soon as possible. Therefore one would prefer to have a fast answer about which route to take (and then take it), rather than spend too much time working out an absolutely shortest route.

AB - A new, rectilinear-monotone polygonally shaped fault block model, called Minimal-Connected-Component (MCC), was proposed in [D. Wang, A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh, IEEE Trans. Comput. 52 (3) (2003) 310-320] for minimal adaptive routing in mesh-connected multiprocessor systems. This model refines the widely used rectangular model by including fewer non-faulty nodes in fault blocks. The positions of source/destination nodes relative to faulty nodes are taken into consideration when constructing fault blocks. Adaptive routing algorithm was given in Wang (2003), that constructs a minimal "Manhattan" route avoiding all fault blocks, should such routes exist. However, if there are no minimal routes, we still need to find a route, preferably as short as possible. In this paper, we propose a heuristic algorithm that takes a greedy approach, and can compute a nearly shortest route without much overhead. The significance of this algorithm lies in the fact that routing is a frequently performed task, and messages need to get to their destinations as soon as possible. Therefore one would prefer to have a fast answer about which route to take (and then take it), rather than spend too much time working out an absolutely shortest route.

KW - Adaptive routing

KW - Fault block model

KW - Fault tolerance

KW - Interconnection network

KW - Mesh

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

U2 - https://doi.org/10.1016/j.sysarc.2006.12.005

DO - https://doi.org/10.1016/j.sysarc.2006.12.005

M3 - Article

VL - 53

SP - 619

EP - 628

JO - Journal of Systems Architecture

JF - Journal of Systems Architecture

SN - 1383-7621

IS - 9

ER -