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

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 .