Publication Details

Evolutionary Optimization of Complex Digital Circuits

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 978-80-214-4305-1.
Czech title
Evoluční optimalizace komplexních číslicových obvodů
Type
conference paper
Language
english
Authors
Vašíček Zdeněk, doc. Ing., Ph.D. (DCSY FIT BUT)
Sekanina Lukáš, prof. Ing., Ph.D. (DCSY FIT BUT)
Keywords

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

Abstract

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

Annotation
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 hard-to-synthesize 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.
Published
2011
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, Lednice, CZ
ISBN
978-80-214-4305-1
Publisher
Masaryk University
Place
Brno, CZ
BibTeX 
@INPROCEEDINGS{FITPUB9794,
   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 = "978-80-214-4305-1",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9794"
}
Back to top