A comparison-based diagnosis algorithm tailored for crossed cube multiprocessor systems

Yang, X. F., Megson, G. M. and Evans, D. J. (2005) A comparison-based diagnosis algorithm tailored for crossed cube multiprocessor systems. Microprocessors and Microsystems, 29 (4). pp. 169-175. ISSN 0141-9331 doi: 10.1016/j.micpro.2004.08.002

Abstract/Summary

Comparison-based diagnosis is an effective approach to system-level fault diagnosis. Under the Maeng-Malek comparison model (NM* model), Sengupta and Dahbura proposed an O(N-5) diagnosis algorithm for general diagnosable systems with N nodes. Thanks to lower diameter and better graph embedding capability as compared with a hypercube of the same size, the crossed cube has been a promising candidate for interconnection networks. In this paper, we propose a fault diagnosis algorithm tailored for crossed cube connected multicomputer systems under the MM* model. By introducing appropriate data structures, this algorithm runs in O(Nlog(2)(2) N) time, which is linear in the size of the input. As a result, this algorithm is significantly superior to the Sengupta-Dahbura's algorithm when applied to crossed cube systems. (C) 2004 Elsevier B.V. All rights reserved.