ˇ I´ NAVRH ´ ˇ E ˇ EVOLUCN A OPTIMALIZACE APLIKACN ´ ´ SPECIFICKYCH MIKROPROGRAMOVYCH ARCHITEKTUR Miloˇs Minaˇr´ık DVI4, 2. roˇcn´ık, prezenˇcn´ı studium ˇ Skolitel: Luk´asˇ Sekanina Fakulta informaˇcn´ıch technologi´ı, Vysok´e uˇcen´ı technick´e v Brnˇe Boˇzetˇechova 2, 612 00 Brno
[email protected]
Abstrakt. Aplikaˇcnˇe specifick´e architektury lze v souˇcasnosti nal´ezt v cel´e rˇadˇe r˚uzn´ych syst´em˚u. K implementaci tˇechto syst´emu se cˇ asto vyuˇz´ıvaj´ı mikroprogramov´e architektury. N´avrh takov´ych mikroprogramov´ych architektur je vˇsak obecnˇe pomˇernˇe sloˇzitou u´ lohou. Tento cˇ l´anek se zab´yv´a moˇznostmi usnadnˇen´ı n´avrhu a optimalizace tˇechto architektur pomoc´ı evoluˇcn´ıch algoritm˚u. Jsou v nˇem nast´ınˇena moˇzn´a vyuˇzit´ı evoluce v t´eto oblasti, urˇceny c´ıle v´yzkumu a rozebr´any moˇznosti jejich splnˇen´ı. Na z´avˇer jsou shrnuty dosavadn´ı v´ysledky v´yzkumu a jejich zhodnocen´ı. Kl´ıcˇ ov´a slova. mikroarchitektura, mikroprogram, evoluce, optimalizace
´ 1 Uvod Masov´a v´yroba vestavˇen´ych syst´em˚u zapoˇcala v souvislosti s v´yrobou raket Minuteman vyr´abˇen´ych od roku 1961. Zde se d´ıky velk´emu objemu produkce podaˇrilo sn´ızˇ it cenu pouˇzit´eho integrovan´eho obvodu z 1000 dolar˚u na 3 dolary. D´ıky tomuto poklesu ceny zaˇcalo b´yt v´yhodn´e pouˇz´ıvat integrovan´e obvody v cel´e ˇradˇe dalˇs´ıch v´yrobk˚u a v souˇcasnosti jsou vestavˇen´a ˇreˇsen´ı z´akladem sˇirok´e sˇk´aly aplikac´ı. V zaˇca´ tc´ıch v´yvoje vestavˇen´ych syst´em˚u bylo nutn´e navrhovat cel´y syst´em ruˇcnˇe. Pozdˇeji zaˇcalo b´yt d´ıky zvyˇsuj´ıc´ı se hustotˇe integrace prvk˚u na cˇ ipu a sniˇzuj´ıc´ı se cenˇe v´yhodn´e nahrazovat mikrokontrol´ery obecn´ymi mikroprocesorov´ymi architekturami. Pro n´avrh vestavˇen´ych syst´em˚u zaloˇzen´ych na tˇechto architektur´ach existuje v souˇcasnosti sˇirok´a sˇk´ala n´astroj˚u. Existuj´ı vˇsak specifick´e aplikace vestavˇen´ych syst´em˚u, kter´e pouˇzit´ı mikroprocesorov´ych architektur neumoˇznˇ uj´ı napˇr´ıklad kv˚ui pˇr´ısn´ym poˇzadavk˚um na plochu nebo rychlost. Pˇri n´avrhu takov´eho syst´emu jiˇz cˇ asto nen´ı moˇzn´e pouˇz´ıt obecn´e postupy jako u mikroprocesorov´ych architektur. M´ısto toho je nutn´e navrhovat syst´em jiˇz od poˇca´ tku s ohledem na jeho konkr´etn´ı aplikaci a vyuˇz´ıvat jej´ı specifika. Tento u´ kol m˚uzˇ e b´yt pro n´avrh´aˇre velmi obt´ızˇ n´y. Je tedy snaha hledat postupy, kter´e by n´avrh nebo alespoˇn jeho cˇ a´ sti usnadnily. Jednou z takov´ych moˇznost´ı je pouˇzit´ı evoluˇcn´ıch technik. Jedn´a se o techniky inspirovan´e evoluc´ı organism˚u v pˇr´ırodˇe. Bˇehem posledn´ıch let se uk´azalo, zˇ e evoluˇcnˇe vytvoˇren´a ˇreˇsen´ı mohou v nˇekter´ych oblastech konkurovat ˇreˇsen´ım vytvoˇren´ym cˇ lovˇekem [1]. Pomoc´ı evoluˇcn´ıch technik bylo dokonce navrzˇ eno i nˇekolik patentovateln´ych vyn´alez˚u. Pouˇzit´ı tˇechto technik pro u´ pln´y n´avrh vestavˇen´eho syst´emu m˚uzˇ e b´yt pomˇernˇe obt´ızˇ n´e, ale lze je vyuˇz´ıt napˇr´ıklad pro jeho optimalizaci.
2
Souˇcasn´y stav rˇ eˇsen´e problematiky
V t´eto cˇ a´ sti je pops´ana problematika vysoko´urovˇnov´e synt´ezy obvod˚u, kter´a je v souˇcasnosti jednou z nejv´ıce pouˇz´ıvan´ych metod pro n´avrh obvod˚u. Je diskutov´an souˇcasn´y stav t´eto metody a moˇzn´e vyuˇzit´ı v t´ematu disertaˇcn´ı pr´ace. D´ale je diskutov´ana problematika evoluˇcn´ıch technik vˇcetnˇe v´ybˇeru pouˇziteln´ych variant.
2.1
ˇ a synt´eza ´ Vysokourov nov´
Vysoko´urovˇnov´a synt´eza (High Level Synthesis, HLS) se zab´yv´a pˇrevodem popisu syst´emu na vysok´e u´ rovni abstrakce na popis na niˇzsˇ´ı u´ rovni pˇri dodrˇzen´ı dan´ych omezen´ı [2]. Poˇca´ teˇcn´ı u´ rovn´ı m˚uzˇ e b´yt napˇr´ıklad behavior´aln´ı popis syst´emu na syst´emov´e nebo algoritmick´e u´ rovni. K tomuto popisu se zpravidla vyuˇz´ıvaj´ı procedur´aln´ı jazyky (napˇr´ıklad VHDL). C´ılem synt´ezy je obvykle pˇrevod syst´emu na popis na u´ rovni RT. Z t´eto u´ rovnˇe jiˇz lze syst´em pˇrev´est pomoc´ı zn´am´ych postup˚u. Kromˇe popisu chov´an´ı na algoritmick´e u´ rovni mohou b´yt souˇca´ st´ı zad´an´ı tak´e dan´a omezen´ı, kter´a mus´ı v´ysledn´y syst´em splˇnovat (napˇr´ıklad maxim´aln´ı plocha nebo pˇr´ıkon). Prvn´ım krokem HLS je pˇrevod poˇca´ teˇcn´ıho zad´an´ı na vnitˇrn´ı reprezentaci specifickou pro dan´y syntetizaˇcn´ı n´astroj. Vˇetˇsinou se vyuˇz´ıv´a grafov´a reprezentace obsahuj´ıc´ı graf datov´eho a ˇr´ıdic´ıho toku. Nad tˇemito grafy se n´aslednˇe prov´ad´ı r˚uzn´e vysoko´urovˇnov´e transformace, jeˇz maj´ı za c´ıl jejich optimalizaci ve smyslu rychlosti nebo prostorov´e n´aroˇcnosti. Jakmile je vytvoˇrena optimalizovan´a vnitˇrn´ı reprezentace, pˇrich´az´ı na ˇradu pl´anov´an´ı a pˇridˇelov´an´ı. Pl´anov´an´ı spoˇc´ıv´a v rozvrˇzen´ı d´ılˇc´ıch operac´ı do jednotliv´ych krok˚u, pˇriˇcemˇz krok je v synchronn´ıch syst´emech z´akladn´ı jednotkou, kter´a obvykle odpov´ıd´a hodinov´emu taktu. Pˇridˇelov´an´ı slouˇz´ı k pˇriˇrazen´ı hardwarov´ych zdroj˚u jednotliv´ym operac´ım a promˇenn´ym. Pl´anov´an´ı a pˇridˇelov´an´ı se prov´ad´ı jiˇz s ohledem na platformu, na n´ızˇ bude v´ysledn´y syst´em zaloˇzen. HLS obsahuje i v souˇcasn´e dobˇe ˇradu otevˇren´ych probl´em˚u, kter´e nejsou v souˇcasnosti st´ale ide´alnˇe vyˇreˇseny. To je d´ano pˇredevˇs´ım komplexnost´ı samotn´e synt´ezy, nebot’ je dok´az´ano, zˇ e mnoho d´ılˇc´ıch krok˚u jsou NP u´ pln´e probl´emy. Nalezen´ı optim´aln´ı obvodov´e realizace dan´e specifikace tedy nen´ı pˇri souˇcasn´ych moˇznostech v´ypoˇcetn´ı techniky snadn´y u´ kol.
2.2
Evoluˇcn´ı v´ypoˇcetn´ı techniky
Tyto techniky jsou inspirov´any evoluc´ı v pˇr´ırodˇe, jak ji popsal Charles Darwin a pozdˇeji teorie neodarwinismu vyuˇz´ıvaj´ıc´ı poznatk˚u molekul´arn´ı genetiky. Vyuˇz´ıv´an´ı tˇechto technik pro automatizovan´e ˇreˇsen´ı probl´em˚u zapoˇcalo v 50. letech minul´eho stolet´ı a od t´e doby bylo u´ spˇesˇnˇe pouˇzito v mnoha oblastech v´yzkumu. Evoluˇcn´ı techniky pracuj´ı s populaci jedinc˚u (kandid´atn´ıch ˇreˇsen´ı) vyskytuj´ıc´ıch se v urˇcit´em prostˇred´ı. Vliv prostˇred´ı na v´yvoj jedinc˚u je v evoluˇcn´ıch technik´ach zastoupen fitness funkc´ı, kter´a urˇcuje m´ıru pˇrizp˚usoben´ı jedince dan´emu prostˇred´ı. Stejnˇe jako v pˇr´ırodˇe maj´ı i v umˇel´e evoluci l´epe pˇrizp˚usoben´ı jedinci vyˇssˇ´ı sˇanci na pˇreˇzit´ı a rozmnoˇzen´ı. Za pˇredpokladu, zˇ e potomci tˇechto jedinc˚u zdˇed´ı“ vlast” nosti sv´ych rodiˇcu˚ zvyˇsuj´ıc´ı pravdˇepodobnost pˇreˇzit´ı, se bude cel´a populace postupnˇe zkvalitˇnovat. V evoluˇcn´ıch algoritmech se pˇri vytv´aˇren´ı n´asleduj´ıc´ı generace vyuˇz´ıvaj´ı genetick´e oper´atory, kter´e jsou obvykle opˇet inspirov´any pˇr´ırodou. Evoluˇcn´ı techniky maj´ı ˇradu r˚uzn´ych variant. Jednotliv´e varianty se liˇs´ı pˇredevˇs´ım pouˇzit´ymi evoluˇcn´ımi oper´atory, zp˚usobem selekce a velikost´ı populace. Pro t´ema disertaˇcn´ı pr´ace se jako nejvhodnˇejˇs´ı jev´ı genetick´e algoritmy a genetick´e programov´an´ı.
3
disertaˇcn´ı pr´ace
3.1
Motivace
V pˇredchoz´ı cˇ a´ sti byl shrnut aktu´aln´ı stav v oblasti n´avrhu obvod˚u a evoluˇcn´ıch technik. Bylo zjiˇstˇeno, zˇ e automatizovan´y n´avrh obvod˚u je v souˇcasnosti pomˇernˇe dobˇre prozkouman´ym odvˇetv´ım. Pˇresto vˇsak st´ale existuje cel´a ˇrada probl´em˚u, kter´e nejsou v t´eto oblasti uspokojivˇe vyˇreˇseny. Z hlediska t´ematu disertaˇcn´ı pr´ace je nejvˇetˇs´ım nedostatkem, zˇ e HLS se v posledn´ıch letech soustˇred’uje pˇredevˇs´ım na n´avrh velk´ych syst´em˚u (napˇr´ıklad v´ıceprocesorov´ych), pˇriˇcemˇz na n´astroje pro synt´ezu a optimalizaci menˇs´ıch obvod˚u (napˇr´ıklad jednoduˇssˇ´ıch mikroprogramov´ych architektur) je kladen minim´aln´ı d˚uraz. St´ale vˇsak existuj´ı aplikace, kde je nutn´e pouˇz´ıt aplikaˇcnˇe specifick´e integrovan´e obvody (ASIC), napˇr´ıklad kv˚uli striktn´ım poˇzadavk˚um na plochu nebo pˇr´ıkon v´ysledn´eho syst´emu. Typick´ym pouˇzit´ım tˇechto architektur je v´ypoˇcet netrivi´aln´ı funkce nad daty ze senzoru v pr˚umyslov´ych aplikac´ıch. Dalˇs´ı zkoumanou oblast´ı byly evoluˇcn´ı techniky. Z pohledu disertaˇcn´ı pr´ace jsou d˚uleˇzit´e techniky schopn´e usnadnit n´avrh HW a SW mikroprogramov´e architektury. Z hlediska n´avrhu digit´aln´ıch obvod˚u patˇr´ı mezi nejvhodnˇejˇs´ı kandid´aty genetick´e algoritmy a nˇekter´e varianty genetick´eho programov´an´ı, napˇr´ıklad kart´ezsk´e genetick´e programov´an´ı (CGP). Pro optimalizaci parametr˚u aplikaˇcnˇe specifick´ych architektur lze pouˇz´ıt evoluˇcn´ı strategie a genetick´e algoritmy. Pˇri n´avrhu SW lze vyuˇz´ıt GP s urˇcit´ymi u´ pravami. K optimalizaci parametr˚u programu lze pouˇz´ıt evoluˇcn´ı programov´an´ı a genetick´e algoritmy. V oblasti jednoduˇssˇ´ıch aplikaˇcnˇe specifick´ych mikroprogramov´ych architektur je cˇ asto nutn´e prov´adˇet sloˇzitˇejˇs´ı v´ypoˇcty za pouˇzit´ı omezen´ych HW prostˇredk˚u. V tomto pˇr´ıpadˇe m˚uzˇ e b´yt v´yhodn´e pouˇz´ıt mikroprogramovou architekturu, kter´a umoˇznˇ uje na z´akladˇe definovan´eho mikroprogramu opakovanˇe vyuˇz´ıvat existuj´ıc´ı funkˇcn´ı jednotky. V´yhodou tohoto pˇr´ıstupu je, zˇ e mikroprogram lze v pˇr´ıpadˇe potˇreby zmˇenit tak, aby obvod prov´adˇel jinou funkci, kterou lze vyˇc´ıslit pomoc´ı dostupn´ych funkˇcn´ıch jednotek. Poˇzadovanou mikroprogramovou architekturu m˚uzˇ e b´yt moˇzn´e navrhnout evoluˇcnˇe. Na z´akladˇe zkuˇsenost´ı s evoluˇcn´ım n´avrhem obvod˚u realizuj´ıc´ıch iteraˇcn´ı algoritmy [3] se vˇsak lze domn´ıvat, zˇ e cel´y n´avrh architektury pomoc´ı evoluˇcn´ıch technik je v souˇcasn´e dobˇe moˇzn´y pouze u architektur menˇs´ıho rozsahu. Pˇri optimalizaci obvod˚u se vˇsak evoluˇcn´ı techniky uk´azaly jako pomˇernˇe dobˇre pouˇziteln´e. S ohledem na tyto skuteˇcnosti lze formulovat pracovn´ı hypot´ezu n´asleduj´ıc´ım zp˚usobem. 3.1.1
Hypot´eza
Pomoc´ı evoluˇcn´ı optimalizace mikroprogramu a mikroarchitektury lze vylepˇsit zvolen´e parametry (napˇr. minimalizovat plochu) aplikaˇcnˇe specifick´eho syst´emu menˇs´ıho rozsahu (typicky realizuj´ıc´ıho speci´aln´ı aritmetick´e operace)vyuˇz´ıvaj´ıc´ıho mikroprogramovou architekturu vzhledem ke st´avaj´ıc´ım ˇreˇsen´ım pouˇz´ıvan´ym v pr˚umyslov´ych aplikac´ıch. Souˇcasnˇe nebudou podstatnˇe zhorˇseny ostatn´ı parametry.
4
C´ıle disertaˇcn´ı pr´ace 1. Vytvoˇrit model umoˇznˇ uj´ıc´ı specifikovat ˇreˇsen´y probl´em pomoc´ı vstupnˇe-v´ystupn´ıch z´avislost´ı, omezuj´ıc´ıch podm´ınek a dalˇs´ıch poˇzadavk˚u na funkci v´ysledn´e architektury tak, aby moˇznosti specifikace probl´emu pokr´yvaly co nejv´ıce pˇr´ıpad˚u pouˇzit´ı. 2. Vytvoˇrit simul´ator, pomoc´ı nˇejˇz lze ovˇeˇrit spr´avnou funkci mikroprogramov´e architektury. 3. Vytvoˇrit platformu pro optimalizaci mikroprogramov´ych architektur pomoc´ı evoluˇcn´ıch technik. 4. Ovˇeˇrit funkˇcnost navrˇzen´e platformy pˇri optimalizaci pr˚umyslov´ych aplikac´ı. 5. Na z´akladˇe z´ıskan´ych v´ysledk˚u vytvoˇrit co nejobecnˇejˇs´ı metodiku popisuj´ıc´ı, jak prov´adˇet optimalizaci jednotliv´ych cˇ a´ st´ı syst´em˚u vyuˇz´ıvaj´ıc´ıch mikroprogramov´e architektury.
5 5.1
˚ Zpusob rˇ eˇsen´ı Model probl´emu
Specifikaci probl´emu lze rozdˇelit na dvˇe cˇ a´ sti. Prvn´ı cˇ a´ st´ı je specifikace chov´an´ı mikroprogramov´e architektury jako celku v r´amci syst´emu, v nˇemˇz je obsaˇzena. Z tohoto pohledu lze na mikroarchitekturu nahl´ızˇ et jako na cˇ ernou skˇr´ınˇ ku, do kter´e lze pˇriv´adˇet vstupy a z´ısk´avat z n´ı v´ystupy. Vztah mezi vstupy a v´ystupy by mˇelo b´yt moˇzn´e urˇcit r˚uzn´ymi zp˚usoby, napˇr´ıklad tabulkou hodnot nebo funkˇcn´ım pˇredpisem. Druh´a cˇ a´ st specifikace urˇcuje intern´ı podobu mikroprogramov´e architektury. Nˇekter´e obvodov´e prvky mus´ı b´yt v architektuˇre obsaˇzeny, jin´e mohou b´yt voliteln´e podle dan´eho pouˇzit´ı. V r´amci t´eto cˇ a´ sti specifikace lze urˇcit funkˇcn´ı jednotky (moduly), kter´e mohou b´yt pro implementaci pouˇzity, a jejich poˇcet. T´ımto zp˚usobem lze v´yslednou architekturu omezit napˇr´ıklad tak, aby neobsahovala v´ıce neˇz dvˇe sˇc´ıtaˇcky. Omezen´ı poˇctu modul˚u lze zadat tak´e cenovou funkc´ı.
5.2
Simul´ator
Hlavn´ım poˇzadavkem na simul´ator je, aby dok´azal simulovat vˇsechny architektury vyhovuj´ıc´ı zaveden´emu modelu. Vstupem simul´atoru jsou kromˇe simulovan´e architektury tak´e cˇ asov´e pr˚ubˇehy vstup˚u, kter´e jsou nutn´e pro simulaci vnˇejˇs´ıch podm´ınek architektury (tedy jej´ıho zapojen´ı ve v´ysledn´em syst´emu). Nejd˚uleˇzitˇejˇs´ım v´ystupem simul´atoru jsou bezesporu cˇ asov´e pr˚ubˇehy v´ystup˚u, u nichˇz lze n´aslednˇe ovˇeˇrit, zda splˇnuj´ı cˇ asov´e specifikace dan´e v zad´an´ı. Pokud se jedn´a o syst´em s koneˇcn´ym poˇctem kombinac´ı vstup˚u, lze t´ımto zp˚usobem v´yslednou architekturu i validovat. Dalˇs´ımi v´ystupy mohou b´yt r˚uzn´e informace usnadˇnuj´ıc´ı optimalizaci syst´emu. Mezi tyto informace lze zaˇradit napˇr´ıklad u´ daje o vyuˇzit´ı jednotliv´ych modul˚u bˇehem simulace. Na z´akladˇe tˇechto u´ daj˚u lze n´aslednˇe rozhodnout, zda by bylo vhodn´e do syst´emu pˇridat nˇejak´y modul nebo jej naopak ze syst´emu odstranit. Kromˇe toho m˚uzˇ e simul´ator poskytovat tak´e informace slouˇz´ıc´ı k ladˇen´ı, protoˇze bˇehem optimalizace architektury se mohou vyskytnout probl´emy, kter´e v p˚uvodn´ı architektuˇre nebyly. Napˇr´ıklad pˇri optimalizaci poˇctu pouˇzit´ych registr˚u se m˚uzˇ e st´at, zˇ e se dva moduly pokus´ı zapisovat v´ysledek do stejn´eho registru. Tyto situace je nutn´e sledovat a vhodn´ym zp˚usobem na nˇe reagovat.
5.3
Evoluˇcn´ı platforma
Z´akladem funkˇcnosti evoluˇcn´ı platformy jsou pouˇzit´e evoluˇcn´ı techniky. Techniky vhodn´e pro evoluˇcn´ı optimalizaci architektury a mikroprogramu byly pops´any v cˇ a´ sti 2.2. V´ybˇer konkr´etn´ıch technik bude proveden na z´akladˇe praktick´ych v´ysledk˚u jejich pouˇzit´ı na jednoduˇssˇ´ıch architektur´ach. Jedn´ım z nejvˇetˇs´ıch probl´em˚u, kter´e lze oˇcek´avat v souvislosti s optimalizac´ı mikroprogramov´e architektury, je prov´azanost architektury s programem. Pokud se hardwarov´a cˇ a´ st nezmˇen´ı, lze programovou cˇ a´ st zpravidla optimalizovat nez´avisle. Naopak zmˇeny v hardwarov´e cˇ a´ sti vˇetˇsinou vyˇzaduj´ı zmˇenu programu. Dalˇs´ım aspektem evoluˇcn´ı platformy je moˇznost ovlivnˇen´ı parametr˚u dan´e evoluˇcn´ı techniky. Evoluˇcn´ı platforma by mˇela umoˇznˇ ovat pouˇzit´ı pevnˇe dan´ych hodnot nebo zmˇenu tˇechto pravdˇepodobnost´ı podle aktu´aln´ı situace. Toho lze dos´ahnout pomoc´ı uˇzivatelem definovan´e funkce, kter´a se bude volat vˇzdy mezi generacemi a nastavovat parametry evoluce. Z v´ysˇe popsan´ych skuteˇcnost´ı je zˇrejm´e, zˇ e pˇri hled´an´ı ˇreˇsen´ı se m˚uzˇ e mˇenit cel´a ˇrada parametr˚u architektury. Jedn´a se tedy o v´ıcekriteri´aln´ı optimalizaci. Pro ˇreˇsen´ı v´ıcekriteri´aln´ıch optimalizac´ı existuje ˇrada metod, napˇr. NSGA–II (Nondominated Sorting Genetic Algorithm) [4]. Pomoc´ı jedn´e z tˇechto metod budou nalezena Pareto–optim´aln´ı ˇreˇsen´ı, kter´ych m˚uzˇ e existovat v´ıce. Z tˇechto ˇreˇsen´ı bude n´aslednˇe tˇreba vybrat nejvhodnˇejˇs´ı ˇreˇsen´ı pro dan´e pouˇzit´ı syst´emu.
5.4
Ovˇerˇ en´ı funkˇcnosti
Jakmile bude syst´em implementov´an, bude tˇreba jej ovˇerˇit na jendoduˇssˇ´ıch i sloˇzitˇejˇs´ıch obvodech. Zpoˇca´ tku se bude s nejvˇetˇs´ı pravdˇepodobnost´ı jednat pˇredevˇs´ım o obvody realizuj´ıc´ı r˚uzn´e iteraˇcn´ı algoritmy. Pozdˇeji budou provedeny pokusy o implementaci architektur, kter´e jsou re´alnˇe nasazen´e v pr˚umyslov´ych aplikac´ıch. Po ovˇeˇren´ı spr´avn´e funkˇcnosti obvodu bude provedeno srovn´an´ı s existuj´ıc´ım pr˚umyslov´ym ˇreˇsen´ım a v´ysledky budou vyhodnoceny.
5.5
Vytvoˇren´ı metodiky
Pokud budou v´ysledky ovˇerˇen´ı funkˇcnosti uspokojiv´e, bude potvrzena i hypot´eza. V tom pˇr´ıpadˇe by mˇelo b´yt moˇzn´e vytvoˇrit obecnou metodiku pro optimalizaci mikroprogramov´ych architektur pomoc´ı evoluˇcn´ıch technik. Tato metodika by mˇela poskytnout n´avod podrobnˇe popisuj´ıc´ı jednotliv´e kroky nutn´e pro u´ spˇesˇnou optimalizaci. Bude v n´ı pops´an zp˚usob vytvoˇren´ı modelu architektury, kter´a se m´a optimalizovat, a nastaven´ı parametr˚u pouˇzit´ych evoluˇcn´ıch technik.
6 6.1
Dosavadn´ı v´ysledky Evoluˇcn´ı n´avrh iteraˇcn´ıch algoritmu˚ pomoc´ı CGP
Na toto t´ema byl v r´amci doktorsk´eho studia publikov´an konferenˇcn´ı cˇ l´anek zab´yvaj´ıc´ı se n´avrhem ´ iteraˇcn´ıch algoritm˚u pomoc´ı upraven´e varianty CGP [3]. Uprava CGP spoˇc´ıvala v iteraˇcn´ı aplikaci fenotypu s c´ılem nal´ezt program aproximuj´ıc´ı c´ılovou funkci, kter´a poˇc´ıt´a v´ysledek i + 1. iterace pomoc´ı v´ysledk˚u i. iterace. S takto upravenou variantou CGP bylo provedeno nˇekolik experiment˚u. Bˇehem tˇechto experiment˚u byly nalezeny napˇr´ıklad algoritmy pro Newtonovo iteraˇcn´ı dˇelen´ı, Goldschmidtovo dˇelen´ı a Euklid˚uv algoritmus pro urˇcen´ı nejvˇetˇs´ıho spoleˇcn´eho dˇelitele. Z experiment˚u, kter´e nevedly k u´ spˇesˇn´emu ˇreˇsen´ı byl nejv´yznamnˇejˇs´ı evoluˇcn´ı n´avrh algoritmu CORDIC, kde se uk´azalo, zˇ e pouˇzit´a evoluˇcn´ı technika neumoˇznˇ uje souˇcasnˇe vyv´ıjet v´ıce vˇetv´ı v´ypoˇctu.
6.2
Model a simul´ator
Jak bylo pops´ano v cˇ a´ sti 5.2, simul´ator mus´ı b´yt schopen simulovat vˇsechny architektury odpov´ıdaj´ıc´ı n´avrhu modelu. V´yvoj simul´atory tedy silnˇe z´avis´ı na v´yvoji modelu. Tato z´avislost je vˇsak oboustrann´a, nebot’ bˇehem v´yvoje simul´atoru se mohou vyskytnout probl´emy, kter´e nelze vyˇreˇsit jinak, neˇz zmˇenou modelu architektury. Z toho d˚uvodu prob´ıh´a v r´amci disertaˇcn´ı pr´ace v´yvoj modelu architektury a simul´atoru soubˇezˇ nˇe a stejn´ym zp˚usobem je pops´an v t´eto cˇ a´ sti. Uveden´a architektura vych´az´ı z potˇreb praxe a pˇredstavuje typick´e zad´an´ı (ve smyslu sloˇzitosti obvodu), kter´ym se disertaˇcn´ı pr´ace bude zab´yvat. Zjednoduˇsen´e sch´ema modelu architektury je zn´azornˇeno na obr. 1. K popisu struktury architektury je nutn´e urˇcit poˇcet registr˚u, pouˇzit´e moduly, propojen´ı jednotliv´ych cˇ a´ st´ı, vstupy a v´ystupy architektury a mikroinstrukˇcn´ı sadu. Registr˚u m˚uzˇ e b´yt v architektuˇre obsaˇzen libovoln´y poˇcet, pˇriˇcemˇz kaˇzd´y z tˇechto registr˚u m˚uzˇ e m´ıt libovolnou sˇ´ıˇrku. Pˇri urˇcov´an´ı modul˚u pouˇzit´ych v mikroarchitektuˇre lze vyuˇz´ıt pˇreddefinovan´e moduly, u nichˇz lze nastavit bitov´e sˇ´ıˇrky vstup˚u a v´ystup˚u. Pokud poˇzadovan´y modul neexistuje, lze jej snadno vytvoˇrit jako novou tˇr´ıdu. Po specifikov´an´ı modul˚u je nutn´e urˇcit propojen´ı registr˚u s jejich vstupy a jejich v´ystup˚u s registry. Na tato propojen´ı nejsou kladena zˇ a´ dn´a omezen´ı, i kdyˇz urˇcit´e kombinace mohou pˇri simulaci zp˚usobit konflikty. Z pohledu simul´atoru nen´ı propojen´ı ch´ap´ano jako pole multiplexor˚u (j´ımˇz je zpravidla ve v´ysledn´e architektuˇre realizov´ano), ale pouze jako pˇredpis urˇcuj´ıc´ı, jak se maj´ı hodnoty pˇren´asˇet mezi registry a moduly. Dalˇs´ımi povinn´ymi parametry architektury jsou specifikace poˇctu a bitov´ych sˇ´ıˇrek vstup˚u a v´ystup˚u a mikroinstrukˇcn´ı sady. Mikroinstrukˇcn´ı sada obsahuje mikroinstrukce, kter´e modelovan´a architektura dok´azˇ e prov´adˇet.
Dekodér Moduly
Reg2 Reg3 Reg4
MUXs
MUXs
Reg1
Reg5 Reg6
Obr´azek 1: Sch´ema modelu architektury. Po urˇcen´ı v´ysˇe uveden´ych parametr˚u je model hardwarov´e cˇ a´ sti mikroprogramov´e architektury u´ pln´y. Dalˇs´ım krokem je urˇcen´ı programov´e cˇ a´ sti, kter´a je tvoˇrena programem sloˇzen´ym z instrukc´ı definovan´ych mikroinstrukˇcn´ı sadou. V simul´atoru je program realizov´an line´arn´ım blokem pamˇeti, z nˇejˇz se postupnˇe naˇc´ıtaj´ı jednotliv´e instrukce. Definov´an´ım programu je dokonˇcena specifikace modelu architektury. Pro simulaci je vˇsak tˇreba urˇcit prostˇred´ı, v nˇemˇz bude architektura pracovat. To je realizov´ano definov´an´ım cˇ asov´ych pr˚ubˇeh˚u vstup˚u. Tyto pr˚ubˇehy lze urˇcit tabulkou hodnot nebo funkˇcn´ım pˇredpisem. Jakmile jsou urˇceny vˇsechny v´ysˇe uveden´e cˇ a´ sti, lze prov´est simulaci cˇ innosti architektury. V´ysledkem t´eto simulace jsou cˇ asov´e pr˚ubˇehy v´ystup˚u. Kromˇe tˇechto pr˚ubˇeh˚u jsou k dispozici dalˇs´ı informace zjiˇstˇen´e bˇehem simulace, napˇr´ıklad detekovan´e kolize, vyuˇzit´ı zdroj˚u architektury atd.
7
Z´avˇer
V tomto dokumentu byla prezentov´ana problematika evoluˇcn´ıho n´avrhu a optimalizace mikroprogramov´ych architektur. Byl pops´an souˇcasn´y stav v oblasti automatizovan´eho n´avrhu obvod˚u a vyuˇzit´ı evoluˇcn´ıch technik. D´ale byly zformulov´any c´ıle disertaˇcn´ı pr´ace a navrˇzeny moˇzn´e zp˚usoby ˇreˇsen´ı jednotliv´ych c´ıl˚u. Nˇekter´e z tˇechto c´ıl˚u jsou v souˇcasn´e dobˇe jiˇz splnˇeny nebo rozpracov´any. Doposud nebyly zjiˇstˇeny zˇ a´ dn´e skuteˇcnosti nasvˇedˇcuj´ıc´ı tomu, zˇ e by nebylo moˇzn´e splnit vˇsechny c´ıle.
Podˇekov´an´ı Tento cˇ l´anek byl vypracov´an v r´amci projekt˚u Pokroˇcil´e bezpeˇcn´e, spolehliv´e a adaptivn´ı IT (FIT-S-11-1) a Natural Computing on Unconventional Platforms (GAP103/10/1517).
Reference [1] Koza, J. R.: Human-competitive results produced by genetic programming, Genetic Programming and Evolvable Machines, 2010, Vol. 11, pp. 251–284 [2] Coussy, P., Morawiec, A.: High-Level Synthesis: from Algorithm to Digital Circuit, 2008, ISBN 978-1-40-208587-1 [3] Minarik, M., Sekanina, L.: Evolution of iterative formulas using Cartesian genetic programming, Proceedings of the 15th international conference on Knowledge-based and intelligent information and engineering systems - Volume Part I, 2011, pp. 11–20, LNCS 6881 [4] Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 2002, Vol 6, pp. 182–197
