Prof. Ing. Lukáš Sekanina, Ph.D.
VAŠÍČEK Zdeněk and SEKANINA Lukáš. Evolutionary Optimization of Complex Digital Circuits. In: 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: Masaryk University, 2011, p. 1. ISBN 9788021443051.  Publication language:  english 

Original title:  Evolutionary Optimization of Complex Digital Circuits 

Title (cs):  Evoluční optimalizace komplexních číslicových obvodů 

Pages:  1 

Proceedings:  7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science 

Conference:  MEMICS'11  7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science 

Place:  Brno, CZ 

Year:  2011 

ISBN:  9788021443051 

Publisher:  Masaryk University 

Keywords 

circuit synthesis, circuit optimization, evolutionary design, satisfiability, formal verification, combinational equivalence checking 
Annotation 

This contribution is based on the paper Formal Verification of Candidate Solutions for PostSynthesis Evolutionary Optimization in Evolvable Hardware that has been published in Genetic Programming and Evolvable Machines journal, Volume 12, Number 3, p. 305327. 
Abstract 

Recent works on logic synthesis have shown that commonly used logic synthesis algorithms are not capable of efficient synthesis for some circuit classes, especially for large circuits and circuits containing hardtosynthesize substructures where the area of the synthesized circuits is of orders of magnitude higher than the optimum. Even if the synthesis by means of the evolutionary algorithms is known to be a powerful tool able to discover compact circuit structures that are unreachable using the conventional synthesis techniques, this approach can handle only small circuit instances due to the so called scalability problems.
The main contribution of this paper is to show that the scalability
limit of digital circuit evolution can reasonably be eliminated by using a new type of fitness evaluation procedure. We introduce a technique that utilizes an equivalence checking algorithm to decide whether a candidate circuit is functionally correct or not. In order to calculate a fitness value, the candidate circuit as well as the specification are converted to one Boolean formula whose satisfiability is investigated using a SAT solver. If the resulting formula is not satisfiable, the candidate circuit is accepted as it is functionally equivalent with the specification. Then, the candidate circuit is analysed to calculate the corresponding fitness value. The implementation of this step depends on the objectives of the optimization process. This method can be used to minimize the area on the chip, delay of the circuit, power consumption or to minimize the number of test vectors.
The proposed technique is evaluated using the LGSynth93 benchmark circuits. It is shown that this approach allows to optimize large logic circuits possessing tens of inputs and hundreds of logic gates. Note that the traditionally used fitness function that evaluates the candidate circuit by applying all the test vectors can practically handle the circuits having about 20 inputs only. 
BibTeX: 

@INPROCEEDINGS{
author = {Zden{\v{e}}k Va{\v{s}}{\'{i}}{\v{c}}ek and
Luk{\'{a}}{\v{s}} Sekanina},
title = {Evolutionary Optimization of Complex Digital
Circuits},
pages = {1},
booktitle = {7th Doctoral Workshop on Mathematical and Engineering
Methods in Computer Science},
year = {2011},
location = {Brno, CZ},
publisher = {Masaryk University},
ISBN = {9788021443051},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php.en?id=9794}
} 
