Evolvable Hardware
J.UCS Special Issue

Nadia Nedjah (Department of Electronics Engineering and Telecommunications, Faculty of Engineering State, University of Rio de Janeiro, Brazil)
nadia@eng.uerj.br

Luiza de Macedo Mourelle (Department of Systems Engineering and Computation, Faculty of Engineering, State University of Rio de Janeiro, Brazil)
ldmm@eng.uerj.br

Abstract: In recent years, genetic programming has attracted many researcher's attention and so became a consolidated methodology to automatically create new competitive computer programs. Concise and efficient synthesis of a variety of systems has been generated by evolutionary computations.

Evolvable hardware is a growing discipline. It allows one to evolve creative and novel hardware architectures given the expected input/output behavior. There are two kinds of evolvable hardware: extrinsic and intrinsic. The former relies on a simulated evolutionary process to evaluate the characteristics of the evolved designs while the latter uses hardware itself to do so. Usually, reconfigurable hardware such FPGA and FPAA are exploited.

While the intrinsic/extrinsic distinction is irrelevant for evolving software, the differences in hardware are very apparent. With most engineering hardware devices, evolution in simulation is quicker than building many prototypes of a device, but electronic hardware can be quicker to evolve intrinsically. This has the potential for producing remarkably different results: whereas in simulation, a design is naturally constrained to the programmer's model of the device, intrinsic evolution allows a design to exploit natural features of the device which may not even be understood by the programmer.

The concept of extrinsic was pioneered by Adrian Thompson who in 1996 evolved a tone discriminator, using fewer than 40 programmable logic gates and no clock signal in a FPGA. This is a remarkably small design for such a device, and it is still not understood how it works. For example, one group of gates has no logical connection to the rest of the circuit, yet is crucial to its function. It is thought that this group somehow modulates the power supply or influences other connections by generating a Magnetic field. One of the main problems that still researchers are faced with in the field of evolutionary hardware design is the scalability. Also, the evolved circuits worked only on the original device and could not be copied and they were only operational in a limited range of temperatures.

This special issue of Journal of Universal Computer Science is devoted to reporting innovative and significant progress in automatic hardware design. It includes five contributed papers, whose main contributions are described in the sequel.

In the first contribution, which is entitled "A Multi-objective Genetic Approach to Mapping Problem on Network-on-Chip", Giuseppe Ascia, Vincenzo Catania, and Maurizio Palesi address the problem of topological mapping of intellectual properties (IPs) on the tiles of a mesh-based NoC architecture. The aim is to obtain the Pareto mappings that maximize performance and minimize power dissipation. The authors propose a heuristic technique based on evolutionary computing to obtain an optimal approximation of the Pareto-optimal front in an efficient and accurate way. Besides, they extend two of the most widely-known approaches to mapping in mesh-based NoC architectures in order to explore the mapping space in a multicriteria mode. The evaluation performed on both synthesized traffic and real applications (an MPEG-4 codec) allowed the authors to confirm the efficiency, accuracy and scalability of the proposed approach.

In the second contribution, which is entitled "Pareto-Optimal Hardware for Substitution Boxes", Nadia Nedjah and Luiza de Macedo Mourelle propose a methodology based on genetic programming to automatically generate hardware designs for substitution boxes necessary for many cryptosystems such as DES and AES encryption systems. They aim at evolving minimal hardware specifications, which minimize both space, response time and dissipated power. The author claim that the evolved hardware compared with existing and well-known designs, which were produced by human designers using conventional methods, is superior.

In the third contribution, which is entitled "Automatic Programming Methodologies for Electronic Hardware Fault Monitoring", Ajith Abraham and Crina Grosan present and apply three variants of Genetic Programming approaches to intelligent online performance monitoring of electronic circuits and systems. Obtained empirical results are compared with artificial neural networks trained using back-propagation algorithm and classification and regression trees. Based on this comparison, the authors claim that the developed model which is GP-based could play an important role for future fault monitoring systems.

In the fourth contribution, which is entitled "Multi-Objective Evolutionary Algorithms and Pattern Search Methods for Circuit Design Problems", Tonio Biondi, Angelo Ciccazzo, Santo D'Antona, Giuseppe Nicosia and Salvatore Spinella experimentally compare the effectiveness of multi-objective evolutionary algorithms and standard optimization techniques applied to problems arising from Analog Circuit Design: the optimization of a Operational Trans-conductance Amplifier and of a fifth-order leapfrog filter. In particular, the authors conclude that Pareto fronts determined by evolutionary algorithms has a better spread of solutions with a larger number of non-dominated solutions when compared to the classical multi-objective techniques.

In the fifth contribution, which is entitled "DS/CDMA Multi-user Detection with Evolutionary Algorithms", Fernando Ciriaco, Taufik Abrão and Paul Jean E. Jeszensky analyse two heuristic algorithms based on the genetic evolution theory applied to direct sequence code division multiple access (DS/CDMA) communication systems.

Based on Monte Carlo simulation results, the authors guarantee that the detection based on evolutionary heuristic algorithms is a viable option when compared with the optimum solution (ML - maximum likelihood), even for hostile channel conditions and severe system operation.

As guest editors of this special issue of J.UCS, we wish to thank all the contributors for their hard work and their promptness. Also, our special thanks go to the reviewers that provided us with the right feedback at the right time. This allowed us to fulfill our aim with the expected quality and delays.

April 2006