We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A fast pessimistic diagnosis algorithm for generalized hypercube multicomputer systems.
- Authors
Duh, Dyi-Rong; Chen, Chien-Hong; Chang, Keh-Ning
- Abstract
The reliability of processors is an important issue for designing a massively parallel processing system for which fault-tolerant computing is crucial. In order to achieve high system reliability and availability, a faulty processor (node) when found should be replaced by a fault-free processor. Within a multiprocessor system, the technique of identifying faulty nodes by constructing tests on the nodes and interpreting the test outcomes is known as system-level diagnosis. The topological structure of a multicomputer system can be modeled by a graph of which the vertices and edges correspond to nodes and links of the system, respectively. This work presents a system-level diagnosis algorithm for a generalized hypercube which is an attractive variance of a hypercube. The proposed algorithm is based on the PMC model and can isolate all faulty nodes to within a set which contains at most one fault-free node. If the total number of nodes to be diagnosed in a generalized hypercube is N, the proposed algorithm can run in O( Nlog N) time, and being superior to Yang's algorithm proposed in 2004, it can diagnose not only a hypercube but also a generalized hypercube.
- Subjects
HYPERCUBE networks (Computer networks); COMPUTER networks; COMPUTER systems; FAULT-tolerant computing; ELECTRONIC data processing; PARALLEL programs (Computer programs)
- Publication
Journal of Supercomputing, 2012, Vol 61, Issue 3, p605
- ISSN
0920-8542
- Publication type
Article
- DOI
10.1007/s11227-011-0620-6