On the diagnosis of two-dimensional grid of processors

We examine diagnosis of processor array systems formed as two-dimensional g rids, with boundaries, and either four or eight neighbors for each interior processor. We employ a parallel test schedule. Neighboring processors test each other and report the results. Our diagnostic objective is to find a f ault-free processor or set of processors. The system may then be sequential ly diagnosed by repairing those processors tested faulty according to the i dentified fault-free set. We establish an upper bound on the maximum number of faults that can be sustained without invalidating the test results unde r worst case conditions. We give test schedules and diagnostic algorithms t hat meet the upper bound as far as the highest order term. We compare these near optimal diagnostic algorithms to alternative algorithms-both new and already in the literature.