CONSTRAINT-BASED DIAGNOSIS ALGORITHMS FOR MULTIPROCESSORS

Abstract

In the latest years, new ideas appeared in system level diagnosis of multiprocessor systems. In contrary to the traditional diagnosis models (like PMC, BGM, etc.) which use strictly graph-oriented methods to determine the faulty components in a system, these new theories prefer Al-based algorithms, especially CSP methods. Syndrome decoding, the basic problem of self-diagnosis, can easily be transformed into constraints between the state of the tester and the tested components. Therefore the diagnosis algorithm can be derived from a special constraint solving algorithm. The bengin nature of the constraints (all their variables, representing the fault states of the components, have a very limited domain; the constraints are simple and similar to each other) reduces the algorithm's complexity so it can be converted to a powerful distributed diagnosis method with a minimal overhead. Experimental algorithms (using both centralized and distributed approach) were implemented for a Parsytec GC massively parallel multiprocessor system.