EVOLUTIONARY SYNTHESIS OF COMPLEX DIGITAL CIRCUITS

Tato dizertacni prace prezentuje vyzkum v oblasti evolucni optimalizace komplexnich kom- binacnich obvodu. Prace zacina studiem existujicich konvencnich i nekonvencnich pristupu k optimalizaci kombinacnich obvodu. Byly analyzovany vlastnosti a problemy spjate s nejcasteji pouzivanymi internimi reprezentacemi v soucasnych synteznich nastrojich. Dale byly predstaveny Booleovske site a moznosti jejich skalovani. Pozornost byla take venovana evolucni synteze logickych obvodu, s durazem na CGP (Kartezske Geneticke Programovani).

Byl navrzen novy pristup k evolucni optimalizaci kombinacnich obvodu. Extrahovanim casti obvodu o vhodnem poctu hradel a jejich naslednou optimalizaci pomoci CGP bylo dosazeno vetsi redukce poctu hradel v obvodech, nez tomu bylo pri optimalizaci celych obvodu pomoci CGP. K extrakci casti obvodu byly navrzeny tri metody. Prvni je zalozena na algoritmu vytvarejicim tzv. rezy. Tato metoda byla schopna optimalizovat kazdy testovaci kombinacni obvod a ve vetsine pripadu prekonala vysledky dosazene optimalizaci celych obvodu pomoci CGP. Druha extrakcni metoda je inspirovana windowing algoritmem, diky cemuz je mozne do vyberu zahrnout i hradla nachazejici se ve smeru vystupu korenoveho hradla vyberu, a ne jen hradla ve smeru jeho vstupu. Tato metoda vyrazne vylepsila vysledky dosazene pomoci metody zalozene na tvorbe rezu. Metoda taktez umoznuje, narozdil od metody prvni, extrahovat cast obvodu z jakehokoli jeho mista, aniz by doslo k vyberu prilis maleho poctu hradel nevhodneho k nasledne optimalizaci. Treti metoda je zalozena na principu vyhledavani rekonvergentnich cest v obvodech. Pritomnost rekonvergentni cesty ve vybrane casti obvodu zvysuje pravdepodobnost pritomnosti redundantnich hradel a tim i vyssi efektivitu navrhovaneho optimalizacniho procesu. Byla take navrzena a implementovana evolucni optimalizacni metoda zohlednujici zpozdeni obvodu. Touto metodou je mozne extrahovat a optimalizovat cast obvodu, aniz by celkove zpozdeni obvodu presahlo pozadovanou mez.

Pomoci principu lokalni evolucni optimalizace bylo dosazeno lepsich vysledku nez pri evolucni optimalizaci celych obvodu, cimz byla potvrzena hypoteza. Je vsak dulezite vhodne zvolit umisteni korenoveho hradla vyberu, vzhledem k jeho pozici v obvode. Taktez je treba vhodne zvolit nastaveni parametru evoluce, extrakce i optimalizacni metody jako celku (napr. pocet hradel v extrahovanych castech obvodu, pocet CGP generaci a pocet casti obvodu, ktere projdou optimalizaci).

Evolucni algoritmy, CGP, synteza, optimalizace, kombinacni obvody, zpozdeni.