U gotovo svakom računalnom programu postoje dijelovi koda koji se granaju u zasebne staze. Na primjer, izjava if-then-else ima dva moguća ishoda. Ove izjave ne predstavljaju nikakav problem za sekvencijalne procesore, budući da CPU obrađuje svaku naredbu redom. Grane predstavljaju veliki problem za cjevovodne procesore, jer se više instrukcija izvršava odjednom.
Scenarij
U slučaju programa s naredbom grananja s dva moguća ishoda, dvije moguće staze koda ne mogu biti na istom mjestu. Obrada potrebna za dovršetak bilo koje opcije bit će drugačija. Inače se program ne bi granao. Vjerojatno će postojati priličan broj naredbi grananja koje se uzimaju samo jednom, poput naredbe if.
Postoje i izjave grananja koje tvore petlju. Iako one možda nisu brojčano uobičajene kao izjave za jednokratnu upotrebu, općenito se statistički ponavljaju. Može se pretpostaviti da je vjerojatnije da će vas grana odvesti natrag oko petlje nego ne.
Zašto je ovo problem?
Nije važno kako je ovaj problem formuliran u potpuno sekvencijalnom procesoru. To jednostavno nije problem. Koja će se grana uzeti zna se prije obrade prvog dijela sljedeće instrukcije.
U cjevovodnom procesoru, međutim, sljedeće upute su u redu čekanja. Već se obrađuju kada procesor zna koja se grana preuzima. Pa kako bi se procesor trebao nositi s ovim scenarijem? Postoji nekoliko opcija. Najgore je jednostavno čekati i ostaviti cjevovod u stanju mirovanja dok čeka odgovor kojom granom krenuti. To bi značilo da svaki put kada imate izjavu o grananju, uvijek biste izgubili najmanje onoliko ciklusa procesorskog vremena koliko imate faza u cjevovodu.
Alternativno, možete pokušati pokrenuti obje opcije u cjevovodu i odbaciti pogrešan izbor. Ovo bi imalo upola manju kaznu nečinjenja, ali bi i dalje izazvalo kaznu izvedbe za svaku izjavu grananja. S obzirom na to da moderni procesori također mogu izvoditi instrukcije bez reda, potencijalno biste mogli pokušati pokrenuti svaku instrukciju grananja što je prije moguće. Dakle, njegov ishod je poznat prije nego što je potreban. Ova bi opcija mogla biti korisna, osim što nije skalabilna. Pretpostavimo da imate relativno visoku gustoću grananja. U tom slučaju jednostavno ih nećete moći sve pokrenuti rano, a da ne ostanete u praznom hodu.
Kako se ovaj problem stvarno rješava
U stvarnosti, procesor uključuje prediktor grananja. Prediktor grananja pokušava pogoditi koji će rezultat izbora grananja biti uzet. Procesor tada pretpostavlja da je predviđanje točno i raspoređuje upute. Ako je prediktor grana točan, nema kazne za učinak.
Ako prediktor grananja pogriješi, morate isprati cjevovod i započeti obradu stvarnog rezultata. To doista rezultira nešto lošijom kaznom izvedbe nego ako niste učinili ništa i samo ste čekali rezultat. Da biste dobili najbolju izvedbu, važno je osigurati da je prediktor grana što točniji. Postoji niz različitih pristupa tome.
Odgovarajući kod
U strojnom kodu, grananje je uvijek izbor između čitanja sljedeće instrukcije ili prelaska na skup instrukcija negdje drugdje. Neke rane implementacije prediktora grana jednostavno su pretpostavljale da će sve grane uvijek ili nikada biti zauzete. Ova implementacija može imati iznenađujuće dobru stopu uspjeha ako prevoditelji znaju ovo ponašanje i znaju dizajniran za prilagodbu strojnog koda tako da se najvjerojatniji rezultat uskladi s općim procesorom pretpostavka. To zahtijeva mnogo podešavanja i prilagođavanja navika razvoja softvera.
Druga je alternativa bila naučiti iz statistike da se petlje općenito uzimaju i uvijek skaču ako grana ide unatrag u tok uputa i nikad ne skačite ako je skok naprijed jer bi to obično bilo statistički manje vjerojatno stanje napuštanja petlja. Ovo su obje vrste predviđanja statičkog grananja, gdje se rezultat grananja predviđa u vrijeme kompajliranja.
Dinamički prediktori grana
Moderni prediktori grana su dinamični, koriste statistiku iz trenutno pokrenutog programa za postizanje boljih stopa uspješnosti predviđanja. Brojač zasićenja je osnova za sve trenutne prediktore grana. Prvo pogađanje odlučuje se statički ili nasumično. Nakon što je grana poduzeta ili nije poduzeta, taj se rezultat pohranjuje u dijelu memorije. Sljedeći put kada se ista grana pojavi, prediktor grana predviđa isti rezultat kao i prije.
To naravno rezultira dobrim stopama predviđanja za petlje. Postoje dvije verzije ovoga. Rane verzije jednostavno su koristile jedan bit podataka da naznače je li grana zauzeta ili ne. Kasnije verzije koriste dva bita za označavanje slabo ili jako prihvaćenog ili neuzetog izbora. Ova postavka još uvijek može predvidjeti rezultat pokretanja petlje ako se program na nju vrati, općenito povećavajući stope uspjeha.
Obrasci praćenja
Kako bi pratili uzorke, neki prediktori grana prate povijest odabira koji su poduzeti. Na primjer, pretpostavimo da se petlja neprestano poziva, ali se okreće samo četiri puta prije izlaska iz petlje. U tom slučaju adaptivni prediktor na dvije razine može identificirati ovaj obrazac i predvidjeti njegovo ponovno događanje. Ovo još više povećava stope uspjeha u odnosu na jednostavan zasićeni brojač. Suvremeni prediktori grana nadograđuju se na ovo dalje korištenjem neuronske mreže za uočavanje i predviđanje uzoraka.
Neki prediktori grana koriste više algoritama i zatim uspoređuju rezultate kako bi odlučili koje predviđanje koristiti. Neki sustavi prate svaku instrukciju grananja zasebno u onome što se naziva lokalno predviđanje grananja. Drugi koriste globalni sustav predviđanja grananja za praćenje svih nedavnih uputa o grananju. Oba imaju svoje koristi i nedostatke.
Zaključak
Prediktor grananja poseban je dio cjevovodnog CPU-a. Pokušava predvidjeti ishod instrukcije grananja prije nego što se stvarna instrukcija obradi. Ovo je temeljna funkcija cjevovodnog CPU-a jer omogućuje CPU-u da održava cjevovod zasićenim čak i ako nije siguran koje upute treba izvršiti. Ne nude smanjenje učinka kada su ispravni. Moderni algoritmi mogu biti točni u relativno predvidljivim radnim opterećenjima čak 97% vremena.
Ne postoji savršena metoda predviđanja, pa se implementacije razlikuju. Učinak pogrešnog predviđanja ovisi o duljini cjevovoda. Točnije, duljina cjevovoda prije nego što se može utvrditi je li predviđanje bilo pogrešno. Također ovisi o tome koliko je instrukcija u svakoj fazi cjevovoda. Moderni vrhunski stolni CPU-i imaju oko 19 stupnjeva cjevovoda i mogu pokretati najmanje četiri instrukcije istovremeno u svakom stupnju.