EHW Overview

Evolvable hardware is based on the idea of combining reconfigurable hardware device with genetic algorithms to execute reconfiguration autonomously [ICES96] [Yao] [Higuchi].

The structure of reconfigurable hardware devices can be changed any number of times by downloading into the device a software bit string called configuration bits. FPGA (Field Programmable Gate Array) and PLD (Programmable Logic Devices) are typical examples of reconfigurable hardware devices, for which there is already a market worth more than 2 Billion US dollars and growing at 23% per year. However it should be noted that the reconfiguration must still be executed manually by hardware designers.

A genetic algorithm (GA) is a robust search algorithm loosely based on population genetics [Goldberg]. It effectively seeks solutions from a vast search space at reasonable computation costs. Before a GA starts, a set of candidate solutions, represented as binary bit strings, are prepared. This set is referred to as a population, and each candidate solution within the set as a chromosome. A fitness function is also defined which represents the problem to be solved in terms of criteria to be optimized. The chromosomes then undergo a process of evaluation, selection, and reproduction. In the evaluation stage, the chromosomes are tested according to the fitness function. The results of this evaluation are then used to weight the random selection of chromosome in favor of the fitter ones for the final stage of reproduction. In this final stage, a new generation of the chromosomes are "evolved" through genetic operations which attempt to pass on better characteristics to the next generation. Through this process, which can be repeated as many times as required, less fit chromosomes are gradually expelled from a population and the fitter chromosomes become more likely to emerge as the final solution.

The basic concept behind the combination of these two elements in EHW is to regard the configuration bits for reconfigurable hardware devices as chromosomes for genetic algorithms (See Figure 1). If a fitness function is properly designed for a task, then the genetic algorithms can autonomously find the best hardware configuration in terms of chromosomes (i.e. configuration bits).

For example, in data compression with EHW, we use a prediction function. Optimal prediction functions vary greatly according to the different kinds of data to be compressed. It is, therefore, not possible to design in advance a prediction hardware function. Instead of specifying a detailed hardware design, we define a fitness function. In the case of data compression, the data compression rate is used as a fitness function. Accordingly, a circuit of prediction function with a higher data compression rate is likely to remain in a population. When a good chromosome is obtained, it is immediately downloaded into the reconfigurable device.

If the prediction performance of a given EHW is reduced due to changes in the nature of the data to be compressed, then the GA process is invoked and the search for a better hardware structure of prediction is initiated. In this way, EHW is capable of both autonomous and dynamic hardware reconfigurations.

References

[Goldberg] D. Goldberg, "Genetic Algorithms in Search, Optimization, and Machine Learning," Addison Wesley, 1989.

[ICES96] Evolvable Systems: From Biology to Hardware, Lecture Notes in Computer Science 1259, Springer-Verlag, 1997.

[Yao] Xin yao, T. Higuchi, "Promises and Challenges of Evolvable Hardware," IEEE Tran. on Systems, Man, and Cybernetics- Part C: Applications and Reviews, Vol. 29, No. 1, pp.87-97, 1999.

[Higuchi] T. Higuchi, N. Kajihara, "Evolvable Hardware Chips for Industrial Applications," Communications of the ACM, Vol. 42, No. 4, pp.60-69, 1999.