Self diagnosis of processor arrays using a comparison model

This paper introduces a diagnosing algorithm for bidimensional processor arrays, where processors are interconnected in horizontal and vertical meshes. For the purpose of diagnosis, the array is considered to be partitioned in square clusters of processors. The algorithm is based on interprocessor tests, using a comparison model. The algorithm is structured in four steps, called intracluster diagnosis, interluster diagnosis.fault-free core identification and augmentation. In the first and the second step, every cluster is c1assified as NZ, F, D, or Z, and those classified Z are combined into a number of contiguous sets, called aggregates. Every aggregate consists of processors which are in the sarne state of faulty or non-faulty; however, the actual state remains unidentified. In the third step, all aggregates of maximum cardinality are combined in the Fault Free Core, which is completely fault-free. The last step exploits the non-faulty state of processors in the Fault Free Core to diagnose as many as possible of the rernaining processors. The diagnosis is proved to be correct in the worst case, assurning 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 that T(N)= O(N2/3). Although correct, the diagnosis is generally incomplete. However, probabilistic evaluation has shown that the diagnosis is very likely to be complete under the sarne lirnitations which ensure correctness in the worst case.