Fault tolerant placement and defect reconfiguration for nano-FPGAs

When manufacturing nano-devices, defects are a certainty and reliability becomes a critical issue. Until now, the most pervasive methods used to address reliability, involve injecting spare resources. However, these methods use predetermined spare placement that is not optimized for each netlist. This is the first work (to the best of our knowledge) that addresses the problem of fault tolerance for nano-FPGAs at the placement stage; fault tolerant placements are generated that are amenable to fast defect reconfiguration through replacement of defective logic elements with spares. We propose a simulated-annealing based placement algorithm that produces placements with the objective of maximizing the chances of successful recovery from faults in logic elements within the circuitpsilas timing constraints. In addition, our study of the fault reconfiguration problem shows it is NP-Complete, and we propose a fast scheme for achieving a good reconfiguration solution for a random or clustered fault map. Experimental results show that these techniques can increase the probability of successful fault reconfiguration by 55% (compared to a uniform spare distribution scheme), without significantly degrading the circuit performance.