A fast diagnosis algorithm for locally twisted cube multiprocessor systems under the MM* model

作者：Yang Hui^*; Yang Xiaofan

来源：Computers & Mathematics with Applications, 2007, 53(6): 918-926.

DOI：10.1016/j.camwa.2006.09.008

• multiprocessor
• system-level fault diagnosis
• comparison model
• diagnosis algorithm
• locally twisted cube

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.

• 出版日期2007-3
• 单位重庆大学