Self diagnosis of grid-interconnected systems, with application to self-test of VLSI wafers

Given a set N of n interconnected processors, some of which may be faulty, the so-called system-level diagnosis is aimed at identifying the faulty processors by analysing the outcomes of the available interprocessor tests. The set of these interprocessor tests must be defined appropriately, with the constraint that processors can only test each other if they are interconnected. Cases of regular or quasi regular interconnection schemes deserve special interest since regular interconnection structures are widely adopted in large parallel machines, and they appear suitable far application to wafer-scale IC-testing. However, the theoretica1 results of system-level diagnosis are quite poor when applied to regular interconnected systems. Far example correct and complete diagnosis of a two-dimensional toroidal mesh is only possible if the number of faults does not exceed four, regardless of the size of the system.