Hardware-efficient and highly reconfigurable 4-and 2-track fault-tolerant designs for mesh-connected arrays

Citation
Nr. Mahapatra et S. Dutt, Hardware-efficient and highly reconfigurable 4-and 2-track fault-tolerant designs for mesh-connected arrays, J PAR DISTR, 61(10), 2001, pp. 1391-1411
Citations number
14
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
ISSN journal
0743-7315 → ACNP
Volume
61
Issue
10
Year of publication
2001
Pages
1391 - 1411
Database
ISI
SICI code
0743-7315(200110)61:10<1391:HAHR42>2.0.ZU;2-4
Abstract
We consider in-track models for constructing fault-tolerant (FT) mesh syste ms which have one primary and rn spare tracks per row and column, switches at the intersection of these tracks, and spare processors at the boundaries . A faulty system is reconfigured by finding for each fault u a reconfigura tion path from the fault to a spare in which, starting from the fault u, a processor is replaced or "covered" by the nearest "available" succeeding pr ocessor on the path-a processor on the path is not available if it is fault y or is used as a "cover" on some other reconfiguration path. In previous w ork, a 1-track design that can support any set of node-disjoint straight re configuration paths, and a more reliable 3-track design that can support an y set of node-disjoint rectilinear reconfiguration paths have been proposed . In this research note, we present: (1) A fundamental result regarding the universality of simple "one-to-one switches" in in-track 2-D mesh designs in terms of their reconfigurabilities. (2) A 4-track mesh design that can s upport any set of edge-disjoint (a much less restrictive criterion than nod e-disjointness) rectilinear reconfiguration paths, and that has 34 % less s witching overhead and significantly higher, actually close-to-optimal, reco nfigurability compared to the previously proposed 3-track design. (3) A new 2-track design derivedfrom the above 4-track design that we show can suppo rt the same set of reconfiguration paths as the previous 3-track design but with 33 % less wiring overhead. (4) Results on the deterministic fault tol erance capabilities (the number of faults guaranteed reconfigurable) of our 4- and 2-track designs, and the previously proposed 1- and 3-track designs .