A survey of fault tolerant methodologies for FPGAs

ABSTRACT

A wide range of fault tolerance methods for FPGAs have been proposed. Approaches range from simple architectural redundancy to fully on-line adaptive implementations. The applications of these methods also differ; some are used only for manufacturing yield enhancement, while others can be used in-system. This survey attempts to provide an overview of the current state of the art for fault tolerance in FPGAs. It is assumed that faults have been previously detected and diagnosed; the methods presented are targeted towards tolerating the faults. A detailed description of each method is presented. Where applicable, the methods are compared using common metrics. Results are summarized to present a succinct, comprehensive comparison of the different approaches.

REFERENCES

• 1: Bruno Codenotti , Roberto Tamassia, A Network Flow Approach to the Reconfiguration of VLSI Arrays, IEEE Transactions on Computers, v.40 n.1, p.118-121, January 1991 [doi>10.1109/12.67329]
• 2: Doumar, A. and Ito, H. 2000. Defect and fault tolerance SRAM-based FPGAs by shifting the configuration data. IEICE Trans. Inf. Syst. 1104--1115.
• 3: Durand, S. and Piguet, C. 1994. FPGA with selfrepair capabilities. In Proceedings of the ACM International Workshop on Field Programmable Gate Arrays. ACM, New York, 1--6.
• 4: Shantanu Dutt , Vimalvel Shanmugavel , Steve Trimberger, Efficient incremental rerouting for fault reconfiguration in field programmable gate arrays, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.173-177, November 07-11, 1999, San Jose, California, United States
• 5: John M. Emmert , Dinesh Bhatia, Partial reconfiguration of FPGA mapped designs with applications to fault tolerance and yield enhancement, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.141-150, September 01-03, 1997
• 6: Emmert, J. and Bhatia, D. 1998. Incremental routing in FPGAs. In Proceedings of the 11th Annual IEEE International ASIC Conference. IEEE Computer Society Press, Los Alamitos, CA, 217--221.
• 7: John M. Emmert , Stanley Baumgart , Pankaj Kataria , Andrew M. Taylor , Charles E. Stroud , Miron Abramovici, On-Line Fault Tolerance for FPGA Interconnect with Roving STARs, Proceedings of the 16th IEEE International Symposium on Defect and Fault-Tolerance in VLSI Systems, p.445-454, October 24-26, 2001
• 8: Donald Fussell , Peter Varman, Fault-tolerant wafer-scale architectures for VLSI, Proceedings of the 9th annual symposium on Computer Architecture, p.190-198, April 26-29, 1982, Austin, Texas, United States
• 9: Jonathan W. Greene , Abbas El Gamal, Configuration of VLSI Arrays in the Presence of Defects, Journal of the ACM (JACM), v.31 n.4, p.694-717, Oct. 1984 [doi>10.1145/1634.2377]
• 10: 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
• 11: 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
• 12: Fran Hanchek , Shantanu Dutt, Methodologies for Tolerating Cell and Interconnect Faults in FPGAs, IEEE Transactions on Computers, v.47 n.1, p.15-33, January 1998 [doi>10.1109/12.656073]
• 13: Hatori, F., Sakurai, T., Sawada, K., Takahashi, M., Ichida, M., Uchida, M., Yoshii, I., Kawahara, Y., Hibi, T., Saeki, Y., Muroga, H., Tanaka, A., and Kanzaki, K. 1993. Introducing redundancy in field programmable gate arrays. In Proceedings of the IEEE Custom Integrated Circuits Conference. IEEE Computer Society Press, Los Alamitos, CA, 7.1.1--7.1.4.
• 14: Howard, N. J., Tyrell, A. M., and Allinson, N. M. 1994. The yield enhancement of field programmable gate arrays. IEEE Trans. VLSI Syst. 2, 1 (Mar.), 115--123.
• 15: Kelly, J. L. and Ivey, P. A. 1994. A novel approach to defect tolerant design for SRAM based FPGAs. In Proceedings of the ACM International Workshop on Field Programmable Gate Arrays. ACM, New York, 1--11.
• 16: Kumar, V., Dahbura, A., Fischer, F., and Juola, P. 1989. An approach for the yield enhancement of programmable gate arrays. In Proceedings of the IEEE/ACM International Conference on Computer Aided Design. ACM, New York, 226--229.
• 17: Sy-Yen Kuo , W. Kent Fuchs, Spare allocation and reconfiguration in large area VLSI, Proceedings of the 25th ACM/IEEE conference on Design automation, p.609-612, June 12-15, 1988, Atlantic City, New Jersey, United States
• 18: John Lach , William H. Mangione-Smith , Miodrag Potkonjak, Efficiently supporting fault-tolerance in FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.105-115, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275125]
• 19: John Lach , William H. Mangione-Smith , Miodrag Potkonjak, Algorithms for Efficient Runtime Fault Recovery on Diverse FPGA Architectures, Proceedings of the 14th International Symposium on Defect and Fault-Tolerance in VLSI Systems, p.386-394, November 01-03, 1999
• 20: 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]
• 21: Lawler, E. L. 1976. Combinatorial Optimization: Networks and Matroids. Rinehard and Winston.
• 22: Nihar R. Mahapatra , Shantanu Dutt, Efficient Network-Flow Based Techniques for Dynamic Fault Reconfiguration in FPGAs, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.122, June 15-18, 1999
• 23: Manning, F. B. 1977. An approach to highly integrated, computer-maintained cellular arrays. IEEE Trans. Comput. 26, 6, 536--552.
• 24: Narasimhan, J., Nakajima, K., Rim, C. S., and Dahbura, A. T. 1994. Yield enhancement of programmable ASIC arrays by reconfiguration of circuit placements. IEEE Trans. Comput. Aid. Des. Integ. Circ. Syst. 13, 8 (Aug.), 976--986.
• 25: Nathan R. Shnidman , William H. Mangione-Smith , Miodrag Potkonjak, On-line fault detection for bus-based field programmable gate arrays, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.6 n.4, p.656-666, Dec. 1998 [doi>10.1109/92.736139]
• 26: Amit Singh , Malgorzata Marek-Sadowska, FPGA interconnect planning, Proceedings of the 2002 international workshop on System-level interconnect prediction, April 06-07, 2002, San Diego, California, USA [doi>10.1145/505348.505353]
• 27: Jordan S. Swartz , Vaughn Betz , Jonathan Rose, A fast routability-driven router for FPGAs, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.140-149, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275134]
• 28: Tessier, R. 1998. Negotiated A* routing for FPGAs. In Proceedings of the 5th Canadian Workshop on Field Programmable Devices.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

General Terms:
Measurement, Performance, Reliability

Keywords:
FPGA, fault tolerance, self test