Evolved Synthesis of Digital Circuits
Laurentiu Ionescu (University of Pitesti, Romania), Alin Mazare (University of Pitesti, Romania), Gheorghe Serban (University of Pitesti, Romania) and Emil Sofron (University of Pitesti, Romania)
Copyright: © 2009
Traditionally physical systems have been designed by engineers using complex collections of rules and principles. The design process is top-down in nature and begins with a precise specification. This contrasts very strongly with the mechanisms which have produced the extraordinary diversity and sophistication of living creatures. In this case the ‘‘designs’’ are evolved by a process of natural selection. The design starts as a set of instructions encoded in the DNA whose coding regions are first transcribed into RNA in the cell nucleus and then later translated into proteins in the cell cytoplasm. The DNA carries the instructions for building molecules using sequences of amino acids. Eventually after a number of extraordinarily complex and subtle biochemical reactions an entire living organism is created. The survivability of the organism can be seen as a process of assembling a larger system from a number of component parts and then testing the organism in the environment in which it finds itself (Miller, 2000). The main target of the evolvable hardware is to build a digital circuit using bio inspired methods like genetic algorithms. Here the potential solutions are coded like configuration vectors which command interconnection between logical cells inside the reconfigurable circuit. All configuration vectors represent the genotype and one single configuration vector is the individual with its own characteristics (like chromosome). The individuals are generated by genetic operators like crossover or mutation. One individual give one solution circuit which is tested in evaluation module. The circuit obtained from the individual consist the phenotype. The circuit behavior is compared with target functions, which we desire to implement. The result is fitness: if the circuit approximates the behavior of the target function, we have a good fitness for the individual which generate the circuit. Then each individual whit its fitness gets into selection module where the future parents in crossover and mutation are decided. Finally we have a circuit solution which implements the target function. We have an evolved synthesis of digital circuit – a method like assemble and test. This method can be useful because explore the design space beyond the limits imposed by traditional design methods. Two research directions are developed in evolvable hardware. In extrinsic evolvable hardware the individuals are obtained from software implementation on computer and phenotype consist in high level abstract circuits like SPICE object files or FPGA configuration files (.bit). The intrinsic evolution, on the other hand, supposes that entire evolution process is inside one or more chips (FPGA): the hardware implementation of evolved hardware. The challenge is to design an intrinsic evolution because can be used for applications like robots control system. But this involves implementation of the software based algorithms in hardware modules.
The dynamic reconfigurable hardware area and evolvable hardware knows, in the last years, a fast evolution. Ten years ago the digital circuit implementation, with high degree of complexity involve more problems caused specially by technologies limits. The market was up most by complex programmable gates array or by the low grains field programmable gates array where upon the main problems are the number of Boolean cells available on chip and the delay time. The fast evolution of the technologies increases in our day the performance of programmable circuits. Thus, today is possible to implement a high speed central processing units core which is comparable with the application specific integrated circuit implementations. Therewith the low product costs make that a modern programmable digital circuit can be purchased by end users like students and researchers. Thus an evolution in designing, synthesis and implementation techniques with programmable logic circuits is required. One very attractive direction of research is implementation of hardware bio-inspired systems on programmable logic circuits like neural networks or evolutionary algorithms (e.g. genetic algorithms).
Key Terms in this Chapter
Genotype: Describe the genetic constitution of an individual, that is the specific allelic makeup of an individual. In evolvable hardware it consist in a vector of configuration bits.
Genetic Algorithms (GA): A genetic algorithm (or GA) is a search technique used in computing to find true or approximate solutions to optimization and search problems. Genetic algorithms are categorized as a stochastic local search technique. Genetic algorithms are a particular class of evolutionary algorithms that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination).Individuals, with coding schema, are initial random values. All individuals are, in the first step of algorithm evaluated to get the fitness value. In the next step, they are sorted by fitness and selected for genetic operators. The parents are the individuals involved in genetic operators like crossover or mutation. The offspring resulted are evaluated together with parents and the algorithm resume with the first step. The loop is repeated until the solution is find or the number of generation reach the limit given by the programmer.
HGA: Hardware genetic algorithm is a hardware implementation of genetic algorithm. Hardware implementation increases the performance of the algorithm by replacing serial software modules with parallel hardware.
Evolvable Hardware: Reconfigurable circuit which is programmed by evolved algorithm like GA. To extrinsic evolvable hardware evolved algorithm run to host station outside of the reconfigurable circuit (PC). To intrinsic evolvable hardware evolved algorithm run inside the same system with reconfigurable circuit (even same chip).
Microstructure: Integration of structure in same chip. Evolvable hardware microstructure is an intrinsic evolvable hardware with all modules in same chip.
Phenotype: Describe one of the traits of an individual that is measurable and that is expressed in only a subset of the individuals within that population. In evolvable hardware phenotype consist in the circuit coded by an individual.
Reconfigurable Circuit: Hardware structure consist in logical cell network which allow configuration of the interconnections between cells