Detail práce
Evolutionary Synthesis of Complex Digital Circuits
Tato dizertační práce prezentuje výzkum v oblasti evoluční optimalizace komplexních kombinačních obvodů. Práce začíná studiem existujících konvenčních i nekonvenčních přístupů k optimalizaci kombinačních obvodů. Byly analyzovány vlastnosti a problémy spjaté s nejčastěji používanými interními reprezentacemi v současných syntézních nástrojích. Dále byly představeny Booleovské sítě a možnosti jejich škálování. Pozornost byla také věnovaná evoluční syntéze logických obvodů, s důrazem na CGP (Kartézské Genetické Programovaní).
Byl navržen nový přístup k evoluční optimalizaci kombinačních obvodu. Extrahováním částí obvodu o vhodném poctu hradel a jejich následnou optimalizaci pomoci CGP bylo dosazeno vetší redukce poctu hradel v obvodech, než tomu bylo při optimalizaci celých obvodu pomoci CGP. K extrakci částí obvodu byly navrženy tři metody. První je založena na algoritmu vytvářejícím tzv. řezy. Tato metoda byla schopna optimalizovat každý testovací kombinační obvod a ve většině případu překonala výsledky dosažené optimalizaci celých obvodu pomoci CGP. Druha extrakční metoda je inspirovaná windowing algoritmem, díky čemuž je možné do vyberu zahrnout i hradla nacházející se ve směru výstupu kořenového hradla vyberu, a nejen hradla ve směru jeho vstupu. Tato metoda výrazně vylepšila výsledky dosažené pomoci metody založené na tvorbě řezu. Metoda taktéž umožňuje, narozdíl od metody první, extrahovat část obvodu z jakéhokoli jeho místa, aniž by došlo k vyberu příliš malého poctu hradel nevhodného k následné optimalizaci. Třetí metoda je založena na principu vyhledávaní rekonvergentnich cest v obvodech. Přítomnost rekonvergentni cesty ve vybrané části obvodu zvyšuje pravděpodobnost přítomnosti redundantních hradel a tím i vyšší efektivitu navrhovaného optimalizačního procesu. Byla také navržena a implementována evoluční optimalizační metoda zohledňující zpozdění obvodu. Touto metodou je možné extrahovat a optimalizovat část obvodu, aniž by celkové zpozděni obvodu přesáhlo požadovanou mez.
Pomoci principu lokální evoluční optimalizace bylo dosaženo lepších výsledků než při evoluční optimalizaci celých obvodů, čímž byla potvrzena hypotéza. Je vsak důležité vhodné zvolit umístěni kořenového hradla vyberu, vzhledem k jeho pozici v obvode. Taktéž je třeba vhodné zvolit nastaveni parametru evoluce, extrakce i optimalizační metody jako celku (např. počet hradel v extrahovaných částech obvodu, počet CGP generaci a počet částí obvodu, které projdou optimalizaci).
Evoluční algoritmy, CGP, syntéza, optimalizace, kombinační obvody, zpoždění.
@phdthesis{FITPT1056,
author = "Jitka Kocnov\'{a}",
type = "Diserta\v{c}n\'{i} pr\'{a}ce",
title = "Evolutionary Synthesis of Complex Digital Circuits",
school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
year = 2024,
location = "Brno, CZ",
language = "english",
url = "https://www.fit.vut.cz/study/phd-thesis/1056/"
}