Új módszer algoritmusok VHDL-be funkcionális nyelvből kiindulva

Budapesti M˝ uszaki ´ es Gazdas´ agtudom´ anyi Egyetem Villamosmérnöki és Informatikai Kar Ir´ any´ıt´ astechnika és Informatika Tanszék

´ m´ Uj odszer algoritmusok VHDL-be to en˝ o transzform´ aci´ oj´ ara Haskell ¨rt´ funkcion´ alis nyelvb˝ ol kiindulva TDK Dolgozat

Kész´ıtette

Konzulens

Suba Gergely

dr. Arató Péter

2011. október 28.

Tartalomjegyz´ ek K¨ osz¨ onetnyilv´ an´ıt´ as

2

Kivonat

3

Bevezet˝ o

4

1. A ford´ıt´ as ki- ´ es bemenete

8

1.1. A Haskell nyelv és saj´ atoss´ agai . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.1.1. Lambda-kalkulus . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.1.2. T´ıpusrendszer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2. A Haskell GHC ford´ıt´ o f¨ obb tulajdonságai . . . . . . . . . . . . . . . . . . . 12 1.2.1. K¨ oztes reprezent´ aci´ o - a Core nyelv . . . . . . . . . . . . . . . . . . . 12 1.2.2. Primit´ıv t´ıpusok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.3. F¨ uggvénybehelyettes´ıtés . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3. A VHDL nyelv és saj´ atoss´ agai . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2. A ford´ıt´ asi m´ odszer alapelvei ´ es megval´ os´ıt´ asa

19

2.1. Az egyes modulok interfészei . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.1. Bemeneti forr´ ask´ od . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.2. Elemi m˝ uveleti gr´ af . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.1.3. Kimeneti hardverle´ır´ as . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.1.4. M˝ uvelethalmaz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2. Forr´ ask´ od ford´ıt´ asa elemi m˝ uveleti gráfra . . . . . . . . . . . . . . . . . . . 30 2.2.1. Forr´ ask´ od magasszint˝ u feldolgozása . . . . . . . . . . . . . . . . . . . 32 2.2.2. El´ agaz´ asok ´ atalak´ıt´ asa . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.2.3. Iter´ aci´ ok ´ atalak´ıt´ asa . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.2.4. Alkalmaz´ asok ´ atnevezése . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.2.5. H´ıv´ asi f´ ara t¨ ortén˝ o´ atalak´ıtás . . . . . . . . . . . . . . . . . . . . . . 37 2.2.6. Faegyszer˝ us´ıtés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.2.7. Elemi m˝ uveleti gr´ afra történ˝o átalak´ıtás . . . . . . . . . . . . . . . . 41 2.3. Elemi m˝ uveleti gr´ af ford´ıt´ asa hardverle´ıró nyelvre . . . . . . . . . . . . . . . 42 2.4. Alap m˝ uvelethalmaz defini´ al´ asa . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.4.1. A m˝ uvelethalmazok kötelez˝o elemei . . . . . . . . . . . . . . . . . . 43 2.4.2. Egyszer˝ u alapm˝ uveletek . . . . . . . . . . . . . . . . . . . . . . . . . 45 ii

3. A m´ odszer kiterjeszt´ ese t¨ obbsebess´ eg˝ u (multi-rate) probl´ em´ akra 48 3.1. T¨ obbsebesség˝ u adatfolyamok a ford´ıtás interfészein . . . . . . . . . . . . . . 49 3.1.1. T¨ obbsebesség˝ u elemi m˝ uveleti gráf . . . . . . . . . . . . . . . . . . . 49 3.1.2. A bemeneti forr´ askód . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.1.3. Kimeneti hardverle´ırás . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.2. A ford´ıt´ asi algoritmus kiterjesztése . . . . . . . . . . . . . . . . . . . . . . . 55 3.2.1. MapConversion transzformáció . . . . . . . . . . . . . . . . . . . . . 56 3.2.2. A hierarchia automatikus felép´ıtése . . . . . . . . . . . . . . . . . . . 56 3.3. A m˝ uvelethalmaz kiv˝ ov´ıtése . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.3.1. Stream m˝ uveletek . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.3.2. T¨ omb m˝ uveletek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4. A m´ odszer gyakorlati alkalmaz´ asa mintafeladatokon

61

4.1. PID szab´ alyoz´ o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.1.1. A ford´ıt´ as lépései . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.1.2. Szimul´ aci´ o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.2. MP3 dek´ odol´ o algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.2.1. VHDL szimul´ aci´ os eredmények . . . . . . . . . . . . . . . . . . . . . 75 5. Tov´ abbfejleszt´ esi lehet˝ os´ egek

76

5.1. Optimaliz´ al´ asi lépések . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.2. Egyebek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 ¨ 6. Osszefoglal´ as

78

Irodalomjegyz´ ek

83

Fu ek ¨ ggel´

84

F.1. Stream m˝ uveletek VHDL kódja . . . . . . . . . . . . . . . . . . . . . . . . . 84 F.2. T¨ omb m˝ uveletek VHDL kódja . . . . . . . . . . . . . . . . . . . . . . . . . . 86 F.3. Az Haskell nyelven implementált szintézis program ford´ıtói naplója . . . . . 88

iii

´ NYILATKOZAT HALLGATOI Alul´ırott Suba Gergely, hallgató kijelentem, hogy ezt a TDK dolgozatot meg nem engedett seg´ıtség nélk¨ ul, saj´ at magam kész´ıtettem, csak a megadott forrásokat (szakirodalom, eszköz¨ ok stb.) haszn´ altam fel. Minden olyan részt, melyet szó szerint, vagy azonos értelemben, de ´ atfogalmazva m´ as forrásból átvettem, egyértelm˝ uen, a forrás megadásával megjel¨ oltem. Hozz´ aj´ arulok, hogy a jelen munkám alapadatait (szerz˝o(k), c´ım, angol és magyar nyelv˝ u tartalmi kivonat, kész´ıtés éve, konzulens(ek) neve) a BME VIK nyilvánosan hozzáférhet˝ o elektronikus form´ aban, a munka teljes szövegét pedig az egyetem bels˝o hálózatán kereszt¨ ul (vagy autentik´ alt felhaszn´ al´ ok sz´ amára) közzétegye. Kijelentem, hogy a beny´ ujtott munka és annak elektronikus verzi´ oja megegyezik.

Budapest, 2011. okt´ ober 28.

Suba Gergely hallgató

K¨ osz¨ onetnyilv´ an´ıt´ as Szeretnék k¨ osz¨ onetet mondani konzulensemnek, Dr. Arató Péternek a TDK dolgozat kész´ıtése során ny´ ujtott tan´ acsokért és azért, hogy kérdéseimmel bármikor fordulhattam hozzá.

A jelen dolgozatot t´ amogatta a 72611 sz. Feladatf¨ ugg˝o többprocesszoros rendszerek ” tervezése” c´ım˝ u OTKA kutat´ asi téma az Irány´ıtástechnika és Informatika Tanszéken.

2

Kivonat Bár egyre nagyobb a hagyom´ anyos, processzoros rendszerek m˝ uködési sebessége, kifejezetten id˝ oigényes feladatok, bonyolult biológiai, fizikai szám´ıtások sz¨ ukségessé teszik, hogy az által´ anos cél´ u processzorokn´ al hatékonyabb hardverstrukt´ urákat, esetenként célhardvereket fejlessz¨ unk a probléma megoldására. Ezeket a hardverstrukt´ urákat általában hardverle´ır´ o nyelveken (HDL) implementálják. A matematikusok, informatikusok el˝ott ezek a nyelvek ´ altal´ aban kevésbé ismertek, ˝ok az algoritmusokat általános programnyelveken fogalmazz´ ak meg. A hardverle´ır´ o és általános programnyelvek nagyon eltér˝o módon használhat´ oak (a két m´ odszert szinte szakadék választja el egymástól), és között¨ uk az átjár´ as lehet˝osége csekély. Az ´ atj´ ar´ as megoldására jelenleg is számos kutatás folyik, ezek a módszerek rendk´ıv¨ ul lényeges részét képezik az u ń. rendszerszint˝ u szintézisnek. Egy funkcion´ alis nyelvb˝ ol kiinduló hardverszintézisnek több el˝onye is van a hardverle´ıró nyelven t¨ ortén˝ o implement´ aláshoz képest. A fejlesztés gyorsabb a magasabb szint˝ u absztrakci´ onak k¨ osz¨ onhet˝ oen, az algoritmus változtatása esetén a hardvermódos´ıtás pedig könnyebben kivitelezhet˝ o, mert egy funkcionális nyelvi program az algoritmusból közvetlen¨ ul és j´ oval egyszer˝ ubben képezhet˝o, mind egy HDL le´ırás. A HDL-re való ford´ıtás pedig a jelen dolgozatban kifejlesztett ford´ıtóprogrammal el˝onyösen automatizálható. A funkcionális nyelvi programk´ od futtatható PC-n, ezáltal könnyen tesztelhet˝o, ezzel szemben a hardverle´ır´ o nyelvek bonyolult szimulációval érik el ezt a funkciót, ahol ráadásul a be- és kimeneteket digit´ alis jelszintekként kezelik, tovább bonyol´ıtva ezzel a tesztelést. Fentiek alapj´ an a TDK dolgozatomban egy olyan eljárás (ford´ıtóprogram) kidolgozása, implement´ al´ asa és tesztelése a célom, amelyek kiindulópontja a funkcionális nyelven le´ırt kód. A funkcion´ alis nyelvek k¨ oz¨ ul a Haskell nyelvre koncentrálok, ami egy igen lend¨ uletesen fejl˝od˝o, a kutat´ omunk´ at el˝ ony¨ osen támogató nyelv. Az elj´ ar´ as f˝ o el˝ onye, hogy automatikusan generálja a bizonyos megkötésekkel rendelkez˝ o Haskell nyelvi k´ odb´ ol az FPGA-ba szintetizálható VHDL le´ırást. A ford´ıtási folyamatba beilleszthet¨ unk ak´ ar egy olyan pipeline optimalizáló fokozatot, mint pl. az Irány´ıtástechnika és Informatika Tanszéken fejlesztett PIPE tervez˝o programrendszert. Az elj´ ar´ as hatékonys´ ag´ at az MP3 dekódoló algoritmus részletén szemléltetem.

3

Bevezet˝ o TDK dolgozatom sor´ an olyan m´ odszert dolgoztam ki, amely egy bizonyos megkötésekkel rendelkez˝ o funkcion´ alis nyelven le´ırt algoritmust hardverle´ıró nyelvre ford´ıt, ezáltal egy kereskedelmi forgalomban kaphat´ o FPGA-s fejleszt˝okörnyezetet seg´ıtség¨ ul véve a magasszint˝ u le´ır´ asb´ ol konkrét hardvermegvalós´ıtást kaphatunk. Mindezt ford´ıtóprogramként implementáltam, amellyel a m´ odszer gyakorlati alkalmazhatóságát demonstrálom. Sokszor el˝ ofordul´ o igény, hogy egy adott alkalmazást hardverként implementáljunk. Bizonyos problém´ ak esetén ´ıgy sokkal hatékonyabb és nagyobb sebesség˝ u feladatvégrehajtást érhet¨ unk el, egy PC fogyaszt´ as´ anak t¨ oredéke árán. Máskor konkrét cél lehet a hardverben történ˝o futtat´ as, mert az algoritmus egy nagyobb hardverrendszer része, és nem szeretnénk PC-t csatlakoztatni a rendszerhez. A rendszerszint˝ u szintézis és a hardver-szoftver egy¨ uttes szintézis során sz¨ ukséges, hogy legal´ abb részfeladatokat hardverben implementáljunk. Egy algoritmust ´ altal´ aban sokkal k¨ onnyebb magasabb szint˝ u, szoftveres nyelveken megfogalmazni, mint hardverle´ır´ asként. A matematikusok és informatikusok világképéhez is közelebb állnak a magasabb szint˝ u nyelvek. A dolgozatom a szoftveres és hardveres néz˝opont k¨ ulönbségeinek ´ athidal´ as´ ara ad seg´ıtséget; az eljárás magasszint˝ u nyelvi le´ırásból automatikusan gener´ alja a hardverhez közeli VHDL kódot. A magasszint˝ u nyelveken bel¨ ul a funkcionális megközel´ıtésre koncentrálok. Ezek a nyelvek (pl. Erlang, SML, Haskell) a deklarat´ıv nyelvcsaládba tartoznak, és legf˝oképpen abban k¨ ulönböznek az imperat´ıv nyelvekt˝ ol (ilyen pl. a C, Java), hogy explicit vezérlésfolyamot nem definiálnak. Ez azt jelenti, hogy egy deklarat´ıv nyelv azt ´ırja le, mit kell végrehajtania az algoritmus adott lépésének, nem azt, hogy ezeket pontosan hogyan, milyen sorrendben kell tennie. Ez a tulajdons´ aga kényelmessé teszi ezeket a nyelveket arra, hogy hardvergenerálás bemeneteként haszn´ aljuk, mert explicit vezérlésáramlás nélk¨ ul a párhuzamosan futtatható részek a le´ır´ asb´ ol egyszer˝ uen adódnak. A funkcion´ alis nyelvek a hardverben történ˝o implementálás szempontjából rendelkeznek egyéb fontos el˝ ony¨ okkel is. Kiz´ arják pl. a globális változók definiálását, tehát nem hozhatunk létre olyan v´ altoz´ ot, aminek az értékét több f¨ uggvény törzséb˝ol is megváltoztathatjuk. Még ennél is nagyobb el˝ ony, hogy minden változó csak egyszer kaphat értéket, amit életciklusa végéig meg˝ oriz. Az ilyen t´ıpus´ u változó könnyen reprezentálható bitenként egy flip-floppal, vagy nagyon egyszer˝ u esetben bitenként egy vezetékkel. Ezeket a nyelveket nagyon sokszor használják általános, szoftveres környezetben. Az el˝onyei szembet˝ un˝ oek gr´ afok felép´ıtésekor ás bejárásakor, láncolt listák kezelésekor, de más algoritmusok esetében is van létjogosultságuk. A tiszta funkcionális programozást követve

4

nagyon j´ ol u ´jrahaszn´ alhat´ o, kevesebb hibalehet˝oséget magában foglaló programokat és modulokat fejleszthet¨ unk. A funkcion´ alis nyelv és hardverle´ırás közötti ford´ıtás kutatásának manapság megvan a kell˝o létjogosults´ aga. M´ıg imperat´ıv nyelvr˝ol, pontosabban C-r˝ol ford´ıtó HLS (magasszint˝ u logikai szintézis) programok kereskedelemi forgalomban is kaphatóak ([1],[2],[3]), ugyanez nem mondhat´ o el a funkcion´ alis nyelvek terén. Matematikusoknak kifejezetten el˝ony¨ os lehet funkcion´ alis nyelvet haszn´ alni, mert a világkép¨ ukhöz sokkal közelebb van ez a fajta programoz´ asi paradigma. Amennyiben hatékonysági okokból egy funkcionális nyelven meg´ırt algoritmust hardverben szeretnének futtatni, manapság erre kevés lehet˝oség ad´ odik, és azok is k´ısérleti, kiforratlan stádiumban vannak. A dolgozatom célkit˝ uzése teh´ at egy funkcion´ alis bemenetr˝ ol t¨ ortén˝o automatizált hardverle´ırás-generálás, aminek sor´ an figyelembe kell venni a jelenleg alapkutatási szakaszban létez˝o megoldásokat. Dolgozatom kész´ıtése sor´ an bemeneti funkcionális nyelvként a Haskell egy megszor´ıtott változata mellett d¨ ont¨ ottem, az indokaim a következ˝ok: • ez egy nagyon dinamikusan fejl˝od˝o nyelv • a Haskell-hez rendelkezésre áll egy, az elm´ ult két évtizedben folyamatosan fejlesztett, viszonylag j´ ol dokument´ alt ford´ıtóprogram (GHC) • a GHC ford´ıt´ o k¨ oztes reprezentációit könyvtári f¨ uggvényekkel kézben lehet tartani, teh´ at saj´ at ford´ıt´ o ´ır´ asakor felhasználhatóak a GHC már meglév˝o algoritmusai is • el˝ otanulm´ anyaim sor´ an megismerkedtem, ill. egy tanszéki kutatás keretében m´ ar foglalkoztam a nyelvvel, és ez alatt megptapasztaltam az el˝onyeit más nyelvekhez (pl. Erlang és SML, ezeket el˝otanulmányaimból szintén ismerem) képest Hab´ ar a konkrét megold´ asom a Haskell nyelvhez köt˝odik, nem lenne nehéz áttérni m´ as funkcion´ alis nyelvekre, hiszen a többi funkcionális nyelvnek is a kés˝obbiek során ismertetett lambda-kalkulus az alapja. Ahogy azt még részletesen taglalni fogom, egy általános Haskell kód nem képzelhet˝ o el hardverszintézis bemeneteként, ezért ésszer˝ u megkötések után a 2. fejezetben definiálni fogok egy ford´ıtand´ o részhalmazt. A k¨ ovetkez˝ okben ´ attekintem azokat a meglév˝o, szakirodalomból ismerhet˝o ford´ıtókat, amelyek funkcion´ alis nyelv˝ u forr´ askódból hardvert vagy hardverle´ıró nyelvet generálnak. Lava: A Lava [16] egy Haskell alapokon nyugvó hardverle´ıró nyelv. Definiál k¨ ulönféle hardverben k¨ ozvetlen¨ ul alkalmazhat´ o t´ıpusokat és kombinátorokat, viszont egy általánosabb (lehet ak´ ar rekurzi´ omentes) Haskell forráskódot nem tud leford´ıtani. A Lava hardverközeli nyelv, teh´ at a dolgozatom egyik f˝o célkit˝ uzését nem teljes´ıti, mégpedig, hogy a hardveres világtól elszakadt, szoftveres fogalmakkal felép´ıthet˝o forráskódot használhassunk a szintézis bemeneteként. (a Lava-ban pl. az elágazást is a hardveres világból ismert multiplexerrel kell megoldanunk, nem pedig a Haskell-ben megszokott if és case szerkezetekkel) A Lava 5

nyelvet a µF P [32] és a Ruby [20] nyelvek alapjain fejlesztették, az el˝obbi hardverspecifikus kombinátorokra ép¨ ul, az ut´ obbi pedig egy relációs hardverle´ıró nyelv, ahol az áramköröket és komponenseiket a ki- és bemenetek közötti relációkkal adják meg. [4] SASL: A Cambridge egyetemen egy SASL (Statically-Allocated Stream Language) nev˝ u funkcionális nyelvet és egy ahhoz tartoz´ o hardverszintézist fejlesztettek ki, ami többek között egy PhD disszert´ aci´ o [19] form´ aj´ aban l´ atott napvilágot 2004-ben. A statikus itt arra utal, hogy fix, hardverben is megval´ os´ıthat´ o strukt´ urákból áll a nyelv, a stream pedig a modulok ki- és bemeneti interfészére vonatkozik. Az itt bemutatott szintézer képes CSP-t [21] és adatfolyamgráfot el˝oáll´ıtani. Az adatfolyamgráf kérés és nyugt´ az´ as jeleket is magában foglal, tehát a dolgozatomban használt adatfolyamgr´ aft´ ol (EOG) ebben a lényeges kérdésben eltér. CλasH: A hollandiai Twente egyetemen 2009-ben két diplomaterv [12, 24] keretében elindult egy projekt CλasH néven, amely az els˝ o nagyobb nyilvánosságot 2010 nyarán kapta a Haskell hackageDB adatb´ azis´ aban val´ o megjelenéssel. A CλasH a CAES Language for Synchronous Hardware elnevezésb˝ ol sz¨ uletett mozaikszó. A fejleszt˝oknek itt is egy funkcionális nyelv˝ u hardverle´ırás megalkot´ asa volt a céljuk, amihez alapnak a Haskell nyelvet választották. (nekem hardverle´ır´ as megalkot´ asa nem volt célom, s˝ot mi több, egy hardveres fogalmaktól mentes forrásk´ od defini´ al´ as´ at t˝ uztem ki) A CλasH a ford´ıt´ as els˝ o lépéseként a GHC frontendet használja, mégpedig a szintaktikai édes´ıt˝oszerek elt´ avol´ıt´ as´ aig. Ezen a ponton a CλasH-ben megvalós´ıtott normalizációs eljárások kapj´ ak bemenetként az itt kialakult Core reprezentációt, és hajtják végre a normalizációs lépéseket, egészen az elv´ art normálformára való átalak´ıtásig. A ford´ıtás végs˝o lépése az elért norm´ alforma hardverle´ırássá alak´ıtása, a szerz˝ok szerint ehhez a lépéshez már egyenes u ´t vezet. A CλasH alapjainak megismerése ut´ an nyilvánvalóvá vált, hogy a feladatki´ırásom szempontjából ez a legink´ abb relev´ ans, dokumentált ford´ıtó, ´ıgy a m˝ uködését részletesebben megismertem. Ezek alapj´ an néh´ any szempont, amiben a dolgozatom során le´ırt ford´ıtó el˝onyre tesz szert a CλasH-sel szemben: • explicit adatfolyamgr´ afot (EOG) használ köztes reprezentációként, ´ıgy a pipeline optimaliz´ al´ as a szakirodalomban [10] ismertetett módon elvégezhet˝o • a modularit´ ast jobban el˝ otérbe helyezi, ´ıgy a ford´ıtás egyes lépései (Haskell-EOG, ill. EOG-VHDL ´ atalak´ıt´ o és ezek almoduljai) u ´jrahasznos´ıthatóak • a forrásk´ odban haszn´ alhat´ o m˝ uvelethalmaz a ford´ıtóprogram át´ırása nélk¨ ul b˝ov´ıthet˝o, csup´ an a m˝ uvelethez tartoz´ o VHDL modult kell definiálnunk • a Core reprezent´ aci´ ot kiértékel˝ o algoritmus determinisztikus (a CλasH normalizációs lépések nem konfluensek, a determinisztikusság pedig a dokumentáció alapján nem eldönthet˝ o) 6

• haszn´ alja a GHC simplifier mechanizmusát, ´ıgy annak nagyfok´ u optimalizáló tulajdons´ ag´ at az egész ford´ıt´ as el˝onyére tudjuk használni (pl. lefutnak a magasszint˝ u át´ır´ asi szab´ alyok, a rewrite rule-ok is) Az egész ford´ıt´ orendszert modulárisan ép´ıtem fel annak érdekében, hogy az egyes részfeladatok j´ ol elk¨ ul¨ on´ıthet˝ oek, a modulok közti interfészek egyszer˝ uek és teljes mértékben definiáltak legyenek. Ezek alapj´ an cserélhet˝o modulokat kapunk, ´ıgy a rendszer az egyes részfeladatok u ´jrahasznos´ıt´ as´ at messzemen˝oen támogatja.

A 1. fejezetben a be- és kimeneti nyelvek, azaz a Haskell és a VHDL sajátosságait taglalom. A 2. fejezetben ismertetem az általam kidolgozott, egysebesség˝ u (single-rate) adatfolyamokra alkalmazhat´ o ford´ıtói módszert és ford´ıtóprogramot, kitérve a CλasH-sel való k¨ ul¨ onbségekre és hasonl´ os´ agokra. A 3. fejezetben a módszert kiterjesztem többsebesség˝ u (multi-rate) adatfolyamokra, és ehhez kapcsolódóan elkész´ıtem a szakirodalomból [10] ismert EOG modell t¨ obbsebesség˝ u környezetben is alkalmazható változatát, az MREOG-t. A 4. fejezetben konkrét péld´ akon ismertetem a módszer m˝ uködését, amit az elkész¨ ult ford´ıtóprogram k¨ oztes reprezent´ aci´ oival és VHDL szimulációval illusztrálok. Az 5. fejezetben kitérek a tov´ abbfejlesztési lehet˝ oségekre, vég¨ ul a 6. fejezetben összefoglalom a dolgozatomban elért eredményeket.

7

1. fejezet

A ford´ıt´ as ki- ´ es bemenete 1.1. A Haskell nyelv ´ es saj´ atoss´ agai A Haskell nyelv egy szabv´ anyos´ıtott, a´ltalános felhasználás´ u, tisztán funkcionális, lusta kiértékelés˝ u, er˝ osen t´ıpusos, polimorf t´ıpusokat támogató nyelv. Ebben a fejezetben a nyelvi sajátosságokat taglalom, amelyeket figyelembe kellett vennem a Haskell nyelvr˝ol történ˝o ford´ıtás során. Az imént felsorolt fogalmak kicsit részletesebben kifejtve a következ˝oket takarják: • szabványos´ıtott: a nyelvnek két szabványa létezik, Haskell 98 [30] és Haskell 2010 [28] néven • általános felhaszn´ al´ as´ u: a nyelvet nem konkrét célfeladatra fejlesztették, széleskör˝ uen használhat´ o, legyen sz´ o tiszt´ an algoritmikus feladatokról vagy grafikus interfésszel rendelkez˝ o programr´ ol • tiszt´ an funkcion´ alis (pure functional): egy f¨ uggvény kimenete csak a bemeneteit˝ol f¨ ugghet, teh´ at a f¨ uggvények mellékhatásmentesek, aminek el˝onye a kódoláskor történ˝o hib´ az´ asok cs¨ okkenése és a modularitás nagy fok´ u támogatása, ugyanis a kódrészek egym´ ast´ ol teljesen f¨ uggetlen¨ ul tesztelhet˝oek ill. felhasználhatóak • lusta ki´ ert´ ekel´ es˝ u (lazy evaluation): egy adott kifejezés csak akkor értékel˝odik ki, amikor a teljes program kiértékelése során erre mindenképpen sz¨ ukség van (ez a call-by-need stratégia, l´ asd kés˝ obb) • er˝ osen t´ıpusos: egy v´ altoz´ o t´ıpusa a futási id˝oben nem változhat, vagyis k¨ ulönböz˝o t´ıpus´ u v´ altoz´ ok k¨ oz¨ ott explicit konverzió sz¨ ukséges (ellentétben pl. a php nyelvvel, ahol a v´ altoz´ ok t´ıpusa fut´ asid˝ oben változhat) • polimorf t´ıpusok: paraméteres t´ıpusok, ahol a paraméterek szintén t´ıpusokat jelentenek (egy t´ıpus ez´ altal specializ´ altabb t´ıpusok egy halmazát jelentheti - ez nagyban növeli a k´ od u ´jrafelhaszn´ alhat´ os´ agát) A funkcion´ alis nyelvek a lambda-kalkulus-ra ép¨ ulnek, ezért a következ˝okben a lambdakalkulus alapjainak r¨ ovid le´ır´ asa k¨ ovetkezik. 8

1.1.1. Lambda-kalkulus A lambda-kalkulus megértésének jó kiindulópontja Henk Barendregt és Erik Barendsen Introduction to Lambda Calculus c´ım˝ u m˝ uve [13]. A lambda-kalkulust lambda-kifejezések alkotják. Egy lambda-kifejez´ es lehet • egy egyszer˝ u v´ altoz´ o • egy lambda-absztrakci´ o, aminek a jelölése: λv.E, ahol v egy változó és E egy lambda-kifejezés • egy alkalmaz´ as, aminek a jelölése: F E, ahol F egy lambda-absztrakció és E egy tetsz˝ oleges lambda-kifejezés A lambda-absztrakci´ ora gondolhatunk u ´gy, mint egy f¨ uggvény megtestes´ıt˝ojére, az alkalmaz´ asra pedig u ´gy, mint egy f¨ uggvény megh´ıvására. (kés˝obb látni fogjuk, hogy ez a felfogás s´ ant´ıt, de most egyszer˝ ubb csak ´ıgy gondolni rá) Tekints¨ uk pl. a következ˝o intuit´ıv kifejezést: (λx.2 ∗ x + 1)3. Ez egy alkalmazás, amely végrehajtja a benne szerepl˝ o lambda-absztrakci´ ot a 3 bemeneti értékkel. Ha az absztrakció x változójára behelyettes´ıtj¨ uk a 3-at, akkor m´ ar egyszer˝ uen látszik, hogy ennek a kifejezésnek (2 ∗ 3 + 1) = 7 az értéke. A következ˝ okben a lambda-kalkulus u ´jabb fogalmait vezetj¨ uk be: • k¨ ot¨ ott/szabad v´ altoz´ o: Egy lambda-absztrakció kifejezésében azok a változók k¨ ot¨ ottek, amelyek szerepelnek az absztrakció defin´ıciójában, a többi változót szabadnak mondjuk. Teh´ at λx.x + y esetében x egy kötött, y egy szabad változó. • fu eny: Azok a lambda-absztrakciók tekinthet˝ok f¨ uggvénynek, amelyben nincs ¨ ggv´ szabad v´ altoz´ o. (teh´ at kimeneti” értéke csak a bemenett˝ol” f¨ ugg) ” ” • α-konverzi´ o: Alpha-konverziónak nevezz¨ uk a kötött változók átnevezését. Pl. λx.x alpha konverzi´ o ut´ an kinézhet ´ıgy is: λy.y. • β-redukci´ o: A beta redukció a lambda-kalkulus legfontosabb konverziója, ez tulajdonképpen az alkalmaz´ as végrehajtását jelenti. A fenti példánál maradva (λx.2 ∗ x + 1)3 a beta redukci´ o ut´ an (2 ∗ 3 + 1) alakot vesz fel. • η-konverzi´ o: Az eta-konverziót a következ˝o egyszer˝ u egyenl˝oséggel illusztráljuk: λx.F x = F , ahol x v´ altoz´ o és F egy lambda-absztrakció. Ez azt jelenti, hogy egy lambda-absztrakci´ o, ami egy F x alkalmazásból áll, egyszer˝ uen helyettes´ıthet˝o az alkalmaz´ as lambda-absztrakciójával, azaz F -fel. • lambda lifting: Olyan m´ odszer, amely eltávol´ıtja a lambda-absztrakciókon bel¨ uli szabad v´ altoz´ okat. Ezt oly módon hajtja végre, hogy a szabad változókat kötötté teszi egy u ´jabb lambda-absztrakció bevezetésével, amin kereszt¨ ul az addigi szabad v´ altoz´ o értékének ´ atad´ asa biztos´ıtható. Funkcionális nyelv˝ u f¨ uggvényekre ez a k¨ ovetkez˝ oképp értelmezhet˝ o. Minden szabad változó esetében létrehozunk egy u ´jabb 9

paramétert, majd a kiz´ ar´ olag k¨ otött változókat tartalmazó lambda kifejezéseket f¨ uggvényként a glob´ alis névtérbe helyezz¨ uk. (a f¨ uggvényeknek persze egyedi névvel kell rendelkezni¨ uk) Ki´ ert´ ekel´ esi strat´ egi´ ak A kiértékelési stratégi´ ak szab´ alyok sorozatai, amelyeket végrehajtva egy programozási nyelv kifejezése kiértékelhet˝ o, vagyis a kifejezés értéke meghatározható. Lambdakalkulusban ezeket ´ altal´ aban redukci´ os stratégiáknak nevezik. A következ˝o részben a leggyakrabban alkalmazott kiértékelési stratégiákat mutatom be: • call-by-value: A moh´ o (m´ as néven szigor´ u) kiértékelés családjába tartozó stratégia. A f¨ uggvényh´ıv´ as el˝ ott kiértékelj¨ uk az o¨sszes argumentum-kifejezést, ´ıgy a f¨ uggvény h´ıvásakor a m´ ar kisz´ am´ıtott értékeket adjuk át. Nagyon sok programozási nyelv használja ezt a m´ odszert, nem is kell messzire menn¨ unk, az egyik legáltalánosabban használt imperat´ıv nyelv, a C pontosan ´ıgy m˝ uködik. • call-by-reference: Szintén a mohó kiértékelés családjába tartozik. Az argumentumok kiértékelése itt is megt¨ orténik a f¨ uggvényh´ıvás el˝ott, de a paraméterátadás a változóra mutat´ o referenci´ an kereszt¨ ul bonyolódik, amely nagyobb méret˝ u változó esetén j´ oval k¨ oltséghatékonyabb lehet. A másik k¨ ulönbség, hogy az indirekció miatt a f¨ uggvényen bel¨ ul a k¨ uls˝ o v´ altoz´ o értéke is megváltoztatható. A C++ alapértelmezetten call-by-value ´ atad´ ast val´ os´ıt meg, de referenciát használva a call-by-reference stratégi´ at is t´ amogatja. • call-by-name: Lusta (nem szigor´ u) kiértékelés˝ u. A f¨ uggvényargumentum kifejezését nem értékeli ki a f¨ uggvény h´ıv´ asa el˝ott, hanem csak egy hivatkozást (thunk) ad át a teljes argumentum-kifejezésre. Akkor értékel˝odik ki az argumentum, ha a f¨ uggvényen bel¨ uli kiértékelés m´ ar mindenképpen sz¨ ukségessé teszi ezt. Ez adja a megoldás legnagyobb el˝ onyét, hiszen addig nem kell foglalkoznunk egy kifejezéssel, am´ıg biztossá nem válik annak tényleges felhasználása. Ez el˝ony lehet akkor is, ha az argumentum kiértékelése o aban végtelen ciklushoz vezetne, hiszen ha az argumentumot a ¨nmag´ f¨ uggvényen bel¨ ul nem haszn´ aljuk, akkor nem állhat el˝o végtelen ciklus. • call-by-need [11]: Lusta kiértékelés˝ u szintén, a call-by-name stratégiától csak abban tér el, hogy az argumentumkifejezést legfeljebb egyszer értékeli ki, majd az értéket eltárolja egy v´ altoz´ oban. Amikor a következ˝okben sz¨ ukség van rá, az értéket a változóból veszi ki, teh´ at tényleges kiértékelés nem történik. A lusta kiértékelés leginkább használatos m´ odja ez a stratégia, többek között a dolgozatom szempontjából fontos Haskell nyelv is ezen alapszik.

1.1.2. T´ıpusrendszer A funkcionális nyelvek t´ıpusrendszerének alapja az algebrai adatt´ıpus (algebraic data type, ADT), amely Haskell esetében a k¨ ovetkez˝o defin´ıciót jelenti ([30], 4.2.1 fejezet):

10

data T t1 t2 ... tn = | | |

A a1 a2 ... ak B b1 b2 ... bl ... X x1 x2 ... xm

T a t´ıpuskonstruktor, t1..tn a paraméterei, A,B..X az adatkonstruktorok, az a1..xm közötti szimb´ olumok pedig az adott konstruktorhoz tartozó t´ıpusokat jelentik. Ez halmazelméleti nyelven megfogalmazva adatok Descartes-szorzatának o¨sszegét, vagyis megk¨ ulönb¨ oztetett uni´ oj´ at jelenti. Az összeg tagjait, vagyis a t´ıpusalternat´ıv´ akat a | (pipe) jelöléssel kell elv´ alasztanunk. Egy T t1 ...tn t´ıpus´ u változó bármelyik t´ıpusalternat´ıva szerinti értéket felvehet. Az n-esek (hétk¨ oznapi nyelven a rekord t´ıpusok) a Descartes szorzatnak felelnek meg. Az n-eseket tekinthetj¨ uk az ´ altal´ anos defin´ıció egyik speciális esetének, amikor az o¨sszegnek csak egyetlen tagja van, és az adatkonstruktor (,) (bármennyi vessz˝o szerepelhet) alakban adott. A nyelvben a szokványos n-es jelölés, pl. (a,b,c,d) csak egy szintaktikai édes´ıt˝oszer, teh´ at egy jobban olvasható le´ırása a (,,,) a b strukt´ urának. Néhány példa algebrai adatt´ıpusok megad´ as´ ara [5]:

data Bool = False | True data Maybe a = Nothing | Just a data Either a b = Left a | Right b

A Bool a szok´ asos boolean t´ıpusnak felel meg, két egyszer˝ u konstruktora van, False és True néven, az ilyen t´ıpus´ u kifejezés csak ezt a két értéket veheti fel. A Maybe a ett˝ ol annyiban tér el, hogy amikor a Just konstruktort használjuk, akkor meg kell adnunk egy tetsz˝oleges t´ıpus´ u kifejezést is. (pl. Just "szoveg" ). Az Either a b ennél is tovább megy, ez arra j´ o, hogy egy t´ıpusba foglaljon o¨ssze két egymással nem kompatibilis kifejezést. Pl. egy ilyen t´ıpus´ u kifejezés lehet Left "szoveg" , vagy Right 67 . A Haskell szabv´ any bevezeti a t´ıpusoszt´ aly fogalmát. Egy t´ıpusosztály f¨ uggvényeket deklar´ al, amelyeket csak a t´ıpusosztályba tartozó t´ıpusokra lehet alkalmazni. Egy t´ıpusosztályt péld´ anyos´ıtva konkrét t´ıpusok esetére megadhatjuk a f¨ uggvények defin´ıcióját, ´ıgy a k¨ ul¨ onb¨ oz˝ o t´ıpusokra k¨ ul¨ onb¨ oz˝ o f¨ uggvényimplementáció adható. Egy egyszer˝ u példa a Num t´ıpusoszt´ aly, amely algebrai f¨ uggvényeket deklarál (pl. (+) , (-) , (*) ). Az Int t´ıpus többek k¨ oz¨ ott a Num t´ıpusoszt´ alynak is tagja, mert létezik egy Num Int példányos´ıtás. Ebben a péld´ anyos´ıt´ asban az algebrai m˝ uveleteket az Int t´ıpus szerint implementálták, ´ıgy pl. két Int t´ıpus ¨ osszead´ asa esetén az itt definiált kód hajtódik végre. 11

1.2. A Haskell GHC ford´ıt´ o f¨ obb tulajdons´ agai Jelenleg a GHC sz´ am´ıt de facto standard” Haskell ford´ıtónak, versenytársai funkcionali” tásban csak messze lemaradva k¨ ovetik. A dolgozatom szempontjából nagyon fontos volt megismernem a GHC ford´ıt´ o m˝ uk¨ odését, ezért jelen fejezetben kitérek azokra a megismert tulajdonságokra, amelyekre a fejlesztés során nagy sz¨ ukség volt.

1.2.1. K¨ oztes reprezent´ aci´ o - a Core nyelv A GHC egy k¨ oztes nyelvet, a Core [35] strukt´ urát használja az éppen ford´ıtott kód egyszer˝ us´ıtett reprezent´ al´ as´ ara, ami tulajdonképpen egy lambdakalkulus elveit követ˝o AST (absztrakt szintaxisfa) reprezent´ aci´ o. Az optimalizációs lépések nagy része ezen a nyelven történik, ezekre a transzform´ aci´ okra éppen ezért szoktak Core2Core néven is hivatkozni. A Core lényegret¨ or˝ o defin´ıci´ oja: data Expr b = | | | | | | | |

Var Id Lit Literal App (Expr b) (Arg b) Lam b (Expr b) Let (Bind b) (Expr b) Case (Expr b) b Type [Alt b] Cast (Expr b) Coercion Note Note (Expr b) Type Type

type Alt b = (AltCon, [b], Expr b) data Bind b = NonRec b (Expr b) | Rec [(b, Expr b)]

Az egyes kifejezések jelentése: • Var Id : Egy v´ altoz´ o haszn´ alat´ at jelenti. Ez tulajdonképpen egy hivatkozás a legfels˝o szinten megadott glob´ alis, vagy a Let kifejezéssel le´ırt lokális változókötésre (más néven ¨ osszerendelésre). • Lit Literal : Konstanst jel¨ ol. A konstansoknak egy sz˝ uk halmazát adhatjuk meg, az obbi konstans ezekb˝ ol sz´ armazhat. (pl. az App kifejezéssel, adatkonstruktort összes t¨ alkalmazva) Néh´ any jellemz˝ o t´ıpus: Int# , Int64# , Float , Double , FastString • App (Expr b) (Arg b) : Egy lambda-kalkulus szerinti alkalmazást jelöl, ezek alapján csak egyetlen argumentuma lehet. Több argumentum´ u f¨ uggvényeket egymásba ágyazott alkalmaz´ asokkal ´ırhatunk le, ´ıgy pl. az 1 és 2 számok összeadása a következ˝oképp néz ki: App (App (Var (+)) (Lit 1)) (Lit 2) . A példából az is kider¨ ul, hogy a (+) f¨ uggvény itt egy v´ altozón kereszt¨ ul jelenik meg, tehát egy el˝oz˝oleg definiált f¨ uggvény alkalmaz´ as´ ara v´ altozóval hivatkozunk. A GHC az adatkonstrukciókat is alkalmaz´ asként kezeli, teh´ at algebrai t´ıpus´ u konstansokat is csak az App seg´ıtségével ´ırhatunk le. 12

• Lam b (Expr b) : Egy lambda-absztrakciót definiál. A lambda-absztrakció tulajdonképpen nem m´ as, mint egy kifejezés burkolva, aminek egyetlen kötött paramétere van (a kifejezés els˝ o, itt b -vel jelölt paramétere). Minden f¨ uggvénydefin´ıció Coreban t¨ ortén˝ o ´ abr´ azol´ asa lambda-absztrakcióval történik. Több argumentum esetén az App -hoz hasonl´ oan egymásba ágyazott Lam kifejezések szerepelnek, ´ıgy pl. az osszead´ asn´ al: Lam(a)(Lam(b)(...)) ¨ • Let (Bind b) (Expr b) : Változó-kifejezés o¨sszerendelést (Bind , lásd kés˝obb) és egy tov´ abbi kifejezést (Expr ) definiál. A változó használata minden esetben a m´ ar bemutatott Var kifejezéssel ´ırható le. A call-by-need kiértékelés miatt egy Let csom´ oponthoz érve csak az Expr kifejezéssel kell érdemben tör˝odni, az összerendelésben tal´ alhat´ o kifejezéssel annak használatáig nem kell foglalkoznunk. • Case (Expr b) b Type [Alt b] : A Core nyelv kétségk´ıv¨ ul legbonyolultabb szerkezete egy el´ agaz´ ast (case ) reprezentál. A Haskell forráskód case és if kifejezései biztosan erre fordulnak, de emellett a változók illesztésére is ezt a formát haszn´ alj´ ak. Az Expr itt az a kifejezés, ami alapján kiválasztásra ker¨ ul az alternat´ıvák köz¨ ul egyetlen ´ ag. (a szakirodalomban erre a kifejezésre scrutinee néven hivatkoznak) A b egy v´ altoz´ o k¨ otés (hasonlóan a Lam b -jéhez), ez a teljes scrutinee-t köti az itt megadott v´ altoz´ ora, ez azért fontos, hogy a továbbiakban hivatkozni lehessen a teljes kifejezésre. A Type a Case visszatérési értékének t´ıpusa, az [Alt b] tömb pedig az alternat´ıv´ ak le´ır´ asa, amir˝ol még szó lesz. • Cast (Expr b) Coercion : Explicit t´ıpuskonverzió. • Note Note (Expr b) : A Core fában lehet˝oség van megjegyzést elhelyezni, ezt a Note kifejezéssel tehetj¨ uk meg. • Type Type : T´ıpusdefin´ıci´ o, a Core legfels˝o szintjén lehet megtalálni. • (AltCon, [b], Expr b) : A case alternat´ıvák ebben a formában jelennek meg. AltCon az alternat´ıva konstruktora, ami adatkonstruktor vagy literál lehet. A [b] t¨ omb azokat a v´ altoz´ okat tartalmazza, amiket az AltCon szerinti paraméterekhez k¨ ot¨ unk, az Expr b pedig az adott alternat´ıva esetén kiértékelend˝o kifejezés. • NonRec b (Expr b) : Nemrekurz´ıv o¨sszerendelést definiál. A b változót és az Expr kifejezést rendeli ¨ ossze, a kifejezésre ezek után a Core Var bejegyzésével hivatkozhatunk, megadva a k¨ ot¨ ott v´ altozó, azaz a b nevét. Az Expr kifejezésben csak a fában ezt a pontot megel˝ oz˝ o¨ osszerendelésre hivatkozhatunk. • Rec [(b, Expr b)] : Rekurz´ıv o¨sszerendeléseket definiál. Egy-egy összerendelés a b paraméterben adott v´ altozót és az Expr paraméterben adott kifejezést rendeli ossze. Az Expr kifejezésben a fában ezt a pontot megel˝oz˝o összerendelésre, vagy a ¨ saj´ at Rec kifejezésben felsorolt többi összerendelésére hivatkozhatunk. (ez a lényegi k¨ ul¨ onbség a rekurz´ıv és nemrekurz´ıv o¨sszerendelés között) A kölcsönös hivatkoz´ as kiz´ ar´ olag rekurz´ıv ¨ osszerendeléssel valós´ıtható meg. 13

1.2.2. Primit´ıv t´ıpusok Primit´ıv t´ıpusnak nevezz¨ uk a GHC beép´ıtett t´ıpusait, vagyis azokat a t´ıpusokat, amelyek alapértelmezetten nem szerepelhetnek a ford´ıtandó kódban. A primit´ıv t´ıpusok között megtaláljuk t¨ obbek k¨ oz¨ ott a nat´ıv környezet t´ıpusait, a mai szokványos szám´ıtógépes környezetben 32 vagy 64 bites integert (Int# ), a float (Float# ) és a double (Double# ) lebeg˝opontos t´ıpusokat. (a z´ ar´ ojeles nevek a t´ıpusok GHC szerinti nevei) A primit´ıv t´ıpusok azonos´ıtója konvencion´ alisan a kett˝ oskereszt karakterrel zárul. Egy primit´ıv t´ıpus lehet csomagolt (boxed) vagy csupasz (unboxed) attól f¨ ugg˝oen, hogy megval´ os´ıt´ asa pointerrel (indirekt) vagy érték alapján történik. Az el˝obb felsorolt t´ıpusok mind csupasz t´ıpusok, de a ByteArray# pl. már csomagolt. A primit´ıv t´ıpusokat saj´ at programjainkban is használhatjuk, ha a GHC.Prim modult importáljuk, és a kett˝ oskereszt karakterek használatát ford´ıtói opcióval engedélyezz¨ uk. ([34], 7.3.2 fejezet) A primit´ıv t´ıpusok azért fontosak sz´ amunkra, mert a GHC t´ıpusrendszer alapját képezik, tehát ezeket mindenképpen tudnunk kell ábrázolni hardverben. A legegyszer˝ ubb t´ıpusok, ´ıgy az Int , Integer , Float és Double is ezeknek a t´ıpusoknak a csomagolt változatai, ahogy az a GHC forr´ asf´ ajljaib´ ol ki is der¨ ul:

-- GHC.Types data Int data Float data Double

modul: = I# Int# = F# Float# = D# Double#

-- GHC.Integer.Type modul: data Integer = S# Int# | J# Int# ByteArray#

-- small integers -- large integers

Látható, hogy ezek az egyszer˝ u, leggyakrabban használt t´ıpusok is ADT-k. Az Int például egy I# adatkonstruktorral és az Int# primit´ıv t´ıpussal képzett t´ıpus. Az Integer korlátlan méret˝ u egész sz´ amot t´ arolhat, ´ıgy a megvalós´ıtása is kör¨ ulményesebb. Attól f¨ ugg˝oen, hogy épp milyen nagys´ agrend˝ u értéket tartalmaz, lehet az Int -hez hasonló (erre szolgál a S# konstruktor) és lehet egy kell˝oen nagy tömb által megvalós´ıtott (erre szolgál a J# konstruktor). A nyilvánval´ o aritmetikai m˝ uveleteknek is mind-mind megvan a primit´ıv megfelel˝oje, ´ıgy az összead´ as a (+#) , a szorz´ as pedig a (*#) primit´ıv m˝ uveletekkel valós´ıtható meg. A GHC.Prim modulban tal´ alhat´ o ezeknek a m˝ uveleteknek a virtuális” defin´ıciója, vagyis egy ” let x = x in x kifejezés, ami tényleges funkcióval nem rendelkezik, ugyanis a primit´ıv m˝ uveleteknek m´ ar k¨ ozvetlen¨ ul nat´ıv k´ odra kell fordulnia. A Num t´ıpusoszt´ alyt megval´ os´ıtja többek között az Int és az Integer t´ıpus is, emiatt mindkét t´ıpushoz defini´ alni kellett a megfelel˝o aritmetikai m˝ uveleteket. Ez Int -ek összeadásánál annyit jelent, hogy a GHC kicsomagolja (unboxing) a bemeneteket Int# primit´ıv t´ıpusra, majd ezeken végrehajtja a (+#) primit´ıv m˝ uveletet, vég¨ ul az eredményt u ´jra becsomagolja (boxing). Pontosan ezen az elven m˝ uködik a GHC.Base.plusInt 14

f¨ uggvény, amit a Num Int péld´ anyos´ıtás o¨sszeadás f¨ uggvénye h´ıv a GHC.Num modulban. Az Integer esetében ennél sokkal bonyolultabb a helyzet, hiszen bármilyen nagyság´ u számokat is tartalmazhat (persze a szám´ıtógép memóriájának f¨ uggvényében), amiket a véges, Int# t´ıpus´ u (+#) m˝ uvelet – rosszabb esetben - egymás utáni végrehajtására kell leképeznie. Eset¨ unkben nagyon fontos kérdés, hogy az egész t´ıpus´ u literálok hogyan szerepelnek a Core reprezent´ aci´ oban. A Literal adatt´ıpus MachInt konstruktora Int# értéket szolg´ altat, ´ıgy a Core f´ aban megjelenik a csomagoláshoz sz¨ ukséges adatkonstruktor is:

app GHC.Types.I\# lit 2

Egy 32 bitnél nagyobb Integer , történetesen a 7 ∗ 109 esetében a Core a következ˝ o, kör¨ ulményes form´ at veszi fel:

app GHC.Integer.plusInteger app GHC.Integer.smallInteger lit 557549059 app GHC.Integer.timesInteger app GHC.Integer.smallInteger lit 3 app GHC.Integer.smallInteger lit 2147483647

Ha belegondolunk, hogy a 32 bites architekt´ urán ez a szám egyetlen nat´ıv konstanssal nem lenne reprezent´ alhat´ o, akkor teljesen logikus, hogy már a Core reprezentációban is csak 32 biten ´ abr´ azolhat´ o konstansok és m˝ uveletek lehetnek. Ez a továbbiakat annyiban érinti, hogy egy nagyobb sz´ am esetében az aritmetikai m˝ uveletek és a konstansok több primit´ıv m˝ uveletet eredményeznek, holott egy hardverben tetsz˝oleges bitszám´ u aritmetika kialak´ıthat´ o, ´ıgy erre a bonyol´ıt´ asra” nem lenne sz¨ ukség. ”

1.2.3. Fu enybehelyettes´ıt´ es ¨ ggv´ A behelyettes´ıt´ es az a k´ odtranszformáció, ami egy f¨ uggvény h´ıvási pontjára a f¨ uggvény törzsét bem´ asolja. (a szakirodalom az inline mellett unfold néven is hivatkozik erre a transzform´ aci´ ora, l´ asd pl. a GHC kézikönyvét [34]) Megjegyzend˝o, hogy a behelyettes´ıtés lambda-kalkulus szerinti megfelel˝oje a β-redukció. A ford´ıt´ as egyik kulcsfontoss´ ag´ u kérdéséhez ért¨ unk, ami mind processzoros, mind hardveres rendszer esetén nagyban kihat a futtatás hatékonyságára. Processzoron történ˝o futtatás esetében a behelyettes´ıtés gyorsabb futást eredményezhet (hisz a f¨ uggvényh´ıvásb´ ol ered˝o overhead elt˝ unik), viszont jó esély van arra, hogy a program bájtkódja ezáltal n¨ ovekszik, mert adott esetben t¨ obb helyre is bemásoljuk ugyanazt a kódot. Ezek alapj´ an 15

az egyik alapvet˝ o szab´ aly, hogy a kiz´ arólag egyszer megh´ıvott f¨ uggvényekre mindenképpen végre kell hajtani az inlining-ot, ez ugyanis bájtkód növekedést nem okoz, ellenben gyorsabb fut´ ast eredményez(het). A GHC egy o ar´ assal d¨ onti el, hogy egy f¨ uggvényt behelyettes´ıt-e vagy sem ¨sszetett elj´ [31]. Az összetettség ellenére vannak alapelvek [6], amik könnyen megérthet˝oek és ezeket ismerve egyszer˝ ubben tudjuk befoly´ asolni a GHC behelyettes´ıtési mechanizmusát, ezért most ezekre térek ki. A GHC simplifier programrésze akkor hajt végre automatikus behelyettes´ıtést, • ha a f¨ uggvény mérete nagyon kicsi, vagy • ha a modul export list´ aj´ aban nem szerepeltetj¨ uk a f¨ uggvényt és a modulon bel¨ ul csak egyszer h´ıvjuk (´ altal´ anosabban: ha a f¨ uggvényt biztosan csak egyszer h´ıvjuk meg) További megjegyzések: • Ha a modul export list´ aj´ aban szerepel a f¨ uggvény, akkor a modul ford´ıtásánál még nem garant´ alhat´ o, hogy azt csak egy helyr˝ol fogjuk megh´ıvni, mert h´ıvhatjuk pl. másik modulb´ ol. • Ha a modul fejlécét megadjuk, de az exportlistát elhagyjuk, az azt jelenti, hogy minden f¨ uggvényt export´ alunk. • Ha modul fejlécet nem ´ırunk, az eredmény a module Main where fejléccel ekvivalens lesz, teh´ at itt is minden f¨ uggvényt exportálunk Hardveres k¨ ornyezetben sokkal egyszer˝ ubbé válhat a megvalós´ıtás a behelyettes´ıt˝o transzformációk elvégzése ut´ an. Ilyen esetben az adatfolyam egyszer˝ u marad, egy adott feldolgozóegység az adatfolyamban csak egyszer fog szerepelni, ´ıgy költséges multiplexerekre sincs sz¨ ukség. Kiz´ ar´ olag nagyon k¨ oltséges f¨ uggvény esetén van értelme behelyettes´ıtés nélk¨ uli megoldásban gondolkodni, teh´ at amikor a multiplexer beillesztésével jobban járunk, mint a m˝ uveletek megfelel˝ o sz´ am´ u sokszoros´ıtásával. (ez persze a futási id˝ot is megnövelheti, mert egy feldolgoz´ oegység p´ arhuzamosan több feladatot nem tud ellátni) A behelyettes´ıtésnek van még egy ´ arnyoldala, ez pedig az információvesztés. Behelyettes´ıtés esetén az inline f¨ uggvény neve elt˝ unik, és az az információ is elvész, hogy az adatfolyamgráfban mely csom´ opontok halmaza alkotta az eredeti f¨ uggvényt. Ezzel az információvesztéssel a teljes f¨ uggvényt m´ ar nem tudjuk egy feldolgozóegységként kezelni, amivel esetleg kés˝obbi optimaliz´ al´ asi lehet˝ oségeket vesz´ıthet¨ unk. Polimorf f¨ uggvény implement´ al´ asa hardverben t´ ulságosan költséges és ésszer˝ utlen lenne, mivel akkor a v´ altoz´ o t´ıpus´ at, egy metaadatot is nyilván kellene tartanunk. Ennek az a következménye, hogy egy polimorf f¨ uggvény más-más t´ıpusparaméterrel történ˝o h´ıvása más-más tényleges f¨ uggvény h´ıv´ as´ anak (nem ugyanazon f¨ uggvény több helyr˝ol történ˝o h´ıvásának) szám´ıt, teh´ at ez nem z´ arhatja ki a behelyettes´ıtést. A gyakorlatban ezt a speciális esetet u ´gy tudjuk megoldani, hogy els˝ o lépésben specializáljuk a f¨ uggvényt (behelyettes´ıtj¨ uk a t´ıpusparamétereket), majd csak egy második lépésben hajtjuk végre a behelyettes´ıtési algoritmust. 16

1.3. A VHDL nyelv ´ es saj´ atoss´ agai A VHDL az egyik legelterjedtebben használt hardverle´ıró nyelv, amely FPGA és ASIC áramk¨ or¨ ok implement´ al´ as´ ara, szimulálására és dokumentálására szolgál. A VHDL nyelvet az IEEE 1076-os szabv´ anya rögz´ıti, amelynek legels˝o verzióját 1987-ban, legfrissebb verziój´ at [23] pedig 2008-ban adták ki. A jelenlegi szabv´ any nagyon terjedelmes (640 oldal), ebben nagyon sok nyelvi kifejezést és lehet˝ oséget defini´ altak, ´ am a kereskedelmi szintézer programok ezeknek csak egy részét támogatj´ ak. Ahhoz, hogy a dolgozatom során le´ırt ford´ıtóprogram a lehet˝o legtöbb szintézerrel egy¨ uttm˝ uk¨ odj¨ on, a tov´ abbiakban csak az itt bemutatott egyszer˝ u és általánosan használt kifejezéseket fogom használni. Egy hardverle´ır´ as és egy szoftveres programnyelv között a legnagyobb k¨ ulönbség, hogy a szoftver egy processzorban fut, ezért egymás után végrehajtandó utas´ıtásokra kell ford´ıtani, m´ıg a hardverle´ır´ as vezetékeket, logikai kapukat, regisztereket, stb. ´ır le statikus módon. ´ Eppen ezért a deklarat´ıv nyelvekhez hasonlóan a VHDL kifejezések sorrendje ugyancsak nem sz´ am´ıt. Egy VHDL modul az 1.1. ´ abr´ an vázolt felép´ıtéssel rendelkezik. Minden modul két fontos részb˝ol ´ all. Az egyik az entity deklarációja, ami a modul interfésze, tehát a portokat és a generikus paramétereket ´ırja le. A másik az architecture , ami a modul törzse, tehát a bels˝o struktur´ at és viselkedést ´ırja le az 1.2. ábrán látható formában. (a -- jelek a VHDL kódban megjegyzések ´ır´ as´ ara szolgálnak) Ha haszn´ alni szeretnénk egy másik modult, akkor azt példányos´ıtani kell. Ehhez az architecture-ben deklar´ aljuk a modult a component kulcsszóval ill. a törzsben el kell végezn¨ unk a konkrét péld´ anyos´ıt´ ast. Az architecture viselked´ esi és struktur´ alis model szerint ´ırható le, vagy akár ezeket vegyesen is haszn´ alhatjuk. A strukturális le´ırás (1.3. ábra) azt jelenti, hogy modulokat példányos´ıtunk, és csup´ an az azok közti o¨sszeköttetéseket, azaz csak a strukturát ´ırjuk le. A viselkedési model szerint (1.4. ábra) konkrét logikát, áramköri elemeket használunk m˝ uveletek form´ aj´ aban. A megval´ os´ıtott ford´ıt´ oprogramban csak a legsz¨ ukségesebb t´ıpusokat használom. Az std_logic az egy bites vezeték, az std_logic_vector pedig több bites vezetékek deklarálására szolg´ al, és a legfels˝ obb szint˝ u modulban ezeken k´ıv¨ ul nincs sz¨ ukség más t´ıpusokra.

17

1.1. ´ abra. VHDL modulok felép´ıtése [9] entity NAME OF ENTITY i s [ generic g e n e r i c d e c l a r a t i o n s ) ; ] port ( s i g n a l n a m e s : mode type ; −− s i g n a l n a m e s : mode type ) ; end [ NAME OF ENTITY ] ; architecture a r c h i t e c t u r e n a m e of NAME OF ENTITY i s −− D e c l a r a t i o n s −− components , s i g n a l s , c o n s t a n t s , −− functions , procedures , types begin −− S t a t e m e n t s end a r c h i t e c t u r e n a m e ; 1.2. ´ abra. VHDL modulok szöveges váza architecture s t r u c t u r a l of BUZZER i s component AND2 port ( in1 , i n 2 : in s t d l o g i c ; out1 : out s t d l o g i c ) ; end component ; −− d e c l a r a t i o n o f s i g n a l s used t o i n t e r c o n n e c t g a t e s s i g n a l DOOR NOT, SBELT NOT, B1 , B2 : s t d l o g i c ; begin −− Component i n s t a n t i a t i o n s s t a t e m e n t s U2 : AND2 port map (IGNITION , DOOR NOT, B1 ) ; end s t r u c t u r a l ; 1.3. ´ abra. VHDL strukturális le´ırás példa [9] architecture b e h a v i o r a l of AND2 i s begin out1 <= i n 1 and i n 2 ; end b e h a v i o r a l ; 1.4. ´ abra. VHDL viselkedési le´ırás példa [9]

18

2. fejezet

A ford´ıt´ asi m´ odszer alapelvei ´ es megval´ os´ıt´ asa A most k¨ ovetkez˝ o fejezetben az ´ altalam fejlesztett ford´ıtási módszert mutatom be, amelyet Haskell nyelven implement´ altam is a módszer tesztelhet˝oségét el˝oseg´ıtve. A módszer, vagyis a ford´ıt´ oprogram k¨ ovetelményeinek elemzését, architekt´ uráját, a köztes adatstrukt´ urákat és az egyes modulok algoritmusait részletezem a most következ˝o oldalakon. Ahogy a bevezet˝ oben le´ırtam és indokoltam, az általam választott funkcionális nyelv a Haskell, ennek értelmében az elkész´ıtend˝o eljárás ill. szoftver egy Haskell és VHDL nyelv közötti ford´ıt´ oprogram. A fejlesztés ezen t´ ulmen˝oen további döntéseket igényel, ´ıgy következ˝o lépésként meghat´ aroztam a ford´ıtóprogrammal szemben támasztott követelményeket: 1. a Haskell forr´ ask´ od és VHDL le´ırás közötti ford´ıtás legyen teljesen automatikus 2. ford´ıt´ as sor´ an a felhaszn´ al´ o kapjon hiba¨ uzenetet, ha a forráskód szintaxisa nem megfelel˝ o, vagy ha egy Haskell kifejezés a megkötések miatt nem használható 3. a program modul´ aris felép´ıtés˝ u legyen, hogy az egyes részek a jöv˝oben minden tov´ abbi nélk¨ ul u ´jrahaszn´ alhatóak legyenek 4. a j¨ ov˝ oben k¨ onnyen, teh´ at a f˝obb modulok legfeljebb minimális módos´ıtása után implement´ alhat´ oak legyenek optimalizációs algoritmusok 5. a forr´ ask´ od megk¨ otéseit ne kelljen teljes egészében a fejlesztési periódus elején meghat´ arozni, vagyis a haszn´ alható Haskell kifejezések lehet˝oleg a ford´ıtóprogram utólagos fejlesztése nélk¨ ul, dinamikusan b˝ov´ıthet˝oek legyenek A modul´ aris felép´ıtés akkor el˝onyös, ha a modulok közötti interfészek egyszer˝ uek és jól meghat´ arozottak. Ennek szellemében interfészként adatfolyamgráfot vezetek be, ami ´ıgy a Haskell és VHDL nyelvek közötti ford´ıtásnál köztes reprezentációként fog szolgálni. A választ´ ast az indokolja, hogy egy adatfolyamgráfból viszonylag egyszer˝ uen generálhat´ o hardverle´ır´ as. R¨ oviden o ´gy, hogy a gráf csomópontjait a hardverle´ırás ope¨sszefoglalva u rátoraira vagy moduljaira képezz¨ uk le, a gráf élei pedig egyszer˝ uen vezetékek lesznek. A Haskell nyev˝ u forr´ ask´ odb´ ol teh´ at ebben az esetben adatfolyamgráfot kell kész´ıten¨ unk, ami 19

az al˝obbinél komplik´ altabb feladat, de erre a jelen fejezetben kidolgozott módszer megoldást ad. Mivel a ford´ıt´ as végs˝ o kimenete ´ orajelvezérlést magában foglaló hardverle´ırás lesz, az adatfolyamgr´ afot érdemes SDF-ként (szinkron adatfolyamgráf) [26] felfogni. Els˝o közel´ıtésben az SDF egyszer˝ us´ıtett, homogén változat (HSDF) vizsgálom, ami csak olyan m˝ uveleteket enged meg, amelyek a bemenetr˝ol egyetlen adatot (tokent) mintavételezve egyetlen adatot (tokent) szolg´ altatnak kimenet¨ ukön. Az ilyen adatfolyamokat egysebess´ eg˝ u (single-rate) [15] adatfolyamoknak nevezz¨ uk. Kés˝obb látni fogjuk, hogy az egysebesség˝ u adatfolyamok kiz´ ar´ olagoss´ aga nagyban korlátozza a ford´ıtó bemenetére adható algoritmusokat. Erre a problém´ ara a m´ odszer a 3. fejezetben le´ırt kiterjesztése fog megoldásként szolgálni. HSDF-b˝ol t¨ obb féle konkrét modell [33] is létezik, de mivel ezek között számottev˝o k¨ ulönbség nincs, a v´ alaszt´ asom az EOG (elemi m˝ uveleti gráf) [10] megoldásra esett. Ehhez a modellhez PIPE néven rendelkezésre ´ all egy, az Irány´ıtástechnika és Informatika Tanszéken fejlesztett pipeline optimaliz´ aci´ os m´ odszer és programcsalád is, ezáltal a 4. követelmény szintén teljes¨ ul. Az EOG teh´ at két részre, egy Haskell-EOG és egy EOG-VHDL ford´ıtóra osztja a teljes problémát, és ezzel tk. az ´ altal´ anos ford´ıtóprogramokból már ismert frontend-backend strukt´ urát kapjuk. A forrásk´ odi megk¨ otések dinamikus változtathatóságát (5. követelmény) a m˝ uvelethalmaz fogalm´ anak bevezetésével val´ os´ıtottam meg. A m˝ uvelethalmaz kör¨ ulhatárolja azokat a m˝ uveleteket (f¨ uggvényeket), amelyeket a forráskódban felhasználhatunk, és amelyeket haszn´ alva a ford´ıt´ oprogram helyes kimenetet generál. Ett˝ol eltér˝o m˝ uveleteket használva a programnak hibajelzést kell adnia, mert az ´ıgy le´ırt forráskód az adott m˝ uvelethalmaz szerint nem ford´ıthat´ o. Ha a dinamikus változtatás célját el szeretnénk érni, akkor a m˝ uvelethalmazt a ford´ıt´ oprogram futási idejében sz¨ ukséges kiértékelni. Ezen megfontol´ asokat alapul véve kialak´ıtottam a 2.11. ábrán látható, DFD (adatfolyam diagram) jel¨ oléssel ´ abr´ azolt architekt´ urát. A bemeneti adat tulajdonképpen a felhasználótól érkez˝o algoritmus Haskell nyelv˝ u forráskód formáj´ aban, amit a ford´ıt´ o Haskell-EOG modulja dolgoz fel els˝o lépésként. A modul felhasználja a m˝ uvelethalmaz f¨ uggvény-m˝ uvelet leképzését (FOpMap) mint másik fontos bemen˝o adatot, és a transzform´ aci´ okat elvégezve kimenetként szolgáltat egy EOG-ben reprezentált algoritmusle´ır´ ast. Az EOG-VHDL ford´ıt´ o az EOG reprezentációból automatikusan generál egy VHDL modult, amely az algoritmus konkrét m˝ uveleteket nem tartalmazó hardveres váza, azaz strukturális le´ır´ asa lesz. A kimeneten megjelen˝o VHDL modul példányos´ıthat egyéb, a m˝ uvelethalmazban defini´ alt VHDL modulokat, ezek tartalmazzák a m˝ uveletek hiányzó implementáci´ oit. Az ´ıgy ad´ od´ o VHDL fájlok egy¨ uttesen adják az algoritmus hardveres le´ırását, amit ´ atadva egy kereskedelemben kapható FPGA vagy ASIC szintézernek, a k´ıvánt hardvermegval´ os´ıt´ ast kaphatjuk. 20

Algoritmus Haskell nyelven

Felhasználó Művelethalmaz

Fordítás paramétere

Fordítóprogram Haskell-EOG fordító

FOpMap

EOG

EOG-VHDL fordító

OpVhdlMap

VhdlModules

VHDL leírás

Külső szoftver FPGA szintézer eszköz

Hardver FPGA konfiguráció

2.1. ´ abra. A ford´ıtó architektúrája

2.1. Az egyes modulok interf´ eszei Ebben a fejezetben sor ker¨ ul az imént felvázolt modulok ki- és bemeneti interfészeinek részletes ismertetésére, teh´ at a forráskód, az elemi m˝ uveleti gráf, a VHDL kimenet és a m˝ uvelethalmaz csatol´ asi fel¨ uleteinek bemutatása következik.

2.1.1. Bemeneti forr´ ask´ od A m˝ uvelethalmaz bevezetése miatt a konkrét, ford´ıtandó f¨ uggvényeket nem kellett a fejlesztés kezdetén meghat´ aroznom, mert azokat csak az aktuálisan használt m˝ uvelethalmaz fogja korl´ atozni. Ennek ellenére fontos kizárni a ford´ıtóprogram által nem értelmezhet˝ o forrásk´ odi kifejezéseket, és ezzel kör¨ ulhatárolni a Haskell nyelv bemenetként használhat´ o részhalmaz´ at. Egy megk¨ otések nélk¨ uli Haskell kód hardverként sajnos aligha lenne implementálhat´ o, gondoljunk pl. az adatrekurzi´ ot vagy f¨ uggvényt´ıpust tartalmazó ADT-re. Az adatrekurzió egyik egyszer˝ u esete a lista, ami elméletben akár végtelen hossz´ u is lehet, ´ıgy világos, hogy megfelel˝ oen alacsonyan tartott korlát nélk¨ ul hardverben nem implementálható. Ennek megfelel˝ oen minden adatrekurziót vagy paraméterként f¨ uggvényt tartalmazó ADT-t ki kell z´ arnunk a ford´ıthat´ o t´ıpusok köz¨ ul. Ezeket a t´ıpusokat más, hardverkompatibilis 21

t´ıpusokkal kell a j¨ ov˝ oben helyettes´ıten¨ unk. Az általános korl´ atoz´ asok ut´ an térj¨ unk át a használható f¨ uggvények kérdéskörére. A továbbiakban elemi fu eny néven hivatkozom minden, a m˝ uvelethalmazban le´ırt, köz¨ ggv´ vetlen¨ ul hardverre ford´ıthat´ o f¨ uggvényre. A forráskódban haszn´ alhat´ o elemi f¨ uggvényeket a gyakorlatban u ´gy tudjuk a m˝ uvelethalmaz elemeire korl´ atozni, hogy elker¨ ulj¨ uk a Haskell szabványt implementáló GHC modul, vagyis a Prelude import´ al´ as´ at. Ezt a következ˝o nyelvi pragma seg´ıtségével érhetj¨ uk el:

{-# LANGUAGE NoImplicitPrelude #-}

A megold´ as lényege az, hogy a m˝ uvelethalmazban definiált elemi f¨ uggvényeket a Prelude helyett az InstructionSet.hs importálásán kereszt¨ ul érhetj¨ uk csak el, és ennek maradéktalanul teljes¨ ulnie kell minden ford´ıtandó modulra. Az elemi f¨ uggvényeken k´ıv¨ ul csak olyan f¨ uggvényeket használhatunk a forráskódban, amiket mi magunk defini´ altunk, és ´ıgy igaz rájuk a fenti szabály, vagyis, hogy a Prelude helyett az InstructionSet modul m˝ uveleteit használják. Az ilyen, általunk megadott f¨ uggvényekre a tov´ abbiakban ¨ osszetett fu eny néven fogok hivatkozni. Egyetlen össze¨ ggv´ tett f¨ uggvényt minden forr´ ask´ odnak konvencionálisan tartalmaznia kell, ez pedig a hwmain , ami a szoftveres main -hez anal´ og m´ odon hardveres topmodulként fog szolgálni. A forráskód egy lehetséges péld´ aja:

{-# LANGUAGE NoImplicitPrelude #-} module Adder(hwmain) where import InstructionSet hwmain :: Int -> Int -> Int hwmain a b = a+b

Ez a példa egy nagyon egyszer˝ u¨ osszeadó áramkört valós´ıt meg. Látható, hogy a Prelude helyett itt az InstructionSet modult importáljuk, és a kód egy összeadót valós´ıt meg.

2.1.2. Elemi m˝ uveleti gr´ af Az EOG a jelen rendszer egy nagyon fontos köztes reprezentációja, amelyet interfészként használva a teljes feladatot két j´ ol elk¨ ulön¨ ul˝o részfeladatra osztjuk. Az EOG részletes le´ırása [10] helyett itt csak egy gyors ´ attekintés következik a lényegi kérdésekr˝ol. Az EOG egy adatfolyam h´ al´ ozatok le´ır´ as´ ara szolgáló gráf, amelynek csomópontjai az adatfolyam hálózat m˝ uveletei, élei pedig a m˝ uveletek közötti adatfolyamok. Egy egyszer˝ u o¨sszeadó EOG reprezent´ aci´ oja l´ athat´ o a 2.2. ´ abrán. A csomópontokon a m˝ uvelet azonos´ıtóját, ill. alsó sorban annak t´ıpusát lehet látni. Az ábrán egyetlen val´ odi, add t´ıpus´ u m˝ uvelet mellett szerepelnek még a ki- és bemenetek jelzésére szolg´ al´ o csom´ opontok, SYSTEM t´ıpusnévvel. 22

IN_1 SYSTEM

IN_2 SYSTEM

add_1 Add

OUT SYSTEM

2.2. ´ abra. Egy összeadó elemi m˝uveleti gráfja

A gr´ afot egy nagyon egyszer˝ u formátum´ u fájl ([10], 13. fejezet) seg´ıtségével ´ırhatjuk le. A f´ ajl h´ arom féle sort tartalmazhat, definiálhatunk m˝ uvelett´ıpusokat, megadhatunk m˝ uveleti csom´ opontokat és besz´ urhatunk megjegyzéseket. A 2.2. ´ abra szerinti ¨ osszead´ o szöveges le´ırása pl. a következ˝o:

## a m˝ uvelettípusok következnek (ez egy megjegyzés) # type add 1 # type SYSTEM 0 ## a m˝ uveleti csomópontok leírása követezik (ez is megjegyzés) IN_A SYSTEM IN_B SYSTEM add_1 add IN_A IN_B OUT SYSTEM add_1

A # type kulcssz´ o seg´ıtségével definiáljuk az add és a SYSTEM m˝ uvelett´ıpusokat, és megadjuk azoknak ´ orajelben kifejezett adatfeldolgozási idejét, vagyis azt az id˝ot, ami a bemenet mintevételezése és az eredmény kimenetre való kiadása közötti órajelek száma, azaz latency-jét (lappang´ asi id˝ o). (a következ˝o példákban helytakarékosság miatt a t´ıpust csak akkor fogom szerepeltetni, amikor a latency is fontos szempont) A csom´ opontok megad´ asakor el˝oször az azonos´ıtó szerepel, ezt követi a t´ıpus, majd azoknak a m˝ uveleteknek az azonos´ıtói következnek, amelyek az adott m˝ uvelet bemeneteire csatlakoznak. Az egyes adatok között whitespace karaktereknek kell szerepelni¨ uk. A t´ıpusokat az eredeti le´ır´ ast´ ol eltér˝oen a kés˝obbiekben karakterf¨ uzérként, idéz˝ojelek köz¨ ott fogom szerepeltetni. Az EOG sz¨ oveges le´ır´ as´ ab´ ol l´ atható, hogy egy m˝ uveletnek csak egyetlen kimenete lehet, viszont az az egy kimenet b´ armennyi m˝ uvelet bemenetére csatlakozhat. Ebb˝ol az következik, hogyha minden m˝ uvelethez hozzárendelj¨ uk a kimenetének adatt´ıpusát, akkor ezzel lényegében meghat´ aroztuk az ¨ osszes adat´ ut t´ıpusát is. 23

2.1.3. Kimeneti hardverle´ır´ as A kimeneti VHDL le´ır´ as az EOG-VHDL részegység által generált topmodulból és a m˝ uvelethalmazban defini´ alt, az elemi f¨ uggvények viselkedésével megegyez˝o VHDL modulokból áll. Ezek a VHDL modulok f´ ajlok formájában jelennek meg, amelyek egy¨ uttesen átadhatóak pl. egy FPGA szintézer programnak. A most k¨ ovetkez˝ o részben a megoldásomban alkalmazott kimeneti VHDL formátum bemutatása k¨ ovetkezik.

Algebrai adatt´ıpus k´ odol´ asa A forráskód t´ıpusrendszerének alapja az ADT, ´ıgy ennek hardveres ábrázolásáról szót kell ejteni. Egy ADT-vel megadott v´ altozó egyszer˝ uen ábrázolható bitvektorként, aminek fels˝o k bitje a konstruktornak fenntartott szakasz, ami abban az esetben használatos, ha az adott t´ıpus´ u v´ altoz´ o egynél t¨ obb konstruktor használatát teszi lehet˝ové, vagyis egynél több t´ıpusalternat´ıv´ aval rendelkezik). Egyetlen lehetséges konstruktor esetében k = 0, azaz a konstruktornak sz´ ant biteket nem használjuk. A fels˝o k bit alatti bitek a konstruktort követ˝o értékek k´ odol´ as´ ara szolg´ alnak. Az, hogy a fels˝ o k bit alatti bitvektorrészlet milyen elosztásban tartalmazza az egyes értékeket, a konstruktort´ ol f¨ ugg. Az ADT-nek megfelel˝o teljes bitvektor hossza a legtöbb bitet igényl˝o t´ıpusalternat´ıva hossz´ aval egyenl˝o. Ha egy adott t´ıpusalternat´ıva esetében az ábrázolás kevesebb bitet igényel, mint a teljes bitvektor szélessége, akkor a fennmaradó bitek értéke konvencion´ alisan 0 . Az imént le´ırt reprezent´ aci´ ot egy példán fogom demonstrálni. A Maybe Int ADT-hez a következ˝o bitvektort kell létrehoznunk:

32. bit

31-0. bitek

Konstruktor

Int

A konstruktor elfér egy biten, hiszen a Maybe a t´ıpus esetén értéke Nothing ill. Just lehet csak. Ezek alapj´ an néh´ any konkrét konstans ábrázolása:

Nothing => 100000000000000000000000000000000 Just 64 => 000000000000000000000000001000000 Just 31 => 000000000000000000000000000011111

Ebben a péld´ aban a Nothing konstruktor kódja 1 , a Just konstruktor kódja 0 (ezek láthatóak az MSB-n), a fennmarad´ o 32 bit pedig az Int triviális ábrázolása.

Vez´ erl´ esi szerkezet lek´ epz´ ese A szakirodalomban [10] két, alapj´ aban k¨ ulönböz˝o vezérlési szerkezetet k¨ ulönböztetnek meg, az egyik egy k¨ ozpontos´ıtott vezérl˝oáramkört feltételez, a másik pedig elosztottan, 24

minden m˝ uvelethez saj´ at sorrendi hálózatot társ´ıtva oldja meg a vezérlés problémáját. Választ´ asom az elosztott vezérlésre esett, ez ugyanis teljes mértékben skálázható és az adatfolyam-szemlélettel sokkal inkább o¨sszeegyeztethet˝o eljárás. Ezek alapj´ an minden egyes m˝ uvelethez csatolunk egy DCC-t (elosztott vezérl˝o cella). Az egyszer˝ u m˝ uveletek esetében ez egy nagyon egyszer˝ u kapcsolás, tulajdonképpen csak annyi a feladata, hogy amint az o¨sszes bemenetén vezérl˝ojel érkezett, a kimeneti vezérl˝obitet akt´ıvra ´ all´ıtja, ez´ altal az adatfolyamban következ˝o m˝ uveletet értes´ıti a m˝ uvelet ´ befejeztér˝ ol. Ez a funkcionalit´ as egy egyszer˝ u ES kapuval megvalós´ıtható. A vezérl˝ obitek tulajdonképpen azt jelzik, hogy a hozzá tartozó adat´ uton éppen érvényes adat van-e. A konkrét megval´ os´ıt´ as a DCC-hez tartozó csomópont t lefutási idejét˝ol f¨ ugg. Ha egy olyan csom´ opontr´ ol van sz´ o, amely csak egy kombinációs hálózatot tartalmaz (t = 0), ´ kapur´ ´ kapu kimenetére egy akkor egyszer˝ u ES ol beszél¨ unk, ha viszont t > 0, akkor az ES t hossz´ u késleltetést is implementálnunk kell.

M˝ uveletek kombin´ aci´ os h´ al´ ozatk´ ent Legegyszer˝ ubb esetben az elemi f¨ uggvény funkcionalitásának megfelel˝o EOG m˝ uvelet egy egyszer˝ u kombin´ aci´ os h´ al´ ozattal megvalós´ıtható. A kombinációs hálózat t´ıpus´ u m˝ uveletek VHDL nyelven t¨ ortén˝ o le´ır´ asát az eddig is használt példán, az o¨sszeadás m˝ uveleten mutatom be. A 2.3. ´ abr´ an l´ atható a m˝ uvelet VHDL kódja és az ebb˝ol Xilinx ISE által generált RTL kapcsol´ asi rajz. Az entity rész meghat´ arozza a VHDL modul interfészét, az architecture pedig a bels˝o viselkedést ´ırja le. L´ athat´ o, hogy bitvektorként két bemenet¨ unk és egy kimenet¨ unk van, a kimeneti érték pedig a két bemenet összege. Ugyancsak két bemenet és egy kimenet szolgál a vezérlés lebonyol´ıt´ as´ ara, de ezek már egy bites portok. Mivel a modul egy egyszer˝ u kombin´ aci´ os h´ al´ ozat, megjegyzésben fel kell t˝ untetn¨ unk a 0 átfutási id˝ot, erre szolgál a latency = 0 sor. Minden egyes aszinkron m˝ uvelethez egy-egy ehhez hasonló VHDL modul tartozik, és ezeket egy-egy k¨ ul¨ on f´ ajlban t´ aroljuk. A modulok rendelkezhetnek generikus paraméterekkel, ami azt jelenti, hogy a VHDL kód egy részét a péld´ anyos´ıt´ as helyén megadott adatokkal cseréli ki a szintézer. Ez egy fontos tulajdons´ ag, ugyanis ezt a lehet˝oséget kihasználva elég pl. egy általános o¨sszead´ ot definiálnunk, aminek a bitsz´ am paraméterét példányos´ıtáskor adjuk meg, ´ıgy nem kell a k¨ ulönb¨ oz˝ o bitsz´ am´ u m˝ uveletekhez k¨ ulönböz˝o VHDL modult létrehoznunk a m˝ uvelethalmazban. A CλasH egyik h´ atr´ anya, hogy a VHDL kódban nem használ generikus paramétereket.

M˝ uveletek szinkron h´ al´ ozatk´ ent Léteznek olyan m˝ uveletek, amelyek csak szinkron hálózatként valós´ıthatóak meg, ilyen pl. egy ´ allapotgép, vagy egy blokk-RAM olvasó és ´ıró m˝ uvelete. Ezen k´ıv¨ ul minden kombinációs h´ al´ ozattal megadott m˝ uvelet le´ırható szinkron hálózattal is. Egy aszinkron hál´ ozat helyett bevezetett szinkron hálózatnak többek között akkor van létjogosultsága, ha a

25

l i b r a r y IEEE ; use IEEE . STD LOGIC 1164 .ALL; use IEEE . STD LOGIC ARITH .ALL; use IEEE . STD LOGIC UNSIGNED .ALL; −− l a t e n c y = 0 entity add i s generic ( p1 : i n t e g e r ) ; port ( a : in s t d l o g i c b : in s t d l o g i c q : out s t d l o g i c ca : in s t d l o g i c cb : in s t d l o g i c cq : out s t d l o g i c ); end add ;

v e c t o r ( ( p1 −1) downto 0 ) ; v e c t o r ( ( p1 −1) downto 0 ) ; v e c t o r ( ( p1 −1) downto 0 ) ; ; ;

architecture B e h a v i o r a l of add i s begin q <= a+b ; cq <= ca and cb ; end B e h a v i o r a l ; 2.3. ´ abra. Aszinkron összeadó

kombinációs h´ al´ ozatként megval´ os´ıtott m˝ uveletek nagy száma miatt a flip-flopok közötti vezetékek nagyon hossz´ uak lennének. Ekkor ugyanis a szintézernek az egész alkalmazás órajelét alacsonyan kellene tartania, ami negat´ıv hatással lehet egy másik részegység teljes´ıtményére. Ebben az esetben az szinkron hálózatra való áttérés jav´ıthat a maximális órajelsebességen, ´ıgy a teljes rendszer teljes´ıtményén. Az el˝obbi ¨ osszead´ o szinkronh´ al´ ozatt´ a alak´ıtott változata a 2.4. ábrán követhet˝o nyomon. Az el˝oz˝oekhez képest az RTL ´ abr´ an egyetlen szembet˝ un˝o változás található, ez pedig a vezérlés kimeneténél megjelen˝ o D flip-flop a vezérl˝o ág kimenetén. A kódban megjelenik a clk órajel port, és a process szekci´ o az órajelre történ˝o vezérléshez. A latency itt 1, mivel a m˝ uvelet egy ´ orajel alatt hajt´ odik végre. Id˝oigényesebb m˝ uveleteknél (pl. osztás) sokszor el˝ofordul, hogy a futási id˝o t > 1, ilyen 26

−− l a t e n c y = 1 entity add i s generic ( p1 : i n t e g e r ) ; port ( a : in s t d l o g i c b : in s t d l o g i c q : out s t d l o g i c ca : in s t d l o g i c cb : in s t d l o g i c cq : out s t d l o g i c c l k : in s t d l o g i c ); end add ;

v e c t o r ( ( p1 −1) downto 0 ) ; v e c t o r ( ( p1 −1) downto 0 ) ; v e c t o r ( ( p1 −1) downto 0 ) ; ; ; ;

architecture B e h a v i o r a l of add i s begin q <= a+b ; p r o c e s s 1 : process ( c l k ) begin i f ( c l k ’ e v e n t and c l k = ’ 1 ’ ) then cq <= ca and cb ; end i f ; end process ; end B e h a v i o r a l ; 2.4. ´ abra. Szinkron o¨sszeadó

esetben a flip-flop helyett t¨ obb o´rajel hossz´ u id˝oz´ıt˝o egységet kell beép´ıten¨ unk, vagy a vezérlés kimenetét k¨ ozvetlen¨ ul a bels˝o állapotgépre kell kötn¨ unk.

Legfels˝ o szint˝ u modul A legfels˝ o szint˝ u modul az egyetlen, ford´ıtás során generált VHDL modul. Ez tulajdonképpen az EOG gr´ afnak megfeleltethet˝o hardverle´ırás, ami kizárólag modul példányos´ıtásokat és a modulok k¨ ozt fut´ o vezetékeket (bitvektorokat) tartalmaz. A topmodulban minden EOG m˝ uvelet péld´ anyos´ıtásként, és minden EOG adatfolyam bitvektorként jelenik meg. 27

entity main i s port ( i n 1 in2 in3 out1 ); end main ;

: : : :

in in in out

std std std std

logic logic logic logic

vector vector vector vector

(39 (39 (39 (39

downto downto downto downto

0); 0); 0); 0)

architecture B e h a v i o r a l of main i s component add i s generic ( p1 : i n t e g e r ) ; port ( a : in s t d l o g i c v e c t o r ( ( p1 −1) downto 0 ) ; b : in s t d l o g i c v e c t o r ( ( p1 −1) downto 0 ) ; q : out s t d l o g i c v e c t o r ( ( p1 −1) downto 0 ) ); end component ; s i g n a l x : s t d l o g i c v e c t o r ( 3 9 downto 0 ) ; s i g n a l cx : b o o l e a n ; −− o s s z e s t o b b i k o z t e s a d a t f o l y a m d e k l a r a c i o j a begin −− add p e l d a n y o s i t a s a add1 neven add1 : add generic map ( p1 => 4 0 ) port map( in1 , in2 , x ) ; −− add p e l d a n y o s i t a s a add2 neven add2 : add generic map ( p1 => 4 0 ) port map( x , in3 , out1 ) ; −− o s s z e s t o b b i p e l d a n y o s i t a s end B e h a v i o r a l ; 2.5. ´ abra. VHDL topmodul példa

A topmodul egy lehetséges péld´ aj´ at a 2.5. ábra mutatja. Az entity rész a teljes alkalmazás ki- és bemeneteit sorolja fel. Az architecture szakaszban el˝oször deklarálnunk kell minden kés˝ obb haszn´ alt modult (component kifejezés), majd az adatfolyamoknak megfelel˝o vezetékeket deklar´ aljuk. Minden adatfolyamhoz két deklaráció tartozik, egyik az adatvezetékeket, m´ asik pedig a vezérl˝ o vezetéket hozza létre. Az architecture t¨ orzsében a m˝ uveleteknek megfelel˝o modulpéldányos´ıtások szerepelnek. A modulok portjaiként egyrészt az imént deklarált vezetékek, másrészt az alkalmazás ki- és bemenetei szerepelhetnek.

2.1.4. M˝ uvelethalmaz A m˝ uvelethalmaz egy olyan interfész, ami felsorolja a forráskódban legálisan felhasználható f¨ uggvényeket és t´ıpusokat, ill. ezekhez konkrét hardveres megvalós´ıtást társ´ıt VHDL le´ırás 28

formáj´ aban. A m˝ uvelethalmazt egyar´ ant felhasználja a Haskell-EOG és az EOG-VHDL ford´ıtómodul is. Az el˝ obbinek ez alapj´ an kell eldöntenie, hogy a használt m˝ uveletek definiáltak-e, vagyis a megadott hib´ atlan szintaktik´ aj´ u forráskód ténylegesen ford´ıtható-e. A VHDL-t generál´ o ford´ıtó a m˝ uvelethalmazban definiált VHDL modulokat példányos´ıtja a kimeneti le´ırásban. A m˝ uvelethalmaz el˝ osz¨ or is magában foglalja a már bevezetett, m˝ uvelethalmazra jellemz˝o f¨ uggvényeket export´ al´ o modult (InstructionSet.hs ), amit a felhasználónak a Prelude helyett import´ alnia kell saj´ at forráskódjában. A használható elemi f¨ uggvények listáját, vagyis a FOpMap-ot ezen k´ıv¨ ul a Haskell-EOG ford´ıtó is megkapja a következ˝o példával szemléltetett f´ ajlform´ atumban:

GHC.Num.(+) GHC.Classes.(||) GHC.Num.abs

Add Or Abs

Ez a leképzés kett˝ os célt szolgál. Egyrészt a Haskell-EOG ford´ıtó ennek seg´ıtségével el tudja d¨ onteni, hogy egy adott elemi f¨ uggvény használata jogos-e, másrészt az EOG le´ırásban nem engedélyezett karaktersorozatok helyett helyettes´ıt˝o neveket vezet be. (a példában a (+) nev˝ u helyett bevezetésre ker¨ ult az Add f¨ uggvény) Egy m´ asik fontos leképezés az OpVhdlMap, ami az adott esetben polimorf módon le´ırt elemi f¨ uggvényeket EOG m˝ uveleti nevekre képezi le. (ezek a nevek már megegyeznek a m˝ uveletnek megfelel˝ o VHDL modul nevével) A polimorf le´ırás azt jelenti, hogy a f¨ uggvény neve ut´ an generikus paraméterként (<> ) szerepelnek a f¨ uggvény t´ıpusargumentumai is. A leképzés egy lehetséges péld´ aja:

Add Add Add Or Abs

add<32> add<8> add_float or abs<32>

Ebb˝ ol a péld´ ab´ ol az l´ athat´ o, hogy a 8 és 32 bites Int -re vonatkozó összeadás egyaránt elvégezhet˝ o az add nev˝ u VHDL modullal, egy esetleges Float t´ıpusargumentummal megh´ıvott o¨sszead´ ast viszont m´ ar egy másik VHDL modulnak kell hardveresen implementálnia, mert a lebeg˝ opontos értékek ¨ osszeadása az egész t´ıpusokéhoz képest t´ ulságosan eltér. A m˝ uvelethalmaz az iménti leképzéseken k´ıv¨ ul definiálja az egyes elemi f¨ uggvények viselkedését le´ır´ o VHDL modulokat a 2.3. és a 2.4. ábrákon már bemutatott formában. A modulok interfésze (entity) kötött sorrendben tartalmazza a portokat, egy két bemenet˝ u EOG m˝ uvelet esetében pl. az ábrákon látható formában kell azokat megadni. A modul portjainak els˝ o fele az adatokat, a második fele a vezérlést szolgálja. Az a és a b a modul bemeneti paraméterei, a q a kimenet, a c prefixszel ellátott változatok pedig az ugyanezen jelekhez tartoz´ o vezérl˝obitek. Ahogy az EOG interfész le´ırásánál már ´ırtam, a 29

m˝ uveletek csak egyetlen kimenettel rendelkezhetnek, ez azt jelenti, hogy a modul portjai köz¨ ul pontosan kett˝ o, egy adat és egy vezérl˝o port lesz kimeneti irány´ u. Az eddigiek ¨ osszefoglal´ asaképpen négy pontban felsoroltam a m˝ uvelethalmaz elemeit: • InstructionSet.hs - az egyed¨ uli, használható, beép´ıtett” könyvtár ” • fop.map - FOpMap leképzés • opvhdl.map - OpVhdl leképzés • m˝ uveletenként egy-egy .vhdl f´ ajl - a m˝ uvelet hardverle´ırására

2.2. Forr´ ask´ od ford´ıt´ asa elemi m˝ uveleti gr´ afra A 2.1.2 fejezetben bemutatott elemi m˝ uveleti gráf a ford´ıtás során egy közb¨ uls˝o, egyszer˝ u absztrakt le´ır´ as´ at adja a funkcion´ alis nyelven megfogalmazott algoritmusnak. A most következ˝o fejezetben ismertetem a Haskell forráskód és az elemi m˝ uveleti gráf közötti átalak´ıtási lépéseket, és az ezekhez sz¨ ukséges algoritmusokat. A forrásk´ odok feldolgoz´ as´ at szerencsére nem kell a legels˝o lépéssel, vagyis a lexikális elemzéssel kezdeni, ugyanis ehhez a forrásnyelvhez létezik már szabad forráskód´ u ford´ıtóprogram. A Haskell forr´ ask´ odok PC-s t´ argykódra ford´ıtására a jelenleg leginkább elterjedt szoftver a Glasgow Haskell Compiler (GHC) [7]. Ez a ford´ıtó is, mint általában a ford´ıtók többsége két j´ ol elk¨ ul¨ on´ıthet˝ o ford´ıt´ asi fázist k¨ ulönböztet meg, egyik a forráskódot egy köztes, leegyszer˝ us´ıtett nyelvre ford´ıtja (frontend fokozat), a másik pedig a köztes nyelvi le´ırásból vég¨ ul t´ argyk´ odot gener´ al (backend fokozat). A GHC frontend végzi a lexik´ alis és szintaktikai elemzést, a szintaktikai édes´ıt˝oszereket feloldja, elkész´ıti az absztrakt szintaxis fát (AST) és alapvet˝o kódoptimalizálást végez. Ezek a funkci´ ok a jelen rendszer sz´ am´ ara is nélk¨ ulözhetetlenek, ezért célszer˝ u ezt a – már meglév˝o – programrészt felhaszn´ alni, elker¨ ulve ezzel ugyanilyen funkciók saját kóddal történ˝o u ´jbóli implement´ al´ as´ at. A CλasH a legels˝o, optimalizáció el˝otti Core reprezentációt veszi alapul, az én megold´ asom pedig az egyszer˝ us´ıtések utánit. Ez a megoldás azért el˝onyös, mert kihaszn´ alja a GHC nagyfok´ u optimalizálását, ´ıgy többek között a magasszint˝ u át´ırási szabályok (rewrite rules) is lefutnak. A GHC backendje u ´gy kész¨ ult, hogy a ford´ıtás végén processzoros tárgykódot kapjunk, ´ıgy ez a rész sz´ amunkra nem u ´jrafelhasználható. A frontend és backend k¨ oz¨ ott az 1.2.1. fejezetben már ismertetett Core nyelv szolgál köztes interfészként. A Haskell forr´ ask´ od helyett az EOG ford´ıtáshoz ezt a reprezentációt tekintem kiindul´ asi alapnak. Ha j¨ ov˝ oben Haskell helyett más funkcionális nyelvet k´ıvánunk hardveres környezetre ford´ıtani, akkor egy jó megoldás lehet Core alakra hozni azt; ´ıgy a dolgozatom sor´ an elkész¨ ult modulok teljes egészében felhasználhatóak lesznek, csupán a GHC frontend rész helyett kell egy adott nyelvre specializált frontendet implementálni. A GHC alapj´ aban egy t¨ obb platformra is leford´ıtott parancssori program, de emellett a konkrét ford´ıt´ ast végz˝ o részeket kiexportálták könyvtári f¨ uggvényekként is, vagyis egy Haskell nyelven ´ırt programmal k¨ onnyedén tudunk Haskell kódot ford´ıtani, s˝ot, a ford´ıtás lépéseit és azok paraméterét mélyrehatóan tudjuk szabályozni. 30

A k¨ ovetkez˝ o alfejezetekben bemutatom az egyes lépések algoritmusait, amik alapj´ an implement´ altam az elkész¨ ult Haskell-EOG modult. Ebben a részben szerepelni fognak Core nyelvi részletek, ´ıgy a használt szintaktikáról szót kell ejtenem. A Core faszerkezet sz¨ ul˝o-gyermek viszony´ at beh´ uz´ assal fogom jelölni, ahol minden azonos sz¨ ul˝ohöz tartoz´ o gyermek azonos oszlopban kezd˝ odik. Péld´ an szemléltetve:

a = lam t u app (+) var t var u

Az app teh´ at a lam egyed¨ uli gyereke, a két var sz¨ ul˝oje pedig az app . Az a = egy azonos´ıt´ o-kifejezés o ¨sszerendelést (a Core szerint ez a Bind ) jelent, ahol a kifejezést gyerekként ´ abr´ azoljuk (ez lesz a lam ). A var -nak és a lit -nek nincs gyereke, a lam -nak és a let -nek egy gyereke van. Az app nak annyi gyermeke van, amennyi paraméterrel rendelkezik, ami eltérés az eredeti Core reprezent´ aci´ ohoz képest, hiszen a lambda-kalkulusban csak egy paraméter˝ u alkalmazások találhat´ oak. Ezt a reprezent´ aci´ ot az egyszer˝ uség kedvéért vezetem be, de a gyakorlati megval´ os´ıt´ asn´ al ugyancsak el˝ oker¨ ul ez az átalak´ıtás. Szerencsére a b˝obeszéd˝ u Core App csomópontjait f¨ uggvénynévre és paraméterlistára átalak´ıtó m˝ uveletet egy GHC könyvtári f¨ uggvény (collectArgs ) megh´ıvásával könnyedén el tudjuk végezni. A case csom´ opont sorrendben els˝o gyermekeként a saját kifejezését, többi gyermekként pedig az el´ agaz´ o alternat´ıv´ akat tartalmazza. A 2.6. ´ abr´ an a Haskell-EOG ford´ıtó architekt´ urája látható, ahol az egyes algoritmusok c´ımszavakban:

1. GHC frontend: forr´ ask´ od magasszint˝ u feldolgozása 2. CaseReduction: el´ agaz´ asok átalak´ıtása 3. IterateConversion: iter´ aci´ ok átalak´ıtása 4. AppRename: alkalmaz´ asok átnevezése 5. CoreToTree: h´ıv´ asi f´ ara t¨ ortén˝o átalak´ıtás 6. TreeSimplifier: faegyszer˝ us´ıtés 7. ConvertToEOG: elemi m˝ uveleti gráfra történ˝o átalak´ıtás A k¨ ovetkez˝ o alfejezetekben részletesen ismertetem a ford´ıtás egymás-utáni fázisait. 31

Algoritmus Haskell nyelven

Művelethalmaz

GHC frontend

FOpMap OpVhdlMap

CaseReduction

IterateConversion

AppRename

ConvertToEOG

TreeSimplifier

CoreToTree

Elemi műveleti gráf

2.6. ´ abra. A Haskell-EOG modul architektúrája

2.2.1. Forr´ ask´ od magasszint˝ u feldolgoz´ asa Ahogy már sz´ o volt r´ ola, a Haskell forr´ askód Core reprezentációra alak´ıtását a GHC könyvtári f¨ uggvényeivel el lehet végezni. A CλasH megoldásával ellentétben nem a kezdeti Core kimenetet haszn´ alom fel, hanem kihasználom a GHC optimalizációs algoritmusait, és az algoritmusok lefut´ asa ut´ an keletkez˝ o Core állapotot használom a következ˝o átalak´ıtási lépés bemeneteként. A GHC h´ arom optimaliz´ aci´ os szintet k¨ ulönböztet meg, 0 a nem optimalizált, 1 a jó min˝oség˝ u, de nem t´ ul hossz´ u ford´ıt´ assal elérhet˝o, a 2 pedig a maximálisan optimalizált kód. Mivel a hardver szempontj´ ab´ ol nagyon fontos az er˝oforrásigény minimálisra szor´ıtása, ezért a ford´ıt´ oprogramban a maxim´ alisan optimalizált kódot használom.

2.2.2. El´ agaz´ asok ´ atalak´ıt´ asa A Core reprezent´ aci´ o kétségk´ıv¨ ul legnagyobb bonyolultság´ u elemei a Case csomópontok, amik egyaránt haszn´ alatosak el´ agaz´ asok és mintailleszt´ esek le´ırására. A ford´ıtás során el˝obb vagy ut´ obb a Core ezen részeit is EOG elemekre (m˝ uveletekre és adatfolyamokra) kell ford´ıtanunk. Azt a megold´ ast v´ alasztottam, hogy a Case csomópontokat már a ford´ıtás elején Let és App csom´ opontokra alak´ıtom, ugyanis ezek EOG-ra ford´ıtása triviálisabb, és a kés˝obb sorra ker¨ ul˝ o CoreToTree algoritmus ezt minden további er˝ofesz´ıtés nélk¨ ul meg is fogja tenni. Ennek a lépésnek a miel˝ obbi elvégzése azért fontos, mert ezáltal a bonyolult Case szerkezettel a tov´ abbiakban nem kell foglalkoznom. A [24] 4.3.5 fejezetében ismertetett Case normalization eljárások nagyon hasonló feladatot látnak el, mint az itt le´ırt CaseReduction transzformáció. A k¨ ulönbség az, hogy az 32

én megold´ asomban minden Case csomópontot azonnal megsz¨ untetek, ezzel egyszer˝ us´ıtve a további ´ atalak´ıt´ asi lépéseket.

01: case of b 02: E 03: . 04: . 05: alt C1 c11 c12 06: . 07: . 08: . 09: . 10: . 11: E1 12: alt C2 c21 c22 13: . 14: . 15: . 16: . 17: . 18: E2

01: 02: let scrutinee_1 = E 03: b = scrutinee_1 04: app mux 05: let c11 = app select 06: var scrutinee_1 07: c12 = app select 08: var scrutinee_1 09: app ifcon 10: var scrutinee_1 11: E1 12: let c21 = app select 13: var scrutinee_1 14: c22 = app select 15: var scrutinee_1 16: app ifcon 17: var scrutinee_1 18: E2

2.7. ´ abra. CaseReduction a´ltalános képlet (a pont-ok csak az átláthatóságot seg´ıtik)

Az itt ismertetett algoritmus az, amely bemenetként kapja a közvetlen¨ ul a GHC könyvtárakb´ ol sz´ armaz´ o Core k´ odot, majd a 2.7. ábrán általánosságban ismertetett átalak´ıtást elvégzi. Els˝o lépésben bevezet¨ unk egy u ´j változót, scrutinee_1 néven, amihez a fenti kódban E -nek jel¨ olt scrutinee -t k¨ otj¨ uk. (ez analóg a CλasH Scrutinee simplification normaliz´ aciójával) A Case szintaktik´ aja megengedi egy u ´j változó bevezetését (a fenti kódban ezt b -vel jel¨ oltem), ilyen esetben ehhez hozzárendelj¨ uk a scrutinee_1 -et, tehát végeredményben mindkét v´ altoz´ o a scrutinee kifejezésre fog mutatni. A CλasH ezt az utóbbi változ´ o bevezetést elimin´ alja az´ altal, hogy a kódban az o¨sszes ilyen változót lecseréli az u ´j scrutinee_1 v´ altoz´ ora. Ezt a megold´ ast nem tartottam szerencsésnek, ugyanis az alkifejezések u ´jabb bej´ ar´ asa miatt plusz k¨ oltséggel jár. Az el˝ oz˝ o elj´ ar´ assal létrehozott Let törzsébe a mux nev˝ u, ebben a fázisban létrehozott alkalmaz´ as ker¨ ul. A mux egy olyan f¨ uggvény, amely több Maybe a t´ıpus´ u bemenetb˝ ol egyetlen Maybe a t´ıpus´ u adattal tér vissza. Azzal a bemenettel tér¨ unk vissza változtat´ as nélk¨ ul, amelyik Just konstruktorral rendelkezik. (ha több ilyen is van, akkor a paraméterek sorrendjében legels˝ ovel tér¨ unk vissza)

33

Egy három bemenet˝ u mux viselkedését tekintve a következ˝o, gyakorlatban nem realizált Haskell kóddal lenne ekvivalens: mux3 a b c = i f ( isJust ( a ) ) then a else i f ( isJust ( b ) ) then b else c

Fontos megjegyezni, hogy ez a Haskell kód nem ker¨ ul leford´ıtásra, mert ha ez megtörténne, azzal az egész ´ atalak´ıt´ as értelmét vesztené, ugyanis ez a kód szintén tartalmaz Case szerkezetet (if form´ aj´ aban), teh´ at ezzel a Case teljes eliminálása nem valósult volna meg. A megoldás az lesz, hogy ezt a speci´ alis f¨ uggvényt elemi f¨ uggvényként használom, tehát közvetlen¨ ul hardverben fogom implementálni. Térj¨ unk át a Case alternat´ıv´ aira, az alt csomópontokra. Minden ilyen bejegyzés egyegy Let csom´ opontra fordul, amiben az alt -ban bevezetett o¨sszes változót kötni fogjuk. (hasonlóan a CλasH Case Normalization megoldásához) A kötés változója az alt -ban megjelen˝o változ´ o, az ahhoz k¨ ot¨ ott kifejezés pedig a select alkalmazás lesz. Példaként tekints¨ uk meg, hogy a select milyen képzeletbeli viselkedést takar (a változó megnevezések a 2.7. ´ abr´ ab´ ol származnak): s e l e c t C 1 0 x = case x of { C1 c11 −> c11 }

Ezzel tulajdonképpen az illesztést valós´ıtottuk meg oly módon, hogy a select f¨ uggvény egy adott ADT kifejezésb˝ ol az adott konstruktorhoz tartozó egyik argumentumértéket adja vissza. Az iménti példak´ od a C1 konstruktor utáni legels˝o paramétert, azaz a c11 -et adja vissza. A mux -hoz hasonl´ oan ez a k´ od is kizárólag hardverben ker¨ ul implementálásra. A Let kifejezés t¨ orzsér˝ ol még nem esett szó. A törzs egy ifcon nev˝ u f¨ uggvény lesz, ami azért felel, hogy csak a megfelel˝ o konstruktor esetében értékelj¨ uk ki az adott kifejezést, és adjuk vissza annak eredményét. Az el˝obbiekhez hasonl´ oan az ifcon is le´ırható képzeletbeli Haskell kóddal: i f c o n C 1 x e = case x of { C1 −> Just e ; −> Nothing }

Ebben az esetben teh´ at akkor adjuk vissza az e kifejezést (ami az e kiértékelését fogja maga után vonni), ha az x argumentum a C1 konstruktorral kapott értéket. A bevezetett mux , select és ifcon alkalmaz´ asok tehát az imént ismertetett szemantikákkal helyettes´ıteni tudnak egy Case csom´ opontot, ´ıgy ez utóbbira a továbbiakban nem lesz sz¨ ukség. Példaként tekints¨ unk meg egy illesztést (2.8. ábra), és egy elágazást (2.9. ábra) megvalós´ıtó Core fát, és azoknak CaseReduction ´ atalak´ıtás utáni változatait!

34

01: case (bind wild) 02: app foo 03: lit 3 04: 05: alt (,,) a b c 06: 07: 08: 09: 10: 11: app bar 12: var a 13: var b

01: 02: let scrutinee_1 = app foo 03: lit 3 04: app mux 05: let a = app select<(,,),0> 06: var scrutinee_1 07: b = app select<(,,),1> 08: var scrutinee_1 09: c = app select<(,,),2> 10: var scrutinee_1 11: app bar 12: var a 13: var b 2.8. ´ abra. CaseReduction illesztés példa

01: case 02: app foo 03: lit 3 04: 05: alt Left a 06: 07: 08: 09: app bar1 10: var a 11: alt Right a 12: 13: 14: 15: app bar2 16: var a

01: 02: let scrutinee_2 = app foo 03: lit 3 04: app mux 05: let a = app select 06: var scrutinee_2 07: app ifcon 08: var scrutinee_2 09: app bar1 10: var a 11: let a = app select 12: var scrutinee_2 13: app ifcon 14: var scrutinee_2 15: app bar2 16: var a 2.9. ´ abra. CaseReduction elágazás példa

35

2.2.3. Iter´ aci´ ok ´ atalak´ıt´ asa A Core Rec {} kifejezéseit a ford´ıt´ oprogram nem dolgozza fel, ez ugyanis rekurz´ıv f¨ uggvényeket vagy v´ altoz´ ohivatkoz´ asokat eredményezne. Rekurzió nélk¨ ul viszont algoritmusok nagy számát z´ arn´ ank ki a ford´ıt´ as al´ ol, ami nem engedhet˝o meg. A probléma megoldására az iterate Haskell f¨ uggvény használatát vezetem be, amelynek eredeti defin´ıciója a GHC.List modulban tal´ alhat´ o: i t e r a t e : : ( a −> a ) −> a −> [ a ] iterate f x = x : iterate f ( f x)

Az iterate els˝ o paramétere egy egyparaméteres f f¨ uggvény, ami minden iterációban megh´ıvódik. Az f az els˝ o iter´ aci´ os lépésnél az iterate második paramétereként megadott kezdeti értéket, a k¨ ovetkez˝ o iter´ aci´ ok során pedig az azt megel˝oz˝o iterációs lépés kimenetét kapja. Az iterate k¨ ozvetlen¨ ul nem ford´ıtható EOG-ra, mivel f¨ uggvényparamétert tartalmaz. A megoldás az IterateConversion Core2Core transzformáció bevezetése, amely a ford´ıtó következ˝o lépései sz´ am´ ara feldolgozhat´ o formába alak´ıtja az iterációt. A CaseReduction lépésnél megismert szintaktika szerint elkész´ıtettem az IterateConversion transzform´ aci´ o´ altal´ anos képletét, amit a 2.10. ábrán ismertetek.

01: app iterate_old 02: lam x 03: E 04: E2 05: 06: 07:

01: let x = 02: app iterate_new 03: var it_out 04: E2 05: let it_out = 06: E 07: var it_out

2.10. ´ abra. IterateConversion a´ltalános képlet

A lam csom´ opont helyett egy let csomópontot vezetek be, ami a lam -ban szerepl˝o x paraméterhez egy u ´jonnan létrehozott kifejezést rendel. Egy u ´jabb let csomópont szintén bevezetésre ker¨ ul, ami az it_out azonos´ıtóhoz az eredeti bels˝o f¨ uggvény lam nélk¨ uli törzsét, azaz az E -t rendeli. Ez utóbbira azért van sz¨ ukség, hogy az E kifejezésre a továbbiakban két helyr˝ ol is hivatkozhassunk. Az x -hez rendelt u ´j kifejezés a f¨ uggvényparamétert˝ol mentes iterate_new alkalmazás, aminek els˝o paramétere az imént bevezetett it_out -ra mutató változó, második paramétere pedig az E2 , vagyis a kezdeti érték kifejezése. Az átalak´ıt´ ast megvizsg´ alva észrevehet˝o, hogy a var it_out bevezetése rekurziót eredményez, ugyanis az egy kés˝ obb bevezetett azonos´ıtóra hivatkozik. (ehhez még azt kell látni, hogy az E kifejezésgr´ af valahol tartalmaz egy var x csomópontot). Ahhoz, hogy a kés˝obbi CoreToTree algoritmus a behelyettes´ıtésekkel ne ker¨ uljön végtelenciklusba, a var it_out -ot egy olyan megjegyzéssel kell ellátnunk, ami az inline -t ezen a ponton 36

megakad´ alyozza.

2.2.4. Alkalmaz´ asok ´ atnevez´ ese Minden elemi f¨ uggvény alkalmaz´ asából EOG m˝ uvelet lesz, ezért ezeknek az alkalmazásoknak egyedi névvel kell rendelkezni¨ uk. Az itt ismertetett, alkalmazásoknak egyedi nevet ad´ o algoritmus a tov´ abbiakban AppRename néven fog szerepelni. A v´ altoz´ ok egyedi nevének t´ arolására a GHC egyszer˝ u lehet˝oséget biztos´ıt a változ´ ok unique mez˝ oivel. A ford´ıt´ o implementálása közbeni saját tapasztalatom, hogy a GHC által biztos´ıtott unique mez˝ ok nem mindig egyediek, pl. a Case csomópont egyes alternat´ıv´ ai tartalmaznak azonos unique értéket. (a Case csomópontokat az el˝oz˝oekben elimináltuk, de az átalak´ıt´ as ut´ an a nevek az u ´j t´ıpus´ u csomópontokban tovább léteznek) Megold´ asomban az alkalmaz´ asok változóinak unique mez˝oi oi formáj´ u értéket kapnak, ahol i az alkalmaz´ as egyedi sorsz´ ama. A sorszámot a Core fa inorder bejárása adja, ami azt jelenti, hogy ebben a sorrendben ker¨ ulnek az egyes indexek az alkalmazások változóinak unique mez˝ oibe.

2.2.5. H´ıv´ asi f´ ara t¨ ort´ en˝ o´ atalak´ıt´ as A Core reprezent´ aci´ o kiértékelésére és egy u ´j, operációkat és hivatkozásokat tartalmaz´ o ´ faszerkezet faszerkezet, az OpTree létrehoz´ asára a CoreToTree algoritmus szolgál. Uj létrehoz´ asa azért volt sz¨ ukséges, mert a Core reprezentáció t´ ulságosan lambda-kalkulus közeli, ´ıgy pl. a t¨ obb bemenet˝ u m˝ uveletek le´ırása nagyon kör¨ ulményes. A CλasH megold´ asban normalizációs eljárások sokaságát alkalmazzák, hogy vég¨ ul egy hardverk¨ ozeli Core sz¨ ulessen. A megoldás hátránya, hogy az egyes normalizációs eljár´ asok futtat´ asi sorrendje nem k¨ ot¨ ott, egy adott állapotban az az át´ırási szabály ind´ıthat´ o, amelynek az el˝ ofeltételei teljes¨ ulnek. Egy adott állapotban több normalizációs lépés is végrehajthat´ o, és a lépések sorrendjét˝ol f¨ ugg˝oen más-és-más végeredmény sz¨ ulethet, tehát az algoritmus nem konfluens. (a szerz˝o, véleményem szerint hibásan, a nem-determinisztikus” ” szót haszn´ alja ennek kifejezésére ([24] 4.4.2. fejezet)) Az én megold´ asomban normalizálás helyett supercompiling közeli technikát alkalmazok. A supercompiling-ot el˝ osz¨ or Turchin mutatta be 1986-ban [36], és azóta is nagy szám´ u cikk foglalkozott a tém´ aval, az egyik legfrissebb pl. Neil Mitchell 2010-es publikációja [29]. A supercompiling tulajdonképpen a program ford´ıtásidej˝ u végrehajtása, tehát pontosan olyan sorrendben j´ arjuk be a Core szerkezetet, ahogyan azt a processzor a programunk futása k¨ ozben tenné. Mivel a Haskell a lusta kiértékelésen alapul, ezért a bejárásnak is eszerint, vagyis call-by-need stratégiával kell történnie. Ahhoz, hogy a bej´ ar´ as minden pontján a ford´ıtóprogram tisztában legyen az ott haszn´ alható azonos´ıt´ ok halmaz´ aval, bevezetek egy környezetet reprezentáló t´ıpust. A környezet tulajdonképpen egy sor azonos´ıtó-kifejezés párt foglal magában, aminek az értelme az, hogy a kés˝ obbiekben az azonos´ıt´ oval hivatkozhatunk az adott kifejezésre. Fontos észrevenni, hogy a k¨ ornyezetet csupán két t´ıpus´ u Core csomópont képes b˝ov´ıteni, a Let , ami u ´j lok´ alis v´ altoz´ ot hoz létre és a Lam , ami u ´j paraméterváltozót hoz létre. (a 37

Case szintén b˝ ov´ıtene a k¨ ornyezetet, de az el˝oz˝o algoritmusok után ez a t´ıpus´ u csomópont már nem jelenlhet meg) A bejárás legbonyolultabb pontja az, amikor egy változó kiértékelésekor a változó által hivatkozott kifejezést kell behelyettes´ıten¨ unk. Ez a fázis nagyban hasonl´ıt az 1.2.3. fejezetben ismertetett GHC ´ altal megvalós´ıtott inlining-ra. Az algoritmus bej´ arja a teljes Core fát, mégpedig u ´gy, hogy els˝o körben kizárólag a hwmain glob´ alis o uk, hogy az egyes cso¨sszerendeléshez tartozó kifejezést értékeli ki. Nézz¨ mópontokhoz érve milyen lépéseket kell végrehajtanunk: • Lit literal : A legegyszer˝ ubb eset, egyetlen literált definiál. A Lit a Core fában egy levél, ezért csak annyi a dolgunk, hogy az OpTree fa adott pontjához ezt a levelet hozzáadjuk. • Let bind expr : A call-by-need stratégia értelmében a fához nem adunk hozzá egyetlen elemet sem, viszonyt a k¨ ornyezetet a bind -ben megadott kötéssel b˝ov´ıtj¨ uk. (azaz létrehozunk egy thunk-¨ ot [22]) A b˝ov´ıtés után a törzset (expr ) az u ´j környezetet átadva kiértékelj¨ uk, ´ıgy biztos´ıtva, hogy a továbbiakban az itt definiált azonos´ıtóra hivatkozhassunk. • App var [params] : Ez az alkalmazások azon formája, amely már több paramétert is tartalmazhat, mert a lambda-kalkulus egyparaméter˝ u alkalmazásait már egyszer˝ uen átalak´ıtottuk t¨ obbparaméter˝ u f¨ uggvényh´ıvásra. Itt két eset lehetséges: – Elemi f¨ uggvény esetén a f´ aban u ´j gyereket hozunk létre, ezeket ugyanis EOG m˝ uveletként kell megval´ os´ıtani. ¨ – Osszetett f¨ uggvény esetén behelyettes´ıtést kell végezn¨ unk. A kiértékelés következ˝ o lépése teh´ at a f¨ uggvény defin´ıciója lesz, amit a teljes eddigi, görgetett k¨ ornyezettel kell végrehajtanunk. Azért sz¨ ukségesek a környezet legutóbb felvett elemei is (teh´ at a lok´ alis vagy argumentum azonos´ıtók), mert a bejárandó lambda-absztrakci´ o a paraméterein kereszt¨ ul ezeket elérheti. A f¨ uggvény defin´ıci´ oj´ anak kiértékelésekor sz¨ ukségesek az argumentumok is, ezért a [params] t¨ omb elemeit ´ atadjuk, mégpedig a lusta kiértékelés miatt feldolgozás nélk¨ ul. • Lam b expr : Egy f¨ uggvény defin´ıciójának kiértékelése ezzel a csomóponttal kezd˝odik. Egy kivétellel minden esetben egy App csomópont el˝ozte meg közvetlen¨ ul ennek a kiértékelését, ez a kivétel pedig a legfels˝o szint˝ u Lam , amely paraméterein kereszt¨ ul kommunik´ al a k¨ ulvil´ aggal. A csomópont kiértékelésénél els˝o lépésként a paraméterill. argumentumlist´ ab´ ol képzett azonos´ıtó-kifejezés párokat a környezethez hozzá kell adnunk, arra az esetre, ha a f¨ uggvényen bel¨ uli csomópontokban hivatkozunk a paraméterekre. Ezt a k¨ ornyezetb˝ ov´ıtést azért ilyen kés˝on tessz¨ uk, mert a lokális névtérben szerepl˝ o paramétereket a Lam hozza létre, tehát a környezethez sz¨ ukséges azonos´ıtónevek csak ett˝ ol kezdve ´ allnak rendelkezésre. • Var id : a csom´ opontn´ al az ´ altala hivatkozott kifejezés értékét kell mögöttes jelentésként elképzeln¨ unk. Ha a hivatkozott kifejezést még nem értékelt¨ uk ki (tehát az csak 38

egy thunk), akkor erre a pontra érve ezt meg kell tenn¨ unk, tehát az adott kifejezést¨ orzset ide kell m´ asolnunk (behelyettes´ıtés). Ha a kiértékelés már megtörtént, akkor az OpTree f´ at csak egy referenciával kell kib˝ov´ıten¨ unk, ami a már kiértékelt kifejezésre (az OpTree m´ ar létez˝ o algráfjára) mutat. Háromfajta azonos´ıtót k¨ ulönböztet¨ unk meg: – glob´ alis azonos´ıt´ o: Amit bármelyik f¨ uggvény törzse elérhet. – lok´ alis azonos´ıt´ o: Egy Let hozta létre az azonos´ıtót, amit a fa ez alatti elemei érnek el. Ha ilyen v´ altozóhoz ér¨ unk, akkor az azonos´ıtóhoz rendelt kifejezés kiértékelésénél a k¨ ornyezet nem változik, hiszen egy lokális o¨sszerendelés nem mutat ki a lambda-absztrakcióból. – argumentum azonos´ıt´ o: Egy Lam hozta létre, szintén a fa ez alatti elemei érik el. Ha ilyen t´ıpus´ u változó ker¨ ul kiértékelésre, akkor a környezet legutols´ o szintjét elt´ avol´ıtjuk (hiszen a Lam -on k´ıv¨ ulr˝ol a Lam által hozzáadott azonos´ıt´ ok nem elérhet˝ oek) és ´ıgy folytatjuk a fabejárást. Az algoritmus m˝ uk¨ odését a 2.1. táblázattal demonstrálom.

a = lam t u app (+) var t var u

01. 02. 03. 04. 05.

node:(lam ...) node:(op +) node:(var t) go:09 node:(var u) go:10

+ [u=10,t=09] [yy..] [y..] [c..] atad: ([yy..] [y..] [c..]) ´ atad: ([yy..] [y..] [c..]) ´

lam aa xx yy app aa var xx var yy

06. 07. 08. 09. 10.

node:(lam node:(app node:(var node:(var

+ [yy=20,xx=19,aa=18] [y..] [c..] atad: ([yy..] [y..] [c..]) ´ atad: ([y,i,x] [c,b,a]) ´ atad: ([y,i,x] [c,b,a]) ´

lam x let i= lit 1 let y= var i app b var a var x var y

11. 12. 13. 14. 15. 16. 17. 18. 19. 20.

node:(lam node:(lit node:(var node:(app node:(var node:(lnk node:(var

b =

c =

...) aa) go:18 xx) go:19 yy) go:20

x) go:15 finish go:17 i) go:14 b) go:07 a) go:02 IN) back:05 y) go:16 1)

+ [c=12,b=07,a=02] + [x=IN] [c,b,a] + [i=14,x] [c,b,a] + [y=16,i,x] [c,b,a] atad: ([i] [c,b,a]) ´ atad: ([yy..] [y..] [c..]) ´ atad: ([i,x] [c,b,a]) ´

2.1. t´ abl´ azat. CoreToTree algoritmus példán keresztül

Az els˝ o oszlopban az algoritmus bemeneteként kapott Core reprezentáció látható. A m´ asodik oszlop az egyes Core elemekhez sorszámot rendel és a Core elemhez köt˝od˝o cselekvést tartalmazza. A go:n azt jelenti, hogy következ˝o lépésben az n. sort kell kiértékeln¨ unk, a node:(nodeexpr) pedig azt, hogy a kimeneti OpTree fában egy nodeexpr gyereket kell létrehoznunk. A harmadik oszlop a környezet mindenkori állapotát t¨ ukrözi. 39

A hwmain f¨ uggvény szerepét helytakarékossági okokból itt a c nev˝ u f¨ uggvény tölti be. Ezek alapján kiindul´ opontunk a c -hez kötött kifejezés, vagyis a 12. sorszámmal jelölt Core elem. A kezdeti k¨ ornyezetben a glob´ alis változók ([c,b,a] ) találhatóak, a program pedig soronként halad, kivéve, ha a go utas´ıtás másképp nem rendelkezik. A 14. és 16. sort ´ atugorjuk, hiszen a call-by-need miatt ezeket nem értékelhetj¨ uk ki addig, am´ıg a végs˝ o érték meghat´ aroz´ asa miatt ez elker¨ ulhetetlenné nem válik. A 17. sorban az alkalmaz´ as kiértékelése app b következik. Ez azt jelenti, hogy a következ˝o OpTree bejegyzések a f¨ uggvény t¨ orzséb˝ ol (7. sor) fognak származni. Láthatjuk, hogy a 7. sorban a környezet az yy , xx és aa argumentumváltozókkal b˝ov¨ ul. Az egyes azonos´ıtókhoz rendelt értékek a jobb ´ atl´ athat´ os´ ag végett a hivatkozott kifejezés sorszámát mutatják. A 8. sorban az aa nev˝ u paraméterben kapott f¨ uggvény alkalmazása követhet˝o látszik. A paraméter a 18. sorban kap értéket, de ez is csak egy hivatkozás a 2. sorban található a nev˝ u f¨ uggvény törzsére. A 3. sorban egy elemi f¨ uggvényt találunk, ´ıgy abból egy tényleges m˝ uveleti bejegyzés (op + ) keletlekzik az OpTree fában. A (+) f¨ uggvény els˝ o bemeneti paramétere többszörös indirekción (4. és 9. sorok) kereszt¨ ul elér a 19. sorban tal´ alhat´ o lnk IN csomópontig, ami vég¨ ul egy levél elem lesz az OpTree fában. Ezt k¨ ovet˝ oen a (+) f¨ uggvény második bemenete ker¨ ul kiértékelésre, ami szintén többsz¨ or¨ os indirekci´ on (5., 10., 20., 16. sorok) kereszt¨ ul a 14. sor lit 1 kifejezésénél ér véget (ebb˝ ol szintén OpTree levél lesz), és ezzel a teljes Core bemenetet bejárta az algoritmus. A kiértékelés eredménye, azaz a kimeneti OpTree fa vég¨ ul a következ˝o formát veszi fel:

lam x app b lam aa xx yy app aa var a lam t u op add var t var xx var x lnk IN var u var yy var y var i lit 1

Az OpTree fa a Core kiértékelt v´ altozata. Szerepel benne a Core Let kifejezésein k´ıv¨ ul az o¨sszes t¨ obbi, ´ıgy l´ athatjuk pl., hogy az összeadás m˝ uvelet operandusai három ill. négy indirekci´ on kereszt¨ ul jutnak el az o¨sszeadáshoz (t -xx -x és u -yy -y -i ). Az op + csomópont a CoreToTree kimenetén op add formában jelenik meg, mert a m˝ uvelethalmaz FOpMap leképzése a + jelet add -ra módos´ıtja. Az azonos´ıtók egyszer˝ uség kedvéért nem tartalmazzák a unique mez˝ ot, ´ıgy pl. az add_o8_i4 helyett csak add , az IN_1_a0 helyett pedig csak IN szerepel. 40

A lam , app és var elemek az EOG gráfban nem jelennek meg, ennek ellenére a hibakeresésnél nagyon fontos, hogy ezen a szinten még megmaradjanak.

2.2.6. Faegyszer˝ us´ıt´ es Az el˝oz˝ o pontban kialakult fa több olyan csomópontot is tartalmaz, amelyeket a kés˝obbiekben nem haszn´ alunk, ´ıgy ezeket meg kell sz˝ untetn¨ unk, ezt az egyszer˝ us´ıtést a TreeSimplifier algoritmus végzi el. Az algoritmus els˝ o lépése, hogy minden App , Lam és Var csomópontot elt¨ untet¨ unk oly módon, hogy ezeket a gyerek¨ ukkel helyettes´ıtj¨ uk. Ezt mindig meg tudjuk tenni, mert ezeknek a csom´ opontoknak k¨ otelez˝oen egyetlen gyereke kell, hogy legyen. Az algoritmus második lépése az, hogy minden egyes Lit csomópontot const t´ıpus´ u Op csomópontt´ a, azaz konstans m˝ uveletté alak´ıt. Elképzelhet˝ o, hogy egy konstans többször is felhasználásra ker¨ ul, pl. a lit 0 adott esetben sok helyen szerepel. Lehet˝oség lenne arra, hogy a konstans csomópont csak egyszer szerepeljen, és minden azt felhasználó m˝ uveletnek ide huzalozzuk be a bemenetét, de ez fölösleges és adott esetben a hardver vezetékeinek számát növeli. Emiatt minden konstanst csak egy m˝ uvelet haszn´ al, ezért a TreeSimplifier az o¨sszes konstansból egyedi nev˝ u Op csomópontot gener´ al. A k¨ ovetkez˝ o k´ odrészleten j´ ol l´ atszik, hogy a CoreToTree algoritmusnál bemutatott bonyolult, magasabbrend˝ u f¨ uggvényeket is tartalmazó Core le´ırásunk a TreeSimplifier lefutása ut´ an j´ oval egyszer˝ ubb form´ at vesz fel:

lam x add_o8_i4 lnk IN_1_a0 op const_1_i4

2.2.7. Elemi m˝ uveleti gr´ afra t¨ ort´ en˝ o´ atalak´ıt´ as A kialakult OpTree f´ at egy inorder bejárással könnyedén EOG fájlformátumra hozhatjuk. Az el˝obbi péld´ anak megfelel˝ o gr´ af a 2.11. ábrán látható. OUT

add_o8_i4

IN_1_a0

const_1_i4

2.11. ´ abra. OpTree

Az EOG els˝ o soraiban felsoroljuk az összes bemeneti, az utolsóban pedig a kimeneti 41

m˝ uveletet. A gr´ af inorder bej´ ar´ asa adja a be- és kimenetek közt az adatfolyamban található m˝ uveletek list´ aj´ at. Az inorder bej´ ar´ as szerinti els˝ o pont az IN_1_a0 , viszont ez csak egy link a bemenetre (ezt jelzi a piros sz´ın), ezért ezzel nem kell semmit tenni. Következ˝o lépés a const_1_i4 levél, ´ıgy ez ker¨ ul a bemenet ut´ ani els˝ o sorba. Ezt követi az add_o8_i4 cs´ ucs, ami ´ıgy a 2. sorba ker¨ ul, a sor végén pedig fel kell t˝ untetni bemenetként az IN_1_a0 és const_1_i4 gráfcs´ ucsokat. Ezeket követve a Haskell-EOG modul kimeneteként a következ˝o EOG le´ırást kapjuk:

IN_1_a0 const_1_i4 add_o8_i4 OUT

"SYSTEM" "const<1>" "add" IN_1_a0 const_1_i4 "SYSTEM" add_o8_i4

2.3. Elemi m˝ uveleti gr´ af ford´ıt´ asa hardverle´ır´ o nyelvre A fejezet sor´ an olyan m´ odszer ker¨ ul bemutatásra, amely a Haskell-EOG modul kimenetéb˝ol, azaz az EOG form´ atum´ u adatfolyam le´ırásból és a m˝ uvelethalmazból el˝oáll´ıtja a VHDL le´ırást. Ezt a le´ır´ ast a piacon kapható FPGA tervez˝o szoftverek fel tudják használni konkrét FPGA szintetiz´ al´ as´ ara, aminek eredményeképp a magas szinten megfogalmazott alkalmazást vég¨ ul ténylegesen hardverként implementálhatjuk. A ford´ıtó egyetlen VHDL modult szolgáltat kimenetként, ami a m˝ uvelethalmazban definiált és a konkrét algoritmusban felhasznált m˝ uveleteket példányos´ıtja, a között¨ uk sz¨ ukséges adatutakat pedig kialak´ıtja. Az EOG-VHDL ford´ıt´ omodul bels˝ o architekt´ uráját a 2.12. ábrán vázoltam. Az egyes almodulok jelentése: • ParseEOG: feldolgozza az elemi m˝ uveleti gráfot, és egy bels˝o strukt´ urában (Operations ) eltárolja. • MakeModuleList: o ujti az összes, EOG-ben megjelen˝o m˝ uveletet, és a hoz¨sszegy˝ zájuk tartoz´ o VHDL modulokat feldolgozza. A feldolgozás eredményeképp létrehozza a ModuleList struktur´ at, ami az egyes m˝ uveletekhez tartozó legfontosabb paramétereket t´ arolja. (latency, port és generic deklarációk) • ProduceComponents: a ModuleList-b˝ol VHDL component szekciókat generál. Ezek a szekci´ ok a topmodulban deklarálják a felhasználni k´ıvánt modulokat, hogy azokat a f˝ omodul t¨ orzsében péld´ anyos´ıtani lehessen. • ProduceSignals: minden m˝ uvelethez létrehozza a hozzá tartozó kimeneti vezetékeket, egy adatvezetéket és egy vezérl˝o vezetéket. Az el˝obbi a m˝ uvelet kimeneti adatcsatornáját, az ut´ obbi pedig az adott csomóponthoz tartozó kimeneti vezérl˝obitet fogja reprezent´ alni. Az adatvezeték bitszámát a m˝ uvelethez tartozó, ModuleList-ben eltárolt deklar´ aci´ ok (port és generic) és a példányos´ıtásnál megadott sablonparaméterek határozz´ ak meg. 42

Elemi műveleti gráf

Művelethalmaz

ParseEOG

MakeModuleList

Operations

ModulList

ProduceOperations

ProduceSignals

OpVhdlMap VhdlModules

ProduceComponents Topmodul sablon

GenerateVHDL

VHDL topmodul

2.12. ´ abra. Az EOG-VHDL modul architektúrája

• ProduceOperations: minden m˝ uvelethez létrehozza az adott t´ıpusnak megfelel˝ o modulpéld´ anyos´ıt´ ast. Péld´ anyos´ıtáskor az EOG t´ıpusnevekben szerepl˝o sablonparamétereket haszn´ alja a generic map -ben, ill. a ProduceComponents által létrehozott k¨ oztes vezetékeket és a ki- bemeneti portokat használja a port map-ben. • GenerateVHDL: a 2.13. a´brán bemutatott topmodul sablonfájl alapján létrehozza a végs˝ o, kimeneti topmodult, azaz a sablonba beilleszti a hiányzó VHDL szekciókat. (a k´ odban a hi´ anyz´ o szekci´ okat %input% , %output% , %components% , %signals% és %operations% sablonparaméterként jelzem).

2.4. Alap m˝ uvelethalmaz defini´ al´ asa A Haskell-VHDL ford´ıt´ oprogram az el˝oz˝o fejezetekben le´ırt algoritmusok alapján elkész¨ ult. A megengedett forr´ asnyelvi f¨ uggvények és t´ıpusok listáját eddig a pontig nem definiáltam, tettem ezt azért, mert a v´ altoztatható m˝ uvelethalmaz bevezetésével a ford´ıtóprogram és a ford´ıthat´ o elemi f¨ uggvények listája szétválik egymástól. A most következ˝o fejezetben bepótolom a hi´ anyoss´ agot, és teljeskör˝ uen definiálok egy alap m˝ uvelethalmazt.

2.4.1. A m˝ uvelethalmazok k¨ otelez˝ o elemei A Haskell-EOG ford´ıt´ o algoritmusai bevezetnek olyan m˝ uveleteket, amelyek nem a forráskódban megadott elemi f¨ uggvények megfelel˝oi, hanem a Haskell forráskód bizonyos kifejezései miatt ker¨ ulnek az EOG interfészre. Ilyen kifejezés a case szerkezet, amelyet a CaseReduction algoritmus h´ arom k¨ ulönböz˝o m˝ uveletre alak´ıt (select , ifcon , mux ), 43

l i b r a r y IEEE ; use IEEE . STD LOGIC 1164 .ALL; use IEEE . STD LOGIC ARITH .ALL; use IEEE . STD LOGIC UNSIGNED .ALL; use work . d e f s . a l l ; entity benchmark i s port ( r e s t a r t , c l k : in s t d l o g i c ; %i n p u t% : in s t d l o g i c v e c t o r ( 3 1 downto 0 ) ; Output : out s t d l o g i c v e c t o r ( 9 5 downto 0 ) ; c%i n p u t% : in s t d l o g i c ; cOutput : out s t d l o g i c ); end benchmark ; architecture B e h a v i o r a l of benchmark i s %components% %s i g n a l s% begin %o p e r a t i o n s% Output <= %output %; cOutput <= c%output %; end B e h a v i o r a l ; 2.13. ´ abra. VHDL topmodul sablon

ezenk´ıv¨ ul a konstansok (const ) és a Core alkalmazásként megvalósuló adatkonstruktorok (dcon ). Az IterationConversion algoritmus az iterate f¨ uggvénnyel operál, ´ıgy ez is része a k¨ otelez˝ o elemeknek. Ezeknek a m˝ uveleteknek sz¨ ukségképpen minden m˝ uvelethalmaznak elemei kell, hogy legyenek, hiszen bármelyik Haskell forráskód tartalmazhatja ezeket a kifejezéseket. A Haskell-EOG ford´ıtó öt k¨ ulönböz˝o m˝ uveletet vezet be, ezek listáját a 2.2. ábrán soroltam fel, az egyes m˝ uveletek és paramétereik jelentése pedig a következ˝o: • const : olyan m˝ uvelet, amelynek nincs bemeneti paramétere, ´ıgy a kimenetén mindig egy konstans értéket k¨ ozvet´ıt – width : a konstans bitszélessége const dcon1 dcon2 dcon3 select ifcon mux2 mux3 iterate

Const<width,value> DCon1 DCon2 DCon3 Select Ifcon<width,cw,c> Mux2<width> Mux3<width> Iterate<width>

konstans 1 param. ADT konstruálás 2 param. ADT konstruálás 3 param. ADT konstruálás ADT adatleválasztás case alternat´ıva case multiplex (2 irány) case multiplex (3 irány) iteráció

2.2. t´ abl´ azat. Kötelez˝o m˝uvelethalmaz elemek (az oszlopok rendre: bevezetett függvénynév, VHDL modulnév sablonparaméterekkel és a m˝ uvelet le´ır´ asa)

44

– value : a konstans értéke • dcon1 ..dcon3 : létrehoz egy ADT adatot megadott konstruktorral és paraméterekkel (data constructor) – cw : a konstruktor bitszélessége – c : a konstruktor értéke – v1 ..v3 : a konstruktor utáni paraméterek (számuk attól f¨ ugg, hogy az adott konstruktornak h´ any paramétere van) • select : egy ADT adat´ utr´ ol leválasztja az egyik konstruktor utáni értéket – inw : a bemeneti bitszélesség – from : az els˝ o olyan bit sorszáma, amely szerepelni fog a kimeneten – outw : a kimeneti bitszélesség • ifcon : megvizsg´ alja, hogy egy ADT adat´ uton a megfelel˝o konstruktorral érkezik-e az adat, ha a v´ alasz igen, adattovább´ıtás történik – width : a bemeneti bitszélesség – cw : a konstruktor bitszélessége – c : a konstruktor értéke • mux2 ..mux3 : az el´ agaz´ asok utáni egyes´ıtésért felel (az elágazások száma szerint k¨ ul¨ onb¨ oz˝ o megval´ os´ıt´ as sz¨ ukséges) – width : a ki- és bemeneti bitszélesség • iterate : iter´ aci´ ot megval´ os´ıtó m˝ uvelet, ami a Haskell iterate f¨ uggvényb˝ol, átalak´ıt´ assal j¨ on létre. – width : a ki- és bemeneti bitszélesség

2.4.2. Egyszer˝ u alapm˝ uveletek Megvizsg´ altam a GHC 6.12.2 verziójának Prelude alapkönyvtárát [5], és ezt alapul véve meghat´ aroztam azokat a m˝ uveleteket, amelyek a számt´ıpusokon értelmesek és seg´ıtség¨ ukkel matematikai f¨ uggvények széles köre ´ırható le. A sz´ amt´ıpusok k¨ oz¨ ul kiz´ arom a Rational és az Integer használatát, ezek ugyanis rekurz´ıv strukt´ ur´ ak, ´ıgy azok implementálása a végtelen számok ábrázolásának elker¨ ulése érdekében nem val´ osulhat meg. A lebeg˝opontos t´ıpusok implementálása megvalós´ıthat´ o lenne létez˝ o, VHDL form´ aban adott hardveres IP-kkel. Ezek er˝oforrásigénye kifejezetten nagy, viszont lényegében nem v´ altoztatják a nyelv kifejez˝oerejét, ugyanis kisebb pontosságot megengedve a m˝ uveletek fixpontos ábrázolással (´ıgy tehát egész t´ıpusokkal) is megvalós´ıthat´ oak. Az alap m˝ uvelethalmazban ezért lebeg˝opontos m˝ uveleteket nem implementáltam. 45

A m˝ uvelethalmazban a 32 bites Int számt´ıpust fogom definiálni, ennek analógiájára bármilyen m´ as fixpontos t´ıpus megvalós´ıtható. A számt´ıpus mellett nélk¨ ulözhetetlen a logikai t´ıpus, ´ıgy a Bool ugyancsak beker¨ ul a m˝ uvelethalmaz t´ıpusai közé. Azok az ADT t´ıpusok, amelyek csak ezeket a t´ıpusokat tartalmazzák paraméterként, minden további nélk¨ ul haszn´ alhat´ oak. (ilyenek pl. a Maybe a és Either a b paraméteres t´ıpusok) A t´ıpusok meghat´ aroz´ asa ut´ an fontos kör¨ ulhatárolni az azokkal végezhet˝o m˝ uveleteket. Fontos, hogy egy olyan m˝ uveletalmazt adjunk meg, amellyel minden értelmes m˝ uvelet megvalós´ıthat´ o. A Bool t´ıpus szok´ asos m˝ uveletei a logikai és, vagy, nem, az Int t´ıpus aritmetikai m˝ uveleteit pedig az Eq , Ord , Num és Integral t´ıpusosztályok definiálják. A m˝ uvelethalmaz o otelez˝ o m˝ uveleteken (2.4.1. fejezet) k´ıv¨ uli elemeit összefog¨sszes, k¨ laltam a 2.3. t´ abl´ azatban. A m˝ uvelethalmaz egyes elemeinek megvalós´ıtása a következ˝oképpen alakul. A Num t´ıpusosztály o uvelete a 2.1.3. fejezetben implementált (+) m˝ uvelethez hasonlóan ¨sszes m˝ egyszer˝ u kombin´ aci´ os h´ al´ ozattal trivi´ alisan megvalós´ıtható. Az Eq és Ord t´ıpusoszt´ alyok m˝ uveletei sem okoznak problémát, ezek annyiban k¨ ulönböznek az el˝ oz˝ o csoportt´ ol, hogy a kimenet¨ uk (Min és Max kivételével) Bool t´ıpus´ u lesz. (Az Eq t´ıpusoszt´ alyn´ al a compare m˝ uveletet nem szerepeltetem, mert ez a többi m˝ uvelettel kiválthat´ o) A Bool t´ıpushoz tartoz´ o && , || és not m˝ uveletek két-két ill. egy db. bitb˝ol áll´ıtanak el˝o ugyancsak egybites adatkimenetet, ez szintén megvalós´ıtható kombinációs hálózatként. K¨ ulön bán´ asm´ odot érdemelnek az Integral t´ıpusosztály quot , rem , div és mod m˝ uveletei, ezeket ugyanis algoritmikus k¨ oltség¨ uknél fogva nem éri meg kombinációs hálózattal megvalós´ıtani, ezeket ezért t¨ obb ´ orajelciklust igényl˝o VHDL modulokkal valós´ıtom meg.

46

Bool m˝ uveletek: (££) :: Bool -> Bool -> Bool (||) :: Bool -> Bool -> Bool not :: Bool -> Bool -> Bool

logikai és logikai vagy logikai nem

And Or Not

GHC.Classes.Eq oszt´ aly m˝ uveletei: (==) :: a -> a -> Bool (/=) :: a -> a -> Bool

Eq<width> Ne<width>

egyenl˝o nem egyenl˝o

GHC.Classes.Ord oszt´ aly m˝ uveletei: (<) :: a -> a -> Bool (<=) :: a -> a -> Bool (>) :: a -> a -> Bool (>=) :: a -> a -> Bool min :: a -> a -> a max :: a -> a -> a

Lt<width> Le<width> Gt<width> Ge<width> Min<width> Max<width>

kisebb kisebb v. egyenl˝o nagyobb nagyobb v. egyenl˝o minimum maximum

GHC.Classes.Num oszt´ aly m˝ uveletei: (+) :: (*) :: (-) :: negate abs :: signum

a -> a -> a -> :: a a -> :: a

a -> a a -> a a -> a -> a a -> a

Add<width> Mul<width> Sub<width> Neg<width> Abs<width> Signum<width>

o¨sszeadás szorzás kivonás negáció abszol´ ut érték szignum

GHC.Real.Integral oszt´ aly m˝ uveletei: quot :: a -> a -> a rem :: a -> a -> a div :: a -> a -> a mod :: a -> a -> a

Quot<width> Rem<width> Div<width> Mod<width>

osztás maradék osztás maradék

2.3. t´ abl´ azat. A m˝uvelethalmaz összes eleme (az oszlopok rendre: Haskell függvényfejléc, VHDL modulnév sablonparaméterrel, ill. a m˝ uvelet sz¨ ovegesen)

47

3. fejezet

A m´ odszer kiterjeszt´ ese to eg˝ u (multi-rate) ¨bbsebess´ probl´ em´ akra A 2. fejezetben bemutatott m´ odszer egyszer˝ u, kizárólag egysebesség˝ u adatfolyamok Haskell nyelv˝ u implement´ al´ as´ ara, és annak VHDL-be történ˝o konvertálására jól használható, azonban t¨ obbsebess´ eg˝ u (multi-rate) [27, 17, 15] adatfolyamokat is tartalmazó Haskell forráskódokra nem alkalmazhat´ o. A következ˝ o szakaszban egy egyszer˝ u szám´ıtási képlet példáján kereszt¨ ul megvilág´ıtom, miért nem hagyhatjuk figyelmen k´ıv¨ ul a többsebesség˝ u adatfolyamokat is tartalmazó próblémákat. Ezt k¨ ovet˝ oen a haszn´ alt adatfolyam modellt (EOG) és a ford´ıtói módszert olyan kiterjesztésekkel l´ atom el, amelyekkel a rendszer alkalmas lesz többsebesség˝ u adatfolyamgráfok kezelésére is. Adott a k¨ ovetkez˝ o egyszer˝ u feladat, miszerint ki kell számolnunk a bemenetként kapott x értékre a k¨ ovetkez˝ o képletet:

g(x) +

k X

f (x + i)

(3.1)

i=0

Itt f és g egy-egy ´ altal´ anos, a 2.4. fejezetben definiált alapm˝ uveletekkel le´ırható f¨ uggvény. (fontos megjegyezni, hogy ezek bármilyen f¨ uggvények lehetnek, ´ıgy pl. nem csak as, amely esetben a fenti képletb˝ol elt˝ untethet˝o lenne a szumma) összeadás vagy szorz´ Tekints¨ uk u ´gy, hogy f és g egy-egy olyan m˝ uvelet, amit az EOG reprezentációban a gráf csomópontjaként felhaszn´ alhatunk, és legyen k = 1023. A probléma f˝o forrása az, hogy a g f¨ uggvényt egy adott x bemenetre egyszer kell kiértékeln¨ unk, m´ıg az f f¨ uggvényt adott x bemenetre 1024-szer alkalmaznunk kell. Ez a képlet az eddig ismertetett EOG le´ırással csak u ´gy realiz´ alhat´ o, ha az egyetlen g csomópont mellett létrehozunk 1024 db. f , és a hozzájuk tartoz´ o 1023 db. ¨ osszead´ o csomópontot. Egyértelm˝ uen látszik, hogy ez az eljárás megfelel˝oen nagy k esetén er˝ oforr´ asproblémák miatt hardverben kivitelezhetetlen, még ha a köztes reprezent´ aci´ oként szolg´ al´ o elemi m˝ uveleti gráf esetleg kezelhetetlen (de legalábbis

48

átláthatatlan) nagys´ ag´ ar´ ol nem is ejt¨ unk szót. A megold´ as az, hogy az f f¨ uggvény fizikailag egyszer (esetleg kis szám´ u egészszer, ezzel az esettel tov´ abbfejlesztési lehet˝ oségként foglalkozom) ker¨ ul megvalós´ıtásra, és egy x bemenet beérkezése esetén egym´ as után többször (k-szor) ker¨ ul alkalmazásra. Ezt az eddig használt EOG modell nem tudja reprezentálni, mert a gráf k¨ ulönböz˝o m˝ uveleteire k¨ ulönböz˝ ou ´jraind´ıt´ asi id˝ okkel kellene számolnunk, ´ıgy az alapfeltevések és az algoritmusok [10] nem haszn´ alhat´ oak. A megoldás az EOG modell kiterjesztése olyan formára, ami m´ ar képes a t¨ obbsebesség˝ u adatfolyamokat is kezelni. A k¨ ovetkez˝ okben megvizsg´ alom a 2. fejezetben ismertetett interfészeket a többsebesség˝ u adatfolyamok megjelenése szempontjából, majd az interfészeket u ´gy módos´ıtom, hogy az u ´j feltételek is kielég´ıthet˝ oek legyenek.

3.1. T¨ obbsebess´ eg˝ u adatfolyamok a ford´ıt´ as interf´ eszein A többsebesség˝ u adatfolyamok problémája a ford´ıtási módszer mindhárom interfészén, a Haskell nyelv˝ u forr´ ask´ odban, a köztes adatfolyam reprezentáción és a VHDL hardverle´ır´ ason is megjelennek. A 3.1.1. fejezetben kiterjesztem az EOG modellt olyan formára, hogy az alkalmas legyen t¨ obbsebesség˝ u adatfolyamgráfok le´ırására, a 3.1.2. fejezetben azt vizsgálom, hogy a Haskell nyelv˝ u forráskódból miként következtethet˝o ki minden m˝ uveletre vonatkoz´ oan a kimeneti adatfolyamok frekvenciáinak eltérése, majd a 3.1.3. fejezetben a kimeneti VHDL le´ır´ as sz¨ ukséges változtatásait taglalom.

3.1.1. T¨ obbsebess´ eg˝ u elemi m˝ uveleti gr´ af A 2.1.2. fejezetben r¨ oviden ismertetett EOG reprezentáció egy egysebesség˝ u adatfolyamgráf, és a modell t¨ obbsebesség˝ u adatfolyamok esetén nem alkalmazható. A most következ˝ o fejezetben kiterjesztem az EOG modellt, ami ennek köszönhet˝oen alkalmas lesz többsebesség˝ u adatfolyamok le´ır´ as´ ara is. A kiteresztésre a továbbiakban MREOG (multi-rate EOG, azaz t¨ obbsebesség˝ u elemi m˝ uveleti gráf) néven fogok hivatkozni. Ahol az egyértelm˝ uség miatt fontos, ott az egysebesség˝ u EOG-t SREOG néven fogom használni. Fontos cél, hogy az EOG modellhez kapcsolódó szabályok az MREOG-n is fennáljanak, ´ıgy a hozz´ a kapcsol´ od´ o nagy sz´ am´ u algoritmusok az u ´j modellen is alkalmazhatóak lesznek. Az MREOG egy olyan adatfolyamgráf, amelyb˝ol egyértelm˝ uen megtudható, hogy melyek az azonos frekvenci´ aj´ u jeleket tovább´ıtó adatfolyamok. (a frekvencia itt a megszokott értelm˝ u, azaz az adatfolyamon érkez˝o értékek egy másodpercre vet´ıtett darabszáma) Az MREOG blokk egy olyan rekurz´ıv strukt´ ura, amely további blokkokat és m˝ uveleteket tartalmaz, az ut´ obbiakra a blokk saj´ at m˝ uveletei néven hivatkozunk. Egy blokk saját m˝ uveletei k¨ oz¨ ul b´ armelyik kett˝o között kizárólag azonos frekvenciáj´ u jeleket tovább´ıtó adatfolyamok szerepelhetnek és erre az azonos frekvenciára a blokk saj´ atfrekvenci´ aja néven is hivatkozhatunk. Az MREOG az el˝ obbi defin´ıci´ ot használva egy egyetlen blokkból álló rekurz´ıv strukt´ ura, amely ´ıgy az ¨ osszes m˝ uveletet tartalmazza a közt¨ uk felép´ıtett adatfolyamokkal egy¨ utt. (az egyetlen blokk persze tartalmazhat u ´jabb blokkokat, ahogy az a defin´ıcióból kider¨ ul) 49

Az ´ıgy defini´ alt blokkok hierarchi´ at alkotnak, ez pedig le´ırható egy fával, aminek gyökéreleme a legk¨ uls˝ o blokk, azaz amit már egyik blokk sem tartalmaz. (ez tulajdonképpen az az egyetlen blokk, ami a teljes MREOG-t jelenti) A fa levelei a m˝ uveletek, köztes csomópontjai pedig az egyes blokkok. Blokk nem lehet levél, hiszen ez azt jelentené, hogy a blokk nem tartalmaz saj´ at m˝ uveletet és további blokkokat sem. A fa csomópontjai tehát az MREOG blokkjai és m˝ uveletei, a közt¨ uk futó éleket pedig a következ˝o szabályokkal határozhatjuk meg. A fában a Bi blokknak megfelel˝ o csomópont a Bj blokknak megfelel˝o csomópont gyereke lesz, ha Bj k¨ ozvetlen¨ ul tartalmazza Bi -t, azaz a feltétel halmazm˝ uveletekkel le´ırva (a halmaz elemei maguk a m˝ uveletek): Bi ⊂ Bj ∧ @k, k 6= i, k 6= j, Bi ⊂ Bk ⊂ Bj A fában az oi m˝ uveletnek megfelel˝ o csomópont a Bj blokknak megfelel˝o csomópont gyereke lesz, ha oi a Bj saj´ at m˝ uvelete, azaz a feltétel: oi ∈ Bj ∧ @k, k 6= j, Bk ⊂ Bj , oi ∈ Bk Az ´ıgy defini´ alt hierarchia f´ at a továbbiakban segédgráfként alkalmazom, ami a m˝ uveletek vagy a blokkok bizonyos paramétereinek szám´ıtására lesz alkalmas. Mivel a fa az eredeti gráf adatfolyamait nem tartalmazza (élei nem adatfolyamok, hanem a hierarchia szinteket választj´ ak el egym´ ast´ ol), ezért VHDL generálásra nem is lenne alkalmas. Fentiekb˝ol k¨ ovetkezik, hogy az SREOG egyetlen blokkot tartalmaz, amelynek sajátfrekvenciája megegyezik a bemenet (és ezzel egy¨ utt a kimenet) frekvenciájával, azaz minden egyes bemeneti jelre az o uvelet egyszer hajtódik végre. Egy MREOG esetében a ¨sszes m˝ modell több, egym´ asba ´ agyazott blokkot is tartalmaz. A gyökér blokk sajátm˝ uveleteire itt is igaz, hogy minden bemenetre egyszer hajtódnak végre, ezzel szemben a gyerek blokkok sajátm˝ uveletei bemenetenként n-szer hajtódnak végre, ahol n > 1, n ∈ N. Minden blokk egyedi azonos´ıt´ oval rendelkezik, a gyökér blokk neve defin´ıció szerint Root. Egy m˝ uvelet hierarchiaszintje a gyökérelem és a m˝ uvelet közötti u ´ton található csomópontok sz´ ama lesz. (a gy¨ okérelem és a m˝ uvelet csomópontok nem szám´ıtanak, ´ıgy egy két él hossz´ uu ´t esetében a hierarchiaszint 1) Az EOG-hez képest a grafikus megjelenése u ´gy módosul, hogy a hierarchia fát tekintve minden blokk esetében keretezéssel l´ atjuk el a blokk gyerekeit, ´ıgy elválasztva azokat a többi m˝ uvelett˝ ol és blokkt´ ol. Az EOG sz¨ oveges le´ır´ asa u ´gy m´ odosul, hogy a t´ıpusmegadás utáni oszlopban listaalakban felsoroljuk a gy¨ okért˝ ol az adott m˝ uvelethez vezet˝o u ´ton található blokkok azonos´ıtóját. A t´ıpus template paraméterének els˝ o értéke a hierarchiaszint lesz (ami nem más, mint az el˝obbi lista elemsz´ ama egyel cs¨ okkentve). Egy egyszer˝ u MREOG szöveges és grafikus ábrázolása és a hozz´ a tartoz´ o hierarchia fa az a 3.1. ábrán követhet˝o nyomon. Az MREOG defini´ al´ asa ut´ an r´ atérek az EOG két fontos paraméterének szám´ıtására a többsebesség˝ u esetre vonatkoz´ oan.

50

a b c d e f g h i j k

"a<0,32>" "b<1,32>" "c<2,32>" "d<2,32>" "e<1,32>" "f<1,32>" "g<1,32>" "h<1,32>" "i<0,32>" "j<0,32>" "k<0,32>"

["Root"] ["Root","B"] ["Root","B","C"] ["Root","B","C"] ["Root","B"] ["Root","B"] ["Root","A"] ["Root","A"] ["Root"] ["Root"] ["Root"]

a b c b d e a g a i h j f

i

a

g

h

j k

b

e

c

f

d

Root

A

g

a

B

h

b

C

c

i

e

j

k

f

d

3.1. ´ abra. Egyszer˝u MREOG szöveges és grafikus le´ırása, és a hozzá tartozó hierarchia gr´ af (az MREOG-ban és a hierarchia gr´ afban egym´ asnak megfeleltethet˝ o blokkokat azonos sz´ınnel és szaggatott vonallal jel¨ oltem)

´ Ujraind´ ıt´ asi- ´ es lappang´ asi id˝ o sz´ am´ıt´ asa SREOG esetében alapvet˝ o fontosság´ u az u ´jraind´ıtási- és lappangási id˝ok szám´ıtása [10]. Az u ´ jraind´ıt´ asi id˝ o (R) azt adja meg, hogy az adatfolyamgráf bemenetére milyen id˝ oközönként érkezhet u ´jabb feldolgozandó adat. A lappang´ asi id˝ o (L) azt adja meg, hogy a bemeneti mintavételezéshez képest mennyi id˝o m´ ulva jelenik meg a kiszám´ıtott eredmény az adatfolyamgr´ af kimenetén. Fontos tehát, hogy ezek szám´ıtása MREOG esetére is megoldhat´ o legyen. 51

Egy MREOG csup´ an a hierarchia elt˝ untetésével ( lap´ıtás”) nem lesz alkalmas az R és ” L meghatároz´ as´ ara, mert az eltér˝ o adatfolyam-frekvenciák miatt a m˝ uveletek egyenként vett futási ideje (ti ) nem o o. ¨sszemérhet˝ Az MREOG azon Bi blokkja, amely csak leveleket (vagyis csak m˝ uveleteket) tartalmaz, az R és L sz´ am´ıt´ as a szok´ asos m´ odon [10] elvégezhet˝o, hiszen ez csak egysebesség˝ u adatfolyamokat tartalmaz. A Bi blokkra megkapott Ri és Li értékekb˝ol kiszám´ıtható a Bi blokkra, mint virtu´ alis m˝ uveletre vett futási id˝o, azaz a ti : ti = (ni − 1) ∗ Ri + Li

(3.2)

A képletben szerepl˝ o ni azt jelenti, hogy az Bi m˝ uveleteit ni -szer futtatjuk le minden olyan bemenetre, ami a Bi -n k´ıv¨ ulr˝ ol jön, azaz közvetlen sz¨ ul˝ojét˝ol. Az ni -t a Bi blokk rátájának nevezz¨ uk, ami azt mondja meg, hogy mialatt Bi sz¨ ul˝ojében egyszer alkalmazzuk a sajátm˝ uveleteket, az alatt mennyiszer alkalmazzuk Bi sajátm˝ uveleteit. (informálisan: mennyivel gyorsabb” a bels˝ o blokk, mint a k¨ uls˝o) ” A képlet azt jelenti, hogy az ered˝ o ti futási id˝o (azaz, hogy meddig foglalt a virtuális m˝ uvelet) nem m´ as, mint a Bi -re vett lappangási id˝o (triviális), hozzáadva ehhez azt az id˝ot, ameddig a bemenetre az egym´ as ut´ ani adatok érkeznek. Mivel a bemenetre Ri id˝onként érkezhet adat, és ni az adatok darabsz´ ama, ez az id˝o (ni − 1) ∗ Ri lesz. Ha ti -t kisz´ amoltuk, akkor a Bi blokkot egyetlen virtuális m˝ uvelettel helyettes´ıtj¨ uk, amelynek fut´ asi ideje ti lesz. Azért fontos a virtuális m˝ uvelet fogalmát bevezetni, mert ez a m˝ uvelet az eredeti adatfolyamgr´ afban nem található meg, ezt az algoritmus hozza létre. A helyettes´ıtés ut´ an minden olyan adatfolyam megmarad, amely a Bi blokkon bel¨ uli és azon k´ıv¨ uli m˝ uveleteket k¨ ot o uli m˝ uvelet helyett (annak ¨ssze, viszont a Bi blokkon bel¨ hiányában) az u ´j virtu´ alis m˝ uvelet lesz a végz˝odése. (azaz az él egyik cs´ ucsa az u ´j virtuális m˝ uvelet lesz) Az iménti algoritmust iterat´ıvan addig futtatjuk, m´ıg vég¨ ul a gyökér blokk is egyetlen virtuális m˝ uveletre reduk´ al´ odik. Ez az a pont, ahol már minden blokkra megkaptuk annak u ´jraind´ıtási- és lappang´ asi idejét. A gy¨ okér blokkra vett R és L értékek lesznek az MREOGra R és L értékei.

3.1.2. A bemeneti forr´ ask´ od A 3.1. képletet sokféleképpen le´ırhatjuk Haskell nyelven, három egyszer˝ u megvalós´ıtást a következ˝o kódrészlet szemléltet. megoldas1 x = g ( x ) + s e g e d f 1023 where s e g e d f 0 = f x s e g e d f i = f ( x+i ) + s e g e d f ( i −1) megoldas2 x = g ( x ) + f s t \ $ i t e r a t e s e g e d f ( 0 , 0 ) ! ! 1024 where s e g e d f ( s , i ) = ( s+f ( x+i ) , i +1) megoldas3 x = g ( x ) + sum \ $ map ( \ i −> f ( x+i ) ) [ 0 . . 1 0 2 3 ]

52

Az els˝ o megold´ as rekurz´ıv f¨ uggvényt használ, a második és a harmadik megoldás a rekurziót magasabb rend˝ u f¨ uggvények seg´ıtségével elrejti, és egy´ uttal bevezet egy-egy list´ at és az ahhoz sz¨ ukséges m˝ uveleteket. (sum , map , (!!) ) Mindhárom megoldásnál egyértelm˝ u, hogy az x adott értékére az f f¨ uggvény többször ker¨ ul alkalmazásra. Els˝o esetben a rekurziób´ ol k¨ ovetkeztethet¨ unk erre, második és harmadik esetben amiatt, mert az iterate , ill. a map be´ agyazott f¨ uggvényében használjuk f -et. A rekurz´ıv f¨ uggvények k¨ ozvetlen használatát kizártuk, ezért az els˝o megoldást nem engedhetj¨ uk meg. A harmadik megoldásnak a másodikkal szemben a le´ırás egyszer˝ usége és az eredeti képlethez nagyon hasonló le´ırásmód az el˝onye, ´ıgy a következ˝o vizsgálatokn´ al ezzel az esettel foglalkozom tov´ abb. A [0..1023] listamegad´ as egy szintaktikai édes´ıt˝oszer, amely az enumFromTo(0,1023) f¨ uggvényh´ıv´ asra képz˝ odik le. Ezek alapján a példamegoldásban négy f¨ uggvény¨ unk van, amelyek pontosan a négy lehetséges ki- és bemeneti t´ıpuskombinációval rendelkeznek: • (+) : skal´ ar bemenet és skalár kimenet, további példák lehetnének a 2.4. fejezetben bemutatott f¨ uggvények (kivétel iterate ) • enumFromTo a b : skal´ ar bemenet és lista kimenet • map f xs : lista bemenet és lista kimenet, és a lista minden elemére lefut az f f¨ uggvény • sum xs : lista bemenet és skalár kimenet, további példák lehetnének a product , maximum és a foldl , ez ut´ obbi egy általános lista és skalár közötti konverter A fejezet bevezet˝ ojében m´ ar szó volt róla, hogy az f f¨ uggvénynek megfelel˝o m˝ uveletet egyszer hozzuk létre és egym´ as után többször alkalmazzuk, azaz a bemeneti adatokat egyesével, id˝ oben elv´ alasztva adjuk át. Ezt a funkciót a Haskell megoldásban a map tölti be, ami a bemeneti lista elemeivel egymás után h´ıvja f -et. Ez azt jelenti, hogy a list´ at felfoghatjuk stream-ként, a map -nek megfelel˝o m˝ uvelet pedig egészen egyszer˝ uen a streamen egym´ as ut´ an érkez˝ o elemeket egymás-után adja át f -nek. Ehhez a gondolatmenethez t¨ okéletesen kapcsolódik a Stream Fusion [18] eljárás, amelyet azonban m´ as céllal hoztak létre. Az volt a cél, hogy az egymás utáni listam˝ uveleteket (map , zip , foldr , stb.) a GHC a ford´ıtás során optimalizálják, és egyetlen átalak´ıtott f¨ uggvénybe t¨ om¨ or´ıtsék. Ezzel az egymás utáni listareprezentációk számát csökkentik, adott esetben ak´ ar a list´ ak teljesen el is t˝ unnek az optimalizálás során, ami a processzorra ford´ıt´ as esetében is nagyon kedvez˝ o hat´ as´ u. Alkalmazva a Stream Fusion eljárást alapjait, fogalmi szinten ´ attérhet¨ unk list´ akr´ ol stream-ek használatára. A skal´ ar bemenet˝ u és lista kimenet˝ u f¨ uggvények gyors´ıt´ o f¨ uggvények, hiszen egyetlen értékb˝ ol egy list´ at (t¨ obb értéket, azaz stream-et) generálnak. A lista bemenet˝ u és skal´ ar kimenet˝ u f¨ uggvények lass´ıt´ o f¨ uggvények, mert listát (több értéket, azaz stream-et) kapnak és ebb˝ ol egyetlen értéket adnak vissza. A példameold´ asb´ ol a sebességszintek nagyon egyszer˝ uen kivehet˝oek. Mivel a g(x) a map-en k´ıv¨ ul van, ezért az minden bemenetre egyszer hajtódik végre, a f(x+i) f¨ uggvényt 53

pedig a map-en bel¨ ulre ´ırtuk, ´ıgy azt meg kell h´ıvni a [0..1023] lista minden elemére, azaz a sebessége egy hierarchiaszinttel gyorsabb a g -nél. (az általánosan fel´ırt map f xs f¨ uggvényh´ıv´ as esetében az f sz´ am´ıt bel¨ ulnek, hiszen ez a f¨ uggvényparaméter) Sajnos által´ anos esetben a helyzet nem ilyen egyszer˝ u, ennek demonstrálására szolgál a következ˝o kódrészlet. maptest : : Int −> Int maptest x = let belso j = l e t a = sum \ $ map ( \ i b = sum \ $ map ( \ i c = sum \ $ map ( \ i d = sum \ $ map ( \ i in ( a , b , c , d ) in sum \ $ map b e l s o [ 0 . . 3 ]

−> −> −> −>

i +5) [ 0 . . 4 ] : : Int i+j +5) [ 0 . . 5 ] : : Int i+x+5) [ 0 . . 6 ] : : Int i+j+x+5) [ 0 . . 7 ] : : Int

A példában egy 0 − 3 intervallumban mozgó k¨ uls˝o ciklus (ciklusváltozója: j ), és az azon bel¨ ul helyet foglal´ o négy darab bels˝o ciklus (ciklusváltozója: i ) található. Látható, hogy bár az a v´ altoz´ o kisz´ am´ıt´ asa a k¨ uls˝o cikluson bel¨ ul található, értékét elég a program futása során egyszer kisz´ am´ıtani, ugyanis nem f¨ ugg a bemenett˝ol. A c változó már f¨ ugg a bemenett˝ol, viszont a k¨ uls˝ o ciklus v´ altozójától, j -t˝ol nem, ´ıgy elég minden x bemenetre egyszer kisz´ am´ıtani értékét. Adott esetben a vagy c kiszám´ıtása nagyon hosszantartó m˝ uvelet is lehet, ´ıgy kifejezetten h´ atr´ anyos, ha ezeket a m˝ uveleteket j -szer hajtjuk végre az elégséges 1 helyett. Az a vagy a c értéke paraméterként a k¨ uls˝o cikluson k´ıv¨ ulr˝ol is megkapható lenne, és ilyen esetben a ford´ıt´ o az inlining-nak köszönhet˝oen szintén a belso f¨ uggvényen bel¨ ulre helyezné ezt a kifejezést. Ebb˝ ol sajnos az következik, hogy nem elég azt vizsgálni, hogy az egymásba ágyazott map f¨ uggvényekben milyen mélyen található egy m˝ uvelet. Egy másik megold´ as lehet, ha minden m˝ uveletnél megvizsgáljuk, hogy operandusai milyen változókt´ ol f¨ uggnek. Ezek a v´ altoz´ ok a ciklusváltozók és az egyetlen bemeneti változó. Egy kizárólag konstans operandusokkal rendelkez˝o o¨sszeadás m˝ uvelet eredménye pl. konstans, ellenben ha az egyik operandus az x bemeneti változótól f¨ ugg, akkor az összeadás eredménye is x -t˝ ol fog f¨ uggni, és ´ıgy tovább. Ha egy m˝ uvelet f¨ ugg a bels˝o j ciklusváltozótól, és a j f¨ ugg a k¨ uls˝ o i ciklusv´ altozótól, akkor a m˝ uvelet mindkét ciklusváltozótól f¨ uggni fog, teh´ at a f¨ uggés tranzit´ıv. Ez utóbbi sz´ am´ıt´ as m´ ar megfelel elv´ arásainknak, mert csak akkor végez el egy m˝ uveletet, ha a m˝ uvelet bemenetei v´ altoztak, és ´ıgy a m˝ uveletek felesleges futásait kisz˝ urt¨ uk. Ismét megjegyzem, ez az inlining miatt egy kulcsfontosság´ u kérdés.

3.1.3. Kimeneti hardverle´ır´ as A VHDL le´ır´ asban az egyes m˝ uveleteket megtestes´ıt˝o modulok a control bitek hatására lépnek m˝ uk¨ odésbe. MREOG esetében ez az egyszer˝ u vezérlés nem elegend˝o, ehhez pedig igazolásként elég csak a sum m˝ uvelet m˝ uködésére gondolni. A sum f¨ uggvény Haskell-ben a lista elemeinek ¨ osszegét sz´ amolja ki, azaz a MREOG sum m˝ uvelete a stream elemeire végzi 54

ezt. A sum VHDL modul a bemenetére érkez˝o értékeket összegzi, de ezt csak addig szabad tennie, am´ıg egy adott stream-en bel¨ uli értékek érkeznek. Amint u ´j stream kezd˝odik, a szumm´ az´ ast ismét null´ ar´ ol kell kezden¨ unk, hiszen a sum a stream elemeit adja o¨ssze, nem a végtelenségig érkez˝ o adatokat. Célszer˝ u teh´ at bevezetni egy második control bitet, ami nem az adott skalár érték mintavételezhet˝ oségét jelzi, hanem a skalárokat tartalmazó stream mintavételezhet˝oségét, azaz a stream kezdetét. Ez a control bit pontosan akkor lesz akt´ıv, amikor a stream els˝ o elemének (skal´ arj´ anak) control bitje akt´ıv. Egy olyan stream-nél, amelynek minden eleme skalárokat tartalmazó stream, be kell vezetn¨ unk egy harmadik control bitet, hiszen egy sum modul összegzi a bels˝o stream-eket, de ennek eredménye skal´ arokat tartalmazó stream, amit egyébként ismét szummázhatunk. Mindebb˝ ol tah´ at az k¨ ovetkezik, hogy minden MREOG m˝ uveleti csomóponthoz a hierarchiaszintjével azonos bitszélesség˝ u vektort kell rendeln¨ unk vezérl˝ojel gyanánt. A 3.2. ´ abra. kétszint˝ u stream vezérl˝ojeleinek hullámformáját mutatja. A cq[2] jel a bemenet mintavételezése, a cq[1] magas szintje a minden bemenetre el˝oálló streamen érkez˝ o adatok mintavételezése, de mivel a stream-en bel¨ uli adatok szintén stream-ek, ezért megjelenik egy harmadik szint is. A cq[0] jel a bels˝o streamen érkez˝o adatok mintavételezését ´ jelenti. Altal´ anosan elmondhat, hogy a vezérl˝o vektor 0. bitje mindig a leggyorsabb mintavételezést fogja jelenteni, ugyanis ´ıgy biztos´ıtható egyszer˝ uen, hogy a skalár-skalár t´ıpus´ u m˝ uveletek mindig a legbels˝ o stream adatain operáljanak. 500 ns

1,000 ns

1,500 ns

3.2. ´ abra. Vezérl˝o bitek stream esetén

Mivel a vezérl˝ obit helyett a vezérléshez bitvektort használunk, és a bitvektor szélessége a hierarchiaszintt˝ ol f¨ ugg, ezért azt a VHDL modulok generikus paramétereként célszer˝ u átadnunk. A generikus paramétereket a 2. fejezetben le´ırt módszer is támogatja, ´ıgy ez nem okoz plusz munk´ at. Innent˝ ol kezdve minden VHDL modul els˝o generikus paramétere a hierarchi´ aban elfoglalt szintet fogja jelezni.

3.2. A ford´ıt´ asi algoritmus kiterjeszt´ ese Az interfészek vizsg´ alata és m´ odos´ıtása után rátérek a ford´ıtó azon módos´ıtásaira, amely lehet˝ové teszi a heterogén sebesség˝ u m˝ uveletek használatát. A Haskell-EOG ford´ıtóban ehhez két u ´j algoritmust kellett bevezetnem, egyik a 3.2.1. fejezetben bemutatásra ker¨ ul˝ o MapConversion, a m´ asikat pedig a 3.2.2. fejezetben mutatom be, és a m˝ uveletek hierarchiában elfoglalt helyét hat´ arozza meg. Az EOG-VHDL ford´ıtó minimális módos´ıtásra szorul, itt a vezérl˝ o signal -ok std_logic -ról (egy bites jel) std_logic_vector -ra (több bites vektor) val´ o´ at´ır´ asa elegend˝ o a sikerhez, ´ıgy ezt a kés˝obbiekben nem fejtem ki b˝ovebben. 55

3.2.1. MapConversion transzform´ aci´ o A map magasabbrend˝ u f¨ uggvény defin´ıciója: map : : ( a −> b ) −> [ a ] −> [ b ] map [] = [] map f ( x : xs ) = f x : map f xs

A map f¨ uggvény els˝ o paramétere egy egyparaméteres f f¨ uggvény, amely a második paraméterben megadott lista o ¨sszes elemére megh´ıvódik. Az f visszatérési értéke a második paraméterrel megegyez˝ o elemsz´ am´ u lista azonos helyére ker¨ ul. A MapConversion transzform´ aci´ o nagyon hasonó a 2.2.3. fejezetben bemutatott IterateConversionhöz, ´ıgy ez is egy egyszer˝ u Core2Core transzformáció, amit a 3.3. ábrán a már megszokott formalizmussal ismertetek.

01: app map 02: lam x 03: E 04: E2

01: let x = 02: E2 03: note "lam x" 04: E 3.3. ´ abra. IterateConversion a´ltalános képlet

Mint láthat´ o, a transzform´ aci´ o nagyon egyszer˝ u, és tulajdonképpen a map f¨ uggvény elt˝ untetésér˝ol sz´ ol. A map kimenetét az E kifezés, azaz a bels˝o lambda absztrakció adja. Azokra a pontokra, ahol a bels˝ o lamda absztrakció paraméterét (x -et) felhasználjuk az E2 kifejezés ker¨ ul, vagyis a m´ asodik paraméterként megadott lista. (ami az MREOG nyelvezet szerint már stream) Ezt a m˝ uk¨ odést az u ´jonnan bevezetett let x = csomópont valós´ıtja meg. Fontos, hogy az E kifejezés gy¨ okerét egy note csomóponttal megjelölj¨ uk, mert az OpTree fában ez a csom´ opont fogja jelezni az elt˝ untetett map bels˝o lambda absztrakciójának kezdetét. A Haskell nyelv szempontj´ ab´ ol a Core a transzformáció után nem marad t´ıpuskonzisztens, ugyanis az E2 -nek a t´ıpusa lista, az E -n bel¨ ul felhasznált x pedig a lista elemei, de x itt magát a list´ at, az E2 -t kapja meg. Az ilyen értelemben vett t´ıpusinkonzisztencia nem okoz problém´ at, hiszen a gr´ afb´ ol MREOG reprezentáció kész¨ ul, ahol a stream és a skalár csak a hierarchi´ aban elfoglalt szint vonatkozásában tér el egymástól, egyébként a kett˝o t´ıpusazonos. A MapConversion transzform´ aci´ ot a 2.6. ábrán vázolt Haskell-EOG pipeline IterateConversion és AppRename transzform´ aciói közé célszer˝ u beékeln¨ unk.

3.2.2. A hierarchia automatikus fel´ ep´ıt´ ese A többsebesség˝ u adatfolyamokat is t´ amogató ford´ıtás leglényegesebb pontjához érkezt¨ unk. Most következik annak az algoritmusnak a le´ırása, amely minden m˝ uveletre, azaz az OpTree minden csom´ opontj´ ara meghat´ arozza az MREOG hierarchiában elfoglalt helyét, azaz felép´ıti mag´ at az MREOG-t. Az algoritmust a 2.6. ábrán látható ford´ıtói pipeline Co56

reToTree és TreeSimplifier ´ atalak´ıtásai közé kell beékeln¨ unk, mert ez az a pont, ahol a Core-b´ ol m´ ar OpTree reprezent´ ació lett, és a sz¨ ukséges segéd csomópontok (mint pl. a note lam x”) még nem t˝ untek el. ” Az algoritmus négy lépésb˝ ol ´ all, ezek mindegyike az OpTree fát járja be O(n) költséggel. A lépések a k¨ ovetkez˝ ok: 1. Ciklusv´ altoz´ ok sorsz´ amoz´ asa: az OpTree preorder bejárása során a MapConversion által létrehozott Note lam csomópontok esetében a kapcsolódó változó (a MapConversion transzform´ aci´ on´ al l´ atott példában ez x volt) neve elé egy sorszámot ´ırunk, ami az egym´ asba ´ agyaz´ as során egyre magasabb értéket vesz fel. Erre azért van sz¨ ukség, hogy a blokk azonos´ıtók sorrendhelyesen (el˝oször a gyökérelem, majd annak gyereke, stb.) ker¨ ulhessenek felsorolásra. 2. M˝ uveletek v´ altoz´ of¨ uggésének meghatározása: az OpTree postorder bejárásánál minden node-ra meg´ allap´ıtjuk, hogy az mely változóktól f¨ ugg, azaz a node alatti részf´ ak mely v´ altoz´ ok értékeit használják fel. A postorder bejárás biztos´ıtja, hogy el˝oször a levelekre értékel˝ odj¨ on ki a f¨ ugg˝oség vizsgálat, ´ıgy minden node szám´ıtásakor csak a k¨ ozvetlen¨ ul alatta lév˝ o node-ok f¨ ugg˝oségeit kell figyelembe venni. 3. V´ altoz´ of¨ ugg˝ oségek tranzit´ıv kiterjesztése: ha egy node az i ciklusváltozótól f¨ ug, és az i ciklusv´ altoz´ o pedig a j ciklusváltozótól, akkor a node is f¨ ugg j -t˝ol. Az OpTree bej´ arjuk preorder módon, és minden Note lam csomópontnál a hozzá tartoz´ o v´ altoz´ ot és f¨ ugg˝ oségeit feljegyezz¨ uk, majd a gyerekeinek a bejáráskor ezt átadjuk. Ha egy m˝ uvelet i -t˝ ol f¨ ugg, akkor a f¨ ugg˝oségi halmazhoz hozzávessz¨ uk az i változóhoz rendelt f¨ ugg˝ oségeket is. Ezt könnyen megtehetj¨ uk, mert a Note lam i csomópontn´ al i f¨ ugg˝ oségeit feljegyezt¨ uk, és paraméterként átadtuk a gyerekeknek. 4. Hierarchiaszintek meghat´ arozása: preorder bejárásnál minden node-ra megszámoljuk az el˝ obbiekben m´ ar feltöltött f¨ ugg˝oségi lista elemeinek számát, ez lesz maga a hierarchiaszint. Az u ugg˝oségi lista azt jelenti, hogy az adott m˝ uvelet eredménye ¨res f¨ konstans. Ilyen esetben a konstanst szinkronizálni kell az azt felhasználó nem konstans m˝ uvelettel, azaz a m˝ uvelet f¨ ugg˝oségi listáját a konstansra átmásoljuk. Ez azért nagyon fontos, mert tal´ alkozhatunk stream konstansokkal is, amelyek a gyakorlatban nem konstansok, hiszen az adatokat egymás után felsorolva k¨ uldik. Ilyen esetben a felsorol´ ast végz˝ o m˝ uveletet (rendszerint EnumFromTo) a blokkjának megfelel˝o bemenettel triggerelni kell. Ha ez nem történik meg, az EnumFromTo m˝ uveletnek nem adjuk ´ at az inform´ aci´ ot, hogy mikor kell elkezdenie a felsorolást, ´ıgy az egymás ut´ an t¨ obbsz¨ or semmiképp nem tud lefutni. (ami pedig követelmény lehet) Az algoritmus lefut´ asa ut´ an minden Node-hoz ismert lesz a hozzá tartozó hierarchiaszint és a tartalmaz´ o blokkok gy¨ okérelemt˝ol ind´ıtott azonos´ıtói Az EOG sz¨ oveges reprezent´ aci´ ojának elkész´ıtésekor a m˝ uvelet els˝o generikus paramétere a hierarchiaszint lesz, a harmadik oszlopba pedig a blokk azonos´ıtók ker¨ ulnek sorrendhelyesen. (a ciklusv´ altoz´ ok sorsz´ amozása miatt ez alfanumerikus sorrendet jelent) 57

3.3. A m˝ uvelethalmaz kiv˝ ov´ıt´ ese A fejezet eddigi részében a ford´ıt´ o m´ odszerének kib˝ov´ıtésével foglalkoztam, hogy a rendszer alkalmas legyen t¨ obbsebesség˝ u adatfolyamok kezelésére is. A módszert implementáltam, a ford´ıtóprogram most m´ ar képes az MREOG-ben reprezentálható algoritmusok Haskellb˝ol VHDL-be történ˝ o ford´ıt´ as´ ara. Egy dolog maradt hátra, ez pedig a konkrét m˝ uveletek definiálása és VHDL-ben t¨ ortén˝ o le´ır´ asa, hogy a ford´ıtó u ´j képességeit ténylegesen ki tudjuk használni Haskell nyelven ´ırt forr´ ask´ odokból. A következ˝o két alfejezet során a m˝ uvelethalmazt kib˝ov´ıtem a stream-, ill. a t¨ ombkezel˝o m˝ uveletekkel.

3.3.1. Stream m˝ uveletek A stream m˝ uveletek a Haskell lista kezel˝o f¨ uggvényeib˝ol adódnak. A továbbiakban a stream-ek fogalm´ an´ al maradok, ezért fontos megjegyezni, hogy a forráskód szintjén ezek még listaként szerepelnek, ezt a m˝ uveletek tárgyalásánál érdemes mindi észben tartani. A 3.1.2. alfejezetben l´ attuk, hogy a 3.1. képlet szám´ıtása három listam˝ uveleten alapszik: enumFromTo , map és sum . Ez a h´ arom m˝ uvelet már elégséges az MREOG létrejöttéhez, mert tartalmaz gyors´ıt´ o (enumFromTo) és lass´ıtó (sum) m˝ uveletet is. Mivel minden lass´ıtó m˝ uvelet megegyezik az alapok szintjén, ezért most példaként csak a sum -mal foglalkozom. Ennek analógi´ aj´ ara nagyon k¨ onnyen ´ attérhetnénk a product vagy a maximum , vagy egyéb lass´ıtó f¨ uggvényre is. A gyors´ıt´ o f¨ uggvényeknél ugyan ez a helyzet. A Map -et a MapConversion transzformáció eliminálta, ´ıgy csak az EnumFromTo , és Sum modulok VHDL le´ır´ as´ ar´ ol kell sz´ ot ejtenem. Az EnumFromTo tulajdonképpen u ´gy viselkedik, mint egy for ciklus. A bemenetén érkez˝o intervallumhat´ arokon bel¨ ul lépteti a kimeneti változójára kötött számláló értékét, a generikus paraméterként megadott késleltetési id˝oközönként. Ez az id˝oköz a blokkra alkalmazott, R u ´jraind´ıt´ asi id˝ o kisz´ am´ıt´ asa során adódik. Ha a Bi blokk u ´jraind´ıtási ideje Ri , akkor a Bi -ben tal´ alhat´ o EnumFromTo késleltetési id˝oköze pontosan az Ri érték lesz. Ez egyszer˝ uen abb´ ol ad´ odik, hogy az EnumFromTo-nak két érték között ki kell várnia az utána következ˝ o m˝ uveletek minim´ alis u ´jraind´ıtási idejét, hogy azok a m˝ uveletek rendben lefussanak. A Sum a bemenetére érkez˝ o stream értékeit o¨sszegzi. A stream kezdetét jelz˝o második szint˝ u vezérl˝ obit a modulban tal´ alható accum regisztert nullázza, ´ıgy minden stream kezdetén a sz´ aml´ al´ as null´ ar´ ol indul. A modulok egy-egy lehetséges VHDL kódja a f¨ uggelékben megtalálható.

3.3.2. T¨ omb m˝ uveletek A stream-ekkel és m˝ uveleteikkel kapcsolatban egy fontos dologról még nem esett szó. Haskell-ben k¨ onnyen le´ırhatunk olyan algoritmust, ami el˝oször el˝oáll´ıt egy listát, majd ezen a listán t¨ obbsz¨ or végigmegy. Egy egyszer˝ u példa, ha a lista maximumát hozzá kell adnunk a lista ¨ osszes eleméhez. Nyilv´ anvaló, hogy el˝oször ki kell választanunk a maximális elemet (els˝o bej´ ar´ as), és csak ezut´ an kezd˝odhet az összeadás (második bejárás). 58

Az el˝ obb felv´ azolt lista a ford´ıtás során stream-ként ker¨ ul létrehozásra, ami azt jelenti, hogy a lista elemei egym´ as ut´ an, és csak egyszer jelennek meg a stream-et megtestes´ıt˝ o adatfolyamon. A stream elemeit tehát nem soroljuk fel kétszer, ´ıgy a fent vázolt algoritmus kudarcot vall. A problém´ ara két f˝obb megoldás létezhet. A stream el˝oáll´ıtásáért felel˝ os m˝ uveleteket esetleg r´ a lehet venni, hogy ismételten kiszámolják a stream elemeit, ´ıgy az u ´jra felsorolhat´ o. M´ asodik esetben az egyszer kiadott stream-et memóriában eltároljuk, és legközelebb a mem´ ori´ ab´ ol olvassuk vissza stream-ként, ´ıgy ameddig a memóriában fellelhet˝o az elmentett stream, azon b´ armennyiszer végig tudunk menni. Az els˝o eset az eddigi m˝ uveletekkel megoldhat´ o, de adott esetben el˝ofordulhat, hogy a stream u ´jra generálása csak nagyon k¨ oltségesen lenne kivitelezhet˝o, és ´ıgy a második megoldás ker¨ ulhet el˝otérbe. Ebben az alfejezetben a m´ asodik megoldással foglalkozom, vagyis azzal, hogy hogyan tudunk egy stream-et elmenteni, majd u ´jra felolvasni. Ezt kidolgozva más el˝onyökhez is jutunk, mégpedig, hogy a let´ arolt lista adott index˝ u elemeihez a memóriában való tárol´ as miatt O(1) id˝ o alatt hozz´ a tudunk férni, szemben a lista vagy a stream esetében, ahol ez az id˝o O(n). Haskell-ben létezik t¨ omb¨ ot megvalós´ıtó adatstrukt´ ura, amelynek defin´ıciója a következ˝oképp néz ki: data (Ix a) => Array a b = MkArray (a,a) (a -> b) deriving ()

Egy t¨ omb¨ ot ezek szerint megadhatunk egy index intervallummal, és egy olyan f¨ uggvénnyel, ami az indexb˝ ol értékre képez le. A m˝ uködésébe ennél részletesebben nem kell belemélyedn¨ unk, helyette az Array -el végezhet˝o alapm˝ uveletekre érdemes koncentrálni: • listArray : Array létrehoz´ as, és az elemek feltöltése kezdeti értékkel • (//) : adott index˝ u elem módos´ıtása • (!) : adott index˝ u elem lekérése Ezzel a h´ arom m˝ uvelettel a felvázolt probléma már megoldható. A listArray -t nem tekintem m˝ uveletnek, mert a létrehozás ford´ıtási id˝oben, statikusan m˝ uködhet. (az elosztottan haszn´ alt mem´ ori´ ak és a memóriaallokálás kérdése t´ ulmutat jelen dolgozat határain) Az elemek kezdeti értékkel val´ o feltöltését pedig szintén statikusan ford´ıtási id˝oben, vagy dinamikusan a (//) m˝ uvelet használatával meg tudjuk valós´ıtani. Minden listArray-hez teh´ at egy-egy block RAM-ot kell létrehoznunk ford´ıtási id˝oben, amit ut´ ana az olvas´ asi és ´ır´ asi m˝ uveletekkel futási id˝oben is kezelhet¨ unk. A (!) oper´ ator, vagyis a VHDL szinten nth -nak h´ıvott modul a bemeneti értékét a block RAM c´ımvonal´ ara k¨ uldi, a block RAM által a kimeneti adatvonalon szolgáltatott érték pedig az nth kimenetére fog ker¨ ulni egy órajel eltolással. (amennyiben a block RAM szintén a rendszer ´ orajelre van k¨ otve, ami szinkron hálózat lévén persze indokolt) A (//) oper´ ator list´ at v´ ar, vagyis VHDL megfelel˝oje, a wr nev˝ u modul stream-et. A stream-en érkez˝ o adatok p´ arosával érkeznek (2-es tuple-ként), aminek egyik eleme az indexet jelenti, m´ asik eleme pedig az indexre be´ırandó értéket. A m˝ uvelet megvalós´ıtása 59

szintén egyszer˝ u, a wr modul az indexet a block RAM c´ımvonalára, az értéket pedig a bemeneti adatvonal´ ara k¨ oti, ´ıgy a k¨ ovetkez˝o órajelre az érték beker¨ ul a block RAM index által meghat´ arozott c´ımére. A modulok egy-egy lehetséges VHDL kódja a f¨ uggelékben megtalálható.

60

4. fejezet

A m´ odszer gyakorlati alkalmaz´ asa mintafeladatokon A 2. és a 3. fejezetekben ´ altalam kidolgozott módszert Haskell nyelven ´ırt ford´ıtóprogramként implement´ altam, melynek a ford´ıtás során keletkezett naplója a f¨ uggelékben megtekinthet˝ o. Az elkész¨ ult ford´ıt´ oprogramot egy PID szabályozó és egy MP3 dekódoló algoritmusrészleten teszteltem, jelen fejezetben a teszt eredményeit mutatom be.

4.1. PID szab´ alyoz´ o Az elkész¨ ult ford´ıt´ oprogramot Csák Bence Ph.D. értekezésében [14] példaként használt PID szab´ alyoz´ o algoritmussal teszteltem, ennek eredményét ismertetem a most következ˝ o fejezetben. Az értekezés szerinti C nyelven ´ırt kód a 4.1. ábrán olvasható. Ennek Haskell nyelvi változat´ at elkész´ıtettem, és a 4.2. ábrán be is mutatom. A plant_algo és pid_algo f¨ uggvények mindkét megold´ asban ugyan azt a bels˝o m˝ uködést valós´ıtják meg, a legf˝obb eltérés az, hogy a Haskell tiszta funkcionális nyelv, tehát a C verzió statikus változóit (esum és e ) a f¨ uggvény paramétereként és a visszatérésnél is szerepeltetni kell. A C példa for ciklus´ anak belsejét a Haskell k´ od iteration f¨ uggvényeként implementáltam, a for ciklus, teh´ at a teljes algoritmus pedig az algo_main f¨ uggvénybe ker¨ ult. Ahhoz, hogy a hardveres oszt´ as minél egyszer˝ ubben megvalós´ıtható legyen, a 8-al való oszt´ ashoz bevezettem egy quot8 nev˝ u f¨ uggvényt, amit ezért a m˝ uvelethalmazban is definiálnom kellett.

4.1.1. A ford´ıt´ as l´ ep´ esei A ford´ıt´ oprogram els˝ o lépésként a Haskell forráskódból a GHC könyvtári f¨ uggvényei seg´ıtségével el˝ o´ all´ıtja a 4.3. ´ abr´ an l´ atható Core reprezentációt. A CaseReduction algoritmus ebb˝ol a reprezent´ aci´ ob´ ol elimin´ al minden case kifejezést, az ´ıgy kapott kódot pedig az IterateConversion alak´ıtja ´ at, ennek eredménye látható a 4.4. ábrán. A még mindig Core formáj´ aban létez˝ o le´ır´ as az AppRename és CoreToTree fázisokon kereszt¨ ulhaladva a 4.5. ábrán sz¨ ovegesen bemutatott gr´ afot eredményezi, aminek a TreeSimplifier algoritmus ut´ a61

#include <s t d i o . h> char p l a n t a l g o ( char c , char y ) { y = (7∗ c + y ) / 8 ; } char p i d a l g o ( char x , char y ) { s t a t i c const char cp =2; s t a t i c const char c i =1; s t a t i c const char cd =2; s t a t i c char esum = 0 ; s t a t i c char e = 0 ; char p , i , d , e o l d , e d i f f ; eold = e ; e = x − y; e d i f f = e − eold ; esum += e ; p = cp ∗ e / 8 ;

i = c i ∗ esum / 8 ; d = cd ∗ e d i f f / 8 ; return p + i + d ; // c } in t main ( ) { char c , y , i , x=8; y = 0; f o r ( i =0; i <30; i ++) { c = pid algo (x , y ) ; y = plant algo (c , y ); p r i n t f ( ”%d\n ” , y ) ; } return 0 ; }

4.1. ´ abra. PID algoritmus C forráskódja {−# LANGUAGE N o I m p l i c i t P r e l u d e #−} module Pid ( hwmain ) where import I n s t r u c t i o n S e t p l a n t a l g o : : Int −> Int −> Int p l a n t a l g o c y = quot8 ( 7 ∗ c + y ) ; p i d a l g o : : Int −> Int −> ( Int , Int ) −> ( Int , ( Int , Int ) ) p i d a l g o x y ( e , esum ) = let eold = e e2 = x − y e d i f f = e2 − e o l d esum2 = esum + e2 p = quot8 $ 2 ∗ e2 i = quot8 $ 1 ∗ esum2 d = quot8 $ 2 ∗ e d i f f in ( p+i+d , ( e2 , esum2 ) ) i t e r a t i o n : : ( Int , Int , Int ) −> Int −> ( Int , Int , Int ) i t e r a t i o n ( e , esum , y ) x = l e t ( c , ( e2 , esum22 ) ) = p i d a l g o x y ( e , esum ) y2 = p l a n t a l g o c y in ( e2 , esum22 , y2 ) a l g o m a i n : : Int −> [ ( Int , Int , Int ) ] a l g o m a i n i n p u t = i t e r a t e ( \ x −> i t e r a t i o n x i n p u t ) ( 0 , 0 , 0 ) hwmain = a l g o m a i n

4.2. ´ abra. PID algoritmus Haskell forráskódja

ni, egyszer˝ us´ıtett v´ altozat´ at grafikusan a 4.6. ábrán szemléltetem. A ConvertToEOG algoritmus ennek a gr´ afnak az inorder bej´ ar´ asával adja a Haskell-EOG ford´ıtómodul kimenetét, azaz a a 4.7. ´ abr´ an sz¨ ovegesen, majd a 4.8. ábrán vizuálisan megjelen´ıtett elemi m˝ uveleti gráfot. Az EOG-VHDL ford´ıt´ omodul az EOG-b˝ol már közvetlen¨ ul VHDL le´ırást tud generálni, az eredményt a 4.9. ´ abr´ an szemléltetem. 62

nrec quot 8 reEp = app I n s t r u c t i o n S e t . quot 8 r e 4n [ 1 ] var GHC. Real . $ f I n t e g r a l I n t r e 0b − GHC. Real . I n t e g r a l GHC. Types . I n t nrec quot 8 1 r e E t = app I n s t r u c t i o n S e t . quot 8 r e 4n [ 1 ] var GHC. Real . $ f I n t e g r a l I n t r e 0b − GHC. Real . I n t e g r a l GHC. Types . I n t nrec Pid . hwmain redC = lam i n p u t aeBj app GHC. L i s t . i t e r a t e r e 4o<( I n t , In t , I n t )> [ 2 ] lam x aeBk case var x aeBk − (GHC. Types . I n t , GHC. Types . I n t , GHC. Types . I n t ) a l t ( , , ) e esum y l e t nrec e 2 s e E l = app GHC.Num. − 01F [ 3 ] var i n p u t aeBj − GHC. Types . I n t var y aeBd − GHC. Types . I n t l e t nrec esum 2 seEk = app GHC.Num.+ rdZC [ 3 ] var esum aeBc − GHC. Types . I n t var e 2 s e E l − GHC. Types . I n t app GHC. Tuple . ( , , ) 7 7 < I n t , I nt , I n t > [ 3 ] var e 2 s e E l − GHC. Types . I n t var esum 2 seEk − GHC. Types . I n t app quot 8 1 reEt<> [ 1 ] app GHC.Num.+ rdZC [ 3 ] app GHC.Num. ∗ rdZD [ 3 ] app GHC. Types . I # 6d<> [ 1 ] lit 7 app GHC.Num.+ rdZC [ 3 ] app GHC.Num.+ rdZC [ 3 ] app quot 8 reEp<> [ 1 ] app GHC.Num. ∗ rdZD [ 3 ] app GHC. Types . I # 6d<> [ 1 ] lit 2 var e 2 s e E l − GHC. Types . I n t app quot 8 reEp<> [ 1 ] app GHC.Num. ∗ rdZD [ 3 ] app GHC. Types . I # 6d<> [ 1 ] lit 1 var esum 2 seEk − GHC. Types . I n t app quot 8 reEp<> [ 1 ] app GHC.Num. ∗ rdZD [ 3 ] app GHC. Types . I # 6d<> [ 1 ] lit 2 app GHC.Num. − 01F [ 3 ] var e 2 s e E l − GHC. Types . I n t var e aeBb − GHC. Types . I n t var y aeBd − GHC. Types . I n t app GHC. Tuple . ( , , ) 7 7 < I n t , In t , I n t > [ 3 ] app GHC. Types . I # 6d<> [ 1 ] lit 0 app GHC. Types . I # 6d<> [ 1 ] lit 0 app GHC. Types . I # 6d<> [ 1 ] lit 0

4.3. ´ abra. GHC által szolgáltatott Core kód

63

nrec Pid . hwmain va = lam i n p u t vb l e t nrec x vc = app i t e r a t e od<> [ 2 ] var C ou − # app GHC. Tuple . ( , , ) oe [ 3 ] app GHC. Types . I # of <> [ 1 ] lit 0 app GHC. Types . I # og<> [ 1 ] lit 0 app GHC. Types . I # oh<> [ 1 ] lit 0 l e t nrec i t out 0 v i = l e t nrec s c r u t i n e e 0 v j = var x vc − (GHC. Types . I n t , GHC. Types . I n t , GHC. Types . I n t ) l e t nrec e vk = app s e l e c t <( , ,) ,0 > o l <> [ 1 ] var s c r u t i n e e 0 v j − # l e t nrec esum vm = app s e l e c t <( , ,) ,1 > on<> [ 1 ] var s c r u t i n e e 0 v j − # l e t nrec y vo = app s e l e c t <( , ,) ,2 > op<> [ 1 ] var s c r u t i n e e 0 v j − # l e t nrec e 2 vq = app GHC.Num. − or [ 3 ] var i n p u t vb − GHC. Types . I n t var y vo − GHC. Types . I n t l e t nrec esum 2 vs = app GHC.Num.+ ot [ 3 ] var esum vm − GHC. Types . I n t var e 2 vq − GHC. Types . I n t app GHC. Tuple . ( , , ) ou [ 3 ] var e 2 vq − GHC. Types . I n t var esum 2 vs − GHC. Types . I n t app quot 8 1 v8<> [ 1 ] app GHC.Num.+ ow [ 3 ] app GHC.Num. ∗ ox [ 3 ] app GHC. Types . I # oy<> [ 1 ] lit 7 app GHC.Num.+ oz [ 3 ] app GHC.Num.+ oA [ 3 ] app quot 8 v3<> [ 1 ] app GHC.Num. ∗ oC [ 3 ] app GHC. Types . I # oD<> [ 1 ] lit 2 var e 2 vq − GHC. Types . I n t app quot 8 v3<> [ 1 ] app GHC.Num. ∗ oF [ 3 ] app GHC. Types . I # oG<> [ 1 ] lit 1 var esum 2 vs − GHC. Types . I n t app quot 8 v3<> [ 1 ] app GHC.Num. ∗ oI [ 3 ] app GHC. Types . I # oJ<> [ 1 ] lit 2 app GHC.Num. − oK [ 3 ] var e 2 vq − GHC. Types . I n t var e vk − GHC. Types . I n t var y vo − GHC. Types . I n t var i t out 0 v i − #

4.4. ´ abra. CaseReduction utáni Core kód

64

lam [ ] input { var [ i t out 0 v i ] l e t −var { op [ C ou ] { var [ e 2 vq ] l e t −var { op [ sub o r ] { var [ i n p u t vb ] lam−var { vv [ IN 1 a 0 ] } var [ y vo ] l e t −var { op [ s e l e c t <( , ,) ,2 > < > op ] { var [ s c r u t i n e e 0 v j ] l e t −var { var [ x vc ] l e t −var { op [ i t e r a t e <> od ] { vv [ C ou ] op [ C oe ] { op [ C o f ] { l i t [ c o n s t 0 ] } op [ C og ] { l i t [ c o n s t 0 ] } op [ C oh ] { l i t [ c o n s t 0 ] }}}}}}}}} var [ esum 2 vs ] l e t −var { op [ add o t ] { var [ esum vm ] l e t −var { op [ s e l e c t <( , ,) ,1 > < > on ] { lnk [ i t e r a t e <> od ] }} lnk [ sub o r ] }} capp [ quot 8 1 ] { var [ quot 8 1 v 8 ] ? { lam [ e t a kamu ] 1 { op [ quot8 o 9 i v ] { op [ add ow ] { op [ mul ox ] { op [ C oy ] { l i t [ c o n s t 7 ] } op [ add oz ] { op [ add oA ] { capp [ quot 8 ] { var [ quot 8 v 3 ] ? { lam [ e t a kamu ] 1 { op [ quot8 o 4 iB ] { op [ mul oC ] { op [ C oD ] { l i t [ c o n s t 2 ] } lnk [ sub o r ] }}}}} capp [ quot 8 ] { var [ quot 8 v 3 ] ? { lam [ e t a kamu ] 1 { op [ quot8 o 4 iE ] { op [ mul oF ] { op [ C oG ] { l i t [ c o n s t 1 ] } lnk [ add o t ] }}}}}} capp [ quot 8 ] { var [ quot 8 v 3 ] ? { lam [ e t a kamu ] 1 { op [ quot8 o 4 iH ] { op [ mul o I ] { op [ C oJ ] { l i t [ c o n s t 2 ] } op [ sub oK ] { lnk [ sub o r ] var [ e vk ] l e t −var { op [ s e l e c t <( , ,) ,0 > < > o l ] { lnk [ i t e r a t e <> od ] }}}}}}}}}} lnk [ s e l e c t <( , ,) ,2 > < > op ] }}}}}}}}

4.5. ´ abra. A CoreToTree algoritmus utáni gráf

65

OUT

C_ou

sub_or

IN_1_a0

select_op

select_on

iterate_od

iterate_od

C_ou

const_0_l7

add_ot

quot8_o9_iv

sub_or

mul_ox

C_oe

const_0_l8

const_2_lm

add_ow

const_7_lh

select_op

add_oz

const_0_l9

add_oA

quot8_o4_iH

quot8_o4_iB

quot8_o4_iE

mul_oI

mul_oC

mul_oF

const_2_lu

sub_or

const_1_lq

add_ot

sub_oK

sub_or

select_ol

iterate_od

4.6. ´ abra. A TreeSimplifier algoritmus utáni gráf

IN 1 a 0 const 0 l 7 const 0 l 8 const 0 l 9 C oe i t e r a t e od s e l e c t op sub o r s e l e c t on add o t const 7 lh c o n s t 2 lm mul oC quot 8 o 4 iB const 1 lq mul oF quot 8 o 4 iE add oA const 2 lu select ol sub oK mul o I quot 8 o 4 iH add oz mul ox add ow quot 8 o 9 i v C ou OUT

”IN<96>” ”Const <32,0>” ”Const <32,0>” ”Const <32,0>” ”C3 <0 ,0 ,32 ,32 ,32 >” ” I t e r a t e <96>” ” S e l e c t <96 ,64 ,32 >” ”Sub<32>” ” S e l e c t <96 ,32 ,32 >” ”Add<32>” ”Const <32,7>” ”Const <32,2>” ”Mul<32>” ”Quot8<32>” ”Const <32,1>” ”Mul<32>” ”Quot8<32>” ”Add<32>” ”Const <32,2>” ” S e l e c t <96 ,0 ,32 >” ”Sub<32>” ”Mul<32>” ”Quot8<32>” ”Add<32>” ”Mul<32>” ”Add<32>” ”Quot8<32>” ”C3 <0 ,0 ,32 ,32 ,32 >” ”OUT<96>”

const 0 l 7 const 0 l 8 const 0 l 9 C ou C oe i t e r a t e od IN 1 a 0 s e l e c t op i t e r a t e od s e l e c t on sub o r

c o n s t 2 lm sub o r mul oC c o n s t 1 l q add o t mul oF quot 8 o 4 iB quot 8 o 4 iE i t e r a t e od sub o r s e l e c t o l c o n s t 2 l u sub oK mul o I add oA quot 8 o 4 iH c o n s t 7 l h add oz mul ox s e l e c t op add ow sub o r add o t quot 8 o 9 i v C ou

4.7. ´ abra. A Haskell-EOG modul kimenete

66

const_0_l7 Const<32,0>



C_oe C3<0,0,32,32,32>

IN_1_a0 IN<96>

iterate_od Iterate<96>

select_on Select<96,32,32>

add_ot Add<32>

sub_or Sub<32>

const_2_lm Const<32,2>

const_1_lq Const<32,1>

mul_oC Mul<32>

select_op Select<96,64,32>

select_ol Select<96,0,32>

sub_oK Sub<32>

mul_oF Mul<32>

const_2_lu Const<32,2>

mul_oI Mul<32>

quot8_o4_iE Quot8<32>

quot8_o4_iB Quot8<32>

add_oA Add<32>

quot8_o4_iH Quot8<32>

add_oz Add<32>

const_7_lh Const<32,7>

mul_ox Mul<32>

add_ow Add<32>

quot8_o9_iv Quot8<32>

C_ou C3<0,0,32,32,32>

OUT SYSTEM

4.8. ´ abra. A Haskell-EOG modul kimenete grafikusan

67

l i b r a r y IEEE ; use IEEE . STD LOGIC 1164 .ALL; use IEEE . STD LOGIC ARITH .ALL; use IEEE . STD LOGIC UNSIGNED .ALL; use work . d e f s . a l l ; entity benchmark i s Port ( r e s t a r t , c l k : I N 1 a 0 : in Output : out c I N 1 a 0 : in cOutput : out ); end benchmark ;

in STD LOGIC ; STD LOGIC VECTOR ( 3 1 downto 0 ) ; STD LOGIC VECTOR ( 9 5 downto 0 ) ; std logic ; std logic

architecture B e h a v i o r a l of benchmark i s component c o n s t s o u r c e i s generic ( width : i n t e g e r ; v a l u e : i n t e g e r ) ; port ( out1 : out s t d l o g i c v e c t o r ( ( width −1)downto 0 ) : = ( others=> ’ 0 ’ ) ; cq : out s t d l o g i c ; c l k : in s t d l o g i c ) ; end component ; component c 3 a i s generic ( cwidth : i n t e g e r ; c v a l u e : i n t e g e r ; w1 : i n t e g e r ; w2 : i n t e g e r ; w3 : i n t e g e r ) ; port ( i n 1 : in s t d l o g i c v e c t o r ( ( w1−1)downto 0 ) ; i n 2 : in s t d l o g i c v e c t o r ( ( w2−1)downto 0 ) ; i n 3 : in s t d l o g i c v e c t o r ( ( w3−1)downto 0 ) ; q : out s t d l o g i c v e c t o r ( ( w1+w2+w3−1)downto 0 ) ; c1 : in s t d l o g i c ; c2 : in s t d l o g i c ; c3 : in s t d l o g i c ; cq : out s t d l o g i c ; c l k : in s t d l o g i c ) ; end component ; component i t e r a t e i s generic ( p1 : i n t e g e r ) ; port ( f e e d b a c k : in s t d l o g i c v e c t o r ( ( p1 −1)downto 0 ) ; f i r s t v a l u e : in s t d l o g i c v e c t o r ( ( p1 −1)downto 0 ) ; q : out s t d l o g i c v e c t o r ( ( p1 −1)downto 0 ) ; c f e e d b a c k : in s t d l o g i c ; c f i r s t v a l u e : in s t d l o g i c ; cq : out s t d l o g i c ; c l k : in s t d l o g i c ) ; end component ; s i g n a l c o n s t 0 l 7 : STD LOGIC VECTOR ((32 −1)downto 0 ) ; signal c c o n s t 0 l 7 : s t d l o g i c ; s i g n a l C oe : STD LOGIC VECTOR ((32+32+32 −1)downto 0 ) ; s i g n a l cC oe : s t d l o g i c ; s i g n a l i t e r a t e o d : STD LOGIC VECTOR ((96 −1)downto 0 ) ; signal c i t e r a t e o d : s t d l o g i c ; −− t o v a b b i s i g n a l −ok begin const 0 l7 o : const source generic map ( 3 2 , 0 ) port map( c o n s t 0 l 7 , c c o n s t 0 l 7 , c l k ) ; C oe o : c 3 a generic map ( 0 , 0 , 3 2 , 3 2 , 3 2 ) port map( c o n s t 0 l 7 , c o n s t 0 l 8 , c o n s t 0 l 9 , C oe , c c o n s t 0 l 7 , c c o n s t 0 l 8 , c c o n s t 0 l 9 , cC iterate od o : iterate generic map ( 9 6 ) port map( C ou , C oe , i t e r a t e o d , cC ou , cC oe , c i t e r a t e o d , c l k ) ; −− t o v a b b i p e l d a n y o s i t a s o k Output <= C ou ; cOutput <= cC ou ; end B e h a v i o r a l ;

4.9. ´ abra. A generált VHDL kód (részlet)

68

4.1.2. Szimul´ aci´ o Az elkész¨ ult VHDL le´ır´ ast a Xilinx ISE 11.5 verziój´ u programjával teszteltem, és ugyanezen programcsomag ISim alkalmaz´ as´ aval szimuláltam. A szimul´ al´ ast a Ph.D értekezés szerinti bemenettel végeztem, azaz a bemeneti jel a hls Project Status (05/30/2011 - 00:56:35)

0 értékr˝ olProject alland´ ´ osult hls.ise 8 -ra v´ altozik, ezImplementation az ugrásState: a 4.11. áPlaced brán bemutatott id˝odiagramon File: and Routed Module Name: benchmark No Errors 50 ns id˝ opillanatban k¨ ovetkezik be. A PIDErrors: szabályzó a cin_1_a0 bemenet felfutó élére Target Device:

xc3s500e-4fg320

Warnings:

223 Warnings (0 new)

mintavételez, 16 cikluson kereszt¨ ul törtéRouting nik. Az outputAll ySignals jele szolg´ altatja a kimenetet, Productami Version: ISE 11.5 Results: Completely Routed Goal: Timing Constraints: a 16 ciklusDesign lefut´ asa ut´ aBalanced n ez 7 -nél állandósul. Design Strategy:

Xilinx Default (unlocked)

All Constraints Met

Final Timing Score:

0 (Setup: 0, Hold: 0) (Timing Report)

Device Utilization Summary Logic Utilization

Used

[-]

Available

Utilization

Note(s)

Number of Slice Flip Flops

194

9,312

2%

Number of 4 input LUTs

773

9,312

8%

Number of occupied Slices

430

4,656

9%

430

430

100%

0

430

0%

815

9,312

8%

232

56%

Number of Slices containing only related logic Number of Slices containing unrelated logic Total Number of 4 input LUTs Number used as logic

773

Number used as a route-thru

42

Number of bonded IOBs

131

1 szint´ 4.10. ´ abra. Az FPGA ezis 24 eredménye

Number of BUFGMUXs Number of MULT18X18SIOs

6

Average Fanout of Non-Clock Nets

20

4% 30%

2.27

0 ps

100,000 ps 200,000 ps Performance Summary

300,000 ps

400,000 ps

500,000 ps [+]

restart clk Detailed Reports

0

in_1_a0[31:0]

[+]

8

cin_1_a0 output[95:0]

Secondary Reports

4

7

6

[+]

e

U

8

5

4

3

esum

U

y

U

8 Date 12 Generated: 19 25 05/30/2011 30 35- 01:02:24 39 43 4 1 2 3 4

46

49

2

52

55

58

60

5

62

64

6

7

coutput 10000 ps

clk_period datas add_oa[31:0]

X

0

3

2

3

add_ot[31:0]

X

0

8

12

19

4

5

5

6

5

35

39

43

46

add_oz[31:0]

X

0

5

1

3

4

5

5

6

5

quot8_o4_ie[31:0]

X

0

1

1

quot8_o9_iv[31:0]

X

0

4

1

2

3

4

4

2

3

4

4

select_ol[31:0] (e)

U

0

8

4

7

6

select_on[31:0] (esum)

U

0

8

12

19

25

select_op[31:0] (y)

U

0

4

1

2

sub_ok[31:0]

X

0

8

-4

3

-1

sub_or[31:0]

X

0

8

4

7

6

25

30

5

5

58

35

39

-1

60

43

46

8

6

7

8

6

49

-1

4

7

52

2 55

58

0 2

1

cquot8_o9_iv coutput - cc_ou

coutput citerate_od

4.11. ´ abra. A szimuláció eredménye

69

-1 1

csub_or

cquot8_o9_iv - cadd_oz - cmul cquot8_o9_iv - cadd_oz - cmul_ox - cadd_ow

64 7

-1

csub_or - cadd_ot - cmul_oc csub_or - cadd_ot - cmul_oc - cadd_oa - cmul_of - cquot8_o4_ie - cquot8_o4_ib

cmul_oi

62

6 0

3

60

cin_1_a0

cmul_oi - csub_ok - cquot8_ cmul_oi - csub_ok - cquot8_o4_ih

65

7

controls

coutput - cc_ou

64

6

5 0

8 62

3

4 0

55

4

3 -1

7

52

5

5 30

6 49

4.2. MP3 dek´ odol´ o algoritmus Második tesztesetként az MP3 dek´ odol´ o algoritmus egy részletét választottam, hogy ezzel is megvilág´ıtsam a m´ odszer gyakorlati használhatóságát. Fontos cél volt, hogy a teszteset a többsebesség˝ u kiterjesztés funkci´ oit használja, az el˝obbiekben bemutatott Pid algoritmus ugyanis egysebesség˝ u adatfolyamgr´ afot ad, ´ıgy a modell kiterjesztésének vizsgálata nem végezhet˝o el seg´ıtségével. A választott MP3 algoritmusrészlet részlet a dekódolás végfokozatában található Synthesis Filter Bank nevet visel˝ o modul, amely a frekvenciatartományban kódolt jelsorozatból el˝oáll´ıtja az id˝ otartom´ anybeli alakot, azaz a mintavételezet hanghullámot. Az MP3 dek´ odol´ o algoritmusnak létezik Haskell forráskód´ u változata [8], ez viszont a Synthesis Filter Bank-et k¨ uls˝ o C nyelv˝ u modulként tartalmazza (PC-n futtatva ´ıgy gyorsabb kódot kaptak). A C k´ odot ´ at´ırtam Haskell-re, ´ıgy a modul tesztelhet˝ové vált közvetlen¨ ul az mp3 dek´ odol´ o rendszerben. Lebeg˝opontr´ ol ´ attértem fixpontos ´ abrázolásra, és az ´ıgy módos´ıtott algoritmust a teljes mp3 dekódol´ asba beillesztve teszteltem a dekódoló funkcionalitását. 7 bites pontosságnál a zajos hanghat´ ast tapasztaltam, de 10 bitnél már nem volt hallható, ´ıgy ráhagyással a választásom 32 bites sz´ am´ abr´ azol´ asra, és ezen bel¨ ul 16 bites törtábrázolásra esett. Az ´ıgy módos´ıtott Synthesis Filter Bank algoritmust a 4.12. ábrán látható kódrészlettel ´ırtam le. Az algoritmus négy f¨ uggvényb˝ ol ´ all: uconv , usum , ssum és synthH1 . Az usum nagyban hasonl´ıt a ssum -ra, ´ıgy modulszint˝ u tesztelésnél csak az utóbbival foglalkozom. A synthH1 f¨ uggvény a tulajdonképpeni Synthesis Filter Bank algoritmus, ez használja segédf¨ uggvényként a többi f¨ uggvényt. Az uconv modul forr´ ask´ odja és az abból generált EOG a 4.13-as ábrán, az ssum a 4.14-es ábrán, a synthH1 pedig a 4.14-es és 4.15-ös ábrán látható. A VHDL szimulációs eredményeit a 4.21. fejezet hull´ amforma ábráival foglalom o¨ssze. A szimulációból jól látható, hogy a kimeneti eredmények megegyeznek a Haskell futtatás során kapott listákkal:

ssum: [(10416,5),(26288,6),(42160,7),(58032,8),(73904,9), (89776,10),(105648,11),(121520,12),(137392,13), (153264,14),(169136,15),(185008,16),(200880,17) .. uconv: [(157470,287),(176928,288),(237534,351),(261280,352) ..

70

{−# LANGUAGE N o I m p l i c i t P r e l u d e #−} module MP3( hwmain ) where import I n s t r u c t i o n S e t import SFBConstants infixr 0 $ ( $ ) : : ( a −> b ) −> a −> b f $ x = f x hwmain x = synthH1 i n p u t A r r a y ( s t a t e A r r a y , [ ] ) x uconv n e w s t a t e s t a r t k = l e t ( i , j ) = divMod64 k c o n v 1 i = i f ( j <32) then ( i ∗128 + j ) e l s e ( i ∗128 + ( j −32) + 9 6 ) conv1 = n e w s t a t e ! ( mod1024 ( c o n v 1 i+s t a r t ) ) conv2 = synthArray ! k in ( conv1 ‘ imul ‘ conv2 , k ) usum : : I n t A r r a y −> [ I n t ] usum uL = map sumn [ 0 . . 3 1 ] where sumn i = sum $ map ( f u n c i ) [ 0 . . 1 5 ] f u n c i j = uL ! ( j ∗32 + i ) ssum : : I n t −> I n t A r r a y −> [ ( I n t , I n t ) ] ssum s t a r t sL = map ( \ i −> ( sumn i , i+s t a r t ) ) [ 0 . . 6 3 ] where sumn i = sum $ map ( f u n c i ) [ 0 . . 3 1 ] f u n c i j = ( ( sL ! j ) ∗ ( lookupArray ! ( i ∗ ( 3 2 : : I n t ) + j ) ) ) synthH1 : : I n t A r r a y −> ( IntArray , [ I n t ] ) −> I n t −> ( IntArray , [ I n t ] ) synthH1 i n p u t ( s t a t e , ) s = l e t sL = map ( \ i −> ( i n p u t ! ( i ∗18 + s ) , i+s t a r t ) ) [ 0 . . 3 1 ] s2L = s l A r r a y // sL s t a r t = mod1024 (2048 −( s +1)∗64) n e w s t a t e = s t a t e // ( ssum s t a r t s2L ) uL = map ( uconv n e w s t a t e ( s t a r t ) [ 0 . . 5 1 1 ] u2L = u l A r r a y // uL in ( newstate , usum u2L )

4.12. ´ abra. MP3 Synthesis Filter Bank

71

hwmain ( s t a r t , k ) = uconv s t a t e A r r a y s t a r t k uconv n e w s t a t e s t a r t k = l e t ( i , j ) = divMod64 k c o n v 1 i = i f ( j <32) then ( i ∗128 + j ) e l s e ( i ∗128 + ( j −32) + 9 6 ) conv1 = n e w s t a t e ! ( mod1024 ( c o n v 1 i+s t a r t ) ) conv2 = synthArray ! k in ( conv1 ‘ imul ‘ conv2 , k )

IN_1_a0 IN<0,64>

synthArray_r0 SynthArray<0,32>

select_o14 Select<0,64,32,32>

divMod64_o18 DivMod64<0,32>

select_o2e Select<0,64,0,32>

const_128_lu Const<0,32,128>

select_o1k Select<0,64,32,32>

mul_o28 Mul<0,32>

const_32_lm Const<0,32,32>

const_32_ld Const<0,32,32>

add_o26 Add<0,32>

lt_o1y Lt<0,32>

select_o1Q Select<0,64,0,32>

sub_o1Y Sub<0,32>

const_96_ln Const<0,32,96>

ifcon_o24 Ifcon<0,32,1>

nth_o2m Nth<0,32>

const_128_lj Const<0,32,128>

mul_o1K Mul<0,32>

add_o1I Add<0,32>

add_o1G Add<0,32>

buf1 Buf<0,32>

ifcon_o1E Ifcon<0,32,0>

select_o10 Select<0,64,0,32>

buf2 Buf<0,32>

mux_o1C Mux<0,32>

add_o1u Add<0,32>

stateArray_r0 StateArray<0,32>

mod1024_o1s Mod1024<0,32>

nth_o1q Nth<0,32>

mul_o1o Mul<0,32>

C_o1m C2<0,0,0,32,32>

OUT1 OUT<0,64>

4.13. ´ abra. Az uconv modul forráskódja és az abból generált EOG

72

hwmain x = ssum x s l A r r a y ssum : : I n t −> I n t A r r a y −> [ ( I n t , I n t ) ] ssum s t a r t sL = map ( \ i −> ( sumn i , i+s t a r t ) ) [ 0 . . 6 3 ] where sumn i = sum $ map ( f u n c i ) [ 0 . . 3 1 ] f u n c i j = ( ( sL ! j ) ∗ ( lookupArray ! ( i ∗ ( 3 2 : : I n t ) + j ) ) )

IN_1_a0 IN<0,32>

const_0_lf Constt<0,32,0>

const_32_lh Const<1,32,32>

mul_oA Mul<1,32>

const_63_lg Constt<0,32,63>

enumFromTo_oa EnumFromTo<1,32,64,70>

const_0_l8 Constt<1,32,0>

const_31_l9 Constt<1,32,31>

levelAdapter2 LevelAdapter<1,32>

enumFromTo_om EnumFromTo<2,32,32,2>

add_oE Add<1,32>

levelAdapter1 LevelAdapter<2,32>

slArray_r0 SlArray<0,32>

add_oy Add<2,32>

lookupArray_r0 LookupArray<0,32>

nth_ou Nth<2,32>

nth_ow Nth<2,32>

mul_os Mul<2,32>

sum_oi Sum<2,32,64>

C_og C2<1,0,0,32,32>

OUT1 OUT<1,64>

4.14. ´ abra. Az ssum modul forráskódja és az abból generált EOG

hwmain x = sum $ synthH1 i n p u t A r r a y ( s t a t e A r r a y , [ ] ) x synthH1 : : I n t A r r a y −> ( IntArray , [ I n t ] ) −> I n t −> [ I n t ] synthH1 i n p u t ( s t a t e , ) s = l e t sL = map ( \ i −> ( i n p u t ! ( i ∗18 + s ) , i+s t a r t ) ) [ 0 . . 3 1 ] s2L = s l A r r a y // sL s t a r t = mod1024 (2048 −( s +1)∗64) n e w s t a t e = s t a t e // ( ssum s t a r t s2L ) for512 = [ 0 . . 5 1 1 ] uL = map ( uconv n e w s t a t e ( s t a r t ) ) [ 0 . . 5 1 1 ] u2L = u l A r r a y // uL in usum u2L

4.15. ´ abra. Sfb algoritmus Haskell forráskódja

73

74

ulArray_r0 UlArray<0,32>

synthArray_r0 SynthArray<0,32>

nth_o2S Nth<1,32>

const_128_l15 Const<1,32,128>

sub_o2u Sub<1,32>

mul_o2g Mul<1,32>

add_o2e Add<1,32>

const_32_l18 Const<1,32,32>

select_o2m Select<1,64,0,32>

add_o2c Add<1,32>

const_96_l19 Const<1,32,96>

ifcon_o2a Ifcon<1,32,0>

lt_o24 Lt<1,32>

mux_o28 Mux<1,32>

ifcon_o2AA Ifcon<1,32,1>

nth_oQ Nth<1,32>

add_oS Add<1,32>

wr_oE Wr<1,32,32>

C_oO C2<1,0,0,32,32>

add_oY Add<1,32>

mul_oU Mul<1,32>

const_18_lo Const<1,32,18>

const_31_ln Constt<0,32,31>

enumFromTo_oI EnumFromTo<1,32,6,4>

const_0_lm Constt<0,32,0>

const_0_lB Constt<1,32,0>

nth_o1m Nth<2,32>

const_31_lC Constt<1,32,31>

const_32_l1u Const<2,32,32>

const_0_l1s Constt<1,32,0>

const_15_l1t Constt<1,32,15>

enumFromTo_o36 EnumFromTo<2,32,6,4>

enumFromTo_o2W EnumFromTo<1,32,6,4>

OUT1 OUT<0,32>

sum_o4 Sum<1,32,33>

sum_o32 Sum<2,32,33>

nth_o3c Nth<2,32>

add_o3e Add<2,32>

wr_oA Wr<1,32,32>

C_o18 C2<1,0,0,32,32>

sum_o1a Sum<1,32,33>

imul_o1k Imul<2,32>

nth_o1o Nth<2,32>

add_o1q Add<2,32>

add_o1w Add<1,32>

enumFromTo_o12 EnumFromTo<1,32,6,4>

enumFromTo_o1e EnumFromTo<2,32,6,4>

mul_o1s Mul<1,32>

const_32_lK Const<1,32,32>

const_63_lJ Constt<0,32,63>

const_31_l1x Constt<0,32,31>

wr_oo Wr<1,32,32>

stateArray_r0 StateArray<0,32>

inputArray_r0 InputArray<0,32>

const_0_lI Constt<0,32,0>

const_0_l1w Constt<0,32,0>

mul_o3g Mul<2,32>

4.16. ´ abra. sfb modul EOG

lookupArray_r0 LookupArray<0,32>

slArray_r0 SlArray<0,32>

mod1024_o8 Mod1024<0,32>

sub_oa Sub<0,32>

const_2048_lu Const<0,32,2048>

const_64_lz Const<0,32,64>

IN_1_a0 IN<0,32>

C_o1S C2<1,0,0,32,32>

imul_o1U Imul<1,32>

nth_o1W Nth<1,32>

mod1024_o1Y Mod1024<1,32>

add_o20 Add<1,32>

mul_o2E Mul<1,32>

add_o2CC Add<1,32>

mul_oe Mul<0,32>

const_128_l1g Const<1,32,128>

const_511_lY Constt<0,32,511>

select_o2K Select<1,64,0,32>

const_32_lZ Const<1,32,32>

select_o1Q Select<1,64,32,32>

divMod64_o1E DivMod64<1,32>

enumFromTo_os EnumFromTo<1,32,6,4>

const_0_lX Constt<0,32,0>

add_og Add<0,32>

const_1_ly Const<0,32,1>

4.2.1. VHDL szimul´ aci´ os eredm´ enyek : 0 us

2 us

4 us

6 us

8 us

4.17. ´ abra. Ssum modul szimulációs hullámformája 10 us nagyságú intervallumban 700 ns

800 ns

900 ns

1,000 ns

1,100 ns

1,200 ns

4.18. ´ abra. Ssum modul szimulációs hullámformája 600 ns nagyságú intervallumban

0 ns

100 ns

200 ns

300 ns

400 ns

4.19. ´ abra. Az uconv modul szimulációs hullámformája

75

500 ns

5. fejezet

Tov´ abbfejleszt´ esi lehet˝ os´ egek Az elkész¨ ult program képes leford´ıtani a definiált m˝ uvelethalmaznak megfelel˝o, le´ırt megkötésekkel rendelkez˝ o Haskell k´ odot. A módszer és a fejlesztett program számtalan továbbfejlesztési lehet˝ oség elé néz, amelyekb˝ ol néhányat a most kezd˝od˝o fejezetben ismertetek.

5.1. Optimaliz´ al´ asi l´ ep´ esek A ford´ıtórendszer t´ amogatja optimaliz´ aciós programok integrálását. Az IIT Tanszéken fejlesztett PIPE optimaliz´ aci´ os tervez˝ orendszer EOG bemenetet vár, ´ıgy az általam fejlesztett ford´ıtóprogram Haskell-EOG és EOG-VHDL moduljai közé beékelhet˝o lenne. Adott esetben az algoritmust EOG szinten optimalizálni tudjuk azzal a céllal, hogy pipeline m˝ uk¨ odés sor´ an nagyobb ´ atereszt˝oképességet, vagyis az u ´jraind´ıtási id˝o csökkenését érj¨ unk el. Ennek a gyakorlati haszna akkor szembet˝ un˝o, ha az EOG-vel meghatározott m˝ uveletsort egym´ as ut´ an sok adaton kell elvégezn¨ unk, ekkor ugyanis a pipeline m˝ uködés hatalmas hatékonys´ agbeli n¨ ovekedést jelenthet. A PIPE rendszer az u ´jraind´ıt´ asi id˝ ot képes redukálni, a m˝ uveletek bemeneti csatornáit szinkronizálja, a feladat végrehajt´ o egységek t´ıpusának és számának ismeretében biztos´ıtja az allokációt, majd meghat´ arozza az egyes m˝ uveletek kezdési idejét.

5.2. Egyebek • A bemenetként haszn´ alhat´ o Haskell kódban jelenleg nem szerepelhet f¨ uggvényrekurzió, és ezzel algoritmusle´ır´ asok egy részét kizárjuk a ford´ıtható kódok köz¨ ul. Megoldás lehet pl., ha el˝ ore meghat´ arozott maximális szám´ u rekurz´ıv h´ıvást megenged¨ unk, mert ´ıgy a hardveres megval´ os´ıt´ as realizálhatóvá válna. A rekurzió kezelésében ezen k´ıv¨ ul is sok nyitott kérdés rejt˝ ozik, ´ıgy a jöv˝oben érdemes lehet ezzel behatóan foglalkozni. • Egy érdekes és id˝ oszeri kutat´ asi téma lehet az LLVM [25] alapján történ˝o automatikus HDL gener´ al´ as, erre a k¨ oztes reprezentációra ugyanis egyre több nyelvr˝ol lehet ford´ıtani, t¨ obbek k¨ oz¨ ott létezik egy Haskell-LLVM frontend is. • A kimeneti VHDL le´ır´ as egyszer˝ us´ıtésén érdemes lehet még dolgozni. Jelenleg minden 76

EOG m˝ uvelet modulpéld´ anyos´ıtásra fordul, ´ıgy pl. a VHDL-ben egyszer˝ uen ábrázolhat´ o konstansok is, amik emiatt nagyobb és átláthatóság szempontjából rosszabb kimeneti f´ ajlt eredményeznek. • VHDL-r˝ ol a szintézerek ´ altalában EDIF (Electronic Design Interchange Format) form´ atumra ford´ıtanak, ´ıgy vizsgálat tárgyát képezheti az is, hogy a ford´ıtó kimenete esetleg a VHDL-t˝ ol alacsonyabb szint˝ u, FPGA közeli kódot jelentsen. • Elképzelhet˝ o lenne a list´ ak olyan kezelése, hogy a lista elmein végrehajtandó m˝ uveleteket el˝ ore megadott n szám´ u feldolgozóegység párhuzamosan végezze, ´ıgy a sebesség és az er˝ oforr´ ashasználat között az n értékének finomhangolásával tudnánk szab´ alyozni a szintézist. • Tervezem egy MicroBlaze lágymagos processzor alap´ u tesztrendszer elkész´ıtését, amellyel a ford´ıt´ oprogram kimeneteként létrejött VHDL kód valódi FPGA-s k¨ ornyezetben is egyszer˝ uen, akár automatikusan tesztelhet˝o lenne.

77

6. fejezet

¨ Osszefoglal´ as Dolgozatom sor´ an egy olyan m´ odszer alapelveit és megvalós´ıtását dolgoztam ki, amely a Haskell nyelven bizonyos megk¨ otésekkel le´ırt algoritmusokat VHDL le´ırássá alak´ıtja. Az eljárás minden lépésére (modulj´ ara) kidolgoztam algoritmusokat és azokat PC-n futó ford´ıtóprogramként implement´ altam is. A kidolgozand´ o m´ odszer és ford´ıt´ oprogram elé a következ˝o követelményeket támasztottam:

1. a Haskell forr´ ask´ od és VHDL le´ırás közötti ford´ıtás legyen teljesen automatikus 2. ford´ıtás sor´ an a felhaszn´ al´ o kapjon hiba¨ uzenetet, ha a forráskód szintaxisa nem megfelel˝o, vagy ha egy Haskell kifejezés a megkötések miatt nem használható 3. a program modul´ aris felép´ıtés˝ u legyen, hogy az egyes részek a jöv˝oben minden további nélk¨ ul u ´jrahaszn´ alhat´ oak legyenek 4. a jöv˝oben k¨ onnyen, teh´ at a f˝ obb modulok legfeljebb minimális módos´ıtása után implement´ alhat´ oak legyenek optimalizációs algoritmusok 5. a forrásk´ od megk¨ otéseit ne kelljen teljes egészében a fejlesztési periódus elején meghatározni, vagyis a haszn´ alhat´ o Haskell kifejezések lehet˝oleg a ford´ıtóprogram utólagos fejlesztése nélk¨ ul, dinamikusan b˝ ov´ıthet˝oek legyenek Az 1. és 3. k¨ ovetelmény a kidolgozott módszer és az ennek alapján elkész¨ ult moduláris felép´ıtés˝ u ford´ıt´ oprogram eredményeként teljes¨ ul. A szintaktikai hibákat a módszerbe beép´ıtett GHC frontend jelzi, ´ıgy a felhasználó azonnal értes¨ ul a forráskódi el´ırásokról vagy a hibás k´ odol´ asr´ ol. Amennyiben a szintaktikailag helyes forráskódban olyan f¨ uggvényt használunk, ami a ford´ıt´ oprogram aktuális m˝ uvelethalmazában nincs benne, szintén hibajelzést kapunk, ezzel teh´ at a 2. k¨ ovetelmény szintén teljes¨ ul. Köztes reprezentációként EOG-t haszn´ alok, ez´ altal optimaliz´ aci´ os algoritmusok beép´ıtését a módszer messzemen˝oen támogatja, ezzel teljes¨ ul a 4. k¨ ovetelmény. Az 5. követelmény a m˝ uvelethalmaz fogalmának bevezetésével teljes¨ ul. A rendszert modul´ aris elven ép´ıtettem fel, hogy az egyes részek k¨ ulön-k¨ ulön is minél általánosabban felhaszn´ alhat´ oak legyenek. A nyelvi vagy technológiai peremfeltételek módos´ıtása esetén csak az elj´ ar´ as egy-egy részét, az annak megfelel˝o modult kell módos´ıtanunk. 78

Amennyiben Haskell forr´ asnyelv helyett más funkcionális nyelvb˝ol szeretnénk kiindulni, akkor a GHC fokozat helyett egy arra specializált ford´ıtóprogramot kell kész´ıten¨ unk, ami a GHC Core nyelv˝ u k¨ oztes le´ır´ ast generálja. Ebb˝ol a le´ırásból az általam elkész´ıtett rendszer képes VHDL-t gener´ alni. FPGA helyett ASIC integrált áramkörök gyártására is van lehet˝oség, a kimenetként kapott VHDL ugyanis ASIC gyártás alapja lehet. A rendszer alkalmas optimaliz´ aló fokozat beép´ıtésére, ´ıgy pl. az IIT Tanszéken fejlesztett PIPE optimaliz´ al´ o rendszert a ford´ıtás részévé lehet tenni, ´ıgy pipeline algoritmusok esetén a hardver hatékonys´ aga nagymértékben javulhat. A rendszer rugalmass´ ag´ at nagyban növeli, hogy a m˝ uvelethalmaz dinamikusan b˝ov´ıthet˝o a ford´ıt´ oprogram fejlesztése nélk¨ ul is. A b˝ov´ıtéshez csupán arra van sz¨ ukség, hogy egy adott Haskell f¨ uggvényhez létrehozzunk egy VHDL modult, és a m˝ uvelethalmaz megfelel˝o fájljaiban ezt a f¨ uggvényt regisztráljuk. Egy megép´ıtett mp3 lejátszó VHDL modulj´ at import´ alva pl. egyetlen haskell f¨ uggvényh´ıvással akár egy mp3 lejátszás is ind´ıtható. A rendszer t´ amogatja a hierarchikus tervezést, tehát a magasszint˝ u nyelven kódoló felhasznál´ o (pl. matematikus vagy informatikus) és a hardvertervez˝o egymástól f¨ uggetlen¨ ul dolgozhat az adott problém´ an. A matematikus le´ırja a szoftvert, és amennyiben nem használ egyedi f¨ uggvényt, a k´ odja automatikusan ford´ıtható hardverre. Ha az algoritmusához k¨ ulönleges hardverre lenne sz¨ ukségel (pl. optimalizáció miatt), akkor a hardvertervez˝o ezzel párhuzamosan meg´ırhatja a sz¨ ukséges VHDL modult, és ennek végeztével a matematikus által le´ırt f¨ uggvény ezt a k´ odot fogja példányos´ıtani. A m´ odszert kiterjesztettem többsebesség˝ u adatfolyamok esetére. Ennek keretében kidolgoztam az EOG modell t¨ obbsebesség˝ u változatát, amire az MREOG nevet vezettem be. Algoritmust adtam az u ´jraind´ıtási- és lappangási id˝ok kiszám´ıtására, hogy azok az u ´j modellben is meghat´ arozhat´ oak legyenek. Egy PID szab´ alyz´ o algoritmuson és az MP3 dekódoló algoritmus részletén kereszt¨ ul bemutattam a ford´ıt´ as lépéseit és a lépések közötti köztes reprezentációkat, a ford´ıt´ oi cs˝ovezeték végén megkapott VHDL kódot pedig a Xilinx ISE FPGA fejleszt˝orendszerrel szimul´ altam.

79

Irodalomjegyz´ ek [1] http://www.mentor.com/esl/catapult/overview. [2] http://www.impulseaccelerated.com/. [3] http://www.c-to-verilog.com/index.html. [4] http://www.comlab.ox.ac.uk/geraint.jones/ruby/. [5] http://haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/ Prelude.html. [6] http://www.haskell.org/haskellwiki/Performance/GHC. [7] http://www.haskell.org/. [8] http://blog.bjrn.se/2008/10/lets-build-mp3-decoder.html. [9] Vhdl tutorial. http://www.seas.upenn.edu/~ese171/vhdl/vhdl_primer.html. [10] Peter Arato, Visegrady Tamas, and Istvan Jankovits. High Level Synthesis of Pipelined Datapaths. John Wiley & Sons, Inc., New York, NY, USA, 2001. [11] Zena M. Ariola and Matthias Felleisen. The call-by-need lambda calculus. J. Funct. Program., 7:265–301, May 1997. [12] C. P. R. Baaij. Cλash: From haskell to hardware. Master’s thesis, Univ. of Twente, December 2009. [13] Henk Barendregt and Erik Barendsen. Introduction to lambda calculus. 1994. [14] Csák Bence. K¨ ozvetlen hardver generálás magasszint˝ u nyelvi le´ırásból - phd értekezés, 2009. [15] Lauwereins R. Peperstraete J.A. Bilsen G., Engels M. Static scheduling of multi-rate and cyclo-static dsp-applications. VLSI Signal Processing, VII, 1994., 1994. [16] Per Bjesse, Koen Claessen, Mary Sheeran, and Satnam Singh. Lava: hardware design in haskell. SIGPLAN Not., 34:174–184, September 1998. [17] Joseph Buck and Edward A. Lee. The token flow model, 1992. 80

[18] Duncan Coutts, Roman Leshchinskiy, and Don Stewart. Stream fusion: From lists to streams to nothing at all. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP 2007, Apr 2007. [19] Simon Frankau. Hardware synthesis from a stream-processing functional language, 2004. [20] Shaori Guo and Wayne Luk. Compiling ruby into fpgas. In Proceedings of the 5th International Workshop on Field-Programmable Logic and Applications, FPL ’95, pages 188–197, London, UK, 1995. Springer-Verlag. [21] C. A. R. Hoare. Communicating sequential processes. Commun. ACM, 21:666–677, August 1978. [22] P. Z. Ingerman. Thunks: a way of compiling procedure statements with some comments on procedure declarations. Commun. ACM, 4:55–58, January 1961. [23] ISO/IEC. Ieee 1076-2008: Ieee standard vhdl language reference manual. Technical report, Institute of Electrical and Electronics Engineers, Computer Society, 26. January 2009. [24] M. Kooijman. Haskell as a higher order structural hardware description language, December 2009. [25] Chris Lattner. LLVM: An Infrastructure for Multi-Stage Optimization. Master’s thesis, Computer Science Dept., University of Illinois at Urbana-Champaign, Urbana, IL, Dec 2002. See http://llvm.cs.uiuc.edu. [26] E.A. Lee and D.G. Messerschmitt. Synchronous data flow. Proceedings of the IEEE, 75(9):1235–1245, Sept. 1987. [27] Edward Ashford Lee and David G. Messerschmitt. Static scheduling of synchronous data flow programs for digital signal processing. IEEE Trans. Comput., 36:24–35, January 1987. [28] Simon Marlow. Haskell 2010 language report, 2010. [29] Neil Mitchell. Rethinking supercompilation. SIGPLAN Not., 45:309–320, September 2010. [30] Simon Peyton Jones et al. The Haskell 98 language and libraries: The revised report. Journal of Functional Programming, 13(1):0–255, Jan 2003. http://www.haskell. org/definition/. [31] Simon Peyton Jones and Simon Marlow. Secrets of the glasgow haskell compiler inliner. J. Funct. Program., 12:393–434, July 2002. [32] Mary Sheeran. ufp, an algebraic vlsi design language - phd thesis, 1983. 81

[33] S. Sriram and S.S. Bhattacharyya. Embedded multiprocessors: scheduling and synchronization. Signal processing and communications. CRC Press, 2009. [34] The GHC Team. The glorious glasgow haskell compilation system user’s guide, version 6.12.2. [35] Andrew Tolmach. An external representation for the ghc core language, 2001. [36] Valentin F. Turchin. The concept of a supercompiler. ACM Trans. Program. Lang. Syst., 8:292–325, June 1986.

82

Fu ek ¨ ggel´ F.1. Stream m˝ uveletek VHDL k´ odja

entity sum i s generic ( c l : i n t e g e r port ( i n 1 : in s t d q : out s t d c1 : in s t d cq : out s t d c l k : in s t d end sum ;

; width : i n t e g e r ; d e l a y : i n t e g e r ) ; l o g i c v e c t o r ( ( width − 1 ) downto 0 ) ; l o g i c v e c t o r ( ( width − 1 ) downto 0 ) ; l o g i c v e c t o r ( c l downto 0 ) ; l o g i c v e c t o r ( ( c l − 1 ) downto 0 ) ; logic );

architecture B e h a v i o r a l of sum i s s i g n a l accum : s t d l o g i c v e c t o r ( ( width − 1 ) downto 0 ) := c o n v s t d l o g i c v e c t o r ( 0 , width ) ; s i g n a l dc : i n t e g e r := 0 ; s i g n a l c d e l a y : s t d l o g i c v e c t o r ( ( c l − 1 ) downto 0 ) ; begin process ( c l k ) begin i f ( r i s i n g e d g e ( c l k ) ) then i f ( c1 ( 1 ) = ’ 1 ’ ) then dc <= 0 ; c d e l a y <= c1 ( c l downto 1 ) ; else dc <= dc +1; end i f ; i f ( dc=d e l a y −1) then q <= accum ; cq <= c d e l a y ; else cq <= c o n v s t d l o g i c v e c t o r ( 0 , c l ) ; end i f ; i f ( c1 ( 1 ) = ’ 1 ’ ) then accum <= i n 1 ; e l s i f ( c1 ( 0 ) = ’ 1 ’ ) then accum <= accum+i n 1 ; end i f ; end i f ; end process ; end B e h a v i o r a l ;

F.1.1. ´ abra. Sum m˝uvelet VHDL modulja

83

entity enumfromto i s generic ( c l : i n t e g e r port ( i n 1 : in s t d i n 2 : in s t d q : out s t d c1 : in s t d c2 : in s t d cq : out s t d c l k : in s t d end enumfromto ;

; width : i n t e g e r ; r a t e : i n t e g e r ; d e l a y : i n t e g e r ) ; l o g i c v e c t o r ( ( width − 1 ) downto 0 ) ; l o g i c v e c t o r ( ( width − 1 ) downto 0 ) ; l o g i c v e c t o r ( ( width − 1 ) downto 0 ) ; l o g i c v e c t o r ( ( c l − 1 ) downto 0 ) ; l o g i c v e c t o r ( ( c l − 1 ) downto 0 ) ; l o g i c v e c t o r ( c l downto 0 ) ; logic );

architecture B e h a v i o r a l of enumfromto i s signal signal signal signal

dc : rc : cqh : qc :

i n t e g e r := 0 ; i n t e g e r := r a t e ; s t d l o g i c v e c t o r ( ( c l − 1 ) downto 0 ) ; s t d l o g i c v e c t o r ( ( width − 1 ) downto 0 ) ;

begin cqh <= c1 and c2 ; q <= qc ; process ( c l k ) begin i f ( r i s i n g e d g e ( c l k ) ) then cq ( c l downto 1 ) <= cqh ; i f ( cqh ( 0 ) = ’ 1 ’ ) then dc <= 0 ; r c <= 0 ; cq ( 0 ) <= ’ 1 ’ ; qc <= i n 1 ; else i f ( dc>=d e l a y −1) then dc <= 0 ; i f ( r c=r a t e −1) then cq ( 0 ) <= ’ 0 ’ ; qc <= qc ; e l s i f ( rc>r a t e −1) then cq ( 0 ) <= ’ 0 ’ ; qc <= qc ; else cq ( 0 ) <= ’ 1 ’ ; qc <= qc +1; end i f ; r c <= r c +1; else dc <= dc +1; cq ( 0 ) <= ’ 0 ’ ; qc <= qc ; end i f ; end i f ; end i f ; end process ; end B e h a v i o r a l ;

F.1.2. ´ abra. EnumFromTo m˝uvelet VHDL modulja

84

F.2. T¨ omb m˝ uveletek VHDL k´ odja

entity nth i s generic ( c l : i n t e g e r ; width : i n t e g e r ) ; port ( blockram : inout s t d l o g i c v e c t o r ( ( width − 1 ) downto 0 ) ; i n 2 : in s t d l o g i c v e c t o r ( ( width − 1 ) downto 0 ) ; q : out s t d l o g i c v e c t o r ( ( width − 1 ) downto 0 ) ; oe : out s t d l o g i c ; c2 : in s t d l o g i c v e c t o r ( c l downto 0 ) ; cq : out s t d l o g i c v e c t o r ( c l downto 0 ) ; c l k : in s t d l o g i c ) ; end nth ; architecture B e h a v i o r a l of nth i s s i g n a l c b u f : s t d l o g i c v e c t o r ( c l downto 0 ) ; begin p r o c e s s 1 : process ( c l k ) begin i f ( f a l l i n g e d g e ( c l k ) ) then i f ( c2 ( 0 ) = ’ 1 ’ ) then oe <= ’ 0 ’ ; blockram <= i n 2 ; else oe <= ’ 1 ’ ; blockram <= ( others => ’ Z ’ ) ; −− r e g e x m i a t t TODO end i f ; end i f ; i f ( r i s i n g e d g e ( c l k ) ) then c b u f <= c2 ; cq <= c b u f ; i f ( c b u f ( 0 ) = ’ 1 ’ ) then q <= blockram ; end i f ; end i f ; end process ; end B e h a v i o r a l ;

F.2.1. ´ abra. Nth m˝uvelet VHDL modulja

85

entity s y n t h a r r a y i s generic ( c l : i n t e g e r ; width : i n t e g e r ) ; port ( q : inout s t d l o g i c v e c t o r ( ( width − 1 ) downto 0 ) ; oe : in s t d l o g i c ; c l k : in s t d l o g i c ) ; end s y n t h a r r a y ; architecture B e h a v i o r a l of s y n t h a r r a y i s s i g n a l temp : s t d l o g i c v e c t o r ( 3 downto 0 ) ; s i g n a l output : s t d l o g i c v e c t o r ( 3 1 downto 0 ) ; s i g n a l a d d r e s s : s t d l o g i c v e c t o r ( 3 1 downto 0 ) ; begin process ( oe , q ) −− output nem v o l t begin i f ( oe = ’ 0 ’ ) then q <= ”ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ” ; a d d r e s s <= q ; else q <= output ; a d d r e s s <= a d d r e s s ; end i f ; end process ; RAMB16 S36 inst : RAMB16 S36 generic map ( INIT => X ”000000000 ” , −− Value o f output RAM r e g i s t e r s a t s t a r t u p SRVAL => X ”000000000 ” , −− Ouput v a l u e upon SSR a s s e r t i o n WRITE MODE => ”WRITE FIRST ” , −− WRITE FIRST , READ FIRST o r NO CHANGE −− The f o l l o w i n g INIT xx d e c l a r a t i o n s s p e c i f y t h e i n i t i a l −− c o n t e n t s o f t h e RAM INIT 00 => INIT 01 => −− . . . −− t o v a b a i −− . . . INIT 3e => I N I T 3 f =>

X ”0000000 a00000009000000080000000700000006000000050000000400000003 ” , X ”0000001200000011000000100000000 f0000000e0000000d0000000c0000000b ” , kezdoertekek X ”000001 fa000001f9000001f8000001f7000001f6000001f5000001f4000001f3 ” , X ”000002020000020100000200000001 ff000001fe000001fd000001fc000001fb ” ,

port map ( DO => output , ADDR => a d d r e s s ( 8 downto 0 ) , CLK => c l k , DI => c o n v s t d l o g i c v e c t o r ( 0 , 3 2 ) , DIP => c o n v s t d l o g i c v e c t o r ( 0 , 4 ) , EN => ’ 1 ’ , SSR => ’ 0 ’ , WE => ’ 0 ’ );

−− −− −− −− −− −− −− −−

32− b i t Data Output 9− b i t Address Input Clock 32− b i t Data Input 4− b i t p a r i t y Input RAM Enable Input Synchronous S e t / Re s e t Input Write Enable Input

end B e h a v i o r a l ;

F.2.2. ´ abra. A block RAM egy lehetséges VHDL kódja (ListArray m˝uvelet)

86

F.3. Az Haskell nyelven implement´ alt szint´ ezis program ford´ıt´ oi napl´ oja GHCi, version 7.0.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Loading package array-0.3.0.2 ... linking ... done. Loading package containers-0.4.0.0 ... linking ... done. Loading package bytestring-0.9.1.10 ... linking ... done. Loading package Win32-2.2.0.1 ... linking ... done. Loading package filepath-1.2.0.0 ... linking ... done. Loading package old-locale-1.0.0.2 ... linking ... done. Loading package old-time-1.0.0.6 ... linking ... done. Loading package directory-1.1.0.0 ... linking ... done. Loading package pretty-1.0.1.2 ... linking ... done. Loading package process-1.0.1.5 ... linking ... done. Loading package Cabal-1.10.1.0 ... linking ... done. Loading package ghc-binary-0.5.0.2 ... linking ... done. Loading package bin-package-db-0.0.0.0 ... linking ... done. Loading package hpc-0.5.0.6 ... linking ... done. Loading package template-haskell ... linking ... done. Loading package ghc-7.0.3 ... linking ... done. Loading package ffi-1.0 ... linking ... done. [ 1 of 14] Compiling CoreVisiting ( CoreVisiting.hs, interpreted ) [ 2 of 14] Compiling DotOutput ( DotOutput.hs, interpreted ) [ 3 of 14] Compiling Typconv ( Typconv.hs, interpreted ) [ 4 of 14] Compiling CorePrint ( CorePrint.hs, interpreted ) [ 5 of 14] Compiling Common ( Common.hs, interpreted ) [ 6 of 14] Compiling SearchCoreNode ( SearchCoreNode.hs, interpreted) [ 7 of 14] Compiling VarRename ( VarRename.hs, interpreted ) [ 8 of 14] Compiling AppRename ( AppRename.hs, interpreted ) [ 9 of 14] Compiling MapConversion ( MapConversion.hs, interpreted ) [10 of 14] Compiling IterateConversion( IterateConversion.hs, interpre [11 of 14] Compiling CaseReduction ( CaseReduction.hs, interpreted ) [12 of 14] Compiling SimplCore ( SimplCore.hs, interpreted ) [13 of 14] Compiling Flpc ( Flpc.hs, interpreted ) [14 of 14] Compiling Main ( Main.hs, interpreted ) Ok, modules loaded: SimplCore, Main, Flpc, CaseReduction, IterateConversion, MapConversion, AppRename, VarRename, Common, CorePrint, Typconv, DotOutput, SearchCoreNode, CoreVisiting. *Main> Loading package transformers-0.2.2.0 ... linking ... done. Loading package mtl-2.0.1.0 ... linking ... done. Loading package regex-base-0.93.2 ... linking ... done. Loading package regex-posix-0.94.4 ... linking ... done. Loading package regex-compat-0.93.1 ... linking ... done. Loading package time-1.2.0.3 ... linking ... done. Loading package random-1.0.0.3 ... linking ... done. Loading package haskell98-1.1.0.1 ... linking ... done. Loading package ghc-paths-0.1.0.8 ... linking ... done. Loading package HUnit-1.2.2.3 ... linking ... done. Loading package parsec-3.1.1 ... linking ... done. Loading package network-2.3.0.2 ... linking ... done. Loading package hslogger-1.1.5 ... linking ... done. Loading package MissingH-1.1.0.3 ... linking ... done.

87

T´ argymutat´ o α-konverzió, 9

GenerateVHDL, 44

β-redukció, 9

globális azonos´ıtó, 38

η-konverzió, 9

gyors´ıtó, 53

uggvény, 22 összetett f¨ u ´jraind´ıtási id˝ o, 51

IterateConversion, 36

adatfolyamok, 22 alkalmazás, 9

kötött/szabad változó, 9 kicsomagolja, 14

AppRename, 36

lambda lifting, 9

argumentum azonos´ıt´ o, 39

lambda-absztrakció, 9

AST, 12

lambda-kifejezés, 9

backend, 30 becsomagolja, 14 behelyettes´ıtés, 15 blokk, 49 blokk sajátfrekvenci´ aja, 49 boxing, 14 CλasH, 6 call-by-name, 10 call-by-need, 10 call-by-reference, 10 call-by-value, 10 CaseReduction, 32

lappangási id˝o, 51 lass´ıtó, 53 latency, 23 lokális azonos´ıtó, 38 lusta kiértékelés˝ u (lazy evaluation), 8 m˝ uveletei, 22 m˝ uvelethalmaz, 20 MakeModuleList, 43 MapConversion, 56 mintaillesztések, 32 MREOG, 49 OpTree, 37

CoreToTree, 37 csomagolt, 14

ParseEOG, 43

csupasz, 14

polimorf t´ıpusok, 8 ProduceComponents, 43

egysebesség˝ u, 20

ProduceOperations, 44

elágazások, 32

ProduceSignals, 43

elemi f¨ uggvény, 22 EOG, 20

saját m˝ uveletei, 49

er˝osen t´ıpusos, 8

scrutinee, 13 SDF, 20

f¨ uggvény, 9

stream, 53

frontend, 30

strukturális, 17 88

supercompiling, 37 többsebesség˝ u, 48 t´ıpusalternat´ıv´ akat, 11 t´ıpusalternat´ıv´ aval, 24 t´ıpusoszt´ aly, 11 tisztán funkcion´ alis (pure functional), 8 TreeSimplifier, 41 unboxing, 14 változó, 9 viselkedési, 17

89

Új módszer algoritmusok VHDL-be funkcionális nyelvből kiindulva

Recommend Documents