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

Research output: Contribution to journalArticle

35 Scopus citations

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

Keywords

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

Fingerprint Dive into the research topics of 'A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh'. Together they form a unique fingerprint.

  • Cite this