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 ofprocessors. The algorithm is based on interprocessor tests, using a comparison model. The algorithm, which is divided in four steps, called intracluster diagnosis, interluster diagnosis.faultfree core identification and augmentation, identifies a set of non-faulty and a set offaulty units. The diagnosis is proved to be correct in the worst case, assuming that the actual number offaulty processors is no more that T(N), an increasing function of the number N ofprocessors. It is shown that T(N) is O(N%). 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 limitationswhich ensure correctness in the worst case.