2-SATISFIABILITY AND DIAGNOSING FAULTY PROCESSORS IN MASSIVELY-PARALLEL COMPUTING SYSTEMS

A fault diagnosis model for multiprocessor computers is proposed. Unde r normal operating mode each processor executes its own data. When an error occurs, the system is switched to the diagnostic mode. Previous input data for each processor is shifted to a different unit, to obtai n a set of comparison results. We show that analysis of the test data to diagnose or locate faulty processors is equivalent to a 2-satisfiab ility problem. Under the assumption that discrepancy in a comparison r esult occurs if and only if at least one of the processors (being comp ared) is faulty, we prove that all the faulty processors can be diagno sed in O(n(2)) time, where n denotes the number of processors in the s ystem.