UNIVERZITET "Sv. Kiril i Metodij"

Prirodno matemati~ki Fakultet - Skopje

Institut za Informatika

 

SEMINARSKA RABOTA

Superskalarni i VLIW procesori

 

Predmet: Kompjuterski sistemi

 

Izrabotil: Boris Volkan

Mentor: d-r Marjan Gu{ev

 

Skopje, septemvri 1997

REZIME

RISC procesorite koristat preklopuvawe na fazite pri izvr{uvaweto na instrukciite: ~itawe (instruction fetch), dekodirawe (decode), izvr{uvawe (execution) i zapi{uvawe na rezultatot (result write - back) so cel de se izvede edna instrukcija za ciklus. Glavnoto ograni~uvawe za izvr{uvawe na pove}e instrukcii vo eden ciklus se instrukciskite zavisnosti. Drugi ograni~uvawa se nametnati od hardverot ili kompajlerot, vklu~uvaj}i gi i preimenuvawata na registrite, limiti vo brojot na funkciski edinici, kako i instrukciskiot i podato~niot propusen opseg (bandwidth) vo procesorot.

Superskalarniot procesor e edno pribli`uvawe za izvr{uvawe na pove}e od edna instrukcija za ciklus. Ovie procesori mo`at da izvr{at dve ili pove}e instrukcii paralelno. Ovoj dobar stepen na paralelizam ~esto e nare~en instrukcisko nivo na paralelizam. Hardverot se koristi za pronao|awe na nezavisnite instrukcii i nivno paralelno izvr{uvawe, ~esto koristej}i tehniki razvivani za prvite superkompjuteri kako Cray-1 i IBM 360/model 91. Superskalarnite procesori do`iveaja komercijalen uspeh so Intel Pentium, DEC Alpha 21064, Motorola 88110, IBM POWER 1 (RS/6000).

Alternativen metod za ispituvawe na instrukciskoto nivo na paralelizam e direktna ekstenzija na mikrokodnata kompaktnost. Ovie arhitekturi koristat agresivni kompajleri za rasporeduvawe na mnogukratnite operacii vo golem instrukciski zbor (very long instruction word). Celta na hardverot e da postigne eden VLIW za eden ciklus. Nao|aweto na vakvite mnogukratni operacii celosno mu se prepu{ta na kompajlerot. Primarnata nadmo} na VLIW procesorite nad superskalarnite procesori e sumata na paralelizmi koi tie gi detektiraat. Hardverskata baza na superskaranite procesori mora vo prelet (on-the-fly) da gi detektira paralelnite instrukcii koristej}i limitirana golemina na hardverskiot prozorec. Za VLIW procesorite ovaa detekcija se vr{i pred izvr{uvaweto (run time) od strana na kompajlerot. Za razlika od superskalarnite procesori koi na{le golema komercijalna primena, VLIW procesorite se so kratok komercijalen spisok na proizvoditeli, toa se samo Multiflow TRACE i Cydrome Cydra-5.

 

SODR@INA

1 SUPERSKALARNI PROCESORI

 

  1. PREZEMAWE INSTRUKCII
  2. SOFTVERSKO PREDVIDUVAWE NA GRANKITE
  3. HARDVERSKO PREDVIDUVAWE NA GRANKITE
  4. PROSLEDUVAWE I RASPOREDUVAWE
  5. EDNOSTAVNO BLOKIRAWE
  6. TOMASULO ALGORITAM
  7. IZVR[UVAWE
  8. EDINICA ZA A@URIRAWE
  9. ZAKLU^OK

2 VLIW PROCESORI

  1. KOMPAJLERSKO GLEDI[TE NA PROGRAMATA
  2. RASPOREDUVAWE [TO SE ZASNOVA NA KOMPAJLEROT
  3. ACIKLI^NO RASPOREDUVAWE
  4. CIKLI^NO RASPOREDUVAWE
  5. KOMPATIBILNOST ME\U GENERACIITE

3 SUPERSKALAR ILI VLIW?

1 SUPERSKALARNI PROCESORI

Arhitekturata na superskalaren procesor e prestaven na slika 1. Instrukciskata i podato~nata ke{ memorija (cache) se prestaveni kako I-cache i D-cache soodvetno. Superskalarniot procesor se sostoi od {est delovi, i toa: ~itawe na instrukcii (instruction fetch), dekodirawe (decode), prosleduvawe (dispatch), rasporeduvawe (scheduling), izvr{uvawe (execution) i a`urirana sostojba (state update). Delot za ~itawe na instrukcii ja izdvojuva aktivnata instrukcija od instrukciskata hierarhiska memorija preku instrukciskata ke{ memorija.

Slika 1: Arhitektura na superskalaren procesor

Ovoj del isto taka odr`uva nekoi RS vrednosti i vr{i manipulirawe so instrukciskite granki. Delot za dekodirawe go vr{i kodiraweto na instrukcijata. Pove}eto komercijalni superskalari kodiraat so fiksna dol`ina na instrukcijata, no toa ne e slu~aj so intelovata serija h86 i digitalovite VAX arhitekturi.

Delovite za prosleduvawe i rasporeduvawe zaedno se odnesuvaat kako kontroleri za soobra}ajot kaj superskalarinite procesori. I dvata dela sodr`at redici od instrukcii. Redicite vo delot za rasporeduvawe ~esto se podeleni vo vlezovi za funkciskite delovi od izvr{uva~kata edinica. vlezovite se nare~eni stanici za anga`irawe (reservation station). Stanicite za anga`irawe se pojavuvaat kako virtuelni funkcionalni edinici na dispe~erot. Dvete redici se prika`ani na slika 2. Ovie redici se spojuvaat vo edna za nekoi modeli na superskalarnite procesori. Vo dodatok na svojata redica dispe~erskata edinica isto taka sodr`i i lista od slobodni funkcionalni edinici nare~eni tabela za rezultati (score board). Tabelata za rezultati se koristi za sledewe na statusot na rasporeduva~kata redica. Dispe~erot gi prenesuva instrukciite od svojata redica i gi ~ita nivnite izvorni operandi, potoa gi smestuva vo redicite na rasporeduva~kite edinici, vo zavisnost od statusot na tabelata za rezultati. Koga instrukcijata }e napravi vakva tranzicija se veli deka e izdadena (issued). Edna{ vo ciklusot rasporeduva~kata edinica ja proveruva sekoja instrukcija vo svojata redica za zavisnosta, potoa po~nuva da izvr{uva instrukcii vo soodvetni funkcionalni edinici. Koga instrukcijata }e ja napu{ti rasporeduva~kata edinica se veli deka e istrelana (fired).

Slika 2: Rasporeduva~ki i prosleduva~ki redici

Izvr{nata edinica (execution unit) se sostoi od mno`estvo od funkcionalni edinici. Primer za vakvi edinici se edinici za celobrojna aritmetika, edinica za sobirawe i mno`ewe na realni broeni i edinica za pristap na podatoci vo memorijata. Sekoja edinica mo`e da bide realizirana proto~no (pipelined) vo pove}e nivoa. Koga instrukcijata }e se izvr{i velime deka e izvr{ena (completed). Koga instrukciite se izvr{eni, nivnite rezultati se vpi{uvaat preku edinicata za a`urirawe (state update unit) za da bidat upotrebeni od instrukciite koi ~ekaat vo prozorecot na rasporeduva~kata edinica. Nekoi superskalarni modeli ovozmo`uvaat neredosledno izvr{uvawe na instrukciite. Ova go ote`nuva re{avaweto na softverskite i hardverskite prekini. Re{avaweto na ovoj problem mo`e da ja promeni funkcijata na edinicata za a`urirawe taka {to taa nema da zapi{uva rezultati vo mno`estvoto registri (register file), tuku upotrebuva dopolnitelni hardverski baferi ili gi udvojuva registrite za da ja zadr`i momentalnata sostojba na. Instrukciite pred da go napu{tat procesorot zapi{uvaat vo registerot za da ja zapamtat momentalnata sostojba. Ovoj posleden ~ekor vo izvr{uvaweto na instrukciite se narekuva penzionirawe ili povlekuvawe (retiring).

Merata naj~esto koristena za merewe na superskalarnite performansi e IPC (broj na instrukcii penzionirani za eden ciklus). IPC e ograni~en so emituva~kata stapka (issue rate) na procesorot, zatoa {to globalnata stapka (overall rate) na instrukciite koi go napu{taat procesorot nemo`e da bide pogolema od stapkata na onie koi vleguvaat vo nego. Stapkata na emitirani instrukcii e kriti~en parametar za superskalarinite procesori. Tipi~na emituva~ka stapka se protega od edna instrukcija vo ciklus za tradicionalni arhitekturi, do ~etri ili {est instrukcii vo ciklus za Power PC 604 i Power2 arhitekturite. Interesno e da se napomene deka IPC e recipro~en so CPI (ciklusi vo instrukcija), koja e tradicionalna merka za ednoemituva~kite procesori. Ottamu, IPC=3 e ekvivalentno so CPI=0.33(3).

Glavnite aspekti na modelot na sekoja od {este edinici se prezentirani vo prodol`enie so objasnuvawe na site razmeni koi se vklu~ni vo slika 2.

1.1 PREZEMAWE INSTRUKCII (INSTRUCTION FETCH)

Edinicata za prezemawe instrukcii mora za sekoj ciklus da ja predvidi slednata instrukcija instrukciskata ke{ memorija (I-cache), ~esto desetina ciklusi pred kompletiraweto na uslovnite granki. So prose~no 4-6 instrukcii me|u instrukciite za granewe i vi{ok od 4 emisioni stapki vo ciklus, metodite za predviduvawe i re{avawe na instrukciite za granewe se kriti~ni za superskalarnite procesori.

Razre{uvaweto na grankite e mnogu razgleduvan problem. Na primer, pristapuvaweto kon instrukciskata ke{ memorija ne e momentalno. Duri i koga ima direkten pogodok vo ke{ memorijata voobi~aeno se potrebni dva ciklusi za da se dobijat sodr`inite od instrukciskata adresa. Edinicata za prezemawe instrukcii mora da planira odnapred. Slednata instrukcija koja pristapuva do programata obi~no se nao|a vo slednata sekvencionalna lokacija od memorijata do postojnata instrukcija. Edinicata za prezemawe instrukcii mo`e da go koristi ova pravilo za da pomogne da se nadmine latentnosta na instrukciskata ke{ memorija. Instrukciite za granewe se zabele`itelen isklu~ok od ova pravilo. Grankite se pojavuvaat relativno ~esto, naj~esto sekoj 4-6 instrukcii. Inteligentnata edinica za prezemawe instrukcii mora da predvidi:

1. deka adresata sodr`i granka pred da se dekodira;

2. kade vo memorijata upatuvaat tranziciite na grankite;

3. vo slu~aj na uslovni granki dali grankata }e bide zemena koga uslovot }e bide procenet.

Re{avaweto na grankite vklu~uva upotreba na softver ili hardver za da se predvidi odnesuvaweto na grankata. Superskalarnite procesori so visoka emituva~ka stapka postavuvaat golemi barawa na hardverot za prezemawe na instrukcii. Ova zna~i deka visokata preciznost vo predviduvaweto na grankite mora da bide poddr`ana od hardverot. Predviduvaweto na grankite ovozmo`uva upotreba na {pekulacija (speculation): izvr{uvawe na instrukcijata na odrednicata na grankata pred da se znae vistinskoto odnesuvawe na grankata. Na {pekulacijata i e potrebno poddr`uvawe od hardverot (poto~no, poddr`uvawe od edinicata za a`urirawe). [pekulacijata mo`e da dostigne mnogu pogolem stepen na paralelizam (pogolem IPC), koe rezultira so pobrzo izvr{uvawe na programot.

1.2 SOFTVERSKO PREDVIDUVAWE NA GRANKITE (SOFTWARE BRANCH PREDICTION)

Softverskite pristapi se potpiraat na kompajlerot za da go predvidat odnesuvaweto na grankata. Ova potoa se {ifrira vo rezerviran bit vo instrukciskiot format, nare~en verojaten bit (likely-bit). Ovoj bit e obi~no prisuten vo site formati, ne samo vo razgranuva~kite instrukcii. Ako bitot e postaven na 1, se pretpostavuva deka instrukcijata e granka koja najposle }e bide zemena. Kaj bezuslovnite granki ovoj bit e sekoga{ postaven na 1.

Kompajlerot mo`e da upotrebi dve osnovni tehniki za postavuvawe na 1 na verojatniot bit. Ednata tehnika izvr{uva analiza na izvorot na programata i odlu~uva dali grankata }e bide zemena ili ne. Na primar, grankata koristena za obi~ni jazolni sintezi, kako for/DO jamki, najverojatno }e bidat zemeni koga }e se sretnat, zatoa {to skoro site jamki se izvr{uvaat za pove}e od edna iteracija. Ovoj stati~en pristap za predviduvawe na grankite strada od relativno niska preciznost (otprilika 60-80 procenti za nenumeri~ki programi).

Osven stati~koto predviduvawe na grankite od kompajlerot postoi i profilirano predviduvawe na grankite (prefiled branch prediction). Vo ovoj pristap, programot se pu{ta nekolku pati, so koristewe mo`ebi na razli~ni programski vlezni podatoci. Odnesuvaweto na sekoja granka se snima vo tekot na ovie testovi. Ovie informacii gi koristi kompajlerot za da ja rekompajlira programata i da ja predvidi nasokata na sekoja granka. Ovoj pristap dostignuva preciznost sporedliva so mnogu hardverski {emi.

1.3 HARDVERSKO PREDVIDUVAWE NA GRANKITE (HARDWARE BRANCH PREDICTION)

Hardverskite {emi za predviduvawe na grankite gi koristat prethodnite izvr{uvawa na razgranuva~kite instrukcii za da go predvidat nivnoto idno izvr{uvawe. Ovaa informacija obi~no se ~uva vo baferot za istorijat na grankata (branch history buffer), koj vsu{nost e specijalizirana ke{ memorija indeksirana so koristewe na adresata na grankata. Postojat dve klasi na vakvi baferi: ednoslojni (one-level) i dvoslojni (two-level) baferi. Ednoslojniot bafer ja koristi adresata na razgranuva~kata instrukcija za indeksirawe vo baferot na odredi{teto na grankata (branch target buffer-BTB), koj sodr`i mal kone~en avtomat za predviduvawe na rezultatot od grankata. Nominalnata golemina na ednoslojniot bafer za predviduvawe na grankite e me|u 256 i 1024 vleza. Koga grankata }e go zavr{i izvr{uvaweto, rezultatot se koristi za a`urirawe na kone~niot avtomat. Slika 3 go opi{uva ovoj proces. Naj~estiot kone~en avtomat za ednoslojni {emi e dvobitniot broja~ za predviduvawe. Predviduva~koto informacisko pole za sekoj vlez vo BTB e {irok 2 bita. Ovie bitovi se koristat za implementacija na ~etiripozicioniot predviduva~ki broja~ (prediction counter), prika`an na slika 4. Sekojpat koga se zema granka, soodvetnata suma vo svojot VTV vlez se zgolemuva za 1. Obratno, za nezemenite granki, sumata se namaluva za 1. Broja~ot se zasituva na 0(002) i 3(112). Predviduvaweto na granka se pravi vo zavisnost od vrednosta na broja~ot. Sumite 002 i 012 se predvideni kako ne zemeni, a 102 i 112 kako zemeni. Ovoj mehanizam mo`e lesno da se realizira so koristewe na najzna~ajniot bit (v1) na broja~ot kako predviduva~ki bit.

Slika 3: Ednosloen bafer za predviduvawe na grankite

Dvobitniot broja~ za predviduvawe e mnogu koristen zaradi svoite visoki performansi so skromna hardverska kompleksnost (empiriska preciznost e obi~no 85-90 procenti). Prednosta na ovaa niska kompleksnost e ednociklusnata ili potencijalna subciklusna predviduva~ka latentnost. Predviduva~ot e implementiran vo nekolku procesori, vklu~uvaj}i go i Intel Pentium i Power PC 604. Vo prosek, dvobitniot broja~ e precizen kako softverski baziraniot profiliraniot predviduva~ na grankite.

Slika 4: ^etiripozicionen predviduva~ki broja~

Dvoslojnite {emi koristat dva izdvoeni baferi. Prviot e ozna~en sli~no kako VTV i go ~uva istorijatot na grankata kako binaren string. Vtoriot e ozna~en so koristewe na ovoj istorijat na grankata i ja ~uva polo`bata na predviduva~ot. Ova e opi{ano na slika 5. Avtori na ovoj algoritam se Yeh i Patt. Baferot od prviot sloj se narekuva register za istorijat na tabelata (history register table-HRT). HRT e dolg v bita i skladira sekvencionalen binaren string na istorijatot na grankata, koristej}i 0 za nezemenite i 1 za zemenite granki. Predviduvaweto se pravi so indeksirawe vo HRT, a potoa se koristi stringot na istorijatot za indeksirawe vo vtorata tabela, tabelata na patekite (pattern table-PT). RT ja skladira sostojbata na maliot kone~en avtomat koj se koristi za predviduvawe na grankata. Ova gi razdvojuva predviduvaweto na grankata od adresata na razgranuva~kata instrukcija. Efektot od ova razdvojuvawe e dramati~en. Jehoviot algoritam mo`e da postigne 96% preciznost na predviduvawe na grankata za SPEC92 benchmarks.

Slika 5: Jehov algoritam za predviduvawe na grankite

1.4 PROSLEDUVAWE I RASPOREDUVAWE

Idealno, procesor so mo`nost da izveduva N instrukcii vo ciklus bi trebalo da postigne IPC od N. Odnosno bi trebalo da mo`e da povlekuva N instrukcii vo ciklus. Vo praksa, ova e ograni~eno od zavisnosta me|u instrukciite i dostapnite resursi koi gi ovozmo`uva hardverot. Za da se vidi ova neophodno e dopolnitelno objasnenie za ovaa zavisnost. Tabelata 1 gi prika`uva trite klasi na mo`ni zavisnosti. Momentni zavisnosti (flow-dependencies) nastanuvaat koga registarot e zapi{an od edna instrukcija a pro~itan od druga instrukcija(na pr.R1 me|u instrukciite I1 i I2). Anti zavisnosta (anti-dependence) se javuvaat koga registarot e zapi{an otkako e pro~itan, spre~uvaj}i neredosledno izvr{uvawe na instrukciite ( na pr. R2 me|u I3 i I4). Izleznata zavisnost (output dependance) e sli~na so antizavisnosta i se javuva koga dve ili pove}e instrukcii se zapi{uvaat vo ist registar, isto spre~uvaj}i neredosledno izvr{uvawe (R1 me|u I5 i I6).

 

Tabela 1: Trite klasi na mo`ni zavisnosti me|u instrukciite

Postojat nekolku {emi za dinami~no koristewe na paralelizmot na instrukciskite sloevi. Trite naj~esto implementirani {emi se: ednostavno blokirawe, CDC 6600, i Tomasulo algoritmot.

Ovie {emi mo`at da se klasificiraat spored nivnata sposobnost da gi rasporeduvaat nerasporedenite instrukcii bez ogled na zavisnostite. Ovaa sposobnost se narekuva re{ava~ki zavisnosti (resolving dependencies). Tabelata 2 ja prika`uva sposobnosta na trite {emi za re{avawe na zavisnostite. Se zabele`uva deka nekoi {emi (Tomasulo i CDC 6600) mo`at da re{avaat izlezni zavisnosti, dodeka pak nitu edna {ema ne mo`e da rasporeduva instrukcii okolu momentnite zavisnosti. Od tie pri~ini, momentnite zavisnosti ponekoga{ se narekuvaat ~isti zavisnosti (pure-dependencies). Sleduvaat opisi na algoritmot za ednostavnoto blokirawe i Tomasulo algoritmot.

Tabela 2: Sposobnost na trite {emi za re{avawe na zavisnostite

Vo diskusiite koi sleduvaat, {ifruvanata sekvenca na slika 6 se koristi kako izvr{uvawe na primerokot. Izvr{nata edinica pretpostavuva deka ima edna operacija za sobirawe/odzemawe so broj so podvi`na zapirka i edna operacija na mno`ewe so broj so podvi`na zapirka. Operacijata za mno`ewe se preklopuva vo dve fazi, {to zna~i deka mo`e da zapo~ne so izvr{uvawe na nova instrukcija vo sekoj ciklus, no potrebni se dva ciklusa za kompletirawe na mno`eweto. Isto taka se pretpostavuva deka emisionata stapka }e bide dve instrukcii vo ciklus.

Slika 6: [ifruvanata sekvenca {to se koristi za izvr{uvawe na primeri

 

Diskusijata isto taka go prestavuva algoritmot za ednostavno blokirawe formatiran vo pseudokod. Tabela 3 ja objasnuva nomenklaturata koja se koristi vo algoritmot.

Tabela 3: Nomenklaturata koristena vo pasporeduva~ko/prosleduva~kiot algoritmot

1.5 EDNOSTAVNO BLOKIRAWE

Ednostavnoto blokirawe go zapira istreluvaweto koga }e se pojavi zavisnost. Za da go napravi ova, toa mora da gi pronajde zavisnostite vo dinami~niot protok na instrukcii. Ova se pravi so dodavawe na bit za zafatenost (busy bit) na sekoe zapi{uvawe vo registerot mno`estvoto registri. (Modificiranoto mno`estvo registri ponekoga{ se narekuva i registerska tabela na rezultati (register score board), iako op{toprifaten e terminot tabela za rezultati za ozna~uvawe na informacijata na statusot na funkciskata edinica.) Semantikata na algoritmot za ednostavno blokirawe e prika`ana na slika 7. Ako funkciskata edinica e nepreklonena (se koristi za pove}ekratni ciklusi), algoritmot mora da go zeme predvid koga instrukcijata e zavr{ena. Prosleduva~kite i rasporeduva~kite sostojbi se esencijamlni integrirani so ovoj algoritam. Kombiniranata prosleduva~ko/rasporeduva~ka redica se realizira kako FIFO strukrura.

Slika 7: Semantika na algoritmot za ednostavno blokirawe

Primer za algoritmot za ednostavno blokirawe e prika`an na slika 8. Statusot na bitot za zafatenost vo mno`estvoto na registri e prestaven so koristewe na imeto na instrukcijata predizvikuvaj}i sostojba na zafatenost. Tabelata za rezultati ne e eksplicitno prezentirana vo primerot. Emisionata stapka se pretpostavuva deka e dve instrukcii vo ciklus.

Slika 8: Primer za algoritmot za ednostavno blokirawe

Nedostatocite na algoritmot za ednostavno blokirawe se javuvaat za sekvenci na instrukcii koi sodr`at zavisni instrukcii prosledeni so nezavisni instrukcii. Vo vakvi slu~ai, slednata grupa instrukcii mora da ~eka da se istrela duri i koga nema zavisnosti ili konflikti vo izvorite koi bi go spre~ile istreluvaweto. Na ovoj na~in, algoritmot za ednostavno blokirawe primenuva redosledno istreluvawe na instrukciite (in-order firing policy): instrukciite mora da se istreluvaat vo sekvencionalen (programski) redosled. Odkako instrukciite }e bidat istrelani, tie sepak mo`at da bidat izvr{eni neredosledno.

Prvenstvena prednost na algoritmot za ednostavno blokirawe e negovata ednostavnost. Baranata kontrolna logika e nekomplicirana. Dodatocite na mno`estvoto registri i vo tabelata za rezultati pravat mal hardverski tro{ok.

1.6 TOMASULO ALGORITAM

Primerot na slika 8 otkriva nekolku problemi vo algoritmot za ednostavno blokirawe. Programski definiranata zada~a na registerot se me{a so paralelnoto izvr{uvawe, a redoslednoto istreluvawe ne go koristi potencijalot na paralelizmot. Re{enieto e da se razdvojat programskite vrednosti od registerot na imiwa. Ova se narekuva registersko preimenuvawe (register renaming). Hardverskiot algoritam za registersko preimenuvawe za prvpat e opi{an vo 1967 godina od R.L.Tomasulo za dizajnot na IBM 360 model 91. Ovaj algoritam ~esto se narekuva Tomasulo algoritam.

Registerskoto preimenuvawe vo hardverot se postignuva so koristewe na nekolku dopolnitelni zapi{uvawa vo mno`estvoto na registri, kako {to e prika`ano na slika 9. Glavnata ideja e da se povrze edinstvena oznaka (tag) so programskata vrednost, potoa da se prevede sekoe sledno upatuvawe kon registerot vo upatuvaweto kon oznakata. Ova se postignuva so sozdavawe na edinstvena oznaka za register sekoga{ koga }e e zapi{ana. Sekoja instrukcija koja go pro~itala registerot mora da ima svoj registerski specifikator preveden vo oznakite za upatuvawe. Ova se ostavaruva so ~uvawe na oznakata so registerot vo mno`estvoto na registri. Resporeduva~kata redica e kriti~na za to~nata operacija na Tomasulo algoritmot. Zapi{uvawata vo ovaa redica, nare~eni stanici za anga`irawe (reservation stations), imaat poliwa za destinacija na instrukcijata koja gi specificira oznakata i registerskiot broj na instrukcijata. Sekoj izvoren operand ima pole koe ja sodr`i oznakata (pole na oznaka), pole da ja ~uva vrednosta koga }e stane dostapna (pole na vrednosta), i bit za podgotvenost koe poka`uva koga vrednosta e validna (ready bit).

Rasporeduva~kata redica, funkciskite edinici, i mno`estvoto na registri sorabotuvaat so cel da gi razre{at zavisnostite. Mehanizmot za ova e zaedni~kata podato~na magistrala (Common_Data_Bus), prika`an na slika 9, koristen za prenesuvawe na vrednosta od izvr{enata instrukcija, zaedno so svojata oznaka i registerski broj za odredi{te.

 

Slika 9: Zaedni~ka podato~na magistrala (Common_Data_Bus)

Izvornite vlezovi vo rasporeduva~kiot prozorec ~ekaat na prenesuvaweto na nivnata soodvetna oznaka. Koga ova }e se slu~i, izvornite vlezovi gi kopiraat vrednosnite linii (Value lines) od zaedni~kata podato~na magistrala (Common_Data_Bus) vo poleto na vrednostite vo rasporeduva~kata redica i go postavuvaat nivniot soodveten bit za podgotvenost (Ready Bit). Mno`estvoto na registri isto taka vnimava na prenesuvawata. Koga tie }e nastapat, poleto na vrednostite se kopira od zaedni~kata podato~na magistrala (Common_Data_Bus) vo registerot i Ready Bit e postaven. Zaedni~kata podato~na magistrala vo originalniot Tomasulo algoritam u{te se narekuva i Result Bus.

Tamosulo alogoritmot e podelen me|u dve sliki. ^ekorite 1 (prosleduva~ka edinica) i 2 (rasporeduva~ka edinica) se prika`ani na slika 10. ^ekorite 3 i 4 (izvr{uva~ki edinici) i ~ekorot 5 (edinica za a`urirawe) se prika`ani na slika 11.

Slika 10: ^ekorite 1 i 2 kaj tomasulo algoritmot

Slika 11: ^ekorite 3 i 4 kaj tomasulo algoritam

Na slika 12 e prika`ana realizacija na tomasulo algoritmot za primerot od slika 6. Rasporeduva~kata redica se pretpostavuva deka e razdelena od funkciskata edinica, i sekoj vlez e ozna~en kako rezervirana sostojba. Notacijata upotrebena vo primerot e vklu~ena na dnoto na slikata. So ogled na toa deka sekoja instrukcija ima eden registar kako odredi{te, identitetot na instrukcijata se koristi kako ime na oznakata. Postojat eden sobira~ (latentnost na eden ciklus) i mno`a~ (latentnost na dva ciklusi). Emisionata stapka e dve instrukcii vo ciklus.

Slika 12: Primerot od slika 6 analiziran so tomasulo algoritam

Tomasulo algoritmot empiriski e mnogu pobrz vo izvr{uvaweto na kodot otkolku algoritmot na ednostavno blokirawe. Sepak postojat i nekoi nedostatoci. Na primer, mno`estvoto na registri e otprilika 30 procenti pogolemo zaradi oznakite. Asocijativnoto prebaruvawe na rasporeduva~kata redica e skapo za implementacija. Najgolemiot nedostatok se manifestira kako tesno grlo vo efikasnosta na operaciite vo zaedni~kata podato~na magistrala. Nekolku privremeni superskalari koristat pove}ekratni Common_Data_Bus-ovi za da go izbegnat efektot na tesno grlo.

1.7 IZVR[UVAWE (EXECUTION)

Mnogu dizajni na superskalatnata izvr{uva~ka edinica ne se razlikuvaat od dizajnot na tradicionalnata izvr{uva~ka edinica i se tema na kompjuterskata aritmetika.

Eden element na superskalarnata izvr{uva~ka edinica se pojavuva kako edinstven. Se raboti za pristapot kon podatoci odnosno tretmanot na podato~nata ke{ memorija (D-cache) kako druga funkciska edinica. Za da se napravi toa podato~nata ke{ memorija ~esto e podelena vo dve logi~ki edinici: edinica za zapi{uvawe, polnewe (Store) i edinica za ~itawe, prezemawe (Load). Edinicata za zapi{uvawe e bafer koj se koristi da se zapi{at rezultatite vo ke{ memorijata. Primarnata prednost na ovoj bafer e toa {to dozvoluva brzo izvr{uvawe na instrukciite za zapi{uvawe, obi~no vo eden ciklus. Edna komplikacija nastanuva koga instrukcija za zapi{uvawe e sledena od instrukcija za ~itawe. Hardverot mora ili da bara vo baferot na edinicata za zapi{uvawe da vidi dali podatokot od instrukcijata za ~itawe e prisuten vo nego, ili da ja prenese sodr`inata na baferot na edinicata za zapi{uvawe vo podato~nata ke{ memorija, pa potoa da ja izvr{i instrukcijata za ~itawe.

Instrukcijata ~itawe mora da pristapi vo ke{ memorijata i nemo`e da bide baferirana. Koga podatokot od inatrukcijata za ~itaewe ne e prisuten vo podato~nata ke{ memorija, se javuva proma{uvawe. Bez modifikacija na ke{ memorijata, site posledovatelni operacii za ~itawe mora da ~ekaat dodeka ke{ memorijat go najde baraniot podatok. Ova mo`e da gi namali performansite na superskalarnite procesori. Za da se izbegne ova, nekoi superskalarni procesori ovozmo`uvaat mehanizam za pribirawe na podatoci od glavnata memorija, paralelno izvr{uvaj}i drugi instrukcii za ~itawe. Ovoj vid ke{ memorija e nare~ena neblokira~ka ke{ memorija (non-blocking cache ili lockup-free). Neblokira~kite ke{ memorii se zna~ajni za visokite performansi na superskalarnite procesori.

1.8 EDINICA ZA A@URIRAWE (STATE UPDATE UNIT)

Paralelnoto izvr{uvawe na instrukciite von redosled gi uslo`nuva prekinot i izvr{uvaweto. Koga }e se pojavi prekin, sostojbata na procesorot na mno`estvoto registri i memorijata mo`e da ne odgovara na bilo koja sekvencijalna sostojba. Ne postoi vrednost na PC koja pravilno bi go obnovila izvr{uvaweto na programata. Primer za ova mo`e da se vidi na slika 13. Da pretpostavime deka izvr{uvaweto na instrukcijata za ~itawe I2 predizvikuva gre{ka vo stranicata. Pred stranicata da bide donesena vo memorijata, kade bi trebalo procesorot da prodol`i? I2 nemo`e da bide povtorno izvr{ena zatoa {to nejzinite argumenti (R3 i R4) se promeneti od instrukciite I3 i I4. Ovaa situacija e nare~ena neprecizna gre{ka (imprecise fault). Za da se izbegne ova nekoi postojani sostojbi (consistent state) mora da se ~uvaat nekade vo memorijata za da ovozmo`at prodol`uvawe na izvr{uvaweto po gre{kata. Ova e rabota na edinicata za a`urirawe. Taa go izveduva povlekuvaweto na instrukciite, {to e akt na vmetnuvawe na rezultatite od instrukcijata vo postojana sostojba na procesorot.

Slika 13: Nepostojanost na sostojbata na procesorot

Terminot upotreben za da se opi{at prekinite i gre{kite ne e univerzalen. Ovde gi koristime slednite definicii:

operator za softverski prekin (Exception handler): rutina koja se izvr{uva koga }e se pojavi softverski prekin

gre{ka (Fault): instrukcija za prekin koja treba da se povtori otkako operatorot za softverski prekin e izvr{en

stapica (Trap): instrukcija za prekin koja ne treba da se povtori otkako operatorot za softverski prekin e izvr{en; izvr{uvaweto prodol`uva po stapicata (sistemski povik) ili voop{to ne prodol`uva (delewe so 0 )

prekin (Interrupt): hardverski prekin

softverski prekin (Exception): uslov koj predizvikuva gre{ka ili stapica; isto taka voobi~aen izraz za gre{ka ili stapica

Sostojbata na procesorot e definirana od tri parametri: (1) sodr`ini na register, (2) vrednost na programskiot broja~, RS, i (3) sodr`ini na memorijata. Instrukciona granica (instruction boundary) e bilo koja pozicija vo programata po izvr{uvaweto na instrukcija vo lokacija i, no pred izvr{uvaweto na instrukcijata (i+1). Postojanata sostojba za instrukcionata granica e sekoja sostojba na procesorot vo koja (a) site instrukcii koi ja prosleduvaat instrukciskata granica vo programata ja zavr{ile i modificirale sostojbata na procesorot, i (b) site instrukcii koi ja sledat instrukciskata granica vo programata se neizvr{eni i ne ja smenile sostojbata na procesorot.

Na primer, Tomasulo algoritmot ja za~uvuva sostojbata na procesorot. Slikata 13 poka`uva deka ovaa sostojba ne e sekoga{ postojana sostojba. Sostojbata upotrebena od prosleduva~kite i rasporeduva~kite edinici e nare~ena momentalna sostojba (current state ili messy state). Mno`estvoto registri koi ja ~uvaat ovaa sostojba e nare~eno zbrkano (messy register file).

Ako instrukciska granica mo`e da se najde za instrukcija za prekin i postojanata sostojba mo`e da se obnovi za taa instrukcija, rezultira~kiot prekin se veli deka e precizen (precise), vo sprotivno za takviot prekin se veli deka ne e precizen (imprecise). IBM 660 model 91 koristel neprecizni prekini. Preciznite prekini se esencijalni za operirawe so softverskite prekini. Isto taka preciznite prekini se bitni za otstranuvawe stapici (delewe so 0). Hardverot koj ima implementirano precizni prekini ~esto vr{i dvojna uloga za podobruvawe na lo{o predvidenite granki.

Postojat {emi razvieni za implementacija na edinicata za a`urirawe. Tri osnovni {emi se implementirani vo komercijalnite procesori. Toa se preureduva~ki bafer (reorder buffer), mno`estvo od idni registri (future file), i checkpoint-repair {emite.

Preureduva~kiot bafer zadr`uva postojana sostojba vo memorijata i registrite koristej}i FIFO redica koja gi ~uva zavr{enite instrukcii i gi povlekuva po red. Koga instrukcijata e emituvana ima alocirani praznini vo baferot. Prekinuva~kata instrukcija ja registrira ovaa sostojba so postavuvawe na bit vo svojot baferski vlez. So zavr{uvawe na instrukcijata ovaa sostojba ne se registrira, no samo koga }e stigne do glavata (vrvot ili prviot element) na FIFO redicata. Tomasulo oznakite se prenesuvaat na zaedni~kata podato~na magistrala (common-data-bus) vo obi~en preureduva~ki bafer. Me|utoa, ova go prodol`uva vremeto za koe rezultatot stignuva do instrukciite koi ~ekaat, vlijaej}i na celosnite performansi na procesorot. Za da se razre{i ovoj problem, ~esto se dodava logika za zaobikoluvawe za da se proveri preureduva~kiot bafer za registerskata vrednost vo instrukciskoto emisiono vreme.

Mno`estvoto idni registri (future file) e dopolnitelno mno`estvo registri koe se koristi zaedno so preureduva~kiot bafer za ~uvawe na sostojbata na procesorot na povle~enite instrukcii. Bidej}i povle~enite instrukcii go a`uriraat mno`estvoto idni registri namesto zbrkanoto mno`estvo registri, logikata za zaobikoluvawe mo`e da se otstrani. Namesto toa, izvr{enite instrukcii gi emitiraat svoite rezultati vo zaedni~kata podato~na magistarla i se zapi{uvaat vo preureduva~kiot bafer. Samo na instrukciite koi }e stignat do glavata na preureduva~kiot bafer im se ~itaat rezultatite vo mno`estvoto idni registri. Sodr`inata na mno`estvo idni registri se kopira vo zbrkanoto mno`estvo registri.

[emata za korekcija na kontrolnite to~ki (checkpoint-repair) ne koristi preureduva~ki bafer. Namesto toa, se sozdavaat periodi~ni kontrolni to~ki na instrukciskiot protok so koristewe na pove}ekratno mno`estvo registri. Hwu i Patt poka`aat deka se potrebni najmnogu tri mno`estva na regstri. Ednoto mno`estvo na registri ja ~uva zbrkanata sostojba, a vtoroto ja ~uva backup kopijata. Tretoto mno`estvo registri se koristi za periodi~no gradewe na nov backup kopija.

1.9 ZAKLU^OK

Vo ovaa glava se opi{ani dizajnite na superskalarnite procesori. Ovie procesori gi izvr{uvaat instrukciite vo paralelen neprogramski redosled so koristewe na hardverski tehniki kako {to se algoritmot za ednostavno blokirawe i Tomasulo algoritmot. Se koristi hardverska ili kompajlerska pomo{ za manipulirawe so instrukciite za razgranuvawe. Problemot so nepreciznite prekini mo`e da se re{i so koristewe na hardverski bafer ili backup kopii na registrite.

2 VLIW PROCESORI

Strukturata na osnovniot VLIW e prika`ana na slika 14. Edna razlika me|u slika 14 i slika 1 e vo otsustvoto na dekodira~kata edinica vo VLIW. Dekodiraweto na instrukciite za VLIW mnogu ednostavno, a oddelnata edinica bi ja preuvali~ala va`nosta na dekodiraweto. Zatoa VLIW ja sledi RISC filozofijata.

Slika 14: Arhitektura na VLIW procesor

Vo VLIW procesorot nema ni prosleduva~ka i rasporeduva~ka edinica. Vo modelot na VLIW procesorot hardverot ne vr{i nikakvo blokirawe. Namesto toa, odgovornost e na kompajlerot da gi rasporeduva kodovite taka {to zavisnostite me|u instrukciite nikoga{ ne se prekr{uvaat. Ovaa pomestuvawe so naglasuvawe od hardverot vo softverot e glavnata prednost na VLIW procesorot vo odnos na superskalarnite procesori. Ovaa glava ja opi{uva strukturata na VLIW procesorite so poseben osvrt na kompajlerskite tehniki razvieni za ovaa potreba.

 2.1 KOMPAJLERSKO GLEDI[TE NA PROGRAMATA

Tradicionalniot kompajler se sostoi od tri fazi:

    1. razdeluvawe na izvorniot kod vo posredna reprezentacija
    2. optimizitawe na posredniot kod
    3. generirawe na izvr{en kod vo zavisnost od strukturata na ma{inata

Rasporeduvaweto na resursite e impliciten vo fazata na generirawe na kodot. Za VLIW strukturite rasporeduvaweto e primarna funkcija i ~esto se me{a so optimizacija.

Kompajlerot ja tretira programata na razli~en na~in od liniite na izvorniot kod ili od binarnoto kodirawe na instrukciite. Prvata rezlika e posredniot kod, koj e tipi~no instrukcija kreirana so mnogu ednostavna struktura. Operaciite vklu~uvaat prosta aritmetika i logi~ki operacii, operacii so broevi so podvi`na zapirka, kontrolen tok i memoriski Load/Store operacii. Sekoja operacija vo posreden jazik ima eden register odredi{te i nekolku pojdovni registri. Isklu~ok od ova se kontrolnite dejstva (na pr. grankite) koi ja opredeluvaat adresata za cel no ne i registerot odredi{te. Edistven pristap do memorijata e preku operacii za ~itawe i zapi{uvawe (Load i Store). Isto taka postoi i neogeni~eno snabduvawe so registri. Ovie registri ~esto se narekuvaat i virtuelni registri (virtual registers).

Kako dodatok na posredniot kod, kompajlerot sodr`i dve primarni podato~ni strukturi koi ja opi{uvaat programata. Toa se kontrolniot tok (control flow) i grafovi za podato~en tok (data flow graphs). Kako {to poka`uvaat nivnite imiwa ovie grafovi go opi{uvaat tokot na kontrolata i podatocite vo programata. Tie sepak celosno ne ja karakteriziraat programata, odnosno ovie dva grafa ne sodr`at dovolno informacii za opi{uvawe na presmetkite bez dodavawe na operaciite na posredniot jazik. Slika 15.a prika`uva kratok primer za operaciite vo posredniot jazik.

Slika 15: (a) primer za operaciite vo posredniot jazik; (b) graf na kontlniot tok

Ovie operacii mo`at da bidat podeleni vo blokovi od grantirano sekvencijalni operacii. Ovie grupirawa se poznati kako osnovni blokovi (basic blocks). Za sozdavawe osnovni blokovi se koristi slednata postapka: kodot e skeniran i nov osnoven blok po~nuva vedna{ posle granka ili ozna~ena adresa. Operaciite se dodavaat na blokot se dodeka se naide na druga granka ili ozna~ena adresa. Osnovnite blokovi se tipi~no numerirani sekvencionalno, zapo~nuvaj}i od po~etokot na izvorniot fajl ili funkcija koja e kompajlirana. Ako odredi{tata na grankite na krajot na osnovnite blokovi se povrzat so nivnite celni blokovi so rebra, se formira grafot na osnovniot blok ili grafot na kontrolniot tok. Ova e opi{ano na slika 15.b.

Definicijata na grafot za podato~niot tok se izvlekuva neposredno od zavisnostite opi{ani vo tabela 1. Tomasulo algoritmot gi otstranuva anti zavisnostite i izleznite zavisnosti so koristewe na hardversko preimenuvawe. Osnovnata cel na preimenuvaweto e da gi izdvoi registerskite imiwa od nivnite vrednosti taka{to registerskoto reiskoristuvawe vo programata ne primenuva sekvencionalen redosled na izvr{uvawe na operaciite. Za kompajlerot, neograni~eniot broj na virtuelni registri ja postignuva istata zada~a, so ogled na toa {to sekoja operacija ja opredeluva vrednosta na novoto ime na virtuelniot registar. Od trite vida zavisnosti samo momentnite zavisnosti me|u operaciite ostanuvaat vo reprezentacijata na posredniot kod. Grafot na podato~niot tok e orientiran graf kade {to temiwa se operacii, izvirot na sekoe rebro e operacija za definirawe na registrite, a odredi{teto e upotreba na registerskata vrednost. Grafot na podato~niot tok za eden osnoven blok vo primerot e prika`an na slika 16.

Slika 16: Grafot na podato~niot tok za eden osnoven blok

2.2 RASPOREDUVAWE [TO SE ZASNOVA NA KOMPAJLEROT

Rasporeduvaweto na kodot za da se podobri paralelizmot kaj VLIW procesorite najdobro se ilustrira so primer. Ovoj primer koristi VLIW procesor so dve adresi, mno`a~, Load i Store edinica. Operacionite latentnosti se pretpostavuva deka se eden ciklus, osven za mno`eweto (3 ciklusi ) i Load edinicata (2 ciklusi). VLIW instrukciite kako na primer blok od slika 16 se prika`ani vo slika 17. Praznite mesta vo slikata prestavuvaat ciklusi vo koi ne se izvr{uva niedna operacija.

 

dest

src

src

dest

src

src

dest

src

src

dest

address

address

dest

R1

R2

R3

     

R6

R2

R3

R4

X

   
           

R7

R1

R3

       

R5

R4

R3

R8

R4

R3

             

R9

R6

R4

                   
                     

X

R7

Slika 17: Osnoven blok pretstaven kako VLIW instrukcija po rasporeduvaweto

Nepostojat razliki vo vremenskoto sekvencirawe pome|u izvr{uvaweto na operaciite od posredniot jazik od slika 17 na superskalar upotrebuvaj}i go Tomasulo algoritmot i izvr{uvaweto na VLIW instrukcii. Mnogu golemite instrukciski zborovi se celosni skripti koi gi sledi funkciskata edinica vo sekoj ciklus od izvr{uvaweto. Dinami~kite odgovornosti na hardverot se svedeni na pokoruvawe na naredbite na instrukciskiot format, bez nikakva hardverska podr{ka koja bi go prisilila da gi razre{uva zavisnostite. VLIW arhitekturata mo`e da postigne isti ili pogolemi performansi od superskalarnata arhitektura. Postojat pove}e pri~ini za ova, vklu~uvaj}i ja vremenskata ciklusna prednost od poednostavniot hardver i kompajlerskite sposobnosti da iznajde pove}e paralelizam pred izvr{uvaweto otkolku hardverot za vreme na izvr{uvaweto.

Gorniot primer go ilustrira rasporeduvaweto na operaciite od vnatre{nosta na osnovniot blok. Ova ~esto se narekuva lokalno rasporeduvawe (local scheduling), zatoa {to rasporeduvaweto se vr{i lokalno na blokot. Za nesre}a, goleminata na blokot e dolga samo 6 operacii. Ova ja ograni~uva sumata na paralelizam {to VLIW mo`e da izvle~e, vo mnogu sli~en na~in kako grankovniot limit na superskalarite.

Za da izvle~e pove}e paralelizam, se koristi tehnikata za globalno rasporeduvawe (global scheduling). Ovaa tehnika gi premestuva operaciite pome|u osnovnite blokovi za da obezbedi poparalelen raspored. So ogled na toa {to instrukciite se preneseni nad granka, VLIW e analogen so predviduvawe na granki za {pekulativno izvr{uvawe kaj superskalarite.

Globalnoto rasporeduvawe mo`e da se klasificira vo acikli~no i cikli~no rasporeduvawe. Acikli~noto rasporeduvawe manipulira so sekvenci od blokovi kade {to kontrolniot tok ne sodr`i jamki. Koga }e se pojavi jamka, acikli~nite tehniki seu{te mo`at da se iskoristat so prekinuvawe na edno od rebrata i rasporeduvawe na teloto na jamkata kako sekvencionalen kod. Podobri rezultati se postignuvaat koga }e se upotrebi tehnikata za cikli~no rasporeduvawe.

2.3 ACIKLI^NO RASPOREDUVAWE

Prviot ~ekor kaj pove}e acikli~ni rasporeduva~ki tehniki e da se formiraat golemi grupi od blokovi nadvor od osnovniot blok. Postojat pove}e tehniki za da se izvr{i ova grupirawe. Dve najprou~eni tehniki se trace selection i superblock formation.

Trace selection e za prvpat upotrebena od istra`uva~ite vo Univerzitetot vo Jeil za Bulldog kompajlerot, za potoa da bide pro{iren za komercijalnite kompajleri na Multifollow, eden od prvite prodava~i na VLIW procesori. Superblock formation e izvedena tehnika od trace selection upotrebena vo Ilinois IMPACT proektot. Ovie dva algoritmi se sli~ni. Ovde e opi{an algoritmot superblock formation a potoa se navedeni razlikite so trace selection algoritmot.

Slika 18.a prika`uva graf na kontrolniot tok koj se sostoi od osnovni blokovi. Brojkite ili te`inite pokraj blokovite i rebrata se egzekucioni sumi za sekoj blok ili rebro soodvetno. Uslu`uvaweto na te`inite mo`e da bide izvr{eno so koristewe na informacii od razli~nite izvr{uvawa na programot, preku softverski procenki, ili so upotreba na hardver za predviduvawe na granki. Grafot na kontrolniot tok upotreben na ovoj na~in ~esto se narekuva te`inski graf na kontrolniot tok.

Slika 18: (a) graf na kontrolniot tok koj se sostoi od osnovni blokovi;

(b) rezultatot od trace selection algoritmot

Superblokovite prvo se formiraat so grupirawe na blokovi koi {to bi trebalo da se izvr{at sekvencijalno. Ovie grupirawa spored Fi{er se nare~eni tragi (traces). Rezultatot od trace selection algoritmot e prika`an na slika 18b. Tragite na ovaa slika se prestaveni so isprekinati pravoagolnici. Superblok e traga koja ima samo eden vlez na vrvot i pove}e izlezi. Ne se dozvoleni strani~ni vlezovi vo superblokot. Golemata traga na slika 18b ne e superblok bidej}i blokot 3 se prenesuva vo sredinata na tragata. Za da se re{i ovoj problem, se vr{i duplirawe. Poto~no blokot 4 e dupliran. Rezultatot e prika`an na slika 19. Mo`e da se zabele`i deka dupliraweto e izvedeno taka {to izvr{uvaweto po blok 3 e blokot 4.

Slika 19: Duplirawe na blokovi

Interesno za superblokot e toa {to operaciite mo`at da se premestat nagore vo superblokot niz granicite na osnovnite blokovi. Ova e direktna posledica od toa {to superblokot nema strani~ni vlezovi. Ova dozvoluva dinamika vo kodot koja go zgolemuva obemot na lokalnoto rasporeduvawe. So ogled na toa {to operaciite se preneseni nad grankite, tie }e bidat izvr{eni spekulativno koga }e se startuva kodot. Kompajlerot mora da vmetne povrzuva~ki kod (patch-up code) vo osnovnite blokovi koi ne se vo superblokot za da se ukinat efektite na ova spekulirawe. Potrebni se i nekoi dodatni modifikacii na hardverot za da ovozmo`at spekulativno izvr{uvawe na potencijalno primenite instrukcii. Se koristi Ekstra bit vo VLIW dekodiraweto za sekoja operacija koj poka`uva dali taa }e bide izvr{ena spekulativno. Ako spekulativnata operacija generira prekin se pojavuva problem na neprecizen prekin sli~en kako kaj superskalarnite procesori. Ova se re{ava preku mala modifikacija vo mno`estvoto registri za da se signalizira prekinot koga se koristi rezultatot za slednata operacija. Ovaa modifikacija za upravuvawe so prekinite e nare~ena stra`arsko rasporeduvawe (sentinel scheduling).

Rasporeduva~kiot algoritam raboti taka {to gi izbegnuva site duplirawa na kodot i dozvoluva dvi`ewe na kodot vo dvete nasoki. Najzabele`itelna od ovie tehniki e tehnikata na rasporeduvawe na hiperblokovi (hyperblock scheduling techniqe) od Ilinois IMPACT proektot. Ovaa tehnika se zasnova na upotreba na IF - konverzija (If -conversion) i predikatno izvr{uvawe (predicated execution).

Predikatite se ednobitni registri koi gi kontroliraat rezultatite od edna operacija vo smisla dali se povle~eni ili otfrleni. Poddr{kata za predikatno izvr{uvawe bara dodavawe na predikatno registersko pole (predicate register field) na site operacii vo VLIW instrukciskoto kodirawe. Postojat dva na~ini da se iskoristat ovie registri. Vo edna tehnika, predikatniot registar se proveruva koga edna operacija treba da se izvr{i. Ako registerot ima vrednost false, operacijata se napu{ta, vo sprotivno taa se izvr{uva normalno. Vo vtorata tehnika, opredeleniot predikaten registar se proveruva koga soodvetnata operacija }e go zavr{i izvr{uvaweto vo svojata funkciska edinica. Ako predikatniot register sodr`i vrednost false, rezultatot od operacijata se otfrla namesto da bide zapi{an nazad. Nekoi predlo`eni VLIW arhitekturi ja podr`uvaat prvata, a drugi vtorata tehnika.

Predikatnoto izvr{uvawe e mehanizam za otstranuvawe na uslovnite acikli~ni granki celosno od kodnata sekvenca. Sleduva primer na slika 20a. Ovde edna granka e vmetnata vo sredinata na kodnata sekvenca na slika 16. Toa zna~itelno }e go namali dvi`eweto na kodot i }e go namali paralelizmot. Slika 20b ja prika`uva predikatnata verzija. Predikatniot specifikator e prestaven so klu~niot zbor " if P2 " vo posredniot jazik. Operacijata "P2 (R1=0)": zna~i "definiraj go predikatot". Se testira sostojbata (na pr. R1=0) i ako rezultatot e true go postavuva predikatniot registar P2 na true, inaku P2 se postavuva na false. Rasporedenata verzija od predikatniot kod e prika`ana na slika 21. Zatoa grankata e konvertirana vo podato~na zavisnost od predikatniot register P2. Ova o~igledno e pri~inata {to konverzijata na kodot od grankoven kontrolen tok vo predikatna forma e nare~ena if-konverzija.

(a) (b)

Slika 20: (a) primer od slika 16 so vmetnata granka; (b) predikatnata verzija

Formacijata na hiperblokot koristi if-konverzija i predikatno izvr{uvawe za da gi otstrani kratkite granki nanazad i da sozdade pogolemi blokovi od sekvencijalen kod. Toa e indikativno za primerot od slika 19, kade blokot 4 e dupliran. Ako namesto predikat se upotrebi spojuvawe na blok 3 vo superblok, rezultira~kiot superblok nema da ima potreba od duplirawe. Rasporeduva~ot mo`e da gi dvi`i operaciite vo hiperblokot vo bilo koj pravec, se dodeka zavisnostite se po~ituvaat. ebroto na kontrolniot tok vo grafot na kontrolniot tok e konvertirano vo rebro na zavisnost vo grafot na podato~en tok od strana na if-konverzijata.

Tehnikata za if-konverzija mo`e da bide prenaso~ena da go pretvori predikatniot kod nazad vo kod so granki. Ova ima interesni posledici za dilemata lokalno ili globalno rasporeduvawe. So ogled na toa da If -konverzijata go pretvora grafot na acikli~niot kontrolen tok vo edine~en, predikatniot osnoven blok, lokalnite resporeduva~ki tehniki mo`at da bidat upterbeni po If - konverzija kako kodot da bil edine~en osnoven blok. Po rasporeduvaweto, blokot mo`e da bide obratno If - konvertiran za izvr{uvawe na strukturi koi ne podr`uvaat predikacija. Kombinacijata od If - konverzija i obratna If - konverzija formiraat transformacionen par koj go pretvora globalnoto rasporeduvawe vo lokalno, sli~no kako Furievata transformacija ja pretvota konvolucijata vo mno`ewe.

Slika 21: Rasporedena verzija od predikatniot kod

2.4 CIKLI^NO RASPOREDUVAWE

Cikli~noto rasporeduvawe efikasno gi rasporeduva jamkite (Loops) za da postigne povisok stepen na paralelizam. Primer na jamka e prika`an na slika 22a. Prviot ~ekor vo pove}eto od algoritmite za cikli~no rasporeduvawe e da se razdvoi jamkata. Razdvoena verzija od petelkata e prika`ana na slika 22b. Ovde teloto na jamkata se replicira ~etiri pati.

Ako jamkata e celosno razdvoena, kako na slika 23, se pojavuva primerok. Ovoj primerok e o~igleden na slikata so zadebeleni linii. Ovoj povtoruva~ki primerok e nare~en jadro (kernel) na jamkata. Jamkata mo`e da bide prezapi{na so upotreba na jadroto. Ova e prika`ano na slika 24, kade sekoja linija odgovara na VLIW instrukcija (specifikite na VLIW kodiraweto se izbegnati zaradi jasnost). Instrukciite na jadroto se nare~ni PROLOG, a tie po jadroto se narekuvaat epilog (epilog). Ako sekoja iteracija na jamkata se razgleduva kako edine~na makro-instrukcija, ovoj vid na cikli~no rasporeduvawe e ekvivalenten so preklopenoto izvr{uvawe na ovaa makro-instrukcija. Vo ovoj slu~aj, preklopuvaweto sodr`i tri fazi: fazata 1 izveduva Load operacija, fazata 2 izveduva mno`ewe, a fazata 3 izveduva Store operacija na rezultatie.

      R1 2.14
      R3 X
    L: R2 Load M[R3]
      R4 R2 * R1
      Store M[R3] R4
  R1 2.14   R2 Load M[R3++]
  R3 X   R4 R2 * R4
      Store M[R3] R4
L: R2 Load M[R3++]   R2 Load M[R3++]
  R4 R2 * R4   R4 R2 * R4
  Store M[R3] R4   Store M[R3] R4
  If R3 < X + 100 goto L   R2 Load M[R3++]
      R4 R2 * R4
      Store M[R3] R4
      If R3 < X + 100 goto l
 

(a)

 

(b)

Slika 22: (a) Primer na jamka;

(b) Razdvoena verzija od jamkata

Prolog-ot go v~ituva preklopuvaweto so makro-instrukcii, potoa tie se izveduvaat so odlu`uvawe. Koga krajot na jamkata e blizu preklopuvaweto odvedeno (drain) od epilogot. Bidej}i preklopuvaweto ne postoi vo hardverot tuku po~esto e konstruirano od kompajlerot, ovoj vid na cikli~no rasporeduvawe ponekoga{ e nare~en softversko preklopuvawe. Bidej}i pove}ekratnite iteracii se izvr{uvaat odedna{, isto taka ~esto se narekuva i policikli~no rasporeduvawe.

Slika 23: Celosno razdvoena jamka

Slika 24: Prezapi{uvawe na jamka

Postojat pove}e uslovi koi go pravat policikli~noto rasporeduvawe od prethodniot primer dosta ednostavno. Ova ja vklu~uva konstantnata gorna granica od 100 iteracii, nedostatokot od usloven kod vo jamkite, i dobroto odnesuvawe na upotrebata na registerskite {abloni i barawata na funkciskata edinica. Koga nema da se slu~i nieden od ovie uslovi policikli~noto rasporeduvawe mo`e da bide ekstremno komplikuvano. Sekoja od ovie situacii e pretstavena na slika 25.

 

          R1 2.14
  R1 2.14   R1 2.14   R3 X
  R3 X   R3 X   R4 1.1 
L: R2 Load M[R3++]

L:

R2 Load M[R3++]

L:

R2 Load M[R3++]
  R4 R2 * R1   R4 R2 * R1   R4 R2 * R1
  Store M[R3] R4       Store M[R3] R4
      If R4 < 50 goto L2    
  If R4 < 0 goto L       If R3<X + 100 goto L
      Store M[R3] R4    
           
   

L2:

If R3<X + 100 goto L    

(a)

(b)

(c)

Slika 25: Jamki koi te{ko se rasporeduvaat cikli~no poradi (a) neodredena gorna granica na brojot na iteracii; (b) granki vo teloto na jamkata; (v) vkrsteni iteraciski zavisnosti

Vo pove}e slu~ai nekonstantna gorna granica vo brojot na iteracii i usloven kod vo teloto na jamkata mo`at da bidat re{eni so upotreba na predikatno izvr{uvawe via if-konverzija.

Rasparuvaweto na vkrstenite iteraciski zavisnosti vo jamka mo`at da bidat napraveni ili so upotreba na dodatni registri ili so hardverska podr{ka. Slika 26a ja prika`uva upotrebata na dodatni registri za jamkata od slika 25s. Ovde jamkata e raspletena do stepen potreben za policikli~no rasporeduvawe, potoa vkrstenata iteraciska zavisnost e premestena so preimenuvawe na R4 vo R5, R6 i R7.

Slika 26: Re{enie za vkrstenite iteraciski zavisnosti preku (a) upoterba na dodatni registri; (b) kru`ni registri

Primarnata hardverska poddr{ka za otstranuvawe na me}u iteraciska zavisnost (cross-iteration dependence removal) e za prv pat predlo`ena vo Cydrome Cydra-5. Tehnikata se narekuva kru`ni registri (rotating registers). Se koristi poseben registerski fajl koj ima pove}e kopii vo sekoj register. Vsu{nost, sekoj register se zamenuva so redica. Pozicijata vo redicata se zadr`uva so koristewe na bazen register (base pointer). Na vrednosta na registerot vo redicata mo`e da se pristapi spored negovata oddale~enost od postojnata vrednost na bazniot register. Na primer, ako registerot R4 sodr`i vrednost, ve}e opredeleniot R4 se izvr{uva, vrednosta na R4 e neopredelena. Na predhodnata vrednost na R4 mo`e da se pristapi kako na R4[1]. Odnosno, na prvobitnata vrednost na R4 po n operacii na preslikuvawe (remap operacii) mo`e da im se pristapi kako R4[n]. Zatoa {to hardverot e ograni~en, operaciite na preslikuvawe mo`at da se definiraat samo vo ograni~en obem, sekoj register e od ograni~ena kru`na redica. Ova e izvorot na rotacionoto registersko ime za ovaa tehnika. Ako R4 na slika 25s se zameni so rotira~ki register, cikli~noto rasporeduvawe }e mo`e da se upotrebi na rezultira~kiot kod povtorno. Modificiraniot kod e prika`an na slika 26v.

2.5 KOMPATIBILNOST ME\U GENERACIITE

VLIW procesorite go koristat paralelizmot na instrukcisko nivo koristej}i tehniki koi {iroko se zasnovaat na kompajler. Najgolemiot del od ovie tehniki baraat poznavawe na latentnostite na funkciskata edinica za da se rasporedi kodot. Bez dodatna poddr{ka, problemi se pojavuvaat so binarnata kompatibilnost na kodot ako ovielatentnosti se zamenat me|u generacii od ista arhitektura.

Na primer na eden proto~en mno`a~ mu trebaat tri ciklusi za da izvr{i operacija (latentnost na tri ciklusa). Ova e procenkata koja se koristi za da se stigne do rasporeduvaweto na slika 17 i slika 21. Za da se razgleda problemot so kompatibilnosta, sleduva opis {to }e se slu~i so kodot ako se izvr{i na VLIW procesor so mno`a~ so zgolemena latentnost (longer-latency multiplier). Kodot nema da se izvr{i pravilno zatoa {to operacijata koja go bara rezultatot na mno`a~ot }e pristigne vo svojot odreduva~ki register porano odo{to treba. Rau predlaga re{enie na ovoj problem nare~eno razdvoeno zadavawe instrukcii (split-issue). Toa se bazira na zaklu~okot deka VLIW operaciite imaat dva dela: inicijalen del (the initiation part) i zapisen del (write-back part). Tabelata 4 pretstavuva primer na slika 16a podelen na ovie dva dela. Ovde Vi prestavuva skrien register: register koj postoi vo hardverot no ne mu e dostapen na programerot.

Tabela 4: Podelba na inicijalen i zapisen del

Postoi latentnost me|u po~etokot na operacijata i nejziniot kraj. Na primer, vo originalnata arhitektura, mno`eweto izvedeno od I3 }e zapo~ne vo ciklusot h. Zapisniot del }e se izvr{i vo ciklusot h+3. Tehnikata za razdvoeno davawe instrukcii go koristi modelot na ednostavno zaklu~uvawe (simple interlocking) za da obezbedi deka sekoj zapisen del e to~en za sekoja operacija. Modelot na ednostavno zaklu~uvawe se koristi i koga registrite se ~itaat vo operation issue. Sekoja operacija koja se sre}ava so zafaten register se stopira se dodeka registerot se oslobodi. Rau uka`uva deka ovoj dodaten hardver e mnogu mal i ne se koristi osven ako postar kod ne odi na ponov hardver. Superskalarnata konstrukcija dodadena na VLIW ovozmo`uva kompatibilnost me|u generaciite.

Problem mo`e da se pojavi koga latentnostite na registerskata edinica }e se namali od edna vo druga generacija. Ovoj problem e prika`an na slika 27. Za ovoj primer, starata ma{ina ima latentnost na tri ciklusa za mno`ewe, a novata ma{ina bi imala latentost od eden ciklus. Koga kodot se izvr{uva na novata ma{ina, vrednosta na R3 se ~ita pred vtoriot pododatok da mo`e da ja koristi vrednosta na R3 sodr`ana vo prviot pododatok, i se pojavuva pogre{no izvr{uvawe. Edno re{enie e kompajlerot da gi eliminira anti-zavisnostote so preimenuvawe na R3. Me|utoa ograni~en broj na hardveri mo`at da go spre~at ova re{enie. Druga mo`nost e da se prinudi rasporeduva~ot da pretpostavuva deka registerskata vrednost e podgotvena porano od momentot koga latentnosta opredelila, i spored toa da se prilagodi rasporeduva~ot. Ovoj vid na VLIW arhitektura se narekuva arhitektura so pomala ili ednakva latentnost, so ogled na toa deka latentnosta se pretpostavuva deka e pomala ili ednakva so objavenata vrednost. Originalniot vid na VLIW se narekuva arhitektura so ednakva latentnost. Arhitekturite so pomala ili ednakva latentnost i arhitekturite so ednakva latentnost se identi~ni vo nivnata hardverska implementacija. Edinstvenata razlika e vo dogovorot vospostaven pome|u programerot ili kompajlerot i dizajnerot na arhitekturata. Eden nedostatok na arhitekturata so pomala ili ednakva latentnost e potrebata od malku podolgi rasporeduva~i koi treba da se proizveduvaat.

Slika 27: Problem so kompatibilnosta koga e vo pra{awe kusokot od latentnost

3 SUPERSKALAR ILI VLIW?

Superskalarniot procesor kako i VLIW koristat paralelizam na instrukcisko nivo za da postignat visoki performansi za eden protok na izvr{uvawa. Me|utoa tehnikite koi ovie dve arhitekturi gi koristat se mnogu razli~ni. Tabelata 5 gi prika`uva ovie razliki.

Tabela 5: Razliki vo paralelizmot me|u superskalarnite i VLIW procesori vo instrukcisko nivo

Superskalarnite dizajni gi re{avaat anti i izleznite zavisnosti koristej}i go metodot Tomasulo algoritmot. VLIW istiot problem go re{ava so koristewe na golem broj registri i so toa opredeluvaj}i gi virtuelnite registri na kompajleroviot intermediaren kod. Rotira~kite registri mo`at da se upotrebat za da se nadminat vkrstenite iteracii kako i anti i izleznite zavisnosti.

Otkako registrite }e se preimenuvaat, superskalarniot hardver koristi hardverski konstrukcii kako {to e rasporeduva~kata redica, tabela na reziltati, zaedni~ka podato~na magistrala, izdavawe pove}ekratni instrukcii za izvr{uvawe na instrukciite nadvor od programskiot red. Pristapot na VLIW koristi lokalni i globalni tehniki zasnovani na kompajlerot, a pokasno vklu~uva acikli~ni i cikli~ni tehniki. Kaj zavisnostite, kade {to superskalarot koristi isklu~ivo tehniki zasnovani na hardverot, VLIW se potpira na kompajlerot. Superskalarinite procesori mo`at da upotrebuvaat profilirano predviduvawe na granki pomognato od kompajlerot ili hardverski zasnovani baferi za predviduvawe na grankite. VLIW procesorite koristat profilirani informacii za da sozdadat te`inski graf na kontrolniot tok, koj potoa se rasporeduva. Ovoj proces nastojuva da ja smesti najverojatnata cel na grankata vedna{ po grankovnata instrukcija. Vo sekoja situacija kade naslednikot na osnovniot blok ne e najverojatnata cel na grankata se obrabotuva so profilirano predviduvawe na grankite. Analogno na supreskalarniot hardver za sostojbata za a`urirawe e VLIW stra`arskata rasporeduva~ka tehnika. Obete pomagaat pri izvr{uvaweto von redosled. VLIW isto taka ima prednost vo predikatnoto izvr{uvawe preku if-konverziite.

  [to e toga{ podobro: VLIW ili supreskalarnite procesori? Bez somnenie kompajlerski zasnovanoto rasporeduvawe e daleku posuperiorno od hardverskite rasporeduva~ki tehniki. Me|utoa starite izve{ni verzii na programite nemo`at da se prekompajliraat da ja iskoristat prednosta na novite kompajlerski rasporeduva~ki tehniki. Vo vakva situacija, hardverskoto rasporeduvawe ima prednost. Vo toj pogled, rasporeduva~kite tehniki koi se koristat od VLIW ne se ograni~eni samo na VLIW. Superskalarniot procesor so ednostavno blokirawe mo`e da se razgleda kako "forgiving" VLIW, koj to~no go izvr{uva nerasporedeniot kod, me|utoa mo`e da postigne posu{tinsko zabrzuvawe za rasporeden kod. Sli~na tehnika e predlo`ena i za VLIW intergeneraciskata kompatibilnost. Vakvata ma{ina e delumno superskalaren procesor, a delumno VLIW. Ona {to go oddvojuva VLIW od superskalarniot procesor e programerskoto gledi{te na procesorot. Latentnostite vo funkciskite edinici vo superskalarniot procesor ne se del od arhitekturata na instrukciskoto mno`estvo. Za VLIW programerot ili kompajlerot mora da gi poznavaat latentnostite zaradi pravilno rasporeduvawe na kodot. Ova se pretvara vo prednost na VLIW, so ogled na toa deka poznatite latentnosti rezultiraat vo to~no i visoko paralelno kodno rasporeduvawe.

Vo 1994 godina Hewlett-Packard (vtoriot proizveduva~ na rabotni stanici po Sun mickrosystems) i Intel (svetski poznat vo proda`bata na mikro-procesori) objavuvaat deka }e zdru`at sili za sozdavawe na nova generacija na procesori. Se smeta deka Intel ja napu{ta arhitekturata na svojot CISCx86. Mnogu od pionerite na VLIW vklu~uvaj}i gi i sozdava~ite od Cyrdrome i Multiflow sega rabotat za Hewlett-Packard. Postoi predviduvawe deka prestavuvaweto na drug komercijalen VLIW procesor }e bide do krajot na ovaa dekada. Drugite proizvoditeli na superskalarni procesori izjavuvaat isto taka deka VLIW e na~inot da se postigne pogolema emituva~ka stapka od 8 instrukcii vo ciklus. Mo`ebi e prerano da se izjavi deka VLIW e navistina pobednik nad superskalarot. Prethodniot uspeh na RISC nad CISC se dol`i na superiornata sposobnost na RISC da predna~i vo kompajlerskite tehniki. Izgleda deka trendot na kompliciran softver so ednostaven hardver }e prodol`i.

Deneska mnozinstvoto na procesori koi se koristat vo sistemite od personalnite ednoprocesorski kompjuteri do mnoguparalelnite pove}e procesorski sistemi go koristat paralelizmot na instrukcisko nivo. Dali superskalarnite procesori }e gi nadminat VLIW ili obratno ne se znae. Me|utoa se znae deka paralelizmot na instrukcisko nivo }e prodol`i da bide naj~esta i najop{ta forma na paralelno procesirawe vo upotreba.

Odli~no razgleduvawe na istra`uvawata na paralelizmot na instrukcisko nivo e napraveno od Fisher i Rau, dvajcata pioneri vo ova pole. Isto takvo razgleduvawe koe e fokusirano na arhitekturata na superskalarnite procesori i nivnata razmena e napraveno od Johnson.