EA-based Resynthesis: An Efficient Tool for Optimization of Digital Circuits

Cartesian genetic programming, Evolutionary resynthesis, Logic optimization

Špatná škálovatelnost výpočtu fitness funkce byla hlavní příčinou, proč se nedařilo po dlouhou dobu aplikovat evoluční algoritmy v oblasti optimalizace číslicových obvodů. Zavedením formálních technik jako jsou SAT a BDD solvery se tento problém podařilo významně redukovat a evoluční techniky tak bylo možné aplikovat i na komplexní číslicové obvody. Nyní však čelíme jinému problému - omezené škálovatelnosti reprezentace, kdy efektivita evoluční optimalizace klesá se zvětšující se složitostí optimalizovaných obvodů. Abychom překonali tento problém, navrhujeme použít koncept lokální resyntézy, tj. extrahovat z obvodu menší celky, které jsou nezávisle optimalizováný a jejich optimalizovaná podoba je implantována zpět do původního obvodu. V článku jsou vyhodnoceny dva komplementární přístupy. Experimentálně bylo ukázáno, že navržená technika umožňuje dosáhnout mnohem lepších výsledků oproti existujícím optimalizátorům pracujícím na globální úrovni.