Evolutionary functional recovery in virtual reconfigurable circuits

ABSTRACT

A virtual reconfigurable circuit (VRC) is a domain-specific reconfigurable device developed using an ordinary FPGA in order to easily implement evolvable hardware applications. While a fast partial runtime reconfiguration and application-specific programmable elements represent the main advantages of VRC, the main disadvantage of the VRC is the area consumed. This study describes experiments conducted to estimate how the use of VRC influences the dependability of FPGA-based evolvable systems. It is shown that these systems are not as sensitive to faults as their area-demanding implementations might suggest. An evolutionary algorithm is utilized to design fault tolerant circuits as well as to perform an automatic functional recovery when faults are detected in the configuration memory of the FPGA. All the experiments are performed on models of reconfigurable devices.

REFERENCES

• 1: M. Alderighi , A. Candelori , F. Casini , S. D'Angelo , M. Mancini , A. Paccagnella , S. Pastore , G. R. Sechi, Heavy Ion Effects on Configuration Logic of Virtex FPGAs, Proceedings of the 11th IEEE International On-Line Testing Symposium, p.49-53, July 06-08, 2005 [doi>10.1109/IOLTS.2005.31]
• 2: P. Bernardi , M. Sonza Reorda , L. Sterpone , M. Violante, On the Evaluation of SEU Sensitiveness in SRAM-Based FPGAs, Proceedings of the International On-Line Testing Symposium, 10th IEEE (IOLTS'04), p.115, July 12-14, 2004 [doi>10.1109/IOLTS.2004.33]
• 3: Daryl Bradley , Cesar Ortega-Sanchez , Andy Tyrrell, Embryonics + Immunotronics: A Bio-Inspired Approach to Fault Tolerance, Proceedings of the 2nd NASA/DoD workshop on Evolvable Hardware, p.215, July 13-15, 2000
• 4: Carmichael, C., Caffrey, M., and Salazar, A. 2000. Correcting single-event upsets through virtex partial configuration. Xilinx Application Note XAPP 216.
• 5: Garvie, M. and Thompson, A. 2003. Evolution of self-diagnosing hardware. In Proceedings of the 6th Conference on Evolvable Systems: From Biology to Hardware. Lecture Notes in Computer Science, vol. 2606. Springer-Verlag, Berlin, Germany, 238--248.
• 6: Glette, K. and Torresen, J. 2005. A flexible on-chip evolution system implemented on a Xilinx Virtex-ii pro device. In Proceedings of the 6th Conference on Evolvable Systems: From Biology to Hardware. Lecture Notes in Computer Science, vol. 3637. Springer-Verlag, Berlin, Germany, 66--75.
• 7: David A. Gwaltney , Kenneth Dutton, A VHDL Core for Intrinsic Evolution of Discrete Time Filters with Signal Feedback, Proceedings of the 2005 NASA/DoD Conference on Evolvable Hardware, p.43-50, June 29-July 01, 2005 [doi>10.1109/EH.2005.6]
• 8: Hartmann, M. and Haddow, P. C. 2004. Evolution of fault-tolerant and noise-robust digital designs. IEE Proceedings---Computers and Digital Techniques 151, 4, 287--294.
• 9: Tetsuya Higuchi , Tatsuya Niwa , Toshio Tanaka , Hitoshi Iba , Hugo de Garis , Tatsumi Furuya, Evolving hardware with genetic learning: a first step towards building a Darwin machine, Proceedings of the second international conference on From animals to animats 2 : simulation of adaptive behavior: simulation of adaptive behavior, p.417-424, August 1993, Honolulu, Hawai, United States
• 10: Korenek, J. and Sekanina, L. 2005. Intrinsic evolution of sorting networks: A novel complete hardware implementation for FPGAs. In Proceedings of the 6th Conference on Evolvable Systems: From Biology to Hardware. Lecture Notes in Computer Science, vol. 3637. Springer-Verlag, Berlin, Germany, 46--55.
• 11: John R. Koza , David Andre , Forrest H. Bennett , Martin A. Keane, Genetic Programming III: Darwinian Invention & Problem Solving, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 12: Lohn, J. D., Larchev, G. V., and DeMara, R. F. 2003. A genetic representation for evolutionary fault recovery in virtex FPGAs. In Proceedings of the 5th Conference on Evolvable Systems: From Biology to Hardware. Lecture Notes in Computer Science, vol. 2606. Springer-Verlag, Berlin, Germany, 47--56.
• 13: Mange, D., Sipper, M., Stauffer, A., and Tempesti, G. 2000. Towards robust integrated circuits: The embryonics approach. Proceedings of IEEE 88, 4, 516--541.
• 14: Martinek, T. and Sekanina, L. 2005. An evolvable image filter: Experimental evaluation of a complete hardware implementation in FPGA. In Proceedings of the 6th Conference on Evolvable Systems: From Biology to Hardware. Lecture Notes in Computer Science, vol. 3637. Springer-Verlag, Berlin, Germany, 76--85.
• 15: Jason Masner , John Cavalieri , James F. Frenzel , James Foster, Size versus Robustness in Evolved Sorting Networks: Is Bigger Better?, Proceedings of the 2nd NASA/DoD workshop on Evolvable Hardware, p.81, July 13-15, 2000
• 16: Julian F. Miller , Dominic Job , Vesselin K. Vassilev, Principles in the Evolutionary Design of Digital Circuits—Part I, Genetic Programming and Evolvable Machines, v.1 n.1-2, p.7-35, April 2000 [doi>10.1023/A:1010016313373]
• 17: Dhiraj K. Pradhan, Fault-tolerant computer system design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 18: qpro. 2001. Qpro Virtex 2.5v QML high-reliability FPGAs. Xilinx data sheet DS002.
• 19: Salomon, R., Widiger, H., and Tockhorn, A. 2006. Rapid evolution of time-efficient packet classifiers. In Proceedings of the 2006 IEEE Congress on Evolutionary Computation. Vancouver, Canada. IEEE CIS, 2793--2799.
• 20: Sekanina, L. 2003. Virtual reconfigurable circuits for real-world applications of evolvable hardware. In Proceedings of the 5th Conference on Evolvable Systems: From Biology to Hardware. Lecture Notes in Computer Science, vol. 2606. Springer-Verlag, Berlin, Germany, 186--197.
• 21: Lukas Sekanina, Evolvable Components: From Theory to Hardware Implementations, SpringerVerlag, 2004
• 22: Lukas Sekanina, On dependability of FPGA-based evolvable hardware systems that utilize virtual reconfigurable circuits, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128052]
• 23: Sekanina, L. and Friedl, S. 2004. An evolvable combinational unit for FPGAs. Comput. Informat. 23, 5, 461--486.
• 24: Sekanina, L., Martinek, T., and Gajda, Z. 2006. Extrinsic and intrinsic evolution of multifunctional combinational modules. In Proceedings of the IEEE Congress on Evolutionary Computation. Vancouver, Canada. IEEE CIS, 9676--9683.
• 25: Stoica, A., Keymeulen, D., Arslan, T., Duong, V., Zebulum, R. S., Ferguson, I., and Guo, X. 2004. Circuit self-recovery experiments in extreme environments. In Proceedings of the 2004 NASA/DoD Conference on Evolvable Hardware. Seattle, WA, IEEE Computer Society, 142--145.
• 26: A. Stoica , D. Keymeulen , R. Zebulum, Evolvable Hardware Solutions For Extreme Temperature Electronics, Proceedings of the The 3rd NASA/DoD Workshop on Evolvable Hardware, p.93, July 12-14, 2001
• 27: A. Stoica , D. Keymeulen , R. Zebulum , A. Thakoor , T. Daud , G. Klimeck , Y. Jin , R. Tawel , V. Duong, Evolution of Analog Circuits on Field Programmable Transistor Arrays, Proceedings of the 2nd NASA/DoD workshop on Evolvable Hardware, p.99, July 13-15, 2000
• 28: Adrian Thompson , C. J. Van Rijsbergen, Hardware Evolution: Automatic Design of Electronic Circuits in Reconfigurable Hardware by Artificial Evolution, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 29: A. M. Tyrrell , G. Hollingworth , S. L. Smith, Evolutionary Strategies And Intrinsic Fault Tolerance, Proceedings of the The 3rd NASA/DoD Workshop on Evolvable Hardware, p.98, July 12-14, 2001
• 30: Tyrrell, A. M., Krohling, R., and Zhou, Y. 2004. A new evolutionary algorithm for the promotion of evolvable hardware. IEE Proceedings: Computers and Digital Techniques 151, 4, 267--275.
• 31: Vasicek, Z. and Sekanina, L. 2007. An evolvable hardware system in Xilinx Virtex II Pro FPGA. Int. J. Innov. Comput. Appli. 1, 1, 63--73.
• 32: Michael Wirthlin , Eric Johnson , Nathan Rollins , Michael Caffrey , Paul Graham, The Reliability of FPGA Circuit Designs in the Presence of Radiation Induced Configuration Upsets, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.133, April 09-11, 2003
• 33: Ricardo S. Zebulum , Didier Keymeulen , Vu Duong , Xin Guo , M. I. Ferguson , Adrian Stoica, Experimental Results in Evolutionary Fault-Recovery for Field Programmable, Proceedings of the 2003 NASA/DoD Conference on Evolvable Hardware, p.192, July 09-11, 2003
• 34: Zebulum, R. S., Stoica, A., Keymeulen, D., Sekanina, L., Ramesham, R., and Guo, X. 2005. Evolvable hardware system at extreme low temperatures. In Proceedings of the 6th Conference on Evolvable Systems: From Biology to Hardware. Lecture Notes in Computer Science, vol. 3637. Springer-Verlag, Berlin, Germany, 37--45.
• 35: Zhang, Y., Smith, S., and Tyrrell, A. 2004. Intrinsic evolvable hardware in digital filter design. In Applications of Evolutionary Computing. Lecture Notes in Computer Science, vol. 3005. Springer-Verlag, Berlin, Germany, 389--398.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids

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

General Terms:
Design

Keywords:
Dependability, FPGA, evolutionary algorithms, evolvable hardware