On the Diagnosis of Two-Dimensional Grid of Processors

Jun ZHAO  Fred J. MEYER  Nohpill PARK  Fabrizio LOMBARDI  

IEICE TRANSACTIONS on Information and Systems   Vol.E84-D   No.11   pp.1486-1499
Publication Date: 2001/11/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Function Integrated Information Systems)
sequential diagnosis,  repair,  regular array,  homogeneous system,  PMC model,  

Full Text: PDF(994.1KB)>>
Buy this Article

We examine diagnosis of processor array systems formed as two-dimensional grids, 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 fault-free processor or set of processors. The system may then be sequentially diagnosed by repairing those processors tested faulty according to the identified fault-free set. We establish an upper bound on the maximum number of faults that can be sustained without invalidating the test results under worst case conditions. We give test schedules and diagnostic algorithms that 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.