Prologue

News

Introduction: Evolvable Hardware

What does it mean Evolvable Hardware?

• Evolvable hardware (EHW) may be considered as a technology, which enables to establish an evolvable system with ability of hardware on-line adaptation to dynamically changing environments [1]. A circuit connection (configuration bits are encoded to a chromosome) of the reconfigurable circuit (RC) is autonomously synthesized by evolutionary algorithm (e.g. by genetic algorithm - GA).
• Performance of evolvable hardware can be seen in two factors:
  • Fast circuit reconfiguration and hardware implementation of genetic algorithm should ensure fast evolutionary process. Thus real-time adaptation could be achieved.
  • The evolutionary process is able to go far beyond traditional circuit design and thus unique non-conventional architecture could be found for each requirement.
• Nature of genetic algorithm does not guarantee that 100% quality of the resulting connection will be achieved in all cases. This annoyance has to be considered during system design and potentially influences the class of evolvable hardware based applications (EHBA).
• The term of extrinsic evolvable hardware (or off-line) is used in the case of SW circuit simulation (only the best connection is downloaded into a chip) and this approach should be only referred as the evolutionary circuit design [2]. It is quite opposite to intrinsic evolvable hardware (or on-line) where all chromosomes are evaluated in the physical chip. Software implementation, which often leads to slow execution, is not usually acceptable in real-world applications. It seems that only intrinsic hardware evolution is suitable for industrial (real- time) systems.
• Circuit connection is usually defined using a collection of circuit elements and the structure of their mutual interconnections. The elements can operate at different levels of abstraction, e.g. the gate or functional levels [3] are the most popular. Other computational models (e.g. cellular automata [6] or artificial neural networks [9] ) are also used to be the subject of evolution.
• In the case of constrained evolution, some strong rules (e.g. for element interconnections) must be kept and the search space is reduced for evolution. On the other hand, unconstrained evolution directly operates with common configuration bit-stream (everything can be connected together) and thus "exotic" connection can occur [4]. It is necessary to consider the physical properties of a given chip.
• Evolvable hardware can be used for a construction of digital circuit using evolution without knowledge of its internal structure. In the case of single fitness function, evolutionary process can be stopped when a correct solution appears. Otherwise, in case of open-ended evolution [2], dynamically changing environment is reflected by dynamically changing fitness function. Then evolution may not be ever stopped since known high quality solution could be unsatisfactory in a new environment. We can speak about double evolution - the circuit and the environment evolve together.
• Analog as well as digital circuits have been sucessfully evolved. Here, we deal with digital evolvable hardware only.
• According to some papers, e.g. [5], circuit connection is not the subject of evolution. Only the circuit behaviour is (and can be) the subject of evolution. Therefore, we speak about black-box nature of evolvable hardware.

Important succesfull results

Classification in Evolvable Hardware

Why does it not work sometime?

• Scalability - the limitation in the chromosome string length. A long string is required for representing a complex system. However, a larger number of generations are required by genetic algorithms as the string increases. This often makes the search space too large and explains why only small circuits have been evolvable so far. For details, see Jim Torresen's pages.
  Other research: Vassilev's and Millers's Scalability Problems of Digital Circuit Evolution - Evolvability and Efficient Designs [20]
• Representation - what should be encoded in the chromosome, see Representations are more important than algorithms [18]
• Generality - will be the evolved connection general enough? What about its sensitivity, e.g. to temperature? For details, see Thompson's results.
• Very time consuming fitness calculation - e.g. combinational explosion during evaluation of the combinational circuits. For details, see Aspects of Digital Evolution: Geometry and Learning by J. Miller and P. Thompson.
• No methodology - how shall we succesfully design and implement evolvable system?
• Applications - which applications are suitable for evolvable hardware?

Computational platforms

• FPGA (Field Programmable Gate Arrays) - XC6200, Virtex - the most popular
• Special chips - visit ETL in Japan
• Special architectures - e.g. Cell matrix
• Unconventional approaches - implementation of the quite new reconfigurable device using common FPGAs (e.g. the XC4000 family or Virtex) [iv]
• Virtual Computer Corporation
• VHDL or SystemC are useful for design in all cases!

Evolutionary Algorithms

• Genetic Algorithms by M. Sipper, [7]
• Illinois Genetic Algorithms Laboratory
• Genetic Algorithms by M. Obitko
• The Hitch-Hiker's Guide to Evolutionary Computation
• Prof. Eiben's pages
• www.genetic-programming.org
• Cartesian Genetic Programming [8]
• other as Evolutionary Programming, Evolutionary Strategies, etc. [7]

Conferences/Journals/...

• See EvoWeb for actual information
• NASA/DoD Workshop on Evolvable Hardware: EH-1999, EH-2000, EH-2001, EH-2002 EH-2003
• Evolvable Systems: From Biology to Hardware: ICES 1996, ICES 1998, ICES 2000, ICES 2001, ICES 2003
• Towards Evolvable Hardware: An international workshop (1995),
• International Workshop in Processing Cells and Tissues 2003
• Other Conferences: FPL 2000, GECCO 2002, EuroGP/Workshops 2002, etc.
• Journals: Genetic Programming and Evolvable Machines (Kluwer), Evolutionary Computation (MIT), IEEE Transaction on Evolutionary Computation, etc.

Towards Evolvable Components

Phases of the design process

• Phase 1
  • The preliminary decision, that evolvable hardware is the best technology to be used for the given application. Note that evolution does not guarantee that the ideal solution will be found. Any resulting connection must not cause the application to crash, only a temporal performance degradation is acceptable in some applications.
  • The selection of the optimal parameters. This is closely related problem to the previous step. Optimal genetic operators, GA parameters (e.g. size of population), model of environment, fitness function, and connection encoding into bit string are the most important problems solved at the side of evolution. Optimal structure (e.g. gate or function level?) and interconnection (e.g. full or restricted?) of the elementary blocks are looked for from the hardware point of view. Simulations may be used to detect system limits. When the promising results are obtained, it is meaningful to go on in design process.
• Phase 2
  • Choosing the target hardware platform.
  • Design and simulation of the final hardware implementation.
  • Hardware implementation.

Which tasks are suitable for evolvable hardware?

Uniform design approach

EHW = RC + GA is revised to EHW = RC + genetic operations

Evolvable Component vs. Common Component

Applications of evolvable components

• Evolvabe component for image compression: [x, xi,i,iii]
  In my MSc-thesis [xi] "Modelling of evolvable hardware", I have implemented and simulated this application. The figure shows our design system during compression.
  
  
  You can download this application here ehwcmpr.zip [1.4MB]
  System requirements: MS Windows 95/98/NT, 486DX/100, 32MB RAM - at least
  
  
• Evolvable component for image operator design: [xiv,xvi]
  successfull evolution of image filters (for Gaussian, random, block and shot noise), edge detectors and illumination enhancement operator.

Summary: Advantages of Evolvable components

• reusability at the application level - the same EC may be used in different applications (business model for Evolvable Hardware?)
• reusability at the component level - a quite new EC may be derived from a generic EC
• open-ended evolution is supported in principle (fitness calculation is outside the EC)
• user friendly design - the user only defines application specific features
• uniform interface of the EC - all the evolvable subsystems have the same (or very similar) interface
• formal approach can be easily applied because of system decomposition
• ...

Our publications are related to these topics:

• Modelling and simulation of evolvable hardware [iii, vii, xi]
• Evolvable components [i, viii]
• Formal description of the evolvable systems [xv, xvii]
• Image compression using EHW [x, xi]
• Evolutionary image operator design [xiv, xvi, xix]
• Design of the special reconfigurable circuits using common FPGA [iv, vi]
• Cellular systems/fault tolerance [ii, v, xii, xxi]
• Popular explanation of EHW [ix, xiii]

People who are also related to the field of evolvable systems at Faculty of Information Technology

Where you can find us:

Citations:

Students' projects

Our publications

1. Sekanina, L., Sllame, A.: Toward Uniform Approach to Design of Evolvable Hardware Based Systems. In: Field-Programmable Logic and Applications - FPL'2000, (C) Springer-Verlag Berlin Heidelberg, Villach, Austria, 2000, pp. 814-817. [ps.gz]
2. Sekanina, L., Drábek, V.: Relation Between Fault Tolerance and Reconfiguration in Cellular Systems. In: 6th IEEE Int. On-Line Testing Workshop, Palma de Mallorca, Spain, 2000, pp. 25-30. [ps.gz]
3. Sllame, A., Sekanina, L.: Simulation and Modeling of Evolvable Hardware Based Systems. In: Proc. of MS2000 International Conference on Modeling and Simulation, Las Palmas, Spain, 2000, pp. 485-492. [pdf]
4. Sekanina, L., Ruzicka, R.: Design of the Special Fast Reconfigurable Chip Using Common FPGA. In: Design and Diagnostic of Electronic Circuits and Systems - IEEE DDECS'2000, Smolenice, Slovakia, 2000, pp. 161-168. [pdf]
5. Sekanina, L., Drábek, V.: Fault Tolerance and Reconfiguration in Cellular Systems. In: Design and Diagnostic of Electronic Circuits and Systems - IEEE DDECS'2000, Smolenice, Slovakia, 2000, pp. 134-137.
6. Sekanina, L., Drábek, V.: The Concept of Pseudo Evolvable Hardware. In: IFAC Workshop on Programmable Devices and Systems - PDS 2000, Elsevier Science Ltd. Oxford, UK, Ostrava, Czech Rep., 2000, pp. -. [ps.gz]
7. Ruzicka, R., Sekanina, L.: The Role of Simulation During Design of Evolvable Systems. In: Proc. of 22-nd International Colloquium Advanced Simulation of Systems - ASIS 2000, MARQ, Ostrava, 2000, pp. 85-90.
8. Sekanina, L.: Components and Communications in Evolvable System. In: Sborník prací studentu a doktorandu, Akademické nakladatelství CERM, Brno, Czech Rep., 2000, pp. 231-233.
9. Sekanina, L., Drábek, V.: Evolvable hardware - evoluce na cipu. In: Elektrorevue, Vol. 1, No. 5/99, FEI VUT Brno, Brno, 1999. [html]
10. Sekanina, L.: Evolvable Hardware as Non-Linear Predictor for Image Compression. In: Proc. of the 2nd Prediction Conference Nostradamus'99, Knihovna F.Bartose, Zlín, Czech Rep., 1999, pp. 87-92. [ps.gz] [html]
    
    2001
11. Sekanina, L., Dvorak, V.: A Totally Distributed Genetic Algorithm: From a Cellular System to the Mesh of Processors. In: The 15th European Simulation Multiconference ESM2001, The SCS Publ. House, Delft, The Netherlands, Prague, 2001, pp. 539-543 [pdf]
    
    2002
12. Sekanina, L., Drabek, V.: Soft-hardware. In: Vesmir 81(7) - Czech scientific journal, pp. 393-395 [html]
13. Sekanina, L.: Image Filter Design with Evolvable Hardware. In: Applications of Evolutionary Computing, The 4th European Workshop on Evolutionary Computation in Image Analysis and Signa Processing EvoIASP2002, Kinsale, Ireland, LNCS 2279, (C) Springer Verlag, 2002, pp. 255-266 [ps]
14. Sekanina, L.: Evolvable Computational Machines: Formal Approach. In: 2nd Euro-International Symposium on Computational Intelligence, Kosice, Slovakia, IOS Press, 2002, pp. 166-172 [ps]
15. Sekanina, L., Drabek, V.: Automatic Design of Image Operators Using Evolvable Hardware. In: 5th IEEE Design and Diagnostics of Electronic Circuits and Systems Workshop 2002 Brno, Czech Rep., 2002, pp. 132-139 [pdf]
16. Sekanina, L.: Automata of Evolvable Computational Machines In: Student Electrical Engineering, Information and Communication Technologies 2002 at Brno University of Technology, Brno, Czech Rep., 2002, pp. 491-495 [pdf]
17. Sekanina, L., Torresen, J.: Detection of Norwegian Speed Limit Signs In: The 16th European Simulation Multiconference ESM2002, DARMSTADT, Germany, 2002, pp. 337-340
18. Sekanina, L.: Evolution of digital circuits operating as image filters in dynamically changing environment In: 8th International Conference on Soft Computing Mendel, Brno, Czech Rep., 2002, pp. 33-38 [pdf]
19. Sllame, A., Sekanina, L.: An Evolutionary-Based Algorithm to the Module Selection Process in High-Level Synthesis In: 8th International Conference on Soft Computing Mendel, Brno, Czech Rep., 2002, pp. 87-92 [pdf]
20. Sekanina, L., Drabek, V.: A Survey of Bioinspired Methods for Design of Fault Tolerant Reconfigurable Architectures In: 8th Baltic Electronic Conference BEC'02, Tallinn, Estonia., pp. 355-358
21. Sllame, A., Sekanina, L.: An Evolutionary-Based Algorithm to the Module Selection Problem with Resource Sharing in High-Level Synthesis In: PPSN-2002 Workshop on Real World Optimisation Using Evolutionary Computing, Granada, Spain, 2002.
22. Sekanina, L.: Nanostructures and Bio-Inspired Computer Engineering In: Nano 2002, Brno, Czech Rep.
    
    2003
23. Sekanina, L.: Virtual Reconfigurable Circuits for Real-World Applications of Evolvable Hardware In: The 5th International Conference on Evolvable Systems: From Biology to Hardware ICES 2003, Trondheim, Norway, 2003, LNCS 2606, (C) Springer-Verlag, pp. 186-197 [zip]
24. Sekanina, L.: From Implementations to a General Concept of Evolvable Machines In: The 6th European Conference on Genetic Programming, EuroGP 2003, Colchester, UK, LNCS 2610 (C) Springer-Verlag [zip]
25. Sekanina, L., Ruzicka, R.: Easily Testable Image Operators: The Class of Circuits Where Evolution Beats Engineers In: The 2003 NASA/DoD Conference on Evolvable Hardware, Chicago, IL, IEEE Computer Press, pp. xxx
26. Sekanina, L.: Towards Evolvable IP Cores for FPGAs In: The 2003 NASA/DoD Conference on Evolvable Hardware, Chicago, IL, IEEE Computer Press, pp. xxx
    
    Tutorials
27. Drabek, V., Sekanina, L.: Basic Principles of Bio-Inspired Approaches to Fault Tolerance: Tutorial. In: Design for Test of Systems on Chip: Digital Test (In: 8th Baltic Electronic Conference BEC'02, Tallinn, Estonia)
    
    Thesis
28. Sekanina, L.: Component Approach to Evolvable Systems, PhD thesis, Faculty of Information Technology, Brno University of Technology, 2002, 132 pp.
29. Sekanina, L.: Modelling of evolvable hardware. MSc-thesis, Brno University of Technology, 62 pp. [abstract]

Acknowledgments

References

1. Sanchez, E., Tomassini, M. (Eds.): Towards Evolvable Hardware: The Evolutionary Engineering Approach. Springer-Verlag, Berlin, 1996.
2. Sanchez, E. et al.: Phylogeny, Ontogeny, and Epigenesis: Three Sources of Biological Inspiration for Softering Hardware. In: Higuchi T. et al. (eds.), Evolvable Systems: From Biology to Hardware, Berlin, Springer-Verlag 1997, pp. 35-54.
3. Murakawa, M. et al.: Hardware Evolution at Function Level. In: Parallel Problem Solving from Nature - PPSN IV, Springer-Verlag, 1996, pp. 62-71.
4. Thompson, A., Layzell, P.: Analysis of Unconventional Evolved Electronics. Communication of the ACM. April 1999/Vol. 42, No.4, pp. 71-79.
5. Yao, X., Higuchi, T.: Promises and Chalenges of Evolvable Hardware. In: Higuchi, T. et al. (eds.), Evolvable Systems: From Biology to Hardware, Berlin, Springer-Verlag 1997, pp. 55-78.
6. M. Sipper. Evolution of Parallel Cellular Machines: The Cellular Programming Approach. Springer-Verlag, Heidelberg, 1997.
7. Back, T.: Evolutionary Algorithms in Theory and Practice. Oxford University Press, New York, 1996.
8. Miller, J., Thomson, P.: Cartesian Genetic Programming. In: EuroGP, 1st International Conference on Genetic Programming, 2000, Edinburgh, Scotland.
9. Kajitani, I, et al.: Evolvable Hardware Chips for Neural Network Applications. In: Proc. of the Fourth International Conference on Artificial Neural Networks and Genetic Algorithms (ICANNGA99), pp. 127-134, 1999.
10. Higuchi, T. et al: Real-World Applications of Analog and Digital Evolvable Hardware. In: IEEE Transactions on Evolutionary Computation, Vol. 3, No. 3, September 1999, pp. 220-235.
11. Miller, J., Job, D., Vassilev, V.: Principles in the Evolutionary Design of Digital Circuits -- Part I, Journal of Genetic Programming and Evolvable Machines, Vol. 1, No. 1, 2000, pp. 8-35.
12. Miller, J., Job, D., Vassilev, V.: Principles in the Evolutionary Design of Digital Circuits -- Part II, Journal of Genetic Programming and Evolvable Machines, Vol. 3, No. 2, 2000, pp. 259-288.
13. Kajitani, I. et al: A gate-level EHW chip: Implementing GA operations and reconfigurable hardware on a single LSI. In: Sipper, M. et al. (eds.): Evolvable Systems: From Biology to Hardware, Springer Verlag, 1998, pp. 1-12.
14. Salami, M., Murakawa, M., Higuchi, T.: Data Compression Based on Evolvable Hardware. In: Higuchi, T. et al. (eds.), Evolvable Systems: From Biology to Hardware, Berlin, Springer-Verlag 1997, pp. 169-179.
15. Tanaka, M., et al.: Data Compression for Digital Color Electrophotographic Printer with Evolvable Hardware. In: Sipper, M. et al. (eds.): Evolvable Systems: From Biology to Hardware, Springer Verlag, 1998, pp. 106-114.
16. Tufte, G., Haddow, P.: Prototyping a GA Pipeline for Complete Hardware Evolution . In: The first NASA/DoD Workshop on Evolvable Hardware, IEEE Press, 1999, pp 143-150.
17. Torresen, J.: Possibilities and Limitations of Applying Evolvable Hardware to Real-World Application . In: 10th International Conference on Field Programmable Logic and Applications (FPL-2000), Villach, Austria, pp. 230-239
18. Bentley, P.: Representations are more important than algorithms: Why Evolution Needs Embryology. In: Evolvable Systems: From Biology to Hardware, html-presentation.
19. Zebulum R.S., Pacheo, M.A., Vellasco, M: Evolvable system in hardware design: Taxonomy, survey and applications.In: Higuchi, T. et al. (eds.), Evolvable Systems: From Biology to Hardware, Berlin, Springer-Verlag 1997, pp. 344-358.
20. Vassilev, V., Miller, J. F.: Scalability Problems of Digital Circuit Evolution - Evolvability and Efficient Designs . In: J. Lohn, A. Stoica, D. Keymeulen and S. Colombano (eds.), Proceedings of the 2nd NASA/DoD Workshop on Evolvable Hardware (2000). Los Alamitos, CA: IEEE Computer Society, pp. 55-64.

---

Please send me e-mail if you have some comments.
2000-3 (C) Lukas Sekanina
Faculty of Information Technology
Brno University of Technology, Czech Republic
Last modification: May 6, 2003
Counter since September 24, 2000: