Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model

Research output: Contribution to journalArticleResearchpeer-review

87 Citations (Scopus)

Abstract

In [10], Sengupta and Dahbura discussed how to characterize a diagnosable system under the comparison diagnosis model proposed by Maeng and Malek and a polynomial algorithm was given to identify the faulty processors provided that the system's diagnosability is known. However, for a general system, the determination of its diagnosability is not algorithmically easy. This paper proves that, for the important hypercube-structured multiprocessor systems (n-cubes), the diagnosability under the comparison model is n when n≥5. The paper also studies the diagnosability of enhanced hypercube, which is obtained by adding 2 n-1 more links to a regular hypercube of 2 n processors. It is shown that the augmented communication ability among processors also increases the system's diagnosability under the comparison model. We will prove that the diagnosability is n+1 for an enhanced hypercube when n≥6.

Original languageEnglish
Pages (from-to)1369-1374
Number of pages6
JournalIEEE Transactions on Computers
Volume48
Issue number12
DOIs
StatePublished - 1 Dec 1999

Fingerprint

Diagnosability
Hypercube
Model Comparison
Polynomials
Model
N-cube
Communication
Multiprocessor Systems
Polynomial Algorithm

Cite this

@article{596d51e9b6414826861fbbf1ee8de1cb,
title = "Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model",
abstract = "In [10], Sengupta and Dahbura discussed how to characterize a diagnosable system under the comparison diagnosis model proposed by Maeng and Malek and a polynomial algorithm was given to identify the faulty processors provided that the system's diagnosability is known. However, for a general system, the determination of its diagnosability is not algorithmically easy. This paper proves that, for the important hypercube-structured multiprocessor systems (n-cubes), the diagnosability under the comparison model is n when n≥5. The paper also studies the diagnosability of enhanced hypercube, which is obtained by adding 2 n-1 more links to a regular hypercube of 2 n processors. It is shown that the augmented communication ability among processors also increases the system's diagnosability under the comparison model. We will prove that the diagnosability is n+1 for an enhanced hypercube when n≥6.",
author = "Dajin Wang",
year = "1999",
month = "12",
day = "1",
doi = "10.1109/12.817401",
language = "English",
volume = "48",
pages = "1369--1374",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "12",

}

Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model. / Wang, Dajin.

In: IEEE Transactions on Computers, Vol. 48, No. 12, 01.12.1999, p. 1369-1374.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model

AU - Wang, Dajin

PY - 1999/12/1

Y1 - 1999/12/1

N2 - In [10], Sengupta and Dahbura discussed how to characterize a diagnosable system under the comparison diagnosis model proposed by Maeng and Malek and a polynomial algorithm was given to identify the faulty processors provided that the system's diagnosability is known. However, for a general system, the determination of its diagnosability is not algorithmically easy. This paper proves that, for the important hypercube-structured multiprocessor systems (n-cubes), the diagnosability under the comparison model is n when n≥5. The paper also studies the diagnosability of enhanced hypercube, which is obtained by adding 2 n-1 more links to a regular hypercube of 2 n processors. It is shown that the augmented communication ability among processors also increases the system's diagnosability under the comparison model. We will prove that the diagnosability is n+1 for an enhanced hypercube when n≥6.

AB - In [10], Sengupta and Dahbura discussed how to characterize a diagnosable system under the comparison diagnosis model proposed by Maeng and Malek and a polynomial algorithm was given to identify the faulty processors provided that the system's diagnosability is known. However, for a general system, the determination of its diagnosability is not algorithmically easy. This paper proves that, for the important hypercube-structured multiprocessor systems (n-cubes), the diagnosability under the comparison model is n when n≥5. The paper also studies the diagnosability of enhanced hypercube, which is obtained by adding 2 n-1 more links to a regular hypercube of 2 n processors. It is shown that the augmented communication ability among processors also increases the system's diagnosability under the comparison model. We will prove that the diagnosability is n+1 for an enhanced hypercube when n≥6.

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

U2 - 10.1109/12.817401

DO - 10.1109/12.817401

M3 - Article

VL - 48

SP - 1369

EP - 1374

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 12

ER -