Adaptive and fault-tolerant routing algorithms for high performance 2D torus interconnection network

Ting-Wei Hou, S. R. Tsai, L. M. Tseng

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Adaptive and fault-tolerant schemes for routing messages in a 2D torus interconnection network for distributed memory multi-computers (message passing concurrent computers) are presented. For the adaptive scheme, two new techniques, channel switching and dimension switching, are developed and proved deadlock-free. For the fault-tolerant scheme, a message can be rerouted to a virtual destination, which in turn sends the message to the real destination. This scheme can tolerate all single faults and many multiple faults, and is deadlock-free. The two routing schemes are suitable for the high performance virtual cut-through and wormhole routing. The required hardware overhead for realizing the fault-tolerant scheme is small and no time penalty is paid in the fault-free case.

Original languageEnglish
Pages (from-to)3-15
Number of pages13
JournalComputers and Mathematics with Applications
Volume23
Issue number1
DOIs
Publication statusPublished - 1992 Jan 1

Fingerprint

Fault-tolerant Routing
Interconnection Networks
Routing algorithms
Routing Algorithm
Torus
High Performance
Message passing
Fault-tolerant
Fault
Deadlock
Hardware
Data storage equipment
Routing
Wormhole Routing
Multicomputers
Distributed Memory
Message Passing
Penalty
Concurrent

All Science Journal Classification (ASJC) codes

  • Modelling and Simulation
  • Computational Theory and Mathematics
  • Computational Mathematics

Cite this

@article{ee0c8eac9a1a4021b0b253cf03f263e0,
title = "Adaptive and fault-tolerant routing algorithms for high performance 2D torus interconnection network",
abstract = "Adaptive and fault-tolerant schemes for routing messages in a 2D torus interconnection network for distributed memory multi-computers (message passing concurrent computers) are presented. For the adaptive scheme, two new techniques, channel switching and dimension switching, are developed and proved deadlock-free. For the fault-tolerant scheme, a message can be rerouted to a virtual destination, which in turn sends the message to the real destination. This scheme can tolerate all single faults and many multiple faults, and is deadlock-free. The two routing schemes are suitable for the high performance virtual cut-through and wormhole routing. The required hardware overhead for realizing the fault-tolerant scheme is small and no time penalty is paid in the fault-free case.",
author = "Ting-Wei Hou and Tsai, {S. R.} and Tseng, {L. M.}",
year = "1992",
month = "1",
day = "1",
doi = "10.1016/0898-1221(92)90075-S",
language = "English",
volume = "23",
pages = "3--15",
journal = "Computers and Mathematics with Applications",
issn = "0898-1221",
publisher = "Elsevier Limited",
number = "1",

}

Adaptive and fault-tolerant routing algorithms for high performance 2D torus interconnection network. / Hou, Ting-Wei; Tsai, S. R.; Tseng, L. M.

In: Computers and Mathematics with Applications, Vol. 23, No. 1, 01.01.1992, p. 3-15.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Adaptive and fault-tolerant routing algorithms for high performance 2D torus interconnection network

AU - Hou, Ting-Wei

AU - Tsai, S. R.

AU - Tseng, L. M.

PY - 1992/1/1

Y1 - 1992/1/1

N2 - Adaptive and fault-tolerant schemes for routing messages in a 2D torus interconnection network for distributed memory multi-computers (message passing concurrent computers) are presented. For the adaptive scheme, two new techniques, channel switching and dimension switching, are developed and proved deadlock-free. For the fault-tolerant scheme, a message can be rerouted to a virtual destination, which in turn sends the message to the real destination. This scheme can tolerate all single faults and many multiple faults, and is deadlock-free. The two routing schemes are suitable for the high performance virtual cut-through and wormhole routing. The required hardware overhead for realizing the fault-tolerant scheme is small and no time penalty is paid in the fault-free case.

AB - Adaptive and fault-tolerant schemes for routing messages in a 2D torus interconnection network for distributed memory multi-computers (message passing concurrent computers) are presented. For the adaptive scheme, two new techniques, channel switching and dimension switching, are developed and proved deadlock-free. For the fault-tolerant scheme, a message can be rerouted to a virtual destination, which in turn sends the message to the real destination. This scheme can tolerate all single faults and many multiple faults, and is deadlock-free. The two routing schemes are suitable for the high performance virtual cut-through and wormhole routing. The required hardware overhead for realizing the fault-tolerant scheme is small and no time penalty is paid in the fault-free case.

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

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

U2 - 10.1016/0898-1221(92)90075-S

DO - 10.1016/0898-1221(92)90075-S

M3 - Article

VL - 23

SP - 3

EP - 15

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

SN - 0898-1221

IS - 1

ER -