Correct and almost complete diagnosis of processor grids

Chessa S, Maestrini P

System-level diagnosis  PMC model  Processor grids  Constant degree diagnosis  Diagnosis algorithm 

A new diagnosis algorithm for square grids is introduced. The algorithm always provides correct diagnosis if the number of faulty processors is below T, a bound with T 2 ...n2=3+, which was derived by worst-case analysis. A more effective tool to validate the diagnosis correctness is the syndrome dependent bound T, with T T, asserted by the diagnosis algorithm itself for every given diagnosis experiment. Simulation studies provided evidence that the diagnosis is complete or almost complete if the number of faults is below T. The fraction of units which cannot be identified as either faulty or nonfaulty remains relatively small as long as the number of faults is below n=3 and, as long as the number of faults is below n=2, the diagnosis is correct with high probability.

Source: I.E.E.E. TRANSACTIONS ON COMPUTERS (PRINT), vol. 50 (issue 10), pp. 1095-1102