Constraint Based Diagnosis Algorithms For Multiprocessors

Constraint-based diagnosis algorithms for multiprocessors A. Petri, P. Urban, J. Altmann, M. Dal Cin, E. Selenyi, K. Tilly, A. Pataricza 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 AI-based algorithms, especially CSP methods. Syndrome decoding, the basic problem of self-diagnosis, can be easily 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 "benign" 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.