Self diagnosis of processor arrays using a comparison model
Authors:
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10609857,p. 218-228
Abstract
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/sup 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.Keywords
This publication has 6 references indexed in Scilit:
- Diagnosis of processor arrays2002
- Almost sure diagnosis of almost every good element [logic testing]IEEE Transactions on Computers, 1994
- Distributed diagnosis algorithms for regular interconnected structuresIEEE Transactions on Computers, 1992
- Almost Sure Fault Tolerance in Random GraphsSIAM Journal on Computing, 1987
- Characterization of Connection Assignment of Diagnosable SystemsIEEE Transactions on Computers, 1974
- On the Connection Assignment Problem of Diagnosable SystemsIEEE Transactions on Electronic Computers, 1967