Correct and Almost complete diagnosis of processor arrays

This paper introduces a diagnosing algorithm for bidimensional processor arrays, wher~ every processor is connected to its four neighbours along horizontal and vertical lines. The algonthrn15 based upon interprocessor tests, according to the PMC model. .' . The algorithm is structured in three steps, called local diagnosis, Fault Free Core identif'tcatLO~ and augmentation. In the first step, every processor is classified as either H (presumably healthy), (dual unit) or F (faulty). The state of faulty or non-faulty remains unidentified, except for processorf being classified F. In the second step, processors classified H are combined into a nurn~er 0 contiguouS sets, called aggregates, and all aggregates of maximum cardinality are combined 111 th~ Fault Free Core, which is completely fault-free. The third step exploits the non-faulty state 0 processors in the Fault Free Core to diagnose as many as possible of the remaining processors. The diagnosis is proved to be correct in the worst case, assuming that the actual number of faulty processors is no more that T(N), an increasing function of the number N of processors. It is shown 2/3 that T(N)== O(N ). Although correct, the diagnosis is generally incomplete. However, the algorithm has been evaluated by means of simulation, and simulation data provide evidence that the diagnosis I'm very likely to be complete or nearly complete under the same limitations which ensure correctness In t e worst case