This paper examines fault tolerant adder designs implemented on FPGAs which are inspired by the methods of modular redundancy, roving, and gradual degradation. A parallel-prefix adder based upon the Kogge-Stone configuration is compared with the simple ripple carry adder (RCA) design. The Kogge-Stone design utilizes a sparse carry tree complemented by several smaller RCAs. Additional RCAs are inserted into the design to allow fault tolerance to be achieved using the established methods of roving and gradual degradation. A triple modular redundant ripple carry adder (TMR-RCA) is used as a point of reference. Simulation and experimental measurements on a Xilinx Spartan 3E FPGA platform are carried out. The TMR-RCA is found to have the best delay performance and most efficient resource utilization for an FPGA fault-tolerant implementation due to the simplicity of the approach and the use of the fast-carry chain. However, the superior performance of the carry-tree adder over an RCA in a VLSI implementation makes this proposed approach attractive for ASIC designs. 1. Introduction Field programmable gate arrays (FPGAs) are growing in popularity with designers as their ability to be reconfigured from a desktop computer allows ease of prototyping, rapid time to market, and minimal nonrecurring engineering (NRE) cost compared to custom integrated circuit (IC) designs. As FPGAs can be configured precisely for a given function, they often offer superior performance in terms of speed and power compared with using a general purpose microprocessor-based design. Hence, FPGA-based designs can form an integral part of a high-performance computing platform. FPGA manufacturers are using state-of-the-art IC processes in order to improve performance. For example, the Virtex 7 FPGA from Xilinx is implemented in a process with 28？nm feature sizes. Currently, leading edge IC designs are at the 22？nm technology node and by next year will be at the 14？nm node. With these nanometric feature sizes, ICs become more susceptible to faults from external sources like electromagnetic interference and cosmic radiation, leading to single-event upsets (SEUs) and multibit upsets (MBUs). As such, fault tolerant design is important for mission-critical applications, such as avionic and medical electronics, and for the improved reliability for space-based systems operating in harsh and remote environments. A fault tolerant system has two main features: the ability to detect faults, and the means to recover from the fault. An ideal fault tolerant system will perform these functions with a
References
[1]
Spartan 3 Generation User Guide, http://www.xilinx.com/support/documentation/user_guides/ug331.pdf.
[2]
D. H. K. Hoe, C. Martinez, and S. J. Vundavalli, “Design and characterization of parallel prefix adders using FPGAs,” in Proceedings of the 43rd IEEE Southeastern Symposium on System Theory (SSST '11), pp. 168–172, Auburn, Ala, USA, March 2011.
[3]
C. D. Martinez, L. P. D. Bollepalli, and D. H. K. Hoe, “A fault tolerant parallel-prefix adder for VLSI and FPGA design,” in Proceedings of the 44th IEEE Southeastern Symposium on System Theory (SSST '12), pp. 121–125, Jacksonville, Fla, USA, March 2012.
[4]
S. Ghosh, P. Ndai, and K. Roy, “A novel low overhead fault tolerant Kogge-Stone adder using adaptive clocking,” in Proceedings of the Design, Automation and Test in Europe (DATE '08), pp. 366–371, Munich, Germany, March 2008.
[5]
P. M. Kogge and H. S. Stone, “A parallel algorithm for the efficient solution of a general class of recurrence equations,” IEEE Transactions on Computers, vol. 22, no. 8, pp. 786–793, 1973.
[6]
Xilinx Inc, http://www.xilinx.com.
[7]
Altera Corporation, http://www.altera.com/.
[8]
R. P. Brent and H. T. Kung, “A regular layout for parallel adders,” IEEE Transactions on Computers, vol. 31, no. 3, pp. 260–264, 1982.
[9]
N. H. E. Weste and D. M. Harris, CMOS VLSI Design, Pearson, Addison-Wesley, 4th edition, 2011.
[10]
D. Harris, “A taxonomy of parallel prefix networks,” in Proceedings of the 37th Asilomar Conference on Signals, Systems and Computers, pp. 2213–2217, Pacific Grove, Calif, USA, November 2003.
[11]
E. Stott, P. Sedcole, and P. Y. K. Cheung, “Fault tolerant methods for reliability in FPGAs,” in Proceedings of the International Conference on Field Programmable Logic and Applications, pp. 415–420, Heidelberg, Germany, September 2008.
[12]
M. Abramovici and C. Stroud, “BIST-based detection and diagnosis of multiple faults in FPGAs,” in Proceedings of the International Test Conference, pp. 785–794, Atlantic City, NJ, USA, October 2000.
[13]
L. Zhao, D. M. H. Walker, and F. Lombardi, “ testing of bridging faults in logic resources of reconfigurable field programmable gate arrays,” IEEE Transactions on Computers, vol. 47, no. 10, pp. 1136–1152, 1998.
L. Sterpone and M. Violante, “Analysis of the robustness of the TMR architecture in SRAM-based FPGAs,” IEEE Transactions on Nuclear Science, vol. 52, no. 5, pp. 1545–1549, 2005.
[16]
F. L. Kastensmidt, L. Sterpone, L. Carro, and M. S. Reorda, “On the optimal design of triple modular redundancy logic for SRAM-based FPGAs,” in Proceedings of the Design, Automation and Test in Europe (DATE '05), pp. 1290–1295, Munich, Germany, March 2005.
[17]
M. G. Gericota, L. F. Lemos, G. R. Alves, and J. M. Ferreira, “On-line self-healing of circuits implemented on reconfigurable FPGAs,” in Proceedings of the 13th IEEE International On-Line Testing Symposium (IOLTS '07), pp. 217–222, Crete, Greece, July 2007.
[18]
M. Abramovici, J. M. Emmert, and C. E. Stroud, “Roving STARs: an integrated approach to on-line testing, diagnosis, and fault tolerance for FPGAs in adaptive computing systems,” in Proceedings of the 3rd NASA/DoD Workshop on Evolvable Hardware, pp. 73–92, Long Beach, Calif, USA, July 2001.
[19]
J. M. Emmert, C. E. Stroud, and M. Abramovici, “Online fault tolerance for FPGA logic blocks,” IEEE Transactions on Very Large Scale Integration Systems, vol. 15, no. 2, pp. 216–226, 2007.
[20]
F. Hatori, T. Sakurai, K. Nogami et al., “Introducing redundancy in field programmable gate arrays,” in Proceedings of the IEEE Custom Integrated Circuits Conference (CICC '93), pp. 7.1.1–7.1.4, San Diego, Calif, USA, May 1993.
[21]
V. Lakamraju and R. Tessier, “Tolerating operational faults in cluster-based FPGAs,” in Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays (FPGA '00), pp. 187–194, Monterey, Calif, USA, February 2000.
[22]
J. M. Emmert and D. Bhatia, “Partial reconfiguration of FPGA mapped designs with applications for fault tolerance and yield enhancement,” in Proceedings of the 7th International Workshop on Field Programmable Logic and Applications, vol. 1304, pp. 141–150, Lecture Notes in Computer Science, London, UK, September 1997.
[23]
Y. Nakamura and K. Hiraki, “Highly fault-tolerant FPGA processor by degrading strategy,” in Proceedings of the 2002 Pacific Rim International Symposium on Dependable Computing, pp. 75–78, Tsukuba, Japan, December 2002.
[24]
J. A. Cheatham, J. M. Emmert, and S. Baumgart, “A survey of fault tolerant methodologies for FPGAs,” ACM Transactions on Design Automation of Electronic Systems, vol. 11, no. 2, pp. 501–533, 2006.
