A low-cost fault-tolerant structure for the hypercube

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)

Abstract

We propose a new, low-cost fault-tolerant structure for the hypercube that employs spare processors and extra links. The target of the proposed structure is to fully tolerate the first faulty node, no matter where it occurs, and "almost fully" tolerate the second, meaning that the underlying hypercube topology can be resumed if the second faulty node occurs at most locations-expectantly 92% of locations. The unique features of our structure are that (1) it utilizes the unused extra link-ports in the processor nodes of the hypercube to obtain the proposed topology, so that minimum extra hardware is needed in constructing the fault-tolerant structure and (2) the structure's node-degrees are low as desired-the primary and spare nodes all have node-degrees of n + 2 for an n-dimensional hypercube. The number of spare nodes is one fourth of primary nodes. The reconfiguration algorithm in the presence of faults is elegant and efficient. The proposed structure also effectively enhances the diagnosability of the hypercube system. It is shown that the diagnosability of the structure is increased to n + 2, whereas an ordinary n-dimensional hypercube has diagnosability n.

Original languageEnglish
Pages (from-to)203-216
Number of pages14
JournalJournal of Supercomputing
Volume20
Issue number3
DOIs
StatePublished - 1 Nov 2001

Fingerprint

Hypercube
Fault-tolerant
Topology
Diagnosability
Vertex of a graph
Costs
Hardware
n-dimensional
Reconfiguration
Fault
Target

Keywords

  • Diagnosability
  • Fault tolerance
  • Hypercubes
  • Interconnection networks
  • Redundant systems

Cite this

@article{92dd11f1f2c0415b9550d95e4cd26eb5,
title = "A low-cost fault-tolerant structure for the hypercube",
abstract = "We propose a new, low-cost fault-tolerant structure for the hypercube that employs spare processors and extra links. The target of the proposed structure is to fully tolerate the first faulty node, no matter where it occurs, and {"}almost fully{"} tolerate the second, meaning that the underlying hypercube topology can be resumed if the second faulty node occurs at most locations-expectantly 92{\%} of locations. The unique features of our structure are that (1) it utilizes the unused extra link-ports in the processor nodes of the hypercube to obtain the proposed topology, so that minimum extra hardware is needed in constructing the fault-tolerant structure and (2) the structure's node-degrees are low as desired-the primary and spare nodes all have node-degrees of n + 2 for an n-dimensional hypercube. The number of spare nodes is one fourth of primary nodes. The reconfiguration algorithm in the presence of faults is elegant and efficient. The proposed structure also effectively enhances the diagnosability of the hypercube system. It is shown that the diagnosability of the structure is increased to n + 2, whereas an ordinary n-dimensional hypercube has diagnosability n.",
keywords = "Diagnosability, Fault tolerance, Hypercubes, Interconnection networks, Redundant systems",
author = "Dajin Wang",
year = "2001",
month = "11",
day = "1",
doi = "10.1023/A:1011636631661",
language = "English",
volume = "20",
pages = "203--216",
journal = "Journal of Supercomputing",
issn = "0920-8542",
publisher = "Springer Netherlands",
number = "3",

}

A low-cost fault-tolerant structure for the hypercube. / Wang, Dajin.

In: Journal of Supercomputing, Vol. 20, No. 3, 01.11.2001, p. 203-216.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - A low-cost fault-tolerant structure for the hypercube

AU - Wang, Dajin

PY - 2001/11/1

Y1 - 2001/11/1

N2 - We propose a new, low-cost fault-tolerant structure for the hypercube that employs spare processors and extra links. The target of the proposed structure is to fully tolerate the first faulty node, no matter where it occurs, and "almost fully" tolerate the second, meaning that the underlying hypercube topology can be resumed if the second faulty node occurs at most locations-expectantly 92% of locations. The unique features of our structure are that (1) it utilizes the unused extra link-ports in the processor nodes of the hypercube to obtain the proposed topology, so that minimum extra hardware is needed in constructing the fault-tolerant structure and (2) the structure's node-degrees are low as desired-the primary and spare nodes all have node-degrees of n + 2 for an n-dimensional hypercube. The number of spare nodes is one fourth of primary nodes. The reconfiguration algorithm in the presence of faults is elegant and efficient. The proposed structure also effectively enhances the diagnosability of the hypercube system. It is shown that the diagnosability of the structure is increased to n + 2, whereas an ordinary n-dimensional hypercube has diagnosability n.

AB - We propose a new, low-cost fault-tolerant structure for the hypercube that employs spare processors and extra links. The target of the proposed structure is to fully tolerate the first faulty node, no matter where it occurs, and "almost fully" tolerate the second, meaning that the underlying hypercube topology can be resumed if the second faulty node occurs at most locations-expectantly 92% of locations. The unique features of our structure are that (1) it utilizes the unused extra link-ports in the processor nodes of the hypercube to obtain the proposed topology, so that minimum extra hardware is needed in constructing the fault-tolerant structure and (2) the structure's node-degrees are low as desired-the primary and spare nodes all have node-degrees of n + 2 for an n-dimensional hypercube. The number of spare nodes is one fourth of primary nodes. The reconfiguration algorithm in the presence of faults is elegant and efficient. The proposed structure also effectively enhances the diagnosability of the hypercube system. It is shown that the diagnosability of the structure is increased to n + 2, whereas an ordinary n-dimensional hypercube has diagnosability n.

KW - Diagnosability

KW - Fault tolerance

KW - Hypercubes

KW - Interconnection networks

KW - Redundant systems

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

U2 - 10.1023/A:1011636631661

DO - 10.1023/A:1011636631661

M3 - Article

VL - 20

SP - 203

EP - 216

JO - Journal of Supercomputing

JF - Journal of Supercomputing

SN - 0920-8542

IS - 3

ER -