Evaluation of diagnosis algorithms for grid interconnected systems

Three related diagnosis algorithms for systems consisting 01 a large number 01grid-interconnected units (usually, but not necessarily, processors) are presented. The application domain of these algorithms includes selfdiagnosis of massive parallel systems and testing 01 VLSIchips in the manufacturing processo The basic algarithm, called Al, is analyzed in more detail. It is shown that its diagnosis is provably correct, although possibly incomplete, assuming that the number of the actualfaults is not above certain bounds. Two different bounds are presented: a syndrome dependent bound Tdn) which.For any syndrome G'. is asserted by the diagnosis algorithm itself, and a syndrome independent bound T(n). FunctionT(n) is (}(n 213), where n is the number 01 units in the system. From simulation results, it is shown that the diagnosis is also likety to be complete and, if not complete. that the number of units whose state cannot be identified can be expected to be very small. With the application ta the testing 01 VLS/ in the mind, two alternate algorithms (named A2 and A3) are also analyzed. These algorithms, which are correct under the same conditions holding for algorithm Al, provide different trade-offs between the time complexity and the degree of completeness.