У скоро сваком рачунарском програму постоје делови кода који се гранају на одвојене путање. На пример, изјава иф-тхен-елсе има два могућа исхода. Ове изјаве не представљају никакав проблем за секвенцијалне процесоре, јер ЦПУ обрађује сваку команду по реду. Гране представљају велики проблем за цевоводне процесоре, пошто се више инструкција извршава одједном.
Сценарио
У случају програма са наредбом о гранању са два могућа исхода, две могуће путање кода не могу бити на истом месту. Обрада потребна за довршавање било које опције биће другачија. У супротном, програм се не би гранао. Вероватно ће постојати приличан број наредби гранања које се узимају само једном, као наредба иф.
Постоје и изјаве о гранању које формирају петљу. Иако они можда нису тако бројчано уобичајени као изјаве за једнократну употребу, генерално се статистички понављају. Може се претпоставити да је већа вероватноћа да ће вас грана вратити кроз петљу него не.
Зашто је ово проблем?
Није важно како је овај проблем формулисан у потпуно секвенцијалном процесору. То једноставно није проблем. Која ће грана бити заузета зна се пре него што се обради први део следећег упутства.
У цевоводном процесору, међутим, следећа упутства су стављена у ред чекања. Они се већ обрађују када процесор зна која грана се преузима. Како онда процесор треба да се носи са овим сценаријем? Постоји неколико опција. Најгоре је једноставно чекати и оставити цевовод у стању мировања док чека одговор на коју грану да иде. То би значило да сваки пут када имате израз гранања, увек бисте изгубили најмање онолико циклуса процесорског времена колико имате фаза у процесу.
Алтернативно, можете покушати да покренете обе опције у цевоводу и одбаците погрешан избор. Ово би имало упола мању казну од нечињења ништа, али би и даље изазвало казну перформанси за сваку изјаву о гранању. С обзиром на то да савремени ЦПУ такође могу да покрећу инструкције ван реда, потенцијално бисте могли да покушате да покренете сваку инструкцију гранања што је пре могуће. Дакле, њен исход је познат пре него што је потребан. Ова опција би могла бити од помоћи, осим што није скалабилна. Претпоставимо да имате релативно велику густину израза гранања. У том случају једноставно нећете моћи да их све покренете раније, а да немате времена мировања.
Како се ово питање заиста решава
У стварности, процесор укључује предиктор гранања. Предиктор гранања покушава да погоди који ће резултат избора гранања бити узет. Процесор тада претпоставља да је предвиђање тачно и заказује упутства. Ако је предиктор гране тачан, нема казне за учинак.
Ако предиктор гранања направи грешку, морате испрати цевовод и почети да обрађује стварни резултат. Ово резултира нешто лошијом казном за учинак него ако ништа нисте урадили и само чекали резултат. Да бисте постигли најбоље перформансе, важно је осигурати да је предиктор гране што је могуће прецизнији. Постоји низ различитих приступа овоме.
Матцхинг Цоде
У машинском коду, грана је увек избор између читања следеће инструкције или преласка на скуп инструкција негде другде. Неке ране имплементације предиктора грана су једноставно претпоставиле да ће све гране увек или никада бити заузете. Ова имплементација може имати изненађујуће добру стопу успеха ако компајлери знају ово понашање и јесу дизајниран да прилагоди машински код тако да се највероватнији резултат усклади са генералним процесором претпоставка. Ово захтева много подешавања и прилагођавања навика развоја софтвера.
Друга алтернатива је била да научимо из статистике да се петље обично узимају и увек прескачу ако грана иде уназад у ток инструкција и никада не скачите ако је скок унапред јер би то обично било статистички мање вероватно стање напуштања петља. Ово су обе врсте статичког предвиђања гранања, где се резултат гранања предвиђа у време компајлирања.
Динамички предиктори грана
Савремени предиктори грана су динамични, користе статистику из тренутно покренутог програма да би постигли боље стопе успеха предвиђања. Засићујући бројач је основа за све тренутне предикторе грана. Прва претпоставка се одлучује статички или насумично. Једном када се грана узме или не узме, тај резултат се чува у делу меморије. Следећи пут када дође до исте гране, предиктор гране предвиђа исти резултат као и раније.
Ово природно резултира добрим стопама предвиђања за петље. Постоје две верзије овога. Ране верзије су једноставно користиле један бит података да назначе да ли је грана заузета или не. Касније верзије користе два бита за означавање слабо или јако прихваћеног или неодузетог избора. Ово подешавање и даље може предвидети резултат узимања петље ако се програм врати на њу, генерално повећавајући стопе успеха.
Трацкинг Паттернс
Да би пратили обрасце, неки предиктори грана прате историју избора који су донети. На пример, претпоставимо да се петља непрекидно позива, али само четири пута пре него што се из петље изађе из петље. У том случају, адаптивни предиктор на два нивоа може идентификовати овај образац и предвидети да ће се он поново десити. Ово још више повећава стопе успеха у односу на једноставан засићени бројач. Савремени предиктори грана ово даље надограђују користећи неуронску мрежу за уочавање и предвиђање образаца.
Неки предиктори гранања користе више алгоритама и затим упоређују резултате да би одлучили које предвиђање користити. Неки системи прате сваку инструкцију гранања посебно у ономе што се зове локално предвиђање гранања. Други користе глобални систем предвиђања гранања за праћење свих недавних инструкција гранања. Оба имају своју употребу и недостатке.
Закључак
Предиктор гранања је посебан део цевоводног ЦПУ-а. Покушава да предвиди исход инструкције гранања пре него што се обради стварна инструкција. Ово је основна функција цевоводног ЦПУ-а јер омогућава ЦПУ-у да одржава цевовод засићеним чак и ако није сигуран које инструкције треба да се изврше. Они не нуде смањење перформанси када су исправни. Савремени алгоритми могу бити прецизни у релативно предвидљивим радним оптерећењима чак 97% времена.
Не постоји савршена метода предвиђања, тако да се имплементације разликују. Утицај на перформансе погрешног предвиђања зависи од дужине цевовода. Конкретно, дужина цевовода пре него што се може утврдити да ли је предвиђање било погрешно. Такође зависи од тога колико је инструкција у свакој фази цевовода. Модерни хигх-енд десктоп ЦПУ-и имају око 19 фаза цевовода и могу да покрећу најмање четири инструкције истовремено у свакој фази.