Fault tolerant placement and defect reconfiguration for nano-FPGAs

ABSTRACT

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 circuit's 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.

REFERENCES

• 1: Jason A. Cheatham , John M. Emmert , Stan Baumgart, A survey of fault tolerant methodologies for FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.2, p.501-533, April 2006 [doi>10.1145/1142155.1142167]
• 2: F. Hatori, T. Sakurai, K. Sawada, M. Takahashi, M. Ichida, M. Uchida, I. Yoshii, Y. Kawahara, T. Hibi, Y. Saeki, H. Muroga, A. Tanaka, K. Kanzaki, "Introducing redundancy in field programmable gate arrays", Proceedings of the IEEE Custom Integrated Circuits Conference, Volume 7, Number 1, pp. 1--4.
• 3: Fran Hancheck , Shantanu Dutt, Design Methodologies for Tolerating Cell and Interconnect Faults in FPGAs, Proceedings of the 1996 International Conference on Computer Design, VLSI in Computers and Processors, p.326-331, October 07-09, 1996
• 4: Fran Hanchek , Shantanu Dutt, Node-Covering Based Defect and Fault Tolerance Methods for Increased Yield in FPGAs, Proceedings of the 9th International Conference on VLSI Design: VLSI in Mobile Communication, p.225, January 03-06, 1996
• 5: N. J. Howard, A. M. Tyrell, N. M. Allison, "The yield enhancement of field programmable gate arrays", IEEE Trans. VLSI Syst. 2, Volume 1, pp. 115--123, Mar 1994.
• 6: Vijay Lakamraju , Russell Tessier, Tolerating operational faults in cluster-based FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.187-194, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329205]
• 7: Y. Chen et al., "Nanoscale Molecular-Switch Crossbar Circuits,", Nanotechnology, vol.14, no. 4, pp. 462--468, 2003.
• 8: Y. Huang et al., "Directed Assembly of One-Dimensional Nanostructures Into Functional Networks,", Science, vol. 291, no. 5504, pp. 630--633, 2001.
• 9: M. Mishra, S. C. Goldstein, "Defect Tolerance at the End of the Roadmap," Int'l Test Conference Proceedings, 2003.
• 10: S. Durand, C. Piguet, "FPGA with selfrepair capabilities", Proceedings of the ACM International Workshop on FPGAs, 1994
• 11: Anmol Mathur , C. L. Liu, Timing Driven Placement Reconfiguration for Fault Tolerance and Yield Enhancement in FPGAs, Proceedings of the 1996 European conference on Design and Test, p.165, March 11-14, 1996
• 12: J. Emmert, D. Bhatia, "Incremental routing in FPGAs", Proceedings of the 11th Annual IEEE International ASIC Conference, 1998
• 13: Gang Chen , Jason Cong, Simultaneous timing-driven placement and duplication, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046200]
• 14: Gang Chen , Jason Cong, Simultaneous timing-driven placement and duplication, Proceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays, February 20-22, 2005, Monterey, California, USA [doi>10.1145/1046192.1046200]
• 15: Alexander Marquardt , Vaughn Betz , Jonathan Rose, Timing-driven placement for FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.203-213, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329208]
• 16: Alexander (Sandy) Marquardt , Vaughn Betz , Jonathan Rose, Using cluster-based logic blocks and timing-driven packing to improve FPGA speed and density, Proceedings of the 1999 ACM/SIGDA seventh international symposium on Field programmable gate arrays, p.37-46, February 21-23, 1999, Monterey, California, United States [doi>10.1145/296399.296426]
• 17: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 18: Shyue-Kung Lu, Fu-Min Yesh, Jen-Shing Shih, "Fault Detection and Fault Diagnosis Techniques for LookupTable FPGAs", VLSI Design, 2002
• 19: Chi-Feng Wu and Cheng-Wen Wu, "Fault Detection and Location of Dynamic Reconfigurable FPGAs", International Symposium on VLSI Technology, Systems, and Applications, 1999.
• 20: E. Bareisa, V. Jusas, K. Motiejunas, R. Seinauskas, "Testing of FPGA Logic Cells", Elektronika IR Elektrotechnica, 2004