Efficient Incremental Rerouting for Fault Reconfiguration in Field Programmable Gate Arrays

摘要

The ability to reconfigue around manufacturing defects and operational faults increases FPGA chip yield, reduces system downtime and maintenance in field operation, and increases reliabilities of mission- and life-critical systems. The fault reconfiguration technique discussed in this work use the principle of node covering in which reconfiguration is achieved by constructing replacement chains of cells from faulty cells to spare/unused ones. A key issue in such reconfiguration is efficient incremental rerouting in the FPGA. Previous methods for node-covering based reconfiguration are "static" in the sense that extra interconnects are added a-priori as part of the initial circuit routing so that a specific fault pattern (e.g., one fault per row) can be tolerated [1]. This, however, results in worst-case track overheads and also in an inflexibility to tolerate other realistic fault patterns. In this paper, we develop dynamic reconfiguration and incremental rerouting techniques that are fault specific. In this approach, the FPGA is initially routed without any extra interconnects for reconfiguration. When faults occur, the routed nets have to be minimally perturbed to allow these interconnects to be inserted "on-the-fly" for reconfiguration. These requirements are addressed in our minimally incremental rerouting technique Conv_T-DAG, which uses a cost-directed depth-first search strategy. We prove several results that establishes the near-optimality of Conv_T-DAG in terms of track overhead. T the best of our knowledge, this is the first time that an incremental rerouting technique has been developed for FPGAs. For several benchmark circuits, the static approach to tolerating one fault per row resulted in a 43precent to 34precent track overhead. Using the dynamic reconfiguration approach and Conv_T-DAG results in an average overhead of only 16precent-an improvement of more than 50precent. Over all circuits, the reconfiguration time per fault ranges from 16.8 to 72.9 secs. Simulation of smaller fault sets of one to four faults show very small track overheads ranging from 1.75precent to 4.49precent. Conv_T-DAG can also be used for interconnect fault tolerance.