У рачунарској архихектури, предвиђање гранања је дигитално коло које покушава да претпостави којим ће путем грана (тј. if-then-else структура) ићи пре него што то буде засигурно познато. Сврха предвиђања гранања је да побољша проток у проточној обради инструкција. Предвиђање гранања има кључну улогу у постизању високих ефикасних перформанси у многим микропроцесорским архихектурама за проточну обарду као што је x86.
Двосмерно гранање се обично спроводи са инструкцијом која се зове условни скок. Условни скок може да се "не узме" и да настави извршење са првом граном кода који следи одмах након условног скока - или се може "узети" и скочити на друго место у програмској меморији где је друга грана кода меморисана.
мини|375px|десно|Слика 1: Пример 4 фазе проточне обраде. Обојени квадратићи представљају инструкције независне једна од друге Није познато да ли ће сигурно доћи до условног скока или не, све док се услов не израчуна и условни скок не пређе у фазу извршења инструкција у проточној обради (види слику 1).
Ако не би било предвиђања гранања, процесор би морао да чека да инструкција условног скока прође фазу извршавања пре него што следећа инструкција може да уђе у фазу у проточне обраде. Предвиђање гранања покушава да избегне ово губљење времена покушавајући да погоди да ли ће до условног скока највероватније доћи или не. Грана, за коју се поретпостави да је најбоља могућа, се учита и спекулативно изврши. Ако се касније испоставило да је претпоставка била погрешна онда се спекулативно извршене или делимично извршене инструкције одбаце и проточна обрада почиње испочетка са исправним гранама, изазивајући одлагање.
Време које је изгубљено у случају промашаја предвиђања гранања једнако је броју фаза у проточној обради од донете фазе до фазе извршења. Савремени микропроцесори имају тенденцију да имају прилично дубоку проточну обраду тако да је кашњење промашаја предвиђања између 10. и 20. тактног сигнала. Што дубља проточна обрада, дужа је потреба за добро предвиђање гранања.
Први пут када условна инструкција скока наиђе, нема много информација на којима је засновано предвиђање. Али предвиђање гранања води евиденцију о томе да ли су гране узете или не. Када наиђе условни скок који је виђен неколико пута, онда он може да заснује предвиђање на основу историје. Предиктор гранања може, на пример, да препозна да ли се условни скок чешће узима или се не узима, или да се узима сваки други пут.
Предвиђање гранања није исто што и циљно предвиђање гранања. Предвиђање гранања покушава да погоди да ли ће доћи до условног скока или не. Циљ предвиђања гранања покушава да погоди мету узетог условног или безусловног скока пре него што се израчуна помоћу декодирања и извршавања саме инструкције. Предвиђање гранања и циљ предвиђања гранања се често комбинују у истом колу.
Имплементација
Статично предвиђање Статичко предвиђање је најједноставнија техника предвиђања гранања, јер се не ослаа на информације о динамичкој историји кода који се извршава. Уместо тога, предвиђа исход гране само на основу инструкција гране.
Ране имплементације SPARC и MIPS (две од првих комерцијалних RISC архихектура) користи један правац статичког предвиђања гранања: оне увек предвиђају да условни скок неће бити узет (неће доћи до условног скока), тако да, оне увек донесу следећу секвенцијалну инструкцију. Само онда када је грана или скок оцењен и пронађен да би се узео, показивач инструкције се поставља на не-секвенцијалну адресу.
Оба процесора оцењују гранање у фази декодирања и имају доношење информација у једном циклусу. Као резултат тога, циљно предвиђање гранања је било дугачко два циклуса, а машина ће увек донети инструкцију одмах после једне предузете гране. Обе архитектуре дефинишу слот одлагања гранања а у циљу искоришћавања ових учитаних инструкција.
Сложенији облик статичког предвиђања претпоставља да ће се узети гране које иду уназад, а гране које су напред-указујуће гране неће се узети. Назадна грана је она која има циљну адресу која је нижа од сопствене адресе. Ова техника може да помогне са предвиђањем тачности петљи, које су обично backward-pointing гране, и чешће су узете него не.
Неки процесори омогућавају да се погодак предвиђања гранања убаци у код, да каже да ли статичко предвиђање треба да се узме или не. Интел Пентиум 4 прихвата погодак предвиђања гранања, док је ова функција напуштена у каснијим процесорима.
Статично предвиђање се користи као fall-back техника у неким процесорима са динамичним предвиђањем гранања, када не постоји било каква информација за коришћење динамичког предвиђања. Оба Моторола MPC7450 (G4e) и Интел Пентиум 4 користе ову технику као fall-back.The Pentium 4 and the G4e: an Architectural Comparison, Ars Technica
Предвиђање следеће линије Бројач засићења или бимодални предсказивач је коначан аутомат са четири фазе: 600px|мини|десно|Слика 2: Дијаграм фазе 2-битног бројача засићења
Снажно не узето Слабо не узето Слабо узето Снажно узето
Када је грана оцењена, одговарајући машина се ажурира. Гране које се оцењују као не узете, смањују ка фази снажно не узето, а гране оцењене као узете, расту ка фази снажно узето. Предност од двобитног бројача преко једно-битне шеме је то да условни скок мора два пута да одступа од онога што је урађено у прошлости пре предвиђања промена. На пример, условни скок затворене-петље је пре један промашак предвиђања него два.
Оригинални, не-MMX Интел Пентиум процесор користи бројач засићења, мада са несавршеном имплементацијом.
На SPEC'89 ознакама, веома велики бимодални предиктори су засићени на 93,5% тачности, једном свака мапа гранања на јединствен бројач.S. McFarling Combining Branch Predictors Digital Western Research Lab (WRL) Technical Report, TN-36, 1993
Табела предвиђања је индексирана са инстукцијом адресних битова, тако да процесор може да донесе предвиђање за сваку инструкцију пре него што се инструкција декодира.
Прилагодљиви предвиђач са Два-нивоа 420px|мини|десно|Слика 3: Two-level adaptive branch predictor. Сваки унос у историју шаблона табеле представља 2-битни бројач засићења типа приказаног на слици 2.
Ако има три if израза у коду, трећи if израз може се узети у зависности да ли су претходна два узета или не. У таквом сценарију прилагодљиви предвиђач са два-нивоа ради ефикасније него бројач засићења.
Условни скокови који се узимају сваки други пут, или имају неки други периодични редовни шаблони, нису добро предвиђени од стане бројача засићења. Прилагодљиви предвиђач са два-нивоа памти историју последњих n појављивања гране и користи један бројач засићења за сваки од могућих 2n шаблона. Метод је илустрован на слици 3.
Узмимо на пример да је n = 2. То значи да су две последње појаве гране меморисане у 2-битном померачком регистру. Ова историја регистра гранања може имати 4 различите бинарне вредности: 00, 01, 10, и 11; где 0 значи "није узето" и 1 значи "узето“. Сада, ми правимо табелу историје шаблона са четири уноса, један за сваки од 2n = 4 могућих грана историје. Сваки унос у табелу историје шаблона садржи 2-битни бројач засићења истог типа као на слици 2. Регистар историје гранања се користи за одабир којег од 4 бројача засићености ће се користити. Ако је историја 00 онда се користи први бројач. Ако је историја 11 онда се користи последњи бројач од сва 4 бројача.
Претпоставимо, на пример, да је условни скок узет сваки трећи пут. Секвенца гране је 001001001... У овом случају, унос броја 00 у табелу шаблона историје ће ићи у фазу "снажно узети", указујући да после нуле иде један. Улаз број 01 ће ићи у фазу "снажно не узима", што указује да је после 01 долази 0. Исти је случај и са уносом броја 10, док се унос броја 11 никада не користи, јер никад постоје две узастопне јединице.
Опште правило за прилагодљиви предвиђач са два-нивоа са n-битном историјом је то што он може да предвиди сваку секвенцу понављања са било којим периодом ако су сви n-битни поднизови другачији.
Предност прилагодљивог предвиђача са два-нивоа је што може брзо да научи да предвиди произвољан шаблон понављања. Овај метод је измислио T.-Y. Yeh и Yale Patt на Универзитету у Мичигену. Од првобитног објављивања 1991, овај метод је постао веома популаран. Варијанте овог метода предвиђања се користе данас у већини савремених микропроцесора.
Локално предвиђање гранања Локално предвиђање гранања има посебан бафер за историју за сваки условни скок инструкција. Он може да користи прилагодљиви предвиђач са два-нивоа. Бафер за историју је посебан за сваки условни скок инструкција, док табела историје шаблон може бити одвојена или може да се дели између свих условних скокова.
Интел Pentium MMX, Pentium II и Pentium III имају локално предвиђање гранања са локалном 4-битном историјом и табелу историје локалног шаблона са 16 уноса за сваки условни скок.
На SPEC'89 ознакама, веома велика локална предвиђања су засићена на 97,1% тачности.S. McFarling Combining Branch Predictors Digital Western Research Lab (WRL) Technical Report, TN-36, 1993:8
Глобално предвиђање гранања Глобално предвиђање гранања не води посебну евиденцију историје за сваки условни скок. Уместо тога држи заједничку историју свих условних скокова. Предност заједничке историје јесте да је било која корелација између различитих условних скокова део прављења предвиђања. Недостатак је да се историја стапа са небитним информацијама, ако су различити условни скокови у корелацији, и да бафер историје не може да садржи битове из исте бранше, ако постоје многи друге гране између. Оно може да користи прилагодљиви предвиђач са два-нивоа.
Ова шема је једино боља од шеме бројача засићења за велике табеле, а ретко је добра као локално предвиђање. Бафер историје мора бити дужи како би направио добро предвиђање. Величина табле историје шаблона расте експоненцијално са величином бафера историје. Дакле, велики шаблон табеле историје мора да се дели између свих условних скокова.
Прилагодљиви предвиђач са два-нивоа дс глобално заједничким историјским бафером и образац табеле историје се зове "gshare" продвиђач, ако његов xors глобалне табеле историје и гране PC-а, и "gselect" ако их спаја. Глобално предвиђања се користи у AMD микропроцесориме и Intel Pentium M, Core и Core 2.
Измешано предвиђање гранања Измешано предвиђање гранања комбинује локалне и глобалне принципе предвиђања помоћу спајања локалне и глобалне историје гранања, вероватно са неким битовима из бројача програма. Тестови показују да VIA Nano процесор може да се користи ову технику.
Предиктор усаглашавања Предиктор усаглашавања је прилагодљиви предвиђач са два-нивоа са глобалном дељеном историјом бафера и табелом шаблона историје, и додатни локални бројаћ засићења. Излази локалног и глобалног предвиђања су XOR-овани једни са другима да дају коначно предвиђање. Циљ је да се смање аргументи у табели шаблона историје где се деси да две гране са супротним предвиђањем деле исти унос у табели шаблона историје.
Предиктор усаглашавања се користио у првој верзији Интел Пентијум 4, али је касније напуштен.
Хибридни предвиђач Хибридни предвиђач, такође се назива комбиновани предвиђач, имплементира више од једног механизма предвиђања. Коначно предвиђање се заснива или на мета-предиктору да памти који од предиктора је направио најбоље предвиђање у прошлости, или на већини укупних функција које су базиране на непарним бројевима различитих предвиђача.
Scott McFarling је предложио комбиновање предвиђање гранања и свом раду 1993. године.McFarling (1993). "Combining Branch Predictors " – introduces combined predictors.
На SPEC'89 ознакама, такав предиктор је добар као и локални предиктор.