A fast diagnosis algorithm for locally twisted cube multiprocessor systems under the MM∗ model
✍ Scribed by Hui Yang; Xiaofan Yang
- Publisher
- Elsevier Science
- Year
- 2007
- Tongue
- English
- Weight
- 372 KB
- Volume
- 53
- Category
- Article
- ISSN
- 0898-1221
No coin nor oath required. For personal study only.
✦ Synopsis
Comparison-based diagnosis is a practical approach to the system-level fault diagnosis of multiprocessors. The locally twisted cube is a newly introduced hypercube variant, which not only possesses lower diameter and better graph embedding capability as compared with a hypercube of the same size, but retains some nice properties of hypercubes. This paper addresses the fault diagnosis of locally twisted cubes under the MM * comparison model. By utilizing the existence of abundant cycles within a locally twisted cube, we present a new diagnosis algorithm. With elaborately organized data, this algorithm can run in O(N log 2 2 N ) time, where N stands for the total number of nodes. In comparison, the classical Sengupta-Dahbura diagnosis algorithm takes as much as O(N 5 ) time to achieve the same goal. As a consequence, the proposed algorithm is remarkably superior to the Sengupta-Dahbura algorithm in terms of the time overhead.