How to Evolve Complex Combinational Circuits From Scratch?

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F14%3APU112025" target="_blank" >RIV/00216305:26230/14:PU112025 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.fit.vutbr.cz/research/pubs/all.php?id=10673" target="_blank" >http://www.fit.vutbr.cz/research/pubs/all.php?id=10673</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/ICES.2014.7008732" target="_blank" >10.1109/ICES.2014.7008732</a>

Jazyk výsledku

angličtina

Název v původním jazyce

How to Evolve Complex Combinational Circuits From Scratch?

Popis výsledku v původním jazyce

One of the serious criticisms of the evolutionary circuit design method is that it is not suitable for the design of complex large circuits. This problem is especially visible in the evolutionary design of combinational circuits, such as arithmetic circuits, in which a perfect response is requested for every possible combination of inputs. This paper deals with a new method which enables us to evolve complex circuits from a randomly seeded initial population and without providing any information about the circuit structure to the evolutionary algorithm. The proposed solution is based on an advanced approach to the evaluation of candidate circuits. Every candidate circuit is transformed to a corresponding binary decision diagram (BDD) and its functional similarity is determined against the specification given as another BDD. The fitness value is the Hamming distance between the output vectors of functions represented by the two BDDs. It is shown in the paper that the BDD-based evaluation procedure can be performed much faster than evaluating all possible assignments to the inputs. It also significantly increases the success rate of the evolutionary design process. The method is evaluated using selected benchmark circuits from the LGSynth91 set. For example, a correct implementation was evolved for a 28-input frg1 circuit. The evolved circuit contains less gates (a 57% reduction was obtained) than the result of a conventional optimization conducted by ABC. 

Název v anglickém jazyce

How to Evolve Complex Combinational Circuits From Scratch?

Popis výsledku anglicky

One of the serious criticisms of the evolutionary circuit design method is that it is not suitable for the design of complex large circuits. This problem is especially visible in the evolutionary design of combinational circuits, such as arithmetic circuits, in which a perfect response is requested for every possible combination of inputs. This paper deals with a new method which enables us to evolve complex circuits from a randomly seeded initial population and without providing any information about the circuit structure to the evolutionary algorithm. The proposed solution is based on an advanced approach to the evaluation of candidate circuits. Every candidate circuit is transformed to a corresponding binary decision diagram (BDD) and its functional similarity is determined against the specification given as another BDD. The fitness value is the Hamming distance between the output vectors of functions represented by the two BDDs. It is shown in the paper that the BDD-based evaluation procedure can be performed much faster than evaluating all possible assignments to the inputs. It also significantly increases the success rate of the evolutionary design process. The method is evaluated using selected benchmark circuits from the LGSynth91 set. For example, a correct implementation was evolved for a 28-input frg1 circuit. The evolved circuit contains less gates (a 57% reduction was obtained) than the result of a conventional optimization conducted by ABC. 

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA14-04197S" target="_blank" >GA14-04197S: Pokročilé metody evolučního návrhu složitých číslicových obvodů</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2014

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

2014 IEEE International Conference on Evolvable Systems Proceedings

ISBN

978-1-4799-4480-4

ISSN

—

e-ISSN

—

Počet stran výsledku

8

Strana od-do

133-140

Název nakladatele

Institute of Electrical and Electronics Engineers

Místo vydání

Piscataway

Místo konání akce

Orlando

Datum konání akce

9. 12. 2014

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—