Self-diagnosing algorithms for processor arrays : Survey and evaluation

A new family of self-diagnosing algorithms for grid Interconnected, massively parallel systems is surveyed. The algorithms exploit interprocessor tests, according the PMC model of system diapnosis. The global diagnosis is built up by combination of diagnoses local to appropriate processor clusters. Different algorithms in the family exploit cluster of different size, and this implies different strategies of test execution, as well as different numbers of tests. The notable feature of the new algorithms consists in their ability to provide correct diagnosis (although generally incomplete) provided the number offaults is not above Tk(n), where n is the number ofprocessors and Tk(n) is O(n2/3) . Furthermore simulation has provided evidence that the diagnosis is very likely to be completeand, if not complete, it is almostcompletein any case. Simulation results are reported.