Peaaegu igas arvutiprogrammis on koodi osi, mis hargnevad eraldi radadeks. Näiteks kui-siis-else-lausel on kaks võimalikku tulemust. Need avaldused ei tekita järjestikustele protsessoritele probleeme, kuna CPU töötleb kõiki käske järjekorras. Filiaalid kujutavad endast konveierprotsessorite jaoks suurt probleemi, kuna korraga täidetakse mitu käsku.
Stsenaarium
Kahe võimaliku tulemusega hargneva lausega programmi puhul ei saa kaks võimalikku kooditeed olla samas kohas. Mõlema valiku täitmiseks vajalik töötlemine on erinev. Vastasel juhul programm ei hargneks. Tõenäoliselt on päris palju hargnevaid avaldusi, mida võetakse ainult üks kord, näiteks if-lause.
On ka hargnevaid väiteid, mis moodustavad silmuse. Kuigi need ei pruugi olla arvuliselt nii tavalised kui ühekordselt kasutatavad väited, korratakse neid üldiselt statistiliselt. Võib eeldada, et on tõenäolisem, et mõni oks viib teid ringi tagasi, kui mitte.
Miks see probleem on?
Pole tähtis, kuidas see probleem on täielikult järjestikuses protsessoris sõnastatud. See lihtsalt ei ole probleem. Milline haru võetakse, on teada enne järgmise juhise esimese osa töötlemist.
Konveierprotsessoris on aga järgmised juhised järjekorras. Neid juba töödeldakse, kui protsessor teab, milline haru võetakse. Kuidas peaks protsessor selle stsenaariumiga hakkama saama? On paar võimalust. Kõige hullem on lihtsalt ootamine ja torujuhtme jõude jätmine, kuni see ootab vastust, millise haru pealt võtta. See tähendaks, et iga kord, kui teil on hargnemislause, kaotate alati vähemalt sama palju protsessori aja tsükleid, kui teil on ettevalmistamisel etappe.
Teise võimalusena võite proovida käivitada mõlemad valikud ja loobuda valest valikust. See tähendaks poole väiksemat karistust kui mitte midagi tegemata, kuid iga hargneva avaldusega kaasneb siiski tulemustrahv. Arvestades, et kaasaegsed CPU-d võivad käske käivitada ka korrast ära, võite proovida käivitada kõik hargnemisjuhised niipea kui võimalik. Seega on selle tulemus teada enne, kui seda vaja läheb. See valik võib olla kasulik, välja arvatud juhul, kui see pole skaleeritav. Oletame, et teil on suhteliselt palju hargnevaid väiteid. Sel juhul ei saa te lihtsalt neid kõiki varakult käivitada ilma tühikäiguta.
Kuidas seda probleemi tegelikult käsitletakse
Tegelikkuses sisaldab protsessor haru ennustajat. Haru ennustaja püüab ära arvata, milline hargnemisvaliku tulemus võetakse. Seejärel eeldab protsessor, et ennustus on õige, ja ajastab juhised. Kui haru ennustaja on täpne, siis sooritustrahvi ei määrata.
Kui haru ennustaja teeb vea, peate torujuhtme loputama ja alustama tegeliku tulemuse töötlemist. Selle tulemuseks on pisut halvem sooritustrahv, kui mitte midagi teha ja lihtsalt tulemust oodata. Parima jõudluse saavutamiseks on oluline tagada, et haru ennustaja oleks võimalikult täpne. Selleks on mitmeid erinevaid lähenemisviise.
Sobiv kood
Masinkoodis on haru alati valik, kas lugeda järgmist käsku või hüpata mujal asuvate käskude komplekti. Mõned harude ennustajate varased rakendused eeldasid lihtsalt, et kõiki harusid võetakse alati või ei võeta kunagi. Sellel teostusel võib olla üllatavalt hea eduprotsent, kui kompilaatorid seda käitumist teavad ja on mõeldud masinkoodi kohandamiseks nii, et kõige tõenäolisem tulemus ühtiks protsessori üldisega oletus. See nõuab palju tarkvaraarenduse harjumuste häälestamist ja kohandamist.
Teine võimalus oli õppida statistikast, et tavaliselt võetakse silmuseid ja hüppatakse alati, kui haru läheb tagasi käsuvoogu ja ärge kunagi hüppage, kui hüpe on ettepoole, sest see oleks tavaliselt statistiliselt vähem tõenäoline silmus. Need on mõlemad staatilise haru ennustamise tüübid, kus haru tulemust ennustatakse kompileerimise ajal.
Dünaamilised haru ennustajad
Kaasaegsed haru ennustajad on dünaamilised, kasutades parema prognoosimise edukuse saavutamiseks praegu töötava programmi statistikat. Küllastusloendur on kõigi praeguste harude ennustajate aluseks. Esimene arvamine otsustatakse staatiliselt või juhuslikult. Kui haru on võetud või mitte võetud, salvestatakse see tulemus mälu ossa. Järgmine kord, kui sama haru ilmub, ennustab haru ennustaja sama tulemust kui varem.
See annab loomulikult head ennustusmäärad silmustele. Sellest on kaks versiooni. Varased versioonid kasutasid lihtsalt ühte andmebitti, et näidata, kas haru võeti või mitte. Hilisemates versioonides kasutatakse kaht bitti, et näidata nõrgalt või tugevalt võetud või mitte võetud valikut. See seadistus võib siiski ennustada tsükli võtmise tulemust, kui programm selle juurde naaseb, suurendades üldiselt edukuse määra.
Jälgimismustrid
Mustrite jälgimiseks jälgivad mõned haru ennustajad tehtud valikute ajalugu. Oletame näiteks, et tsüklit kutsutakse pidevalt, kuid enne tsüklist väljamurdmist teeb see ainult neli korda ringi. Sel juhul saab kahetasandiline adaptiivne ennustaja selle mustri tuvastada ja ennustada, et see juhtub uuesti. See suurendab edukuse määra veelgi lihtsal küllastunud loenduril. Kaasaegsed harude ennustajad tuginevad sellele veelgi, kasutades mustrite tuvastamiseks ja ennustamiseks närvivõrku.
Mõned haru ennustajad kasutavad mitut algoritmi ja võrdlevad seejärel tulemusi, et otsustada, millist ennustust kasutada. Mõned süsteemid jälgivad iga hargnemisjuhist eraldi nn kohaliku haru prognoosis. Teised kasutavad kõigi hiljutiste hargnemisjuhiste jälgimiseks globaalset haruennustussüsteemi. Mõlemal on oma kasutusalad ja varjuküljed.
Järeldus
Haru ennustaja on konveierprotsessori eriline osa. See püüab ennustada hargneva käsu tulemust enne tegeliku käsu töötlemist. See on konveierprotsessori põhifunktsioon, kuna see võimaldab CPU-l hoida konveieri küllastatuna isegi siis, kui ta pole kindel, milliseid juhiseid tuleb täita. Need ei vähenda jõudlust, kui need on õiged. Kaasaegsed algoritmid võivad suhteliselt prognoositava töökoormuse korral olla täpsed kuni 97% ajast.
Täiuslikku ennustamismeetodit pole olemas, seega on rakendused erinevad. Vale prognoosi tegemise mõju tulemuslikkusele sõltub torujuhtme pikkusest. Täpsemalt, torujuhtme pikkus enne seda, kui saab kindlaks teha, kas ennustus oli vale. See sõltub ka sellest, kui palju juhiseid on igas torujuhtme etapis. Kaasaegsetel tipptasemel lauaarvuti protsessoritel on umbes 19 konveieri etappi ja igas etapis saab samaaegselt käitada vähemalt nelja käsku.