Adaptive system-level diagnosis for hypercube multiprocessors using a comparison model

Fault detection and localization are important in multiprocessor computing systems. Several methods of system self-diagnosis have been developed, including the model proposed by Preparata, Metze, and Chien (known as the PMC model) and a comparison model proposed by Maeng and Malek (the MM model). Adaptive diagnosis is a practical system-level diagnostic scheme whose main design objectives are to reduce the number of test rounds and the total number of tests. A number of interesting research results have been presented for adaptive diagnosis using the classical PMC model. However, adaptive diagnosis using the MM model has been discussed only in relation to completely connected systems and torus systems. In this paper we consider the problem of adaptive fault diagnosis in an n-dimensional hypercube using the MM model. The hypercube is an important interconnection network and an n-dimensional hypercube has been shown to be n-diagnosable using the MM model. The goal is to correctly identify the status of all processors, assuming that the number of faulty vertices does not exceed the hypercube dimension. For a cycle of N vertices, we show that at least four test rounds are necessary for complete diagnosis if N is not a multiple of three. We propose a scheme that completely diagnoses a 4-dimensional hypercube in at most seven test rounds and an n-dimensional hypercube, for n ⩾ 5 in at most six test rounds and at most N + 2n3 + 8n2 tests, where N = 2n.