Minimum assignment of test links for hypercubes with lower fault bounds

Dajin Wang, Zhongxian Wang

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

Abstract

In ann-dimensional hypercube multiprocessor system, to correctly diagnose faulty processors among themselves, the maximum allowed number of faulty processors isnunder the well-known PMC diagnostic model. When thenfault bound is adopted, all links between processors will be used in the diagnosis. However, if the fault bound is lower thann, many links can be freed from the task of performing diagnosis. In this paper, we show that each drop of the fault bound by 1 will free 2n-1links from diagnosis. We will present an algorithm that selects, in a symmetric manner, the to-be-freed links, so that only a minimum number of links will be used to perform diagnosis. A rigorous proof for the algorithm's correctness is given. The freed links will never be used for the purpose of diagnosis, so that the diagnosis and some conventional computations may be carried out simultaneously, improving the performance of the system as a whole.

Original languageEnglish
Pages (from-to)185-193
Number of pages9
JournalJournal of Parallel and Distributed Computing
Volume40
Issue number2
DOIs
StatePublished - 1 Feb 1997

Cite this

@article{fda347ea56e84c55b40601056d7b2fed,
title = "Minimum assignment of test links for hypercubes with lower fault bounds",
abstract = "In ann-dimensional hypercube multiprocessor system, to correctly diagnose faulty processors among themselves, the maximum allowed number of faulty processors isnunder the well-known PMC diagnostic model. When thenfault bound is adopted, all links between processors will be used in the diagnosis. However, if the fault bound is lower thann, many links can be freed from the task of performing diagnosis. In this paper, we show that each drop of the fault bound by 1 will free 2n-1links from diagnosis. We will present an algorithm that selects, in a symmetric manner, the to-be-freed links, so that only a minimum number of links will be used to perform diagnosis. A rigorous proof for the algorithm's correctness is given. The freed links will never be used for the purpose of diagnosis, so that the diagnosis and some conventional computations may be carried out simultaneously, improving the performance of the system as a whole.",
author = "Dajin Wang and Zhongxian Wang",
year = "1997",
month = "2",
day = "1",
doi = "10.1006/jpdc.1996.1279",
language = "English",
volume = "40",
pages = "185--193",
journal = "Journal of Parallel and Distributed Computing",
issn = "0743-7315",
publisher = "Academic Press Inc.",
number = "2",

}

Minimum assignment of test links for hypercubes with lower fault bounds. / Wang, Dajin; Wang, Zhongxian.

In: Journal of Parallel and Distributed Computing, Vol. 40, No. 2, 01.02.1997, p. 185-193.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Minimum assignment of test links for hypercubes with lower fault bounds

AU - Wang, Dajin

AU - Wang, Zhongxian

PY - 1997/2/1

Y1 - 1997/2/1

N2 - In ann-dimensional hypercube multiprocessor system, to correctly diagnose faulty processors among themselves, the maximum allowed number of faulty processors isnunder the well-known PMC diagnostic model. When thenfault bound is adopted, all links between processors will be used in the diagnosis. However, if the fault bound is lower thann, many links can be freed from the task of performing diagnosis. In this paper, we show that each drop of the fault bound by 1 will free 2n-1links from diagnosis. We will present an algorithm that selects, in a symmetric manner, the to-be-freed links, so that only a minimum number of links will be used to perform diagnosis. A rigorous proof for the algorithm's correctness is given. The freed links will never be used for the purpose of diagnosis, so that the diagnosis and some conventional computations may be carried out simultaneously, improving the performance of the system as a whole.

AB - In ann-dimensional hypercube multiprocessor system, to correctly diagnose faulty processors among themselves, the maximum allowed number of faulty processors isnunder the well-known PMC diagnostic model. When thenfault bound is adopted, all links between processors will be used in the diagnosis. However, if the fault bound is lower thann, many links can be freed from the task of performing diagnosis. In this paper, we show that each drop of the fault bound by 1 will free 2n-1links from diagnosis. We will present an algorithm that selects, in a symmetric manner, the to-be-freed links, so that only a minimum number of links will be used to perform diagnosis. A rigorous proof for the algorithm's correctness is given. The freed links will never be used for the purpose of diagnosis, so that the diagnosis and some conventional computations may be carried out simultaneously, improving the performance of the system as a whole.

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

U2 - 10.1006/jpdc.1996.1279

DO - 10.1006/jpdc.1996.1279

M3 - Article

VL - 40

SP - 185

EP - 193

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

SN - 0743-7315

IS - 2

ER -