Gandrīz jebkurā datorprogrammā ir koda daļas, kas sazarojas atsevišķos ceļos. Piemēram, ja-then-else paziņojumam ir divi iespējamie rezultāti. Šie paziņojumi nerada nekādas problēmas secīgajiem procesoriem, jo centrālais procesors apstrādā katru komandu kārtībā. Filiāles rada lielas problēmas konveijera procesoriem, jo vienlaikus tiek izpildītas vairākas instrukcijas.
Scenārijs
Programmā ar sazarojošu paziņojumu ar diviem iespējamiem rezultātiem divi iespējamie koda ceļi nevar atrasties vienā un tajā pašā vietā. Apstrāde, kas nepieciešama, lai pabeigtu jebkuru iespēju, būs atšķirīga. Pretējā gadījumā programma netiktu sazarota. Visticamāk, būs diezgan daudz sazarotu paziņojumu, kas tiek izmantoti tikai vienu reizi, piemēram, ja paziņojums.
Ir arī sazarojoši paziņojumi, kas veido cilpu. Lai gan tie skaitliski var nebūt tik izplatīti kā vienreiz lietojami paziņojumi, parasti tie statistiski atkārtojas. Var pieņemt, ka ir lielāka iespēja, ka zars jūs aizvedīs atpakaļ ap cilpu, nekā nē.
Kāpēc tā ir problēma?
Nav svarīgi, kā šī problēma ir formulēta pilnībā secīgā procesorā. Tā vienkārši nav problēma. Kurš atzars tiks ņemts, ir zināms pirms nākamās instrukcijas pirmās daļas apstrādes.
Tomēr konveijera procesorā rindā tiek ievietotas šādas instrukcijas. Tie jau tiek apstrādāti, kad procesors zina, kura filiāle tiek ņemta. Tātad, kā procesoram būtu jārīkojas šajā scenārijā? Ir dažas iespējas. Sliktākais ir vienkārši gaidīt un atstāt cauruļvadu dīkstāvē, kamēr tas gaida atbildi, pa kuru atzaru ņemt. Tas nozīmētu, ka katru reizi, kad jums ir sazarojuma paziņojums, jūs vienmēr zaudētu vismaz tik daudz procesora laika ciklu, cik jums ir sagatavošanās posmi.
Varat arī mēģināt palaist abas opcijas un atmest nepareizo izvēli. Tas nozīmētu pusi no soda par neko nedarīšanu, bet par izpildes sodu par katru sazaroto paziņojumu. Ņemot vērā, ka mūsdienu CPU var arī palaist instrukcijas, kas nav kārtībā, jūs varētu mēģināt palaist katru atzarošanas instrukciju pēc iespējas ātrāk. Tātad tā iznākums ir zināms, pirms tas ir nepieciešams. Šī opcija varētu būt noderīga, izņemot to, ka tā nav mērogojama. Pieņemsim, ka jums ir salīdzinoši liels sazarojumu apgalvojumu blīvums. Tādā gadījumā jūs vienkārši nevarēsit tos visus palaist agri, ja jums nebūs dīkstāves.
Kā šī problēma patiešām tiek risināta
Patiesībā procesors ietver zaru prognozētāju. Atzaru prognozētājs mēģina uzminēt, kurš sazarošanas izvēles rezultāts tiks pieņemts. Pēc tam procesors pieņem, ka prognoze ir pareiza, un ieplāno instrukcijas. Ja zaru prognozētājs ir precīzs, izpildes soda nav.
Ja atzarojuma prognozētājs pieļauj kļūdu, jums ir jāizskalo konveijera un jāsāk apstrādāt faktisko rezultātu. Tā rezultātā tiek uzlikts nedaudz sliktāks sods par sniegumu nekā nekas nedarīts un tikai rezultāta gaidīšana. Lai iegūtu vislabāko veiktspēju, ir svarīgi nodrošināt, lai zaru prognozētājs būtu pēc iespējas precīzāks. Tam ir dažādas pieejas.
Atbilstošs kods
Mašīnkodā filiāle vienmēr ir izvēle starp nākamās instrukcijas lasīšanu vai pāreju uz instrukciju kopu citur. Dažas agrīnas zaru prognozētāju ieviešanas vienkārši pieņēma, ka visas filiāles vienmēr vai nekad netiks izmantotas. Šai ieviešanai var būt pārsteidzoši labs panākumu līmenis, ja kompilatori zina šo uzvedību un zina paredzēts, lai pielāgotu mašīnas kodu tā, lai visticamākais rezultāts atbilstu procesora vispārīgajam rezultātam pieņēmums. Tas prasa daudz noregulēšanas un programmatūras izstrādes paradumu pielāgošanas.
Vēl viena alternatīva bija mācīties no statistikas, ka cilpas parasti tiek izmantotas un vienmēr lec, ja zars virzās atpakaļ instrukciju straumi un nekad nelēkt, ja lēciens ir uz priekšu, jo tas parasti būtu statistiski mazāk ticams stāvoklis, kad cilpa. Tie ir abi statiskās zaru prognozēšanas veidi, kur zara rezultāts tiek prognozēts kompilēšanas laikā.
Dinamiskie zaru prognozētāji
Mūsdienu zaru prognozētāji ir dinamiski, izmantojot pašlaik darbojošās programmas statistiku, lai sasniegtu labākus prognozēšanas panākumus. Piesātinājuma skaitītājs ir visu pašreizējo zaru prognozētāju pamats. Pirmais minējums tiek izlemts statiski vai nejauši. Kad zars ir paņemts vai nav ņemts, šis rezultāts tiek saglabāts atmiņas daļā. Nākamajā reizē, kad tiks parādīts tas pats atzars, zaru prognozētājs prognozē tādu pašu rezultātu kā iepriekš.
Tas, protams, rada labus cilpu prognozēšanas rādītājus. Tam ir divas versijas. Agrīnās versijas vienkārši izmantoja vienu datu bitu, lai norādītu, vai filiāle tika izmantota vai nē. Vēlākās versijās tiek izmantoti divi biti, lai norādītu vāji vai stipri pieņemtu vai nepieņemtu izvēli. Šī iestatīšana joprojām var paredzēt cilpas izņemšanas rezultātu, ja programma atgriežas pie tā, kopumā palielinot panākumu līmeni.
Izsekošanas modeļi
Lai izsekotu modeļiem, daži zaru prognozētāji seko līdzi veikto izvēļu vēsturei. Piemēram, pieņemsim, ka cilpa tiek izsaukta nepārtraukti, bet tā tiek izsaukta tikai aptuveni četras reizes, pirms izkļūt no cilpas. Tādā gadījumā divu līmeņu adaptīvais prognozētājs var identificēt šo modeli un paredzēt, ka tas atkārtosies. Tas vēl vairāk palielina panākumu līmeni, izmantojot vienkāršu piesātinātu skaitītāju. Mūsdienu zaru prognozētāji to papildina, izmantojot neironu tīklu, lai noteiktu un prognozētu modeļus.
Daži zaru prognozētāji izmanto vairākus algoritmus un pēc tam salīdzina rezultātus, lai izlemtu, kuru prognozi izmantot. Dažas sistēmas izseko katru atzarošanas norādījumu atsevišķi tā sauktajā vietējās filiāles prognozēšanā. Citi izmanto globālo atzaru prognozēšanas sistēmu, lai izsekotu visiem nesenajiem atzarošanas norādījumiem. Abiem ir savi lietojumi un negatīvās puses.
Secinājums
Atzaru prognozētājs ir īpaša konveijera CPU daļa. Tas mēģina paredzēt sazarošanas instrukcijas iznākumu, pirms tiek apstrādāta faktiskā instrukcija. Šī ir konveijera CPU pamatfunkcija, jo tā ļauj CPU uzturēt konveijera piesātinājumu pat tad, ja nav pārliecināts, kādi norādījumi ir jāizpilda. Tie nesamazina veiktspēju, ja tie ir pareizi. Mūsdienu algoritmi var būt precīzi salīdzinoši paredzamās darba slodzēs pat 97% laika.
Nav ideālas prognozēšanas metodes, tāpēc ieviešanas veidi atšķiras. Nepareizas prognozes ietekme uz veiktspēju ir atkarīga no cauruļvada garuma. Konkrēti, cauruļvada garums, pirms var noteikt, vai prognoze bija nepareiza. Tas ir atkarīgs arī no tā, cik instrukciju ir katrā cauruļvada posmā. Mūsdienu augstākās klases galddatoru centrālajiem procesoriem ir aptuveni 19 konveijera posmi, un katrā posmā tie var vienlaikus izpildīt vismaz četras instrukcijas.