Programovanie v jazyku symbolických adries

Dynamické spracovanie inštrukcií je súbor metód, ktorých cieľom je zvýšiť efektívnosť práce procesora tým, že sa predpovedá a mení poradie vykonávania inštrukcií. O spracovaní inštrukcií mimo poradia sme hovorili v predchádzajúcej kapitole. V tejto kapitole sa zameriame na predpovedanie skokov.

Predpovedanie skokov zohráva svoju úlohu v prípade nesekvenčného vykonávania programu v dôsledku príkazu skoku. Pretože príkaz skoku prenáša riadenie do iného miesta programu, môže sa stať, že príslušné inštrukcie nie sú v okamihu potreby preložené a pripravené na vykonanie. Úlohou predpovedania skokov je na základe správania sa programu v minulosti predvídať, na akej inštrukcii bude vykonávanie programu pokračovať, aby sa ďalšie inštrukcie mohli vybrať z pamäti a dekódovať skôr, ako sa vykoná inštrukcia skoku. Táto snaha je opodstatnená, lebo skoky predstavujú 15 až 25 % všetkých vykonávaných inštrukcií.

V ďalšom výklade bude reč o podmienených a nepodmienených skokoch. Inštrukciami skoku sa podrobne zaoberá kapitola Skokové inštrukcie. Nateraz bude stačiť, ak si pod nepodmieneným skokom predstavíme príkaz goto v Pascale. Príkazy vetvenia výpočtu if a case a príkazy cyklu for, repeat a while preloží prekladač pomocou podmienených skokov. V tomto prípade sa skok vykoná, ak je splnená nejaká logická podmienka.

Zdržaniu v práci procesora sa dá ľahšie zabrániť pri nepodmienených skokoch. Nepodmienený skok nezávisí od výsledku predchádzajúcej operácie, preto vzápätí po jeho preddekódovaní procesor vie, na ktorej inštrukcii bude vykonávanie programu pokračovať a výberová jednotka môže hneď priniesť inštrukciu z adresy, ktorá bola operandom inštrukcie nepodmieneného skoku.

Pri podmienených skokoch je situácia zložitejšia, pretože až v okamihu vyhodnotenia podmienky skoku procesor vie, na ktorej inštrukcii má pokračovať. Môže však predvídať, ako sa podmienka skoku vyhodnotí. Vychádza sa pritom z predpokladu, že obidve vetvy podmieneného skoku nemajú rovnakú pravdepodobnosť vykonania. Ak sa podmienený skok opakuje, je viac pravdepodobné, že sa jeho podmienka vyhodnotí rovnako ako v predchádzajúcom prípade. Táto metóda predpovedania skokov sa nazýva dynamická predikcia. Predikčná logika si v tabuľke histórie skokov (Branch History Table - BHT) pamätá niekoľko desiatok až stoviek posledných skokových inštrukcií, presnejšie vývoj, čiže udalosti, ktoré pri nich nastali (či sa skok vykonal, alebo nie). Indexom do tabuľky je niekoľko (povedzme k) najnižších bitov adresy skokovej inštrukcie. Potom BHT má 2^k položiek.

Na dynamické predpovedanie skokov existuje viacero metód. V  architektúre Haswell sa používa dvojúrovňová predikcia. Dvojúrovňová predikcia znamená, že každá položka BHT má dve úrovne (obr. 3): na 1. úrovni je 4-bitový posuvný register, ktorý si pamätá 4 posledné udalosti: ak sa skok vykonal, zapíše sa do najnižšieho bitu 1, ak sa nevykonal, zapíše sa 0. Pred každou aktualizáciou sa register posunie doľava. Obsah tohto registra sa vyhodnotí ako poradové číslo čítača na 2. úrovni. Každý z čítačov na 2. úrovni sa môže nachádzať v jednom zo 4 stavov. Prechodový diagram medzi stavmi je znázornený na obr. 3 vpravo. Šípka so znamienkom plus znamená prechod v prípade, že sa podmienka skoku vyhodnotila ako pravdivá a skok sa vykonal, znamienko mínus znamená, že skok sa nevykonal. Ak je hodnota čítača 0 alebo 1, jednotka predpovedania skokov predpokladá, že skok sa nevykoná, v stavoch 2 a 3 sa predpokladá, že skok sa vykoná. Počiatočná hodnota všetkých čítačov je 0.

Obr. 3. Dvojúrovňová dynamická predikcia

Dvojúrovňová predikcia je presnejšia ako jednoúrovňová, lebo dovoľuje rozpoznať opakujúce sa vzory. Napríklad predpokladajme, že skok sa vykoná každý druhý raz, teda jeho história bude 10101010... Čítač s indexom 0101 zostane stále na svojej pôvodnej hodnote (0), teda stále bude správne predpokladať, že skok sa nevykoná. Čítač s číslom 1010 sa po troch iteráciách dostane do stavu 3 a v ňom už zostane, preto jeho predpoveď stále bude, že skok sa vykoná.

Okrem BHT väčšina prediktorov používa ešte tabuľku cieľových adries (Branch Target Buffer - BTB), ktorá obsahuje použité cieľové adresy skokov. Procesor nemusí čakať na výpočet cieľovej adresy, ale v prípade kladnej predikcie môže prinášať inštrukcie z cieľovej adresy zaznamenanej v BTB.

Ak sa podmienený skok doteraz nevyskytol, t.j. nemá položku v BHT a BTB, použije sa tzv. statická predikcia. Táto vychádza zo štatistických odhadov chovania typických vetviacich inštrukcií. Príkladom môže byť vyhodnotenie riadiacej premennej na konci cyklu. Oveľa pravdepodobnejšie je nové pokračovanie cyklu návratom na jeho začiatok, než výstup z cyklu. Preto sa predpokladá, že skok dozadu sa vykoná a skok dopredu sa nevykoná.