Predviđanje grananja

U računarskoj arhihekturi, predviđanje grananja je digitalno kolo koje pokušava da pretpostavi kojim će putem grana (tj. if-then-else struktura) ići pre nego što to bude zasigurno poznato. Svrha predviđanja grananja je da poboljša protok u protočnoj obradi instrukcija. Predviđanje grananja ima ključnu ulogu u postizanju visokih efikasnih performansi u mnogim mikroprocesorskim arhihekturama za protočnu obardu kao što je x86.

Dvosmerno grananje se obično sprovodi sa instrukcijom koja se zove uslovni skok. Uslovni skok može da se "ne uzme" i da nastavi izvršenje sa prvom granom koda koji sledi odmah nakon uslovnog skoka - ili se može "uzeti" i skočiti na drugo mesto u programskoj memoriji gde je druga grana koda memorisana.

Slika 1: Primer 4 faze protočne obrade. Obojeni kvadratići predstavljaju instrukcije nezavisne jedna od druge

Nije poznato da li će sigurno doći do uslovnog skoka ili ne, sve dok se uslov ne izračuna i uslovni skok ne pređe u fazu izvršenja instrukcija u protočnoj obradi (vidi sliku 1).

Ako ne bi bilo predviđanja grananja, procesor bi morao da čeka da instrukcija uslovnog skoka prođe fazu izvršavanja pre nego što sledeća instrukcija može da uđe u fazu u protočne obrade. Predviđanje grananja pokušava da izbegne ovo gubljenje vremena pokušavajući da pogodi da li će do uslovnog skoka najverovatnije doći ili ne. Grana, za koju se poretpostavi da je najbolja moguća, se učita i spekulativno izvrši. Ako se kasnije ispostavilo da je pretpostavka bila pogrešna onda se spekulativno izvršene ili delimično izvršene instrukcije odbace i protočna obrada počinje ispočetka sa ispravnim granama, izazivajući odlaganje.

Vreme koje je izgubljeno u slučaju promašaja predviđanja grananja jednako je broju faza u protočnoj obradi od donete faze do faze izvršenja. Savremeni mikroprocesori imaju tendenciju da imaju prilično duboku protočnu obradu tako da je kašnjenje promašaja predviđanja između 10. i 20. taktnog signala. Što dublja protočna obrada, duža je potreba za dobro predviđanje grananja.

Prvi put kada uslovna instrukcija skoka naiđe, nema mnogo informacija na kojima je zasnovano predviđanje. Ali predviđanje grananja vodi evidenciju o tome da li su grane uzete ili ne. Kada naiđe uslovni skok koji je viđen nekoliko puta, onda on može da zasnuje predviđanje na osnovu istorije. Prediktor grananja može, na primer, da prepozna da li se uslovni skok češće uzima ili se ne uzima, ili da se uzima svaki drugi put.

Predviđanje grananja nije isto što i ciljno predviđanje grananja. Predviđanje grananja pokušava da pogodi da li će doći do uslovnog skoka ili ne. Cilj predviđanja grananja pokušava da pogodi metu uzetog uslovnog ili bezuslovnog skoka pre nego što se izračuna pomoću dekodiranja i izvršavanja same instrukcije. Predviđanje grananja i cilj predviđanja grananja se često kombinuju u istom kolu.

Implementacija

Statično predviđanje

Statičko predviđanje je najjednostavnija tehnika predviđanja grananja, jer se ne oslaa na informacije o dinamičkoj istoriji koda koji se izvršava. Umesto toga, predviđa ishod grane samo na osnovu instrukcija grane.

Rane implementacije SPARC i MIPS (dve od prvih komercijalnih RISC arhihektura) koristi jedan pravac statičkog predviđanja grananja: one uvek predviđaju da uslovni skok neće biti uzet (neće doći do uslovnog skoka), tako da, one uvek donesu sledeću sekvencijalnu instrukciju. Samo onda kada je grana ili skok ocenjen i pronađen da bi se uzeo, pokazivač instrukcije se postavlja na ne-sekvencijalnu adresu.

Oba procesora ocenjuju grananje u fazi dekodiranja i imaju donošenje informacija u jednom ciklusu. Kao rezultat toga, ciljno predviđanje grananja je bilo dugačko dva ciklusa, a mašina će uvek doneti instrukciju odmah posle jedne preduzete grane. Obe arhitekture definišu slot odlaganja grananja a u cilju iskorišćavanja ovih učitanih instrukcija.

Složeniji oblik statičkog predviđanja pretpostavlja da će se uzeti grane koje idu unazad, a grane koje su napred-ukazujuće grane neće se uzeti. Nazadna grana je ona koja ima ciljnu adresu koja je niža od sopstvene adrese. Ova tehnika može da pomogne sa predviđanjem tačnosti petlji, koje su obično backward-pointing grane, i češće su uzete nego ne.

Neki procesori omogućavaju da se pogodak predviđanja grananja ubaci u kod, da kaže da li statičko predviđanje treba da se uzme ili ne. Intel Pentium 4 prihvata pogodak predviđanja grananja, dok je ova funkcija napuštena u kasnijim procesorima.

Statično predviđanje se koristi kao fall-back tehnika u nekim procesorima sa dinamičnim predviđanjem grananja, kada ne postoji bilo kakva informacija za korišćenje dinamičkog predviđanja. Oba Motorola MPC7450 (G4e) i Intel Pentium 4 koriste ovu tehniku kao fall-back.

Predviđanje sledeće linije

Brojač zasićenja ili bimodalni predskazivač je konačan automat sa četiri faze:

Slika 2: Dijagram faze 2-bitnog brojača zasićenja

• Snažno ne uzeto
• Slabo ne uzeto
• Slabo uzeto
• Snažno uzeto

Kada je grana ocenjena, odgovarajući mašina se ažurira. Grane koje se ocenjuju kao ne uzete, smanjuju ka fazi snažno ne uzeto, a grane ocenjene kao uzete, rastu ka fazi snažno uzeto. Prednost od dvobitnog brojača preko jedno-bitne šeme je to da uslovni skok mora dva puta da odstupa od onoga što je urađeno u prošlosti pre predviđanja promena. Na primer, uslovni skok zatvorene-petlje je pre jedan promašak predviđanja nego dva.

Originalni, ne-MMX Intel Pentium procesor koristi brojač zasićenja, mada sa nesavršenom implementacijom.

Na SPEC'89 oznakama, veoma veliki bimodalni prediktori su zasićeni na 93,5% tačnosti, jednom svaka mapa grananja na jedinstven brojač.

Tabela predviđanja je indeksirana sa instukcijom adresnih bitova, tako da procesor može da donese predviđanje za svaku instrukciju pre nego što se instrukcija dekodira.

Prilagodljivi predviđač sa Dva-nivoa

Slika 3: Two-level adaptive branch predictor. Svaki unos u istoriju šablona tabele predstavlja 2-bitni brojač zasićenja tipa prikazanog na slici 2.

Ako ima tri if izraza u kodu, treći if izraz može se uzeti u zavisnosti da li su prethodna dva uzeta ili ne. U takvom scenariju prilagodljivi predviđač sa dva-nivoa radi efikasnije nego brojač zasićenja.

Uslovni skokovi koji se uzimaju svaki drugi put, ili imaju neki drugi periodični redovni šabloni, nisu dobro predviđeni od stane brojača zasićenja. Prilagodljivi predviđač sa dva-nivoa pamti istoriju poslednjih n pojavljivanja grane i koristi jedan brojač zasićenja za svaki od mogućih 2ⁿ šablona. Metod je ilustrovan na slici 3.

Uzmimo na primer da je n = 2. To znači da su dve poslednje pojave grane memorisane u 2-bitnom pomeračkom registru. Ova istorija registra grananja može imati 4 različite binarne vrednosti: 00, 01, 10, i 11; gde 0 znači "nije uzeto" i 1 znači "uzeto“. Sada, mi pravimo tabelu istorije šablona sa četiri unosa, jedan za svaki od 2ⁿ = 4 mogućih grana istorije. Svaki unos u tabelu istorije šablona sadrži 2-bitni brojač zasićenja istog tipa kao na slici 2. Registar istorije grananja se koristi za odabir kojeg od 4 brojača zasićenosti će se koristiti. Ako je istorija 00 onda se koristi prvi brojač. Ako je istorija 11 onda se koristi poslednji brojač od sva 4 brojača.

Pretpostavimo, na primer, da je uslovni skok uzet svaki treći put. Sekvenca grane je 001001001... U ovom slučaju, unos broja 00 u tabelu šablona istorije će ići u fazu "snažno uzeti", ukazujući da posle nule ide jedan. Ulaz broj 01 će ići u fazu "snažno ne uzima", što ukazuje da je posle 01 dolazi 0. Isti je slučaj i sa unosom broja 10, dok se unos broja 11 nikada ne koristi, jer nikad postoje dve uzastopne jedinice.

Opšte pravilo za prilagodljivi predviđač sa dva-nivoa sa n-bitnom istorijom je to što on može da predvidi svaku sekvencu ponavljanja sa bilo kojim periodom ako su svi n-bitni podnizovi drugačiji.

Prednost prilagodljivog predviđača sa dva-nivoa je što može brzo da nauči da predvidi proizvoljan šablon ponavljanja. Ovaj metod je izmislio T.-Y. Yeh i Yale Patt na Univerzitetu u Mičigenu. Od prvobitnog objavljivanja 1991, ovaj metod je postao veoma popularan. Varijante ovog metoda predviđanja se koriste danas u većini savremenih mikroprocesora.

Lokalno predviđanje grananja

Lokalno predviđanje grananja ima poseban bafer za istoriju za svaki uslovni skok instrukcija. On može da koristi prilagodljivi predviđač sa dva-nivoa. Bafer za istoriju je poseban za svaki uslovni skok instrukcija, dok tabela istorije šablon može biti odvojena ili može da se deli između svih uslovnih skokova.

Intel Pentium MMX, Pentium II i Pentium III imaju lokalno predviđanje grananja sa lokalnom 4-bitnom istorijom i tabelu istorije lokalnog šablona sa 16 unosa za svaki uslovni skok.

Na SPEC'89 oznakama, veoma velika lokalna predviđanja su zasićena na 97,1% tačnosti.

Globalno predviđanje grananja

Globalno predviđanje grananja ne vodi posebnu evidenciju istorije za svaki uslovni skok. Umesto toga drži zajedničku istoriju svih uslovnih skokova. Prednost zajedničke istorije jeste da je bilo koja korelacija između različitih uslovnih skokova deo pravljenja predviđanja. Nedostatak je da se istorija stapa sa nebitnim informacijama, ako su različiti uslovni skokovi u korelaciji, i da bafer istorije ne može da sadrži bitove iz iste branše, ako postoje mnogi druge grane između. Ono može da koristi prilagodljivi predviđač sa dva-nivoa.

Ova šema je jedino bolja od šeme brojača zasićenja za velike tabele, a retko je dobra kao lokalno predviđanje. Bafer istorije mora biti duži kako bi napravio dobro predviđanje. Veličina table istorije šablona raste eksponencijalno sa veličinom bafera istorije. Dakle, veliki šablon tabele istorije mora da se deli između svih uslovnih skokova.

Prilagodljivi predviđač sa dva-nivoa ds globalno zajedničkim istorijskim baferom i obrazac tabele istorije se zove "gshare" prodviđač, ako njegov xors globalne tabele istorije i grane PC-a, i "gselect" ako ih spaja. Globalno predviđanja se koristi u AMD mikroprocesorime i Intel Pentium M, Core i Core 2.

Izmešano predviđanje grananja

Izmešano predviđanje grananja kombinuje lokalne i globalne principe predviđanja pomoću spajanja lokalne i globalne istorije grananja, verovatno sa nekim bitovima iz brojača programa. Testovi pokazuju da VIA Nano procesor može da se koristi ovu tehniku.

Prediktor usaglašavanja

Prediktor usaglašavanja je prilagodljivi predviđač sa dva-nivoa sa globalnom deljenom istorijom bafera i tabelom šablona istorije, i dodatni lokalni brojać zasićenja. Izlazi lokalnog i globalnog predviđanja su XOR-ovani jedni sa drugima da daju konačno predviđanje. Cilj je da se smanje argumenti u tabeli šablona istorije gde se desi da dve grane sa suprotnim predviđanjem dele isti unos u tabeli šablona istorije.

Prediktor usaglašavanja se koristio u prvoj verziji Intel Pentijum 4, ali je kasnije napušten.

Hibridni predviđač

Hibridni predviđač, takođe se naziva kombinovani predviđač, implementira više od jednog mehanizma predviđanja. Konačno predviđanje se zasniva ili na meta-prediktoru da pamti koji od prediktora je napravio najbolje predviđanje u prošlosti, ili na većini ukupnih funkcija koje su bazirane na neparnim brojevima različitih predviđača.

Scott McFarling je predložio kombinovanje predviđanje grananja i svom radu 1993. godine.

Na SPEC'89 oznakama, takav prediktor je dobar kao i lokalni prediktor.

Predviđači poput gshare koriste više stavki tabele za praćenje ponašanja jedne posebne grane. Ovo umnožavanje unosa čini da je mnogo veća verovatnoća će dve grane biti mapirane na isti unos tabele (situacija se zove preklapanje), što zauzvrat čini da je mnogo verovatno da će tačnost predviđanja trpeti zbog tih grana. Kada imate više prediktora, to je korisno da se organizuje da svaki prediktor ima različito preklapanje šablona, tako da je više verovatno da bar jedan prediktor neće imati preklapanje. Kombinovani predviđači sa različitim indeksiranjem funkcija za različite predviđače se zove gskew predviđač, i analogan je iskrivljenom asocijativnom kešu koji se koristi za podatke i keširanje instrukcija.

Predviđač petlje

Uslovni skok koji kontroliše petlju se najbolje predviđa sa specijalnim predviđačem petlje. Uslovni skok na kraju petlje koji se ponavlja N puta će se izvršiti N-1 puta i jednom neće. Ako se uslovni skok nalazi na početku petlje, on se neće izvršiti N-1 puta i onda će se izvršiti jednom. Uslovni skok koji ide mnogo puta na jedan način, a zatim na drugačiji jednom, ispostavlja se da ima ponašanje petlje. Takav uslovni skok se može lako predvideti sa jednostavnim brojačem. Prediđač petlje je deo hibridnog predviđača gde cilj-predviđača detektuje da li uslovni skok ima ponašanje petlje.

Danas mnogi mikroprocesori imaju predviđač petlje.

Predviđanje indirektinih skokova

Instukcija indirektnog skoka može da bira između više od dve grane. Noviji procesori iz Intela i AMD-a mogu da predvide indirektno grananje koristeći prilagodljivi predviđač sa dva-nivoa. Ova vrsta instrukcije doprinosi više od jednog bita na istoriju bafera.

Procesori bez ovog mehanizma mogu jednostavno da predvide indirektni skok da ide ka istom cilju kao što je išao i prošli put.

Predviđanje povratka funkcije

Funkcija će se normalno vratiti tamo odakle je pozvana. Instrukcija povratka je indirektni skok koji čita svoju ciljnu adresu iz poziva steka. Mnogi mikroprocesori imaju odvojen mehanizam predviđanja za povratne instrukcije. Ovaj mehanizam se zasniva na takozvanom engl. return stack buffer, što je lokalno ogledalo poziva steka. Veličina bafera povratnog steka je tipično 4 - 16 unosa.

Zaobilaženje predviđanja grananja

Kompromis između brzog predviđanja grananja i dobrog predviđanja grananja se ponekad uspostavi tako što će imati dva predviđanja grananja. Prvo predviđanje grananja je brže i jednostavnije. Drugo predviđanje grananja, koje je sporije, komplikovanije, i sa većim je tabelama, će verovatno zameniti pogrešno predviđanje od strane prvog predviđača.

Alpha 21264 i Alpha EV8 mikroprocesori koriste brzi jedno-ciklusni predviđač sledeće linije da bi upravljali ponavljanjem ciljnog grananja i da bi pružili jednostavno i brzo predviđanje grananja. Zato što je sledeći red predviđanja netačan, ponavljanje rešenja grananja traje jako dugo, oba jezgra imaju dva-siklusa sekundarnog predviđanja grananja koje može da zaobiđe predviđanje sledećeg reda po cenu da se izgubi jedan donet ciklus.

Intel Core i7 ima dva ciljna bafera grananja i eventualno dva ili više predviđanja grananja.

Neuronski predviđač grananja

Mašinsko učenje za predviđanje grananja koristi LVQ i MLP, koje se naziva "neuronsko predviđanje grananja", predloženo je od stane Prof. Lucian Vintan.

Istraživanjima neuronskog predviđača grananja je mnogo doprineo prof Daniel Jimenez (USA). Godine 2001., (HPCA konferencija) predstavljen je prvi engl. perceptron predviđač kojeg je bilo moguće implementirati u hardveru.

Glavna prednost neuronskog predviđača je njegova sposobnost da iskoristi dugu istoriju dok zahteva samo linearnu rast resursa. Klasični predviđači zahtevaju eksponencijalni rast resursa. Jimenez izveštava o sveukupnom poboljšanju od 5,7% nad McFarling-ovim stilom hibridnog predviđača.

Glavni nedostatak ovog perceptron predviđača je njegovo visoko kašnjenje. Čak i nakon iskorišćenja prednosti velike brzine aritmetičkih trikova, računanje kašnjenja je relativno zahtevno u odnosu na period takta mnogih savremenih mikroarhihektura. Da bi se smanjilo predviđanje kašnjenja, 2003. godine Jimenez je predložio brzi-put neuronskog predviđača, gde perceptron predviđač bira svoju težinu prema tenutnom putu grananja, a ne prema PC grananju. Mnogi drugi istraživači su razvili ovaj koncept (A. Seznec, M. Monchiero, D. Tarjan & K. Skadron, V. Desmet, Akkary et al., K. Aasaraai, Michael Black, itd.)

Većina najsavremenijih predviđača grananja koristiti perceptron predviđač (vidi Intelovo "Prvenstvo takmičenja u predviđanju grananja" ). Intel već implementira ovu ideju u jednom od simulatora IA-64 (2003).

Istorija

IBM Stretch, dizajniran u kasnim 50-im, unapred izvrši sva bezuslovna grananja i bilo koje uslovno grananje koje zavisi od indeksiranih registara. Za drugo uslovno grananje, prva dva modela implementiraju netaknuto predviđanje; kasniji modeli su promenjeni tako da implementiraju predviđanja zasnovana na trenutnoj vrednosti indikatora bitova (odgovara današnjem stanju kodova). Dizajneri Stretch-a su razmatrali statički pogodak bitova u instrukcijama grananja, u početku rada na projektu, ali su se odlučili protiv toga. Oporavak od greške predviđanja je obezbeđen od strane engl. lookahead jedinice na Stretch-u. Naknadni dizajn IBM-ovih velikidž računara ne koristi predviđanj grananja sa spekulativnim izvršenjem sve do pojave IBM 3090, 1985. godine.

Dvobitne predviđače su uveli Tom McWilliams i Curt Widdoes, 1977. godine, za Lawrence Livermore National Lab S-1 superračunar i nezavisno od stane Jim Smith-a, 1979. godine na CDC.

Mikroprogramirani procesori, popularni od 1960-ih do 1980-ih i dalje, uzimaju više ciklusa po instrukciji, a generalno ne zahtevaju predviđanje grananja. Međutim, zajedno sa IBM-3090, postoji nekoliko primera mikroprogramiranih dizajna koji imaju ugrađeno predviđanje grananja.

Burroughs B4900, mikroprogramirana COBOL mašina izbačena 1982. god. bila je sa protočnom obradom i koristila je predviđanje grananja. B4900 istorija predviđanja grananja je uskladištena nazad u unutrašnjoj memoriji instrukcija tokom izvršavanja programa. B4900 realizuje 4-fazno predviđanje grananja pomoću 4 semantički ekvivalentnih grana opcode-a da predstavljaju svaku vrstu grane operatora. Opcode koristi ukazanu istoriju te instrukcije grananja. Ako hardver utvrdi da faza predviđanja grananja određene grane treba da se ažurira, on će preraditi operacioni kod sa semantički ekvivalentnim operacionim kodom koji je pogodio odgovarajuću istoriju. Ova šema je dobila 93% stopu pogotka. US patent 4.435.756 i drugi, odobreni su na ovoj šemi.

VAX 9000, najavljen 1989. godine, bio je i mikroprogramiran i sa protočnom obradom, i obavljao je predviđanje grananja

Prvi komercijalni RISC procesori, MIPSR2000 i R3000 i raniji SPARC procesori, izvršavali su samo jednostavno "ne-uzeto" predviđanje grananja. Zato što koriste kašnjenje slota grananja, preuzimaju samo jednu instrukciju po ciklusu, a izvršavaju u-redu, nije bilo gubitka performansi. Kasnije, R4000 koristi isto trivijalno "ne-uzet" predviđanje grananja, i gubi dva ciklusa za svaku uzetu granu, jer ponavljanje rezolucija grana je bilo dugo četiri ciklusa.

Predviđanje grananja je postalo važnije sa instrukcijom protočne obrade, superskalarnog procesora kao što je Intel Pentijum, DEC Alpha 21064, MIPS R8000, i IBM POWER serije. Svi ovi procesori se oslanjaju na jedan bit ili na jednostavni bimodalni predviđač.

DEC Alpha 21264 (EV6) koristi predviđač sledeće linije koji je zamenjen kombinacijom lokalnog i globalnog predvođača, gde je izbor kombinacije napravljen pomoću bimodalnog predviđača

AMD K8 kombinuje bimodalni i globalni predviđač, gde je izbor kombinacije drugi bimodalni predviđač. Ovaj procesor kešira bazu i izbor brojača bimodalnog predviđača u bitove L2 keša koji se inače koriste za ECC. Kao rezultat toga, ona ima veoma veliku bazu i izbor predviđanja tabele, i parnost umesto ECC-a na instrukciji u L2 keš memoriji. Parnost je sasvim u redu, jer svaka greška instrukcije parnosti može se poništiti i vratiti iz memorije.

Alpha 21464 (EV8, kasnije otkazano u dizajnu) ima kaznu od 14 ciklusa za promašaj predviđanja grananja. Koristila je složen ali brz predviđač narednne linije zamenjen kombinacijom bimodalnog i majority-voting predviđača. Majority vote je bio između bimodalnog predviđača i dva gskew predviđača.

Vidi još

• RSA
• Asimetrična kriptografija

Literatura

• P. Shen, John; Lipasti, Mikko (2005). Modern processor design: fundamentals of superscalar processors. Boston: McGraw-Hill Higher Education. str. 455. ISBN 978-0-07-057064-1. 

Spoljašnje veze

• Seznec et al. (1996). "Multiple-Block Ahead Branch Predictors" – demonstrates prediction accuracy is not impaired by indexing with previous branch address.
• Seznec et al. (2002). "Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor" – describes the Alpha EV8 branch predictor. This paper does an excellent job discussing how they arrived at their design from various hardware constraints and simulation studies.
• Jimenez (2003). "Reconsidering Complex Branch Predictors" – describes the EV6 and K8 branch predictors, and pipelining considerations.
• Fog, Agner (2009). „The microarchitecture of Intel, AMD and VIA CPUs”. Pristupljeno 1. 10. 2009. 
• Andrews, Jeff (30. 10. 2007). „Branch and Loop Reorganization to Prevent Mispredicts”. Intel Software Network. Arhivirano iz originala 17. 04. 2008. g. Pristupljeno 20. 8. 2008. 
• Yee, Alexander. „What is Branch Prediction? - Stack Overflow Example”.