Tolerating operational faults in cluster-based FPGAs

ABSTRACT

In recent years the application space of reconfigurable devices has grown to include many platforms with a strong need for fault tolerance. While these systems frequently contain hardware redundancy to allow for continued operation in the presence of operational faults, the need to recover faulty hardware and return it to full functionality quickly and efficiently is great. In addition to providing functional density, FPGAs provide a level of fault tolerance generally not found in mask-programmable devices by including the capability to reconfigure around operational faults in the field. In this paper, incremental CAD techniques are described that allow functional recovery of FPGA design configurations in the presence of single or multiple operational faults. Our preferred approach to fault recovery takes advantage of device routing hierarchy in architectural families such as Xilinx Virtex [2] and Altera Apex [3] to quickly swap unused logic and routing resources in place of faulty ones within logic clusters. These algorithms allow for straight-forward implementation within a local fault-tolerant system without the need to access a remote processing location. If initial recovery attempts through localized swapping fail, an incremental router based on the widely-used PathFinder maze routing algorithm [10] can be applied remotely in an attempt to form connections between newly-allocated logic and interconnect based on the history of the initial design route.

REFERENCES

• 1: Flez10K Data Sheet. Alters Corporation, 1998.
• 2: Virtez Data Sheet. Xilinx Corporation, 1998.
• 3: Apex Data Sheet. Alters Corporation, 1999.
• 4: J. Babb , M. Frank , V. Lee , E. Waingold , R. Barua , M. Taylor , J. Kim , S. Devabhaktuni , A. Agarwal, The RAW benchmark suite: computation structures for general purpose computing, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.134, April 16-18, 1997
• 5: K. Bernhardt. Advanced Technologies for a Command and Data Handling Subsystem in a "Better, Faster, Cheaper" Environment. In 14th Digital Avionics Systems Conference, Cambridge, Ms, Nov. 1995.
• 6: V. Betz and J. Rose. Cluster-Based Logic Blocks for FPGAs: Area-Efficiency vs. Input Sharing and Size. In Proceedings, IEEE Custom Integrated Circuits Conference, pages 551-554, 1997.
• 7: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 8: J. Cong and Y. Diag. FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Design. IEEE Transactions on Computer-Aided Design, pages 1-12, Jan. 1994.
• 9: William A. Dees, Jr. , Robert J. Smith, II, Performance of interconnection rip-up and reroute strategies, Proceedings of the 18th conference on Design automation, p.382-390, June 29-July 01, 1981, Nashville, Tennessee, United States
• 10: Carl Ebeling , Larry McMurchie , Scott A. Hauck , Steven Burns, Placement and routing tools for the Triptych FPGA, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.4, p.473-482, Dec. 1995 [doi>10.1109/92.475966]
• 11: 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
• 12: J. M. Emmert and D. Bhatia. Incremental Routing in FPGAs. In International ASIC Conference (ASIC'98), 1998.
• 13: 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]
• 14: I. G. Harris and R. Tessier. Testing Approaches for Cluster-based FPGAs. In submitted to 11th Design Automation Conference, June 2000.
• 15: Scott Hauck , Stephen Knol, Data security for Web-based CAD, Proceedings of the 35th annual conference on Design automation, p.788-793, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277242]
• 16: Dwight D. Hill, A CAD system for the design of field programmable gate arrays, Proceedings of the 28th conference on ACM/IEEE design automation, p.187-192, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127662]
• 17: N. Howard, A. TyrreU, and N. Allinson. The Yield Enhancement of Field-Programmable Gate Arrays. IEEE Transactions on VLSI Systems, pages 115-123, Mar. 1994.
• 18: Michael Hutton , Jonathan Rose , Derek Corneil, Generation of synthetic sequential benchmark circuits, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.149-155, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258333]
• 19: R. Katz, K. LaBel, J. J. Wang, B. Cronquist, R. Koga, S. Penzin, and G. Swift. Radiation Effects on Current Field ProgrammableTechnologies. IEEE Transactions on Nuclear Science, 44(6):1945-1956, Dec. 1997.
• 20: 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
• 21: 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]
• 22: Daniel P. Siewiorek , Robert S. Swarz, Reliable computer systems (2nd ed.): design and evaluation, Digital Press, Newton, MA, 1992
• 23: 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]
• 24: R. Tessier. Negotiated A* Routing for FPGAs. In Proceedings: Fifth Canadian Workshop on Field- Programmable Devices, Montreal, Quebec, June 1998.
• 25: S. Webber and J. Beirne. The Stratus Architecture. In Proceedings: 21st International Symposium on Fault- Tolerant Computing, 1991.
• 26: S. Yang. Logic Synthesis and Optimization Benchmarks. Microelectronics Centre of North Carolina Tech. Report, 1991.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

General Terms:
Algorithms, Design, Performance