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, which is divided in four steps, called intracluster diagnosis, interluster diagnosis, fault-free core identification and augmentation, identifies a set of non-faulty and a set of faulty units. 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 that T(N) is O(N^2/3). Although correct, the diagnosis is generally incomplete. However, using probabilistic techniques, it is shown that the diagnosis is very likely to be complete under the same limitations which ensure correctness in the worst case