Skip to main content
SpringerLink
Log in

Embryonics: A Bio-Inspired Cellular Architecture with Fault-Tolerant Properties

  • Published:
Genetic Programming and Evolvable Machines Aims and scope Submit manuscript

Abstract

This paper details and expands the work on Embryonics, a recently proposed fault-tolerant cellular architecture with reconfiguration properties inspired by the ontogenetic development of multicellular systems. The design of a selector-based embryonic cell, its applications and the reliability models associated to different embryonic reconfiguration strategies are presented. It is noted that embryonic distributed systems possess, in the majority of cases, better reliability characteristics than equivalent centralised systems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Actel, FPGA Databook and Design Guide, Actel: Sunnyvale, CA, 1995.

    Google Scholar 

  2. T. Ae, H. Fukumoto and S. Hiwatashi, “Special-purpose brainware architecture for data processing,” in Proc. 1st Int. Conf. on Evolvable Systems: From Biology to Hardware ICES96, LNCS 1259, T. Higuchi et al. eds., Springer-Verlag: Berlin, 1997, pp. 289–304.

    Google Scholar 

  3. S. Akers, “Binary decision diagrams,” IEEE Trans Comput. vol. 27–6 pp. 509-516, June 1978.

    Google Scholar 

  4. I. Aleksander, “Iconic learning in networks of logical neurons,” in Proc. 1st Int. Conf. on Evolvable Systems: From Biology to Hardware ICES96, LNCS 1259, T. Higuchi, et al. eds., Springer-Verlag: Berlin, 1997, pp. 3–16.

    Google Scholar 

  5. S. Allworth and R. Zobel, Introduction to Real-Time Software Design, Macmillan, New York, 1990.

    Google Scholar 

  6. P. Anderson, K. Arrow and D. Pines, The Economy as an Evolving Complex System, Addison-Wesley: Reading, MA, 1988.

    Google Scholar 

  7. A. Avizienis, “Toward systematic design of fault-tolerant systems,” IEEE Comput. April pp. 51–58, 1997.

  8. K. Belkhale and P. Banerjee, “Reconfigurable strategies for VLSI processor arrays and trees using a modified Diogenes approach,” IEEE Trans. Comput. vol. 41–1 January, pp. 83-96, 1992.

    Google Scholar 

  9. F. Bennett, J. Koza, D. Andre and M. Keane, “Evolution of a 60dB op amp using genetic programming,” in Proc. 1st Int. Conf. on Evolvable Systems: From Biology to Hardware ICES96, LNCS 1259, T. Higuchi, et al. eds., Springer-Verlag: Berlin, pp. 455–469, 1997.

    Google Scholar 

  10. J. Bowles, “A survey of reliability-prediction procedures for microelectronic devices,” IEEE Trans. Reliability vol. 41–1 March, pp. 2-12, 1992.

    Google Scholar 

  11. E. Cerny, “Synthesis of minimal binary decision trees,” IEEE Trans. Comput. vol. 28–7 July, pp. 472-482, 1979.

    Google Scholar 

  12. M. Chean and J. Fortes, “A taxonomy of reconfiguration techniques for fault-tolerant processor arrays,” Computer January, pp. 55–69, 1990.

  13. C. Darwin, The Origin of Species, Collier Brooks, 1872.

  14. R. Dawkins, “The evolution of evolvability,” in Artificial Life, C. Langton ed., Addison-Wesley: Reading, MA, 1987.

    Google Scholar 

  15. S. Dutt and N. Mahapatra, “Node-covering, error-correcting codes and multiprocessors with very high average fault tolerance,” IEEE Trans. Comput. vol. 46–9 pp. 997-1014, 1997.

    Google Scholar 

  16. J. Fortes and C. Raghavendra, “Gracefully degradable processor arrays,” IEEE Trans. Comput. vol. 34–11 pp. 1033-1043, 1985.

    Google Scholar 

  17. H. de Garis, “Evolvable hardware: genetic programming of a Darwin machine,” in Artificial Neural Nets and Genetic Algorithms, R. Albrecht, C. Reeves and N. Steele eds., Springer-Verlag: Berlin, pp. 441–449, 1993.

    Google Scholar 

  18. H. de Garis, “CAM-BRAIN: the evolutionary engineering of a billion meuron artificial brain by 2001,” in Towards Evolvable Hardware: The Evolutionary Engineering Approach, LNCS 1062, E. Sanchez and M. Tomassini eds., Springer-Verlag: Berlin, pp. 76–98, 1996.

    Google Scholar 

  19. J. Gerhart and M. Kirschner, Cells, Embryos and Evolution, Blackwell Science: London, 1997.

    Google Scholar 

  20. K. Grosspietsch, “Fault tolerance in highly parallel hardware systems,” IEEE Micro. February, pp. 60–68, 1994.

  21. G. Hinton and S. Nowlan, “How learning can guide evolution,” Complex Syst. vol. 1, 1987.

  22. J. Holland, Adaptation in Natural and Artificial Systems, MIT Press: Cambridge, MA, 1992.

    Google Scholar 

  23. D. Keymulen, M. Durantez, T. Hoshino, et al., “An evolutionary robot navigation system using a gate-level evolvable hardware,” in Proc. 1st Int. Conf. on Evolvable Systems: From Biology to Hardware ICES96, LNCS 1259, T. Higuchi, et al. eds., Springer-Verlag: Berlin, pp. 195–209, 1997.

    Google Scholar 

  24. S. Kung, et al., “Fault-tolerant array processors using single-track switches,” Trans. Comput. vol. 38–4 pp. 501-513, 1989.

    Google Scholar 

  25. P. Lala, Fault Tolerance and Fault Testable Hardware Design, Prentice-Hall: Upper Saddle River, NJ: 1985.

    Google Scholar 

  26. P. Lala, Practical Digital Logic Design and Testing, Prentice-Hall: Upper Saddle River, NJ: 1996.

    Google Scholar 

  27. C. Langton, “Self-reproduction in cellular automata,” Physica 10D, pp. 135–144, 1984.

    Google Scholar 

  28. P. Lee, et al., Fault-Tolerance: Principles and Practice, Springer-Verlag: Wien-New York, 1990.

    Google Scholar 

  29. H. Liaw, et al., “On the OBDD-representation of geneal Boolean functions,” IEEE Trans. Comput. vol. 41–6 June, pp. 661-664, 1992.

    Google Scholar 

  30. D. Mange, M. Goeke, D. Madon, et al. “Embryonics: a new family of coarse-grained FPGA with self-repair and self-reproduction properties,” in Towards Evolvable Hardware: The Evolutionary Engineering Approach, LNCS 1062, E. Sanchez and M. Tomassini eds., Springer-Verlag: Berlin, pp. 197–220, 1996.

    Google Scholar 

  31. D. Mange and M. Tomassini eds., Bio-Inspired Computing Machines, Presses Polytechniques et Universitaires Romandes: Switzerland, 1998.

    Google Scholar 

  32. P. Marchal, P. Nussbaum, C. Piguet, et al., “Embryonics: The birth of synthetic life,” in Towards Evolvable Hardware: The Evolutionary Engineering Approach, LNCS 1062, E. Sanchez and M. Tomassini eds., Springer-Verlag: Berlin, pp. 166–196, 1996.

    Google Scholar 

  33. T. Morishita and I. Teramoto, “Architecture of cell array neuro-processor,” in Proc. 1st Int. Conf. on Evolvable Systems: From Biology to Hardware ICES96, LNCS 1259, T. Higuchi, et al. eds., Springer-Verlag: Berlin, pp. 277–288, 1997.

    Google Scholar 

  34. J. C. Murrell and L. M. Roberts eds.: Understanding Genetic Engineering, Ellis Horwood: Great Britain, 1989.

    Google Scholar 

  35. M. Murakawa, S. Yoshizawa and T. Higuchi, “Adaptive equalization of digital communication channels using evolvable hardware,” in Proc. 1st Int. Conf. on Evolvable Systems ICES96, LNCS 259, T. Higuchi, et al. eds., Springer-Verlag: Berlin, pp. 379–389, 1997.

    Google Scholar 

  36. T. Naito, “Genetic evolution of a logic circuit which controls an autonomous mobile robot,” in Proc. 1st Int. Conf. on Evolvable Systems: From Biology to Hardware ICES96, LNCS 1259, T. Higuchi, et al. eds., Springer-Verlag: Berlin, pp. 210–219, 1997.

    Google Scholar 

  37. R. Negrini, M. Sami and R. Stefanelli, Fault Tolerance Through Reconfiguration in VLSI and WSI Arrays, MIT Press: Cambridge, MA, 1989.

    Google Scholar 

  38. C. Nusslein-Volhard, “Gradients that organize embryo development,” Sci. Am. August, pp. 38–43, ¨ 1996.

  39. P. Nussbaum, P. Marchal and C. Piguet, “Functional organisms growing in silicon,” in Proc. 1st Int. Conf. on Evolvable Systems: From Biology to Hardware ICES96, LNCS 1259, T. Higuchi, et al. eds., Springer-Verlag: Berlin, pp. 139–151, 1997.

    Google Scholar 

  40. C. Ortega and A. Tyrrell, “Fault-tolerant systems: the way biology does it!,” Short contribution in Euromicro 97 Conference, Budapest, September, pp. 146–151, 1997.

  41. C. Ortega and A. Tyrrell, “Biologically inspired reconfigurable hardware for dependable applications,” IEE Colloq. on Hardware Design for Dependable Applications, London, Digest No: 97r335, 1997.

  42. C. Ortega and A. Tyrrell, “Design of a basic cell to construct embryonic arrays,” IEE Proc. Comput. Digital Techn. May, 1998.

  43. C. Ortega and A. Tyrrell, “Biologically inspired real-time reconfiguration technique for processor arrays,” in Proc. 5th IFAC Workshop on Algorithms and Architectures for Real-Time Control, Cancun, Mexico, Elsevier Science Ltd.: Oxford, April, 1998.

    Google Scholar 

  44. C. Ortega and A. Tyrrell, “Reliability analysis in self-repairing embryonic systems,” in Proc. 1st NASArDoD Workshop on Evolvable Hardware, A. Stoica ed., Pasadena, CA: IEEE Computer Society, pp. 120–128, July 1999.

    Google Scholar 

  45. H. Sakanashi, “Evolution of binary decision diagrams for digital circuit design using genetic programming,” in Proc. 1st Int. Conf. on Evolvable Systems: From Biology to Hardware ICES96, LNCS 1259, T. Higuchi, et al. eds., Springer-Verlag: Berlin, pp. 470–481, 1997.

    Google Scholar 

  46. E. Sanchez, D. Mange, M. Sipper, M. Tomassini, A. Perez-Uribe and A. Stauffer, “Phylogeny, ontogeny and epigenesis: three sources of biological inspiration for softening hardware,” in Proc. 1st Int. Conf. on Evolvable Systems: From Biology to Hardware ICES96, LNCS 1259, T. Higuchi, et al. eds., Springer-Verlag: Berlin, pp. 35–54, 1997.

    Google Scholar 

  47. M. Sipper, “Designing evolware by cellular programming,” in Proc. 1st Int. Conf. on Evolvable Systems: From Biology to Hardware ICES96, LNCS 1259, T. Higuchi, et al. eds., Springer-Verlag: Berlin, pp. 81–95, 1997.

    Google Scholar 

  48. C. Taylor and D. Jefferson, “Artificial life as a tool for biological inquiry,” in Artificial Life: An Overview, C. Langton ed., MIT Press: Cambridge, MA, pp. 30–45, 1995.

    Google Scholar 

  49. G. Tempesti, “A new self-reproducing cellular automaton capable of construction and computation,” in ECAL'95: 3rd Eur. Conf. Artif. Life, LNCS 929, F. Moran, et al. eds., Springer-Verlag: Berlin, 1995.

    Google Scholar 

  50. G. Tempesti, “A robust multiplexer-based FPGA inspired by biological systems,” Special Issue of JSA on Dependable Parallel Computer Systems, February, pp. 719–733, 1997.

  51. A. Thompson, “An evolved circuit, intrinsic in silicon, entwined with physics,” in Proc. 1st International Conference on Evolvable Systems: From Biology to Hardware ICES96, LNCS 1259, T. Higuchi, et al. eds., Springer-Verlag: Berlin, pp. 390–405, 1997.

    Google Scholar 

  52. J. Turino, Design to Test: A Definitive Guide for Electronic Design, Manufacture and Service, Van Nostrand Reinhold: New York, 1990.

    Google Scholar 

  53. A. M. Tyrrell, “Evaluation of fault tolerant structures on a transputer module,” in Proc. 2nd Euromicro Workshop on Parallel and Distributed Processing, Malaga, IEEE Computer Society Press, January, pp. 134–140, 1994.

    Google Scholar 

  54. A. Tyrrell, “Computer know thy self!? A biological way to look at fault-tolerance,” 2nd IEErEROMICRO Workshop on Dependable Computing Systems, Milan, September, 1999.

  55. J. Yamamoto, et al., “Autonomous robot with evolving algorithm based on biological systems,” in Proc. 1st Int. Conf. on Evolvable Systems: From Biology to Hardware ICES96, LNCS 1259, T. Higuchi, et al. eds., Springer-Verlag: Berlin, pp. 220–233, 1997.

    Google Scholar 

  56. L. Wolpert, The Triumph of the Embryo, Oxford University Press: Oxford, UK, 1991.

    Google Scholar 

  57. Xilinx, FPGA Databook, 1996.

  58. K. Misra, Reliability Analysis and Prediction, Elsevier: New York, 1992.

    Google Scholar 

  59. D. Mange, et al., “Embryonics: a new methodology for designing field-programmable gate arrays with self-repair and self-replicating properties,” IEEE Trans. VLSI Syst. vol. 6–3, September, pp. 387-399, 1998.

    Google Scholar 

  60. MIL-HDBK-217E, Reliability Prediction of Electronic Equipment, Military Handbook, United States Department of Defense, October, 1986.

  61. Virtual Computer Corporation, The Virtual Workbench Guide, version 1.01, 1999.

Download references

Author information

Authors and Affiliations

  1. Department of Electronics, University of York, York, YO10 5DD

    Cesar Ortega-Sanchez

  2. Logic Systems Laboratory, Swiss Federal Institute of Technology, CH-1015, Lausanne, Switzerland

    Daniel Mange

  3. Department of Electronics, University of York, York, YO10 5DD, UK

    Steve Smith & Andy Tyrrell

Authors
  1. Cesar Ortega-Sanchez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Daniel Mange
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Steve Smith
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Andy Tyrrell
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ortega-Sanchez, C., Mange, D., Smith, S. et al. Embryonics: A Bio-Inspired Cellular Architecture with Fault-Tolerant Properties. Genetic Programming and Evolvable Machines 1, 187–215 (2000). https://doi.org/10.1023/A:1010080629099

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1010080629099

Search

Navigation