Siirete ennustamine

Siirete ennustamine (inglise keeles branch prediction) on programmi koodis oleva siirde ehk hüppe ennustamine, kas hüppe toimub või mitte, enne, kui see on kindlalt teada. Siirete ennustamise eesmärgiks on protsessori tööd kiirendada. Kuna instruktsioonide konveier on mitmesammuline ja käsu täitmiseks kulub mitu takti, siis hüppele järgnevaid käske ei saa alati kohe mällu laadida, vaid tuleb oodata, kuni eelnevad käsud on konveieri läbinud ja nende tulemuse järgi on teada, kas hüpe toimub. Selle ootamise vältimiseks kasutatakse siirete ennustamist ja selle efektiivsusel on tänapäeva protsessorite kiiruse määramisel oluline roll.

Joonis 1: Näide kuidas käsud liiguvad läbi 4-sammulisest konveierist ehk torust. Ühte värvi kastid kujutavad ühte instruktsiooni. Kui lilla käsk on hüpe, mis sõltub rohelise käsu tulemusest, siis ei saa hüppele järgnevat sinist käsku kohe kindlalt sisse lugeda, sest ei ole teada, kas hüpe toimub ja võib-olla tuleb hoopis mõni teine käsk sisse lugeda. Üks võimalus on oodata, kuni roheline käsk saab täidetud, aga see tekitab viivise. Parem variant on siirete ennustamine

Siire ehk hüpe tehakse vastava protsessori instruktsiooniga. Selle instruktsiooniga muudetakse programmiloenduri väärtust ja hakatakse uusi käske lugema teiselt aadressilt, mis ei pruugi kohe järgneda hüppe enda aadressile. Hüpped on tihtipeale tingimuslikud ja võivad sõltuda näiteks staatusregistri lippude väärtustest. Osadel juhtudel hüpe sooritatakse ja osadel juhtudel mitte. Et hüppe sooritamine või mittesooritamine oleks kindel, peavad varasemad käsud olema täidetud, millest see otsus sõltub ja mis näiteks staatusregistri väärtusi muudavad.

Kui siirete ennustamist ei ole, siis peab protsessor ootama, kuni siirde toimumise määravad käsud täidetakse ja alles siis saab õigelt aadressilt järgmised käsud sisse lugeda. Siirete ennustamisega üritatakse seda aja raiskamist vältida ja hakatakse kohe ennustatavaid käske täitma. Kui hiljem selgub, et ennustati valesti, siis nende käskude tulemused jäetakse kõrvale ja hakatakse õigeid käske täitma. Käskude kõrvalejätmisel tekkiv ümberlülitamine tekitab viivise konveieri töös, aga ilma ennustamiseta tekiks see viivis alati. Kuna tänapäeva protsessoritel on üpris pikad konveierid, võib käsu tulemuse ootamine kesta kümneid takte.

Kui siiret esimest korda kohatakse, siis on vähe informatsiooni, mille põhjal ennustada. Siirete ennustamise käigus võidakse meelde jätta, kas teatud hüppe tehti või mitte. Edaspidi saab sama siirde juures selle järgi ennustada, kas hüpe pigem toimub või mitte. Erinevate algoritmide abil on võimalik ennustada, et hüpe tehakse tihedamini kui jäetakse tegemata, või et hüpe tehakse iga teine kord.

Implementatsioonid

Ennustamine võib olla staatiline või dünaamiline. Esimesel juhul on hüpete ennustamisel üks kindel algoritm, mida ei muudeta programmi täites sõltuvalt hüpete toimumisest ja mis ei arvesta programmi täites saadavat infot. Dünaamiline ennustamine kasutab programmi jooksmise ajal saadavat infot hüpete täitmise kohta, et muuta enda edasisi ennustusi. Dünaamilisus võimaldab kohaneda sama programmi täitmisel tekkivate erinevate olukordade ja tingimustega.

Staatiline ennustamine

Staatiline ennustamine on kõige lihtsam tehnika, kuna selle tarvis ei ole vaja informatsiooni varasemate hüpete kohta. Ennustamine käib ainult hüppeinstruktsiooni põhjal.

Näiteks varajastes SPARC ja MIPS arhitektuuri implementatsioonides ennustati alati, et hüpe ei toimu ja loeti sisse hüppele järgnev käsk. Alles siis, kui hüppe tingimus oli välja arvutatud ja tuli välja, et hüpe tuleb teha, muudeti programmiloendurit vastavalt hüppele.

Keerulisem hüpete ennustamine võib kõikide tagasi suunatud siirete puhul eeldada, et see siire toimub, ja edasi suunatud siirete puhul eeldada, et see ei toimu. Tagasi suunatud siire on selline, mille sihtaadress on käsu enda aadressist väiksem ehk programmiloenduri väärtus väheneb hüppe korral. See tehnika suurendab tsüklite korral õigesti ennustamist, sest tihtipeale tsükli lõpus on tagasi suunatud hüpe, mida enamasti teostatakse, sest tsükleid täidetakse mitu korda.

Mõned protsessorid lubavad lisada koodi vihjeid, mis ütlevad, kas siire tehakse või mitte ja siirete ennustamine käib nende vihjete järgi. Intel Pentium 4 võimaldab selliseid vihjeid lisada.

Staatilist ennustamist kasutatakse ka keerulisemate ennustamise implementatsioonide olemasolu korral siis, kui siirete kohta ei ole piisavalt infot. Nii töötab Intel Pentium 4. Keerulisemad implementatsioonid vajavad edukaks toimimiseks piisavalt pikka käivitusaega, et nad saaksid koguda statistilist infot. (vaata järgnevaid implementatsioone)

Küllastuv loendur

Joonis 2: Kahebitise küllastuva loenduri olekudiagramm

2-bitisel küllastuval loenduril on neli olekut, vaata kõrvalolevat joonist. Olekud näitavad, kas hüpe on pigem tõenäolisem või mitte:

• Väga tõenäoline
• Pigem tõenäoline
• Pigem ebatõenäoline
• Väga ebatõenäoline

Iga kord kui on välja arvutatud, kas hüpe toimub või mitte, uuendatakse loenduri olekut. Kui hüpe ei toimunud, siis muudetakse olekut selliselt, et hüppe toimumise tõenäosus on ühe astme võrra madalam. Kui hüpe toimus, siis minnakse ühe astme võrra kõrgema tõenäosusega olekusse. Hüppe ennustamine käib selle järgi, kas praegune olek vastab tõenäolisemale või ebatõenäolisemale hüppe toimumisele. Kahebitise loenduri eelis ühebitise loenduri ees on see, et hüppe toimumine peab kaks korda järjest erinema tavapärasest, enne kui ennustamine muutub. Seega kui tsükli lõpus on hüppe käsk, mida palju kordi täidetakse ja ühe korra ei täideta, siis järgmine kord sama käsu juures ennustatakse ikka, et seda täidetakse. Niiviisi ennustatakse tsükli lõpu hüpet ainult ühe korra valesti.

Originaalne Intel Pentium protsessor kasutas küllastuvat loendurit.

SPEC'89 testides on küllastuv loendur saavutanud kuni 93,5% täpsuse, kui igal siirdel on oma loendur.

Loendureid hoitakse tabelis, kust instruktsiooni aadressi järgi leitakse õige loendur. Tabel on kindla suurusega ja hüppe instruktsioonile vastava elemendi saab leida näiteks võttes instruktsiooni aadressist kindla arvu madalamaid bitte. Koos hüppe instruktsiooni lugemisega loetakse ka loenduri bitid vastavast tabeli elemendist. Tabelis hoitakse andmeid erinevate hüpete kohta sarnaselt protsessori vahemäluga. Tabel võib kasutada oma elementide struktureerimiseks ja paigutamiseks erinevat assotsiatiivsust nagu vahemälugi:

• Tabel võib olla täisassotsiatiivne, kus iga loendur võidakse salvestada igale kohale ja lisaks hoitakse iga tabeli elemendi juures infot, mis aadressilt hüpe pärit on. Miinusena on õige instruktsiooni loenduri üles otsimine aeglasem, kuna ta võib paikneda paljudes eri kohtades ja kõik kohad tuleb lihtsalt läbi otsida. Plussina saame kasutada suuremat osa tabelit efektiivselt, kuna loendurid ei pea minema ühte kindlasse kohta.
• Tabeli elemendid võivad olla hüppe instruktsiooni aadressiga otseses vastavuses. Tabeli element valitakse instruktsiooni aadressi k madalama biti abil. See on kõige lihtsam ja kiirem moodus. Miinuseks on see, et väikese tabeli korral võivad mitmed loendurid viidata samale tabeli elemendile, kuigi märkimisväärne osa tabelist on kasutamata.
• Moodul assotsiatiivne tabel, kus hüppe instruktsiooni aadress viitab teatud osale tabelist ja selle osa sees otsitakse õige element üles kasutades täisassotsiatiivset meetodit. Nii ei ole üks täisassotsiatiivne osa liiga suur, et otsimine läheks väga aeglaseks, samas saab tabelit efektiivsemalt kasutada võrreldes otsese vastavusega.
• Räsifunktsioonide abil tabeli elemendi vastavusse seadmine siirdega. Instruktsiooni aadressi järgi arvutatakse räsifunktsiooni põhjal väärtus, mis määrab talle vastava tabeli elemendi. Räsifunktsiooni eesmärk on aadresse ühtlaselt tabeli peale ära jaotada, et tabelit efektiivselt kasutada.

Analoogselt kasutavad ka teised implementatsioonid erineva assotsiatiivsusega tabeleid andmete hoidmiseks.

Kahetasemeline adaptiivne ennustamine

Joonis 3: Kahetasemeline adaptiivne ennustaja. Tabeli iga element on ühele kindlale ajaloole vastav küllastuv loendur, mis peab arvet selle üle, kui tõenäoline on hüppe toimumine konkreetse ajaloo korral.

Koodis olevate hüpete toimumises võib esineda mustreid. Sellistes olukordades töötab kahetasemeline ennustamine paremini kui küllastuv loendur. Küllastuv loendur ei arvesta keerulisemaid seoseid, vaid ennustab ainult selle järgi, kas hiljuti on palju hüppeid olnud või ei ole. Sellepärast ei ennusta küllastuv loendur hästi hüppeid, mis toimuvad näiteks iga teine kord. Kahetasemeline adaptiivne ennustaja peab meeles viimase n hüppe ajalugu ja kasutab iga 2ⁿ ajaloo variandi jaoks küllastuvat loendurit. Meetodit illustreerib joonis 3.

Võtame näiteks n = 2. Siis kahebitisesse nihkeregistrisse kirjutatakse selle hüppe kaks viimast toimumist või mittetoimumist. Sellel registril võib olla neli väärtust: 00, 01, 10 või 11. 0 tähendab siin, et hüpe ei toimunud ja 1 tähendab, et toimus. Eraldi tabelis on iga eelneva nelja väärtuse jaoks kahebitine küllastuv loendur. Sõltuvalt viimase kahe hüppe toimumisest valitakse tabelist õige küllastuv loendur ja selle järgi toimub ennustamine ning seda loendurit uuendatakse. Näiteks kui hüpete ajaloo nihkeregistris on 00, siis vaadatakse sellele ajaloole vastavast kahebitisest loendurist, kas hüpe on tõenäoline või mitte ja loenduri tõenäosust muudetakse vastavalt sellele, kas hüpe tuli teha või mitte, nagu tavalise küllastuva loenduri puhul.

Vaatleme juhtu, kui ühte hüpet sooritatakse iga kolmas kord. Siis hüpete ajalugu oleks 001001001... Sellisel juhul ajaloole 00 vastav loendur ütleb, et hüpe on väga tõenäoline, sest peale seda on alati tulnud 1. Ajalugudele 01 ja 10 vastavad loendurid ütlevad, et hüpe on väga ebatõenäoline. Nii ennustatakse kõiki siirdeid õigesti, aga tavaline kahebitine küllastuv loendur ennustaks iga toimuva hüppe mittetoimuvaks.

Sellel ennustamise meetodil on omadus, et n-bitise ajalugude tabeli korral suudetakse õigesti ennustada suvalist korduvat jada suvalise perioodiga kui perioodi sees kõik n-bitised lõigud on erinevad. Näiteks kolmebitine kahetasemeline adaptiivne ennustaja suudab hüpete jada 0101100111 (sama jada kordub uuesti) ennustada vigadeta, kui jada on alguses läbi käidud ja loendurite väärtused on saanud antud jada väärtuste abil end uuendada. Meetodi miinuseks on nö soojenemisfaas, mille käigus tabelis olevate kombinatsioonide väärtuste uuenemiseks tuleb jada mõni kord läbi käia, et edaspidi seda jada edukalt ennustada.

Meetodi leiutasid T.-Y. Yeh ja Yale Patt Michigani ülikoolist ja avaldasid selle aastal 1991.

Lokaalne siirete ennustamine

Lokaalse siirete ennustamise korral on igal hüppel eraldi enda ajaloo puhver. Võidakse kasutada kahetasemelist adaptiivset ennustamist või muud ennustamist. SPEC'89 testidel on lokaalsed ennustajad saavutanud täpsuse kuni 97,1%.

Globaalne siirete ennustamine

Globaalse siirete ennustamise korral ei hoita iga hüppe jaoks eraldi andmeid, vaid kõigil hüpetel on ühine ajalugu. Implementatsiooni eeliseks on see, et erinevatel aadressidel paiknevate hüpete vahel olevad seoseid ja korrelatsioone võetakse arvesse ennustuste tegemisel. Miinuseks on see, et kui erinevate hüpete vahel ei ole seoseid, vaid seosed on ühe konkreetse hüppe ja tema ajaloo vahel, siis on globaalne ajalugu teiste hüpete segava infoga sassis ja ennustamise täpsus kannatab. Lisaks kui vahepeal toimub palju hüppeid, ei pruugi ajaloos olla andmeid sama hüppe kohta, sest lihtsalt hüppeid oli nii palju, et selle hüppe ajalugu enam ei mahtunud ajalukku ja kirjutati üle.

Antud meetodi efektiivsuse jaoks on vajalik suur tabel ajaloo hoidmiseks. Kahetasemelise adaptiivse ennustaja korral kasvab ajalugude tabel eksponentsiaalselt meeles hoitavate hüpete arvust.

Globaalset ennustamist kasutavad AMD protsessorid ja Intel Pentium M, Core, Core 2 ja Silvermont Atomi protsessorid.

Hübriidne ennustamine

Hübriidse ennustamise korral kasutatakse mitut ennustamismeetodit. Lõplik otsus tehakse pidades meeles, milline ennustusmeetod on kõige täpsem olnud ja usaldatakse tema ennustust, või selle järgi, millise ennustuse enamus meetodeid teeb. Hübriidse ennustamise pakkus välja Scott McFarling 1993. aasta artiklis.

Näitena vaatame kahe ennustajaga hübriidset süsteemi. Kumbki ennustaja töötab iseseisvalt, aga neid haldav süsteem omab kahebitist loendurit ja uuendab enda seisu selle järgi, kas ennustati õigesti või mitte. See sarnaneb kahebitilise küllastuva loenduriga. Loenduri väärtused muutuvad järgneva tabeli järgi:

Ennustaja 1	Ennustaja 2	Haldaja loendur
Ennustas õigesti	Ennustas õigesti	Väärtus ei muutu
Ennustas õigesti	Ennustas valesti	Väärtus väheneb ühe võrra
Ennustas valesti	Ennustas õigesti	Väärtus suureneb ühe võrra
Ennustas valesti	Ennustas valesti	Väärtus ei muutu

Loenduri väärtus alla nulli või üle kolme ei lähe. Kui haldaja loendur on 0 või 1, siis lõplik otsus tehakse esimese ennustaja järgi, kui loenduri väärtus on 2 või 3, siis tehakse otsus teise ennustaja järgi.

Sõltuvalt ennustamise implementatsioonist võivad osad olla kiiremad, aga vähem täpsed, ja teised olla täpsemad, aga aeglasemad ja vajavad suuremaid tabeleid. Vastavalt olukorrale võib üks meetod olla teisest eelistatum. Selle jaoks võivad protsessoril olla erinevad ennustajad, aga sõltuvalt hiljutisest täpsusest vähem täpsema, aga kiirema ennustaja otsused asendatakse teise ennustaja otsustega, kui tehakse kindlaks, et lõpptulemusena on protsessori töö kiirem, hoolimata sellest, et see ennustaja on veidi aeglasem.

Tsüklite ennustamine

Tsüklis olevaid hüppeid on kõige parem ennustada spetsiaalse ennustajaga. Kui tsüklit täidetakse N korda, siis N-1 korda hüpatakse ühte moodi ja 1 kord teist moodi. Sellist käitumist on kõige lihtsam ennustada loenduri abil, mis tuvastab, kui hüppeid tehakse palju kordi ühte pidi ja ühe korra teist pidi, jätab arvu meelde ja edaspidi ennustab vastavalt loendurile hüppeid. Tsüklite ennustamine on osa hübriidsest süsteemist, kus vastavalt sellele, kas tuvastatakse tsüklilist käitumist, võetakse tsükli ennustaja või mõne muu ennustaja otsust kuulda.

Masinõppel põhinev ennustamine

Professor Lucian Vintan on siirete ennustamiseks pakkunud välja masinõppel põhineva mitmekihilise neuronite võrgustiku. Meetodi peamiseks eeliseks on võimalus kasutada pikka ajalugu, kusjuures ajaloo kasvuga kasvab ressursinõudlikkus lineaarselt, mitte eksponentsiaalselt nagu klassikaliste meetodite puhul. Ennustamise täpsust on suudetud parandada 5,7% võrreldes teatud hübriidse ennustamisega. Miinuseks on ajakulu. Isegi meetodit optimeerides kulub ennustamiseks suhteliselt palju protsessori tsükleid.

Ajalugu

1950ndate lõpus disainitud IBM Stretch oskas eeltäita kõiki hüppeid, mis alati tingimusteta võeti. Tingimuslike hüpete korral ennustasid kaks esimest mudelit iga hüppe kohta, et neid ei võeta. Edasised mudelid kasutasid ennustamiseks indikaatorbitte. Stretchi madala kiiruse üheks põhjuseks oli viivis, kui oli vaja vale ennustuse korral valed käsud kõrvale jätta ja õigest kohast jätkata. Järgnevad IBM disainitud arvutid ei kasutanud siirete ennustamist kuni aastal 1985 tuli IBM 3090.

Kahebitised ennustajad võtsid kasutusele Tom McWilliams ja Curt Widdoes 1977. aastal Lawrence Livermore National Lab S-1 superarvuti jaoks.

Burroughs B4900 kasutas instruktsioonide konveierit ja siirete ennustamist. Siirete ajalugu salvestati mällu hüpete instruktsioonide aadressidele programmi täitmise jooksul. Kasutati 4 olekuga ennustamist, mille tarvis oli sama hüpet teostava käsu jaoks 4 erinevat instruktsiooni, kus iga erinev instruktsioon viitas lisaks hüppe käsule vastava hüppe täitmise ajaloole. Kui riistvara tegi kindlaks, et siirde ennustamise olekut tuleb muuta, siis kirjutati samale hüppele, aga teisele siirete ajaloole vastav käsk mällu senise hüppe käsu asemele. Nii oli mälust hüppe instruktsiooni lugemisel kohe teada, kumba pidi tuleb hüpe ennustada. Selle meetodiga saavutati täpsus 93%.

Siirete ennustamine muutus olulisemaks superskalaarsete konveieriga protsessorite tulekuga. Kui konveierit ei ole ja uut käsku ei hakata sisse lugema enne eelmise täitmist, siis ei ole vaja ka siirdeid ennustada, kuna mitut käsku samaaegselt nii kui nii täita ei saa. Konveieri puhul täidetakse käsku samm-sammult ja uus käsk liigub konveieri ühest otsast sisse enne kui eelmine käsk on konveieri teisest otsast välja jõudnud. Seega on vaja enne käskude tulemuste selgumist ennustada, kas hüpe toimub või mitte ja vastavalt sellele millist käsku tuleks hakata konveierist läbi laskma.

Välislingid

• Seznec et al. (2002). "Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor"Mall:Snd kirjeldab Alpha EV8 siirete ennustajat. Artikkel kirjeldab hästi kuidas nad selle disainini jõudsid arvestades riistvara piiranguid ja simulatsioone.
• Jimenez (2003). "Reconsidering Complex Branch Predictors"Mall:Snd kirjeldab Ev6 ja K8 siirete ennustajat ja konveierit.
• Fog, Agner (2009). "The microarchitecture of Intel, AMD and VIA CPUs". Vaadatud 1.10.2009.
• Andrews, Jeff (30. oktoober 2007). "Branch and Loop Reorganization to Prevent Mispredicts". Intel Software Network. Vaadatud 20.08.2008.
• Yee, Alexander. "What is Branch Prediction? – Stack Overflow Example".