ADAPTIVE SYSTEM-LEVEL DIAGNOSIS FOR HYPERCUBE MULTIPROCESSORS

System-level diagnosis is an important technique for fault detection a nd location in multiprocessor computing systems. Efficient diagnosis i s highly desirable for sustaining the original system power. Moreover, effective diagnosis is particularly important for a multiprocessor sy stem with high scalability but low connectivity. Most of the existing results are not applicable in practice because of the high diagnosis c ost and limited diagnosability. Over-d fault diagnosis, where dis the diagnosability, has only been addressed using a probabilistic method i n the literature. Aiming at these two issues, we propose a hierarchica l adaptive system-level diagnosis approach for hypercube systems using a divide-and-conquer strategy. We first propose a conceptual algorith m HADA to formulate a rigorous analysis. Then we present its practical variant IHADA. In HADA and IHADA, the over-d fault problem is inheren tly tackled through a deterministic method. Three measures for diagnos is cost (diagnosis time, number of tests, and number of test links) ar e analyzed for the proposed algorithms. It is proved that the diagnosi s cost required by our approach is lower than in previous diagnosis al gorithms. It is shown that the diagnosis cost for the proposed algorit hms depends on the number and location of faulty units in the system a nd the cost is extremely low when only a small number of faulty units exist. It is also shown that our algorithms are characterized by lower costs than a pessimistic diagnosis algorithm which trades lower diagn osis cost for a lower degree of accuracy. Experimental results on the nCUBE are provided to substantiate the practicality of the proposed ap proach.