V skoraj vsakem računalniškem programu obstajajo deli kode, ki se razvejajo v ločene poti. Na primer, stavek if-then-else ima dva možna rezultata. Ti stavki ne predstavljajo nobene težave zaporednim procesorjem, saj CPE obdela vsak ukaz po vrsti. Veje predstavljajo veliko težavo za cevovodne procesorje, saj se hkrati izvaja več ukazov.
Scenarij
V primeru programa s stavkom razvejanja z dvema možnima izidoma dve možni poti kode ne moreta biti na istem mestu. Obdelava, potrebna za dokončanje obeh možnosti, bo drugačna. V nasprotnem primeru se program ne bi razvejal. Verjetno bo na voljo precej stavkov za razvejanje, ki se sprejmejo samo enkrat, na primer stavek if.
Obstajajo tudi razvejani stavki, ki tvorijo zanko. Čeprav ti morda niso tako številčno pogosti kot izjave za enkratno uporabo, se na splošno statistično ponavljajo. Lahko domnevamo, da je bolj verjetno, da vas bo veja pripeljala nazaj po zanki kot ne.
Zakaj je to problem?
Ni pomembno, kako je ta problem izražen v popolnoma sekvenčnem procesorju. To preprosto ni problem. Katera veja bo prevzeta, je znano, preden se obdela prvi del naslednjega navodila.
V cevovodnem procesorju pa so naslednja navodila postavljena v čakalno vrsto. Obdelujejo se že, ko procesor ve, katero vejo zavzame. Kako naj torej procesor obravnava ta scenarij? Obstaja nekaj možnosti. Najslabše je preprosto čakati in pustiti cevovod v mirovanju, medtem ko čaka na odgovor, na katero vejo naj gre. To bi pomenilo, da bi vsakič, ko imate stavek razvejanja, vedno izgubili vsaj toliko ciklov procesorskega časa, kot imate stopenj v cevovodu.
Druga možnost je, da poskusite zagnati obe možnosti v pripravi in zavržete napačno izbiro. To bi imelo polovično kazen, če ne bi storili ničesar, vendar bi še vedno povzročilo kazen učinkovitosti za vsak stavek o razvejanju. Glede na to, da lahko sodobni CPU-ji izvajajo navodila tudi brez vrstnega reda, bi lahko poskusili zagnati vsako razvejano navodilo čim prej. Torej je njegov rezultat znan, preden je potreben. Ta možnost bi lahko bila koristna, le da ni razširljiva. Recimo, da imate razmeroma visoko gostoto razvejanih stavkov. V tem primeru preprosto ne boste mogli zagnati vseh zgodaj, ne da bi imeli nekaj časa nedejavnosti.
Kako se ta težava v resnici rešuje
V resnici procesor vključuje napovedovalec vej. Prediktor razvejanja poskuša uganiti, kateri rezultat izbire razvejanja bo uporabljen. Procesor nato domneva, da je napoved pravilna, in načrtuje navodila. Če je napovedovalec veje točen, ni kazni za uspešnost.
Če napovedovalec veje naredi napako, morate splakniti cevovod in začeti obdelavo dejanskega rezultata. Posledica tega je nekoliko slabša kazen za uspešnost, kot če ne storite ničesar in samo čakate na rezultat. Da bi dosegli najboljšo zmogljivost, je pomembno zagotoviti, da je napovedovalec veje čim natančnejši. Obstaja vrsta različnih pristopov k temu.
Ustrezna koda
V strojni kodi je veja vedno izbira med branjem naslednjega navodila ali skokom na nabor navodil drugje. Nekatere zgodnje izvedbe napovedovalcev vej so preprosto domnevale, da bodo vse veje vedno ali nikoli zavzete. Ta izvedba ima lahko presenetljivo dobro stopnjo uspešnosti, če prevajalniki poznajo to vedenje in so zasnovan za prilagajanje strojne kode, tako da se najverjetnejši rezultat ujema s splošnim procesorjem predpostavka. To zahteva veliko prilagajanja in prilagajanja navad pri razvoju programske opreme.
Druga možnost je bila, da se iz statistike naučimo, da se zanke na splošno uporabljajo in vedno skočijo, če gre veja nazaj v tok navodil in nikoli ne skočite, če je skok naprej, ker bi bilo to običajno statistično manj verjetno stanje zapuščanja zanka. To sta obe vrsti statične napovedi veje, kjer je rezultat veje predviden v času prevajanja.
Dinamični napovedovalci vej
Sodobni napovedovalci vej so dinamični in uporabljajo statistične podatke iz trenutno delujočega programa za doseganje boljših stopenj uspešnosti napovedi. Števec nasičenja je osnova za vse trenutne napovedovalce vej. Prvo ugibanje se določi statično ali naključno. Ko je veja vzeta ali ne vzeta, se ta rezultat shrani v del pomnilnika. Naslednjič, ko pride ta ista veja, napovedovalec veje napove enak rezultat kot prej.
To seveda povzroči dobre stopnje napovedovanja zank. Obstajata dve različici tega. Prve različice so preprosto uporabile en sam bit podatkov, da bi pokazale, ali je bila veja prevzeta ali ne. Kasnejše različice uporabljajo dva bita za označevanje šibko ali močno sprejete ali ne sprejete izbire. Ta nastavitev lahko še vedno predvidi rezultat izvajanja zanke, če se program vrne k njej, kar na splošno poveča stopnjo uspešnosti.
Vzorci sledenja
Da bi sledili vzorcem, nekateri napovedovalci vej spremljajo zgodovino sprejetih odločitev. Na primer, predpostavimo, da se zanka neprekinjeno kliče, vendar se le štirikrat obrne, preden se prekine iz zanke. V tem primeru lahko dvonivojski prilagodljivi napovedovalec identificira ta vzorec in napove, da se bo ponovil. To še dodatno poveča stopnje uspeha v primerjavi s preprostim nasičenim števcem. Sodobni napovedovalci vej nadgrajujejo to še naprej z uporabo nevronske mreže za odkrivanje in napovedovanje vzorcev.
Nekateri napovedovalci vej uporabljajo več algoritmov in nato primerjajo rezultate, da se odločijo, katero napoved uporabiti. Nekateri sistemi sledijo vsakemu navodilu razvejanja posebej v tako imenovanem lokalnem predvidevanju razvejanja. Drugi uporabljajo globalni sistem za predvidevanje razvejanja za sledenje vsem nedavnim navodilom za razvejanje. Oba imata svojo uporabo in slabosti.
Zaključek
Prediktor vej je poseben del cevovodnega CPE-ja. Poskuša predvideti izid ukaza razvejanja, preden se dejanski ukaz obdela. To je glavna funkcija cevovodnega CPE-ja, saj omogoča CPE-ju, da ohranja cevovod nasičen, tudi če ni prepričan, katera navodila je treba izvesti. Ne nudijo zmanjšanja učinkovitosti, če so pravilni. Sodobni algoritmi so lahko natančni v relativno predvidljivih delovnih obremenitvah kar 97 % časa.
Popolne metode napovedovanja ni, zato se izvedbe razlikujejo. Vpliv napačne napovedi na zmogljivost je odvisen od dolžine cevovoda. Natančneje, dolžina cevovoda, preden se lahko ugotovi, ali je bila napoved napačna. Odvisno je tudi od tega, koliko navodil je v posamezni stopnji cevovoda. Sodobni vrhunski namizni procesorji imajo približno 19 stopenj cevovoda in lahko izvajajo vsaj štiri navodila hkrati v vsaki stopnji.