Efficient network-flow based techniques for dynamic fault reconfiguration in FPGAs
- 20 January 2003
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 122-129
- https://doi.org/10.1109/ftcs.1999.781042
Abstract
In this paper we consider a "dynamic" node covering frameworks for incorporating fault tolerance in SRAM-based segmented array FPGAs with spare row(s) and/or column(s) of cells. Two types of designs are considered: one that can support only node-disjoint (and hence nonintersecting) rectilinear reconfiguration paths, and the other that can support edge-disjoint (and hence possibly intersecting) rectilinear reconfiguration paths. The advantage of this approach is that reconfiguration paths are determined dynamically depending upon the actual set of faults and track segments are used as required, thus resulting in higher reconfigurability and lower track overheads compared to previously proposed "static" approaches. We provide optimal network flow based reconfiguration algorithms for both of our designs and present and analyze a technique for speeding up these algorithms, depending upon the fault size, by as much as 20 times. Finally, we present reconfigurability results for our FPGA designs that show much better fault tolerance for them compared to previous approaches-the reconfigurability of the edge-disjoint design is 90% or better and 100% most of the time, which implies near-optimal spare-cell utilization. Author(s) Mahapatra, N.R. Dept. of Comput. Sci. & Eng., State Univ. of New York, Buffalo, NY, USA Dutt, S.Keywords
This publication has 7 references indexed in Scilit:
- An approach for the yield enhancement of programmable gate arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A dual granularity and globally interconnected architecture for a programmable logic devicePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Design methodologies for tolerating cell and interconnect faults in FPGAsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Node-covering based defect and fault tolerance methods for increased yield in FPGAsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Methodologies for tolerating cell and interconnect faults in FPGAsIEEE Transactions on Computers, 1998
- On routability for FPGAs under faulty conditionsIEEE Transactions on Computers, 1995
- Yield enhancement of programmable ASIC arrays by reconfiguration of circuit placementsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1994