Prof. Ing. Lukáš Sekanina, Ph.D.

VAŠÍČEK Zdeněk a SEKANINA Lukáš. Evolutionary Optimization of Complex Digital Circuits. In: 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science. Brno: Masarykova universita, 2011, s. 1. ISBN 978-80-214-4305-1.
Jazyk publikace:angličtina
Název publikace:Evolutionary Optimization of Complex Digital Circuits
Název (cs):Evoluční optimalizace komplexních číslicových obvodů
Strany:1
Sborník:7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Konference:MEMICS'11 -- 7th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science
Místo vydání:Brno, CZ
Rok:2011
ISBN:978-80-214-4305-1
Vydavatel:Masarykova universita
Klíčová slova
circuit synthesis, circuit optimization, evolutionary design, satisfiability, formal verification, combinational equivalence checking
Anotace
Příspěvek vycházející z článku Formal Verification of Candidate Solutions for Post-Synthesis Evolutionary Optimization in Evolvable Hardware publikovaného v časopise Genetic Programming and Evolvable Machines, Volume 12, Number 3, p. 305-327.
Abstrakt
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.
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 = {978-80-214-4305-1},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=9794}
}

Vaše IPv4 adresa: 54.166.232.243
Přepnout na IPv6 spojení

DNSSEC [dnssec]