Euro**GP**2006 & Evo**COP**2006,

incorporating Evo**Workshops**2006

### 10-12 April, 2006

### Budapest, Hungary

incorporating Evo

IEEE publishes an average of 20 papers each year where evolutionary techniques are exploited to solve design automation problems.

Concurrently, the field of evolutionary computation shows a growing significant interest in evolvable hardware and problems such as routing, placement, or test pattern generation.

EvoHOT2006, the second EvoHOT workshop, will show the latest developments in the field of evolutionary algorithms applied to design automation, and will offer good opportunities for informal contact in a friendly and relaxed setting.

Web address: http://www.evonet.info/eurogp2006

- Analog circuit design
- Automatic test pattern generation
- Built-in self test
- Evolutionary design of electronic circuits
- Evolutionary hardware design methodologies
- Evolutionary robotics
- Evolvable hardware
- Floorplanning
- Hardware/Software co-design
- Hybrid evolutionary/exact approach
- Hardware accelerated methodologies
- Logic synthesis
- Routing
- Test program generation

- Program Chairs
- Giovanni Squillero
- giovanni DOT squillero AT polito DOT it
- Politecnico di Torino, Italy
- Rolf Drechsler
- drechsle AT informatik DOT uni-bremen DOT de
- University of Bremen, Germany
- EvoWorkshops2006 Chair
- Franz Rothlauf
- rothlauf AT uni-mannheim DOT de
- University of Mannheim, Germany
- Local Chair
- Anikó Ekárt
- ekart AT sztaki DOT hu
- Hungarian Academy of Sciences
- Publicity Chair
- Steven Gustafson
- smg AT cs DOT nott DOT ac DOT uk
- University of Nottingham, UK

**Note:** the e-mail addresses are masked for spam protection.

- Varun Aggarwal
- Bernd Becker
- Michelanglo Grosso
- Andrew Kinane
- Gabriella Kókai
- Una-May O'Reilly
- Mihai Oltean
- Gregor Papa
- Ernesto Sanchez
- Lukás Sekanina
- Massimiliano Schillaci
- Luca Sterpone
- Andreas Veneris

**Optimisation of Constant Matrix Multiplication Operation Hardware Using a Genetic Algorithm
***Andrew Kinane, Valentin Muresan, Noel O’Connor
*

The efficient design of multiplierless implementations of constant matrix multipliers is challenged by the huge solution search spaces even for small scale problems. Previous approaches tend to use hill-climbing algorithms risking sub-optimal results. The three-stage algorithm proposed in this paper partitions the global constant matrix multiplier into its constituent dot products, and all possible solutions are derived for each dot product in the first two stages. The third stage leverages the effective search capability of genetic programming to search for global solutions created by combining dot product partial solutions. A bonus feature of the algorithm is that the modelling is amenable to hardware acceleration. Another bonus feature is a search space reduction early exit mechanism, made possible by the way the algorithm is modelled. Results show an improvement on state of the art algorithms with future potential for even greater savings.

**
Finding Compact BDDs Using Genetic Programming
***Ulrich K¨uhne, Nicole Drechsler
*

Binary Decision Diagrams (BDDs) can be used to design multiplexor based circuits. Unfortunately, the most commonly used kind of BDDs - ordered BDDs - has exponential size in the number of variables for many functions. In some cases, more general forms of BDDs are more compact. In constrast to the minimization of OBDDs, which is well understood, there are no heuristics for the construction of compact BDDs up to today. In this paper we show that compact BDDs can be constructed using Genetic Programming.

**
Efficient Evolutionary Approaches for the Data Ordering Problem with Inversion
***Doina Logofatu, Rolf Drechsler
*

An important aim of circuit design is the reduction of the power dis-sipation. Power consumption of digital circuits is closely related to switching activity. Due to the increase in the usage of battery driven devices (e.g. PDAs, laptops), the low power aspect became one of the main issues in circuit design in recent years. In this context, the Data Ordering Problem with and without In-version is very important. Data words have to be ordered and (eventually) ne-gated in order to minimize the total number of bit transitions. These problems have several applications, like instruction scheduling, compiler optimization, sequencing of test patterns, or cache write-back. This paper describes two evo-lutionary algorithms for the Data Ordering Problem with Inversion (DOPI). The first one sensibly improves the Greedy Min solution (the best known related polynomial heuristic) by a small amount of time, by successively applying mu-tation operators. The second one is a hybrid genetic algorithm, where a part of the population is initialized using greedy techniques. Greedy Min and Lower Bound algorithms are used for verifying the performance of the presented Evo-lutionary Algorithms (EAs) on a large set of experiments. A comparison of our results to previous approaches proves the efficiency of our second approach. It is able to cope with data sets which are much larger than those handled by the best known EAs. This improvement comes from the synchronized strategy of applying the genetic operators (algorithm design) as well as from the compact representation of the data (algorithm implementation). KEY WORDS: Evolu-tionary Algorithms, Digital Circuit Design, Low Power, Data Ordering Prob-lem, Transition Minimization, Optimization, Graph Theory, Complexity

**
On the Practical Limits of the Evolutionary Digital Filter Design at the Gate Level
***Luk´aˇs Sekanina, Zdenˇek Vaˇs´ýˇcek
*

Simple digital FIR filters have recently been evolved directly in the reconfigurable gate array, ignoring thus a classical method based on multiply--and--accumulate structures. This work indicates that the method is very problematic. In this paper, the gate-level approach is extended to IIR filters, a new approach is proposed to the fitness calculation based on the impulse response evaluation and a comparison is performed between the evolutionary FIR filter design utilizing a full set and a reduced set of gates. The objective of these experiments is to show that the evolutionary design of digital filters at the gate level does not produce filters that are useful in practice when linearity of filters is not guaranteed by the evolutionary design method.

**
GRACE: Generative Robust Analog Circuit Exploration
***Michael A. Terry, Jonathan Marcus, Matthew Farrell, Varun Aggarwal, Una-May O’Reilly
*

We motivate and describe an analog evolvable hardware design platform named GRACE (i.e. Generative Robust Analog Circuit Exploration). GRACE combines coarse-grained, topological circuit search with intrinsic testing on a Commercial Off-The-Shelf (COTS) field programmable device, the Anadigm AN221E04. It is suited for adaptive, fault tolerant system design as well as CAD flow applications.