For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On the Diagnosis of Two-Dimensional Grid of Processors
Jun ZHAO Fred J. MEYER Nohpill PARK Fabrizio LOMBARDI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2001/11/01
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>>
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.