Chinese Journal of Computers   Full Text
Title	A Fast Diagnosis Algorithm on M?bius Cube Under the MM* Comparison Model
Authors	YANG Hui YANG Xiao-Fan
Address	(College of Computer Science, Chongqing University, Chongqing 400044)
Year	2007
Issue	No.7(1125—1131)
Abstract &   Background	Abstract Comparison-based diagnosis is a practical approach to the system-level fault diagnosis of multicomputers. The M?bius cube is a variant of the hypercube, which possesses some features desirable for parallel processing. This paper addresses the fault diagnosis of the M?bius cube under the MM* comparison model. By employing the distributed property of cycles over a M?bius cube, the authors present a new diagnosis algorithm. With elaborately organized data, this algorithm can operate in O(Nlog22N) time, where N stands for the total number of nodes. In comparison, the classical Sengupta-Dahbura diagnosis algorithm takes as much as O(N5) 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. keywords multicomputer; system-level diagnosis; comparison-based diagnosis algorithm; M?bius cube background The system-level diagnosis of multicomputers, which is aimed at identifying faulty processors by conducting tests on processors and interpreting the test outcomes, is an important topic of research from fault-tolerant computing. The central task of system-level diagnosis is to develop efficient diagnosis algorithms. As a result, many diagnosis algorithms tailored for various interconnection network architectures have been proposed. However, to our knowledge, there is no known efficient diagnosis algorithm on M?bius cube network under the MM*comparison model. By employing the distributed property of cycles over a M?bius cube, the authors present a new diagnosis algorithm. With elaborately organized data, this algorithm can operate in O(Nlog22N) time, where N stands for the total number of nodes. In comparison, the classical Sengupta-Dahbura diagnosis algorithm takes as much as O(N5) time to achieve the same goal. Therefore, the diagnosis algorithm is remarkably superior. The work of this paper is a constituent part of a large project entitled "Parallel Computing and Fault Tolerance", which is supported by Program of Educational Ministry of China for New Century Excellent Talents (Grant No. NCET-05-0759), Doctorate Foundation of Educational Ministry of China (20050611001), Natural Science Foundation of Chongqing CSTC (2006BB2231, 2005BB2191), and Chongqing University Postgraduates’Science and Innovation Fund (200701Y1A0050191). The research group has published more than 20 academic papers in distinguished international journals towards this direction of research.