EvoWorkshops2006: EvoHOT

3rd European Workshop on Evolutionary Computation in Hardware Optimisation

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

Topics include

Organising Committee

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.

Programme Committee

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

Accepted papers: titles and abstracts

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.