EvoWorkshops2005: EvoHOT

2nd European Workshop on Evolutionary Computation in Hardware Optimisation

In Applications of Evolutionary Computing.

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.

EvoHOT2005, 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/eurogp2005

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
 
EvoWorkshops2005 Chair
Franz Rothlauf
rothlauf AT uni-mannheim DOT de
University of Mannheim, Germany
 
Local Chair
Marco Tomassini
Marco.Tomassini AT hec DOT unil DOT ch
University of Lausanne, Switzerland
 
Publicity Chair
Jano van Hemert
jvhemert AT cwi DOT nl
Napier University, Edinburgh, Scotland, UK

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

EvoHOT Programme

Thursday, 31 March 2005

Session 1: Evolutionary Design I (0930-1100)

Chair: G. Squillero

A Biological Development model for the Design of Robust Multiplier
Heng Liu
Julian F. Miller
Andy M. Tyrrell
(Best Paper Award Candidate)

Evolutionary Design of Gate-Level Polymorphic Digital Circuits
Lukáš Sekanina
(Best Paper Award Candidate)

Session 2: Evolutionary Design II (1120-1250)

Chair: G. Squillero

Evolving reversible circuits for the even-parity problem
Mihai Oltean

A Genetic Algorithm for VLSI Floorplanning Using O-Tree Representation
Maolin Tang
Alvin Sebastian

Session 3: Evolutionary Optimization (1415-1545)

Chair: Lukas Sekanina

Use of an evolutionary tool for antenna array synthesis
Luca Manetta
Laura Ollino
Massimiliano Schillaci

Counter-based Ant Colony Optimization as a Hardware-oriented Meta-Heuristic
Bernd Scheuermann
Martin Middendorf

Automatic completion and refinement of verification sets for microprocessor cores
Ernesto Sánchez
Matteo Sonza Reorda
Giovanni Squillero

EvoHOT: Titles and abstracts of accepted papers

Heng Liu
Julian F. Miller
Andy M. Tyrrell

A Biological Development model for the Design of Robust Multiplier

(Best Paper Award Candidate)
A biologically inspired developmental model targeted at hardware implementation (off-shelf FPGA) is proposed which exhibits extremely robust transient fault-tolerant capability. All cells in this model have identical geno-type (physical structures), and only differ in internal states. In a 3x3 cell digital organism, some individuals which implement a 2-bit multiplier were discovered using evolution that have the ability to ÁˇrecoverÁ± themselves from almost any kinds of transient faults. An intrinsic evolvable hardware platform based on FPGA was realized to speed up the evolution process.

Luca Manetta
Laura Ollino
Massimiliano Schillaci

Use of an evolutionary tool for antenna array synthesis

paper describes an evolutionary approach to the optimization of element antenna arrays. Classic manual or automatic optimization methods do not always yield satisfactory results, being either too labour-intensive or unsuitable for some specific class of problems. The advantage of using an evolutionary approach is twofold: on the one hand it does not introduce any arbitrary assumptions about what kind of solution shows the best promise; on the other hand, being intrinsically non-deterministic, it allows the whole process to be repeated in search of better solutions. A generic evolutionary tool originally developed for a totally different application area, namely test program generation for microprocessors, is employed for the optimization process. The results show both the versatility of the tool (it? s able to autonomously choose the number of array elements) and the validity of the evolutionary approach for this specific problem.

Mihai Oltean

Evolving reversible circuits for the even-parity problem

Reversible computing basically means computation with less or not at all electrical power. Since the standard binary gates are not usually reversible we use the Fredkin gate in order to achieve reversibility. An algorithm for designing reversible digital circuits is described in this paper. The algorithm is based on Multi Expression Programming (MEP), a Genetic Programming variant with a linear representation of individuals. The case of digital circuits for the even-parity problem is investigated. Numerical experiments show that the MEP-based algorithm is able to easily design reversible digital circuits for up to the even-8- parity problem.

Ernesto Sánchez
Matteo Sonza Reorda
Giovanni Squillero

Automatic completion and refinement of verification sets for microprocessor cores

In the design cycle of a microprocessor core, the unit is usually refined through a series of subsequent steps. To deliver a flaw free unit at the end of the process, in each stage a verification step is required. While it would be useful to automatically develop the set of test programs for verification concurrently to the design, in most of the existing approach verification is performed manually and starting from scratch. This paper presented a methodology for the automatic completion and refinement of existing verification programs. It shows a new technique for allowing a Genetic Programming-based framework to import an existing test-program set and assimilate it for further test generation. A case study is considered, in which a sample pipelined processor is used, and new test programs are generated starting from existing functional ones. Different metrics are targeted, and preliminary results are reported, showing the effectiveness of the method with respect to a pure random approach.

Bernd Scheuermann
Martin Middendorf

Counter-based Ant Colony Optimization as a Hardware-oriented Meta-Heuristic

In this paper, we present the Counter-based Ant Colony Optimization (C-ACO) algorithm as a meta-heuristic, which allows for a resource-efficient implementation on Field Programmable Gate Arrays. In comparison to the standard ACO approach in software on a sequential machine, the implementation of C-ACO in hardware leads to significant asymptotic speed-ups. In experimental studies, we investigate the performance of the proposed C-ACO algorithm. Furthermore, we introduce and examine alternative means of integrating heuristic information into the optimization process, thereby considering the requirements of the hardware architecture.

Lukáš Sekanina

Evolutionary Design of Gate-Level Polymorphic Digital Circuits

(Best Paper Award Candidate)
A method for the evolutionary design of polymorphic digital combinational circuits is proposed. These circuits are able to perform different functions (e.g. to switch between the adder and multiplier) only as a consequence of the change of a sensitive variable, which can be a power supply voltage, temperature etc. However, multiplexing of standard solutions is not utilized. The evolved circuits exhibit a unique structure composed of multifunctional polymorphic gates considered as building blocks instead. In many cases the area-efficient solutions were discovered for typical tasks of the digital design. We demonstrated that it is useful to combine polymorphic gates and conventional gates in order to obtain the required functionality.

Maolin Tang
Alvin Sebastian

A Genetic Algorithm for VLSI Floorplanning Using O-Tree Representation

Floorplanning is one of the most important problems in VLSI physical design automation. A fundamental research problem in the VLSI floorplanning is representation because it determines the size of search space and the complexity of the transformation between a representation and its corresponding floorplan. O-tree representation is one of the most efficient floorplan representations as it has the smallest search space among all the admissible floorplan representations and the computational complexity of transformation between a representation and its corresponding floorplan is only O(n). The efficiency of O-tree representation was demonstrated by a deterministic algorithm proposed by Guo et al.. The deterministic algorithm can quickly find a reasonably good floorplan. However, the deterministic floorplanning algorithm, by its nature, is a local search algorithm, and thereby may not be able to find an optimal or near-optimal solution sometimes. This paper presents a genetic algorithm for the VLSI floorplanning problem using O-tree representation. Experimental results show that the GA can consistently produce better results than the deterministic algorithm.