Způsoby predikce větvení

...

Moderátoři: Marfy, Mods_senior, Mods_junior, HW spec team

Uživatelský avatar
dom324
Level 5.5
Level 5.5
Příspěvky: 2768
Registrován: prosinec 16
Pohlaví: Muž

Způsoby predikce větvení

Příspěvekod dom324 » 11 kvě 2019 17:22

Způsoby predikce větvení

Predikce větvení (anglicky branch prediction) je součástí všech pokročilých procesorů a značným způsobem ovlivňuje jejich výkon. V poslední době jsem věnoval trochu času analýze a testování jednotlivých metod predikce větvení, a napadlo mě, že bych z nasbíraných výsledků mohl vytvořit článek, který rozebere jednotlivé metody pro predikci větvení. Článek začne pomalu se statickou predikcí, následně prosvištíme metodami, které vyžadují spolupráci programátora/kompilátoru, poté se konečně dostaneme k dynamické predikci větvení.
Vzhledem k množství času potřebného k testování jednotlivých metod bude článek postupně aktualizován a doplňován o čím dál pokročilejší metody predikce. Hned z kraje můžu prozradit, že dosáhnout 90% úspěšnosti bude hračka a brzy této mety dosáhneme.
Doufám, že se článek bude líbit :)

  1. Metodika
  2. Úvod do predikce větvení, aneb proč vlastně predikovat?
  3. Statická predikce
    1. Always Taken/Not Taken
    2. Backward Taken Forward Not Taken
    3. Eager Execution
  4. SW metody predikce
    1. Hint bit
    2. Delay slot
  5. Dynamická predikce
    1. Single bit
    2. 2-bit Saturating counter
  6. Local prediction

1. Metodika
Veškeré testování bylo provedeno na infrastruktuře ze soutěže Championship Branch Prediction (dostupná zde https://www.jilp.org/cbp2016/), test je složen ze 440 souborů, z nichž každý obsahuje 1-100 miliónů instrukcí. Soubory jsou příklady programů z jak serverového prostředí, tak i z klasického desktopu - rozhodně bych se tedy nebál, že náš testovací vzorek nebude reprezentativní (až tedy na malou nuanci u statické predikce, na kterou Vás upozorním).
Trochu bych chtěl naťuknout způsob vyhodnocování přesnosti jednotlivých prediktorů. Asi nejintuitivnější je uvádět přesnost v procentech. Ale v praxi, kdy inženýři navrhují prediktory s 98+% přesností, procenta přestávají být relevantní metrikou přesnosti (protože 98,1% a 98,2% působí jako úroveň odchylky měření, ale ve skutečnosti je to podstatný rozdíl). Zavedla se proto nová metrika MPKI (Misspredictions Per Thousand Instructions), která vyjadřuje počet mispredikcí na 1000 instrukcí.
Jelikož infrastruktura CBP vyhazuje výsledky rovnou v MPKI (a bohužel je nejde jednoduše přepočítat na %), budu uvádět hlavně tyto údaje. Později bych chtěl přidat % údaje pro základní metody.
Všechny grafy doporučuju otevřít v novém okně - ze začátku to tak možná nebude, ale postupně se prokoušeme k méně přehledným grafům a jejich roztáhnutí na celý displej může věci pouze zpřehlednit.

Velikost dynamických prediktorů
Velikost (cenu) prediktorů budeme měřit v bitech/bytech - to může znít zvláštně, ale dynamické prediktory jsou vlastně velmi rychlá paměť, do které se ukládá různá historie. Dává tedy smysl udávat velikost prediktorů v bitech/bytech.
V procesorech se běžně nacházejí rychlé paměti Cache - ty mají velice podobnou strukturu jako naše prediktory, lze je tedy použít jako vodítko, jak velké prediktory jsou reálné. Pro představu lze tedy říct, že velikost prediktorů v moderních procesorech AMD/Intel může být řádově dost podobná jako velikost L1 Cache - bavíme se o rozmezí od pár KB až do stovky KB, nejpravděpodobněji pár desítek KB. Toto uvádím jen pro orientaci, jak jsou vlastně prediktory velké. Konkrétní velikosti prediktorů znají jen inženýři z Intelu/AMD.
V soutěži Championship Branch Prediction 2016 se soutěžilo v kategoriích 8KB, 64KB a neomezená velikost prediktorů.

2. Úvod do predikce větvení, aneb proč vlastně predikovat?
Kdykoliv programátor použije slůvko "if", vytvoří podmínku. Takováto podmínka rozdělí běh programu do dvou větví. Dnešní procesory jsou vysoce paralelizované, tj. vykonávají mnoho instrukcí najednou (cca 100, pokud máme mluvit o moderních CPU Intel/AMD), v momentě kdy má být programátorovo "if" zpracováno, nastane problém - procesor neví, co za instrukci má načíst jako další, protože proud instrukcí může pokračovat dvěma cestami. Kontrolní jednotka tedy provede pipeline stall - pipeline nebude načítat žádné nové instrukce do doby, než procesor zjistí, jestli podmínka "if" bude přijata (logická 1, nebo T jako Taken) nebo odmítnuta (logická 0, nebo N jako Not taken).


Obrázek

Na tomto obrázku je zobrazeno schéma jednoduchého MIPS jádra, které používá pipelining (zpracování instrukce je rozděleno do 5 kroků), je skalární (jádro sice pracuje na 5 instrukcích zároveň, ale za každý takt dokončí pouze jednu instrukci) a zároveň je in-order (zpracovává instrukce tak, jak jdou za sebou).
  1. První krok v pipeline, jmenovitě "Fetch", slouží k získání instrukce z paměti - v tomto kroku známe pouze PC (Program Counter, adresa aktuálně zpracovávané instrukce - na obrázku lze úplně vlevo vidět registr s názvem PC), ještě vůbec nevíme, co za instrukci vlastně načítáme (add, branch, jump..). Aby se naše pipeline neflákala, potřebujeme na začátku každého cyklu znát adresu následující instrukce (neboli Next PC).
  2. Druhý krok, "Decode", dekóduje instrukci, kterou jsme získali v prvním kroku. Zde již máme přístup k instrukci v celé její kráse a dozvídáme se, o jakou instrukci se jedná - zjistíme, že se jedná o branch. Známe již její cílovou adresu
  3. Třetí krok, "Execute", konečně zpracuje data získaná v předchozích krocích a vyhodí nám výsledek - tedy jestli je naše větev přijata nebo ne.
  4. Ve čtvrtém kroku, "Memory acces", konečně vidíme mux (multiplexer), který nám vyhodí naši adresu Next PC.
  5. Pátý krok, "Write back", zůstává v případě instrukce branch nevyužit.


Proč Vám toto povídám? Pro pochopení důležitosti predikce větvení je nutné mít představu, jaká penalizace nás čeká v případě mispredikce.
V tomto případě je naše penalizace tři cykly - během Decode se nám nepodaří získat adresu další instrukce (první promarněný cyklus), během Execute pouze zjistíme, zda je větev přijata (druhý promarněný cyklus) a PC Next dostaneme až ve čtvrtém kroku (třetí promarněný cyklus), a až v dalším cyklu můžeme načíst novou instrukci z této adresy.
Větve představují zhruba pětinu všech instrukcí. Pokud by naše jádro mělo zpracovat 1000 instrukcí, 200 z nich by byly větve. Za každou z nich promarníme tři cykly, tj. celkem 600 cyklů. Naše jádro vykoná 1000 instrukcí za 1600 cyklů, větve způsobily 60% nárůst času potřebného k vykonání programu.

60% není zas tak moc. Ale je potřeba si uvědomit, že situace bude vypadat razantně jinak, když přesedláme z takto jednoduchého jádra na nabušené superskalární out-of-order jádro.
Zkusíme si podobný výpočet aplikovat na modelové moderní x86 CPU (které bude parametry hodně podobné jádrům od Intelu a AMD):
Penalizace za mispredikci - 20 cyklů (toto může být trochu zavádějící parametr, protože u takto pokročilého jádra se jedná o minimální penalizaci - můžeme čekat (a často budeme) ještě déle než už tak dlouhých 20 cyklů)
Počet instrukcí zpracovávaných najednou - 5

Máme našich 1000 instrukcí, z toho 200 větví. Čas potřebný na zpracování 1000 instrukcí je pouhých 200 cyklů (zpracováváme 5 instrukcí najednou, 1000/5), ale k tomu musíme přičíst penalizaci za mispredikci, celých 4000 cyklů (počet větví krát penalizace za mispredikci, 20 * 200). 4200 cyklů na zpracování 1000 instrukcí.
Ukázalo se, že naše nabušené jádro má bez predikce větvení 2x nižší IPC než jedno z nejzákladnějších MIPS jader.
Ale pokud použijeme predikci větvení, dostaneme o poznání zajímavější výsledky:

Přesnost 30%: 200 + (0,7 * 200 * 20) = 3000 cyklů
Přesnost 50%: 200 + (0,5 * 200 * 20) = 2200 cyklů
Přesnost 80%: 200 + (0,2 * 200 * 20) = 1000 cyklů
Přesnost 90%: 200 + (0,1 * 200 * 20) = 600 cyklů
Přesnost 99%: 200 + (0,01 * 200 * 20) = 240 cyklů

Toto už vypadá lépe. Bez predikce větvení bychom mohli zapomenout na hry v takové podobě, jako máme dnes.

Poslední věc, kterou bych v této úvodní (a věřím že nudné) kapitole chtěl zmínit, je BTB (Branch Target Buffer, někdy i Cache of target addresses). BTB je velmi podobný klasické Cache, jen se do něj ukládají cílové adresy větví. Když dojde k Fetch, procesor prohledá BTB zda v něm není záznam pro aktuálně zpracovávanou instrukci. Pokud ano, ví že aktuální instrukce je větev. Zeptá se pak prediktoru, jestli tato větev bude přijata. Ten buď vrátí 1 (Next PC bude adresa z BTB) nebo 0 (Next PC bude instrukce následující hned za větví). BTB může obsahovat i jiné informace než cílovou adresu např. historii chování větve.
Ne každý procesor musí mít BTB, u jednodušších procesorů BTB chybí a predikce začíná až v kroku Decode.


3. Statická predikce

A. Always Taken/Not Taken

Statická predikce na rozdíl od dynamické nevyužívá žádnou formu historie. Díky tomu se jedná o velmi levnou metodu, oblíbenou u nejjednodušších procesorů. Úplně nejzákladnější forma je predikovat vždy 1 nebo 0.
Pokud budeme pokaždé predikovat 0, dosáhneme MPKI 51,256 (připomínám, že nižší MPKI = lepší), neboli přibližně 60%.
Pokud budeme pokaždé predikovat 1, dosáhneme MPKI 80,383, neboli přibližně 40%.
Drobná nuance, kterou jsem zmínil v úvodu, spočívá v tom, že to jsou přesně opačné výsledky než ty, kterých bychom dosáhli v praxi (tzn. cca 60% pro vždy Not taken a 40% pro vždy Taken).

B. Backward Taken Forward Not Taken

Další forma statické predikce je o poznání důmyslnější. Je založena na informaci o tom, zda větev odkazuje na adresu větší než PC (tudíž skáče "dopředu", anglicky forward) nebo naopak menší než PC (větev skáče "dozadu", anglicky backward).
Tuto informaci můžeme lehce zneužít díky faktu, že cykly (pro procesor není mezi cyklem a běžnou větví rozdíl) které skáčou dozadu bývají N-krát přijaty (N je počet opakování cyklu) a poté jednou nepřijaty.
Pokud tedy spatříme větev, jejíž cílová adresa je nižší než PC, budeme předpokládat, že se jedná o cyklus a budeme vždy predikovat 1. V případě větve odkazující na adresu vyšší než PC budeme vždy predikovat 0.
Nevýhodou této metody predikce je, že ji můžeme provést až potom, co proběhne dekódování instrukce (musíme znát adresu cílové instrukce). Pokud chceme predikci provést hned ve fázi Fetch, musíme mít cílové adresy uložené v BTB - tuto verzi si nasimulujeme my.
A jak si tedy metoda Backward taken, forward not taken vede? S BTB o velikosti 8192 záznamů tato metoda dosáhla velmi slušného výsledku MPKI 26,191. V budoucnu pravděpodobně doplním výsledky i pro další velikosti BTB a možná i možnost neukládat celou cílovou adresu nýbrž pouze spodních N-bitů.

C. Eager Execution

Poslední metoda je spíše teoretická než praktická - Eager execution. Její princip je naprosto jednoduchý - predikce větvení úplně chybí (ale stále se jedná o způsob predikce větvení, což je trochu ironické), za to má pipeline zdvojené všechny kroky od Fetch až do "vypočítání" větve. V momentě kdy se vykonává větev, CPU vypočítá obě strany větve (jedna kopie pipeline bude počítat stranu 1, druhá kopie pipeline bude počítat stranu 0) a až CPU zjistí zda větev je/není přijata bude pokračovat ve výpočtu dané strany - nemáme zde žádnou bublinu, kdy by se naše pipeline flákala.
Je to dost brutální způsob (co se ceny provedení týče), ale dosahuje 100% přesnosti. Tento koncept brzy narazí na svůj velký problém - máme v pipeline větev, budeme zpracovávat obě strany této větve. Ale co když se v obou stranách objeví další větev, která nám rozdělí každou stranu větve na další dvě menší strany? Budeme mít 4 kopie pipeline? A co když v těch menších stranách budou další větve? Budeme mít 8 kopií pipeline?
Kvůli své extrémní cenně pro implementaci se tento způsob v praxi nepoužívá vůbec. Mnohem výhodnější než mít 4 nesmyslné kopie pipelineje vyrobit jádro, které může zpracovávat 2 instrukce za takt a přidat k tomu nějakou průměrnou metodu predikce - takové řešení bude mít mnohem vyšší výkon.

4. SW metody predikce

A. Hint bit

Často používaná metoda je tzv. Hint bit. V samotné instrukci je zakomponován bit, který má procesoru poradit (od toho název Hint bit), zda bude větev přijata či ne. Procesor se pak může zcela spolehnout na Hint bit a založit celou predikci na něm, nebo může predikci založit na kombinaci Hint bitu a nějaké formy historie (tuto metodu používal Intel u P4).

Problém by měl být vidět hned na první pohled - někdo musí nastavit Hint bit pro každou větev. Programovací jazyky umožňují, aby programátor napověděl kompilátoru (likely, unlikely), zda bude větev častěji přijata nebo odmítnuta - ale tato metoda vyžaduje spolupráci programátora, kterému se v mnoha případech nechce u každé podmínky řešit, zda bude častěji přijata nebo odmítnuta. Tuto práci může převzít i kompilátor, který sám umí nastavit Hint bity (například u podmínky p==q nastaví nulu, protože je malá šance, že zrovna tyto neznámé se budou sobě rovnat. Ale u podmínky p > 0 nastaví jedničku, protože je relativně vysoká pravděpodobnost, že p bude kladné. Navíc takováto podmínka se může vyskytovat u cyklů). Ale kompilátor není všemocný a takto nastavené Hint bity nebudou úplně ideální.
Kompilátory dokonce umožňují, aby mu programátor dal sadu vstupních hodnot, on tyto hodnoty projel programem a na základě pozorovaného chování nastavil Hint bity jednotlivých větví. Pokud je sada vstupních hodnot dobře zvolena, Hint bity budou nastaveny velmi dobře, ale v opačném případě, kdy je soubor vstupních hodnot zvolen tragicky, budou i Hint bity zvoleny tragicky.

Výhody jsou jasné - vyšší přesnost než staticky predikovat 1 nebo 0, levné na implementaci.

Nevýhod je poněkud více - je nutné, aby Hint bit podporovala přímo ISA (ISA definuje samotnou instrukční sadu. Například jádra AMD Zen a Intel Skylake jsou v mnoha ohledech rozdílná, ale obě spadají pod ISA x86, což znamená, že na obou z nich poběží kód napsaný pro x86). Pokud tedy rozhodnutí o podpoře Hint bitu nepadlo rovnou u návrhu ISA, už není možné toto rozhodnutí později jen tak změnit.

U x86 je Hint bit řešen tak, že se před instrukci branch strčí jedna 8 bitová instrukce (tudíž by to spíš měla být Hint instruction), která hraje roli Hint bitu. Z toho co se mi podařilo zjistit, tak Intel tuto metodu naposledy využíval u Pentií 4, AMD ji nepoužívalo nikdy. U moderních x86 jader jsou tyto Hint instrukce naprosto zbytečné, pouze plýtvají pamětí a komplikují instrukční sadu.

Druhá nevýhoda spočívá v samotné nutnosti nastavovat Hint bity - přesnost predikce tudíž plně závisí na snaze programátora, což nemusí být vždy ideální řešení.
A ani když budou Hint bity správně nastaveny, nemusí být přesnost predikce nijak závratná. Pokud budeme mít větev, jejíž historie bude vypadat takto "TNTNTNTNTN" (Taken, Not Taken, Taken....), nedosáhneme nikdy vyšší přesnosti než 50%.
Existuje možnost rekompilovat program za běhu - procesor bude ukládat chování větví a program se pak sám na základě uložených hodnot za běhu rekompiluje a nastaví znovu Hint bity. Ale osobně si toto řešení v praxi nedokážu moc představit, navíc by se tím neuvěřitelně zkomplikovalo schéma, jehož hlavní výhodou je jeho jednoduchost.

Většina těchto nevýhod metody Hint bit se týká použití ve velkých jádrech, kde zkrátka této metodě už dochází dech. Ale pro použití v nějakých menších jádrech, kde si ideálně koncový zákazník sám vyvine kód a zoptimalizuje Hint bity, je toto řešení velmi výhodné. Pokud se Hint bity nastaví správně, toto schéma dosahuje vyšší přesnosti než Backward taken forward not taken.

B. Delay slot

Druhou SW metodou (ačkoliv zde už bude potřeba větší podpora v HW) predikce je tzv. Delay slot. Delay slot zajišťuje, že první instrukce následující za instrukcí branch bude vždy (i když bude větev přijata) vykonána. Tato metoda neřeší samotnou predikci větvení, ale ovlivňuje penalizaci za mispredikci - snižuje ji o jeden cyklus.
Díky tomuto schématu naše výše zmíněné MIPS jádro může snížit penalizaci z 3 na 2 instrukce, čili snížení o celých 33%.
Kdyby podobnou vychytávku používalo i naše x86 jádro, snížila by se penalizace ze 100 instrukcí na 99, čili snížení o pouhé procento.
Samozřejmě je možné tuto metodu rozšířit a vykonat vždy první 2 instrukce následující po instrukci branch, zda toto rozhodnutí je rozumné rozebereme níže.
První nevýhodou je nutná podpora přímo v instrukční sadě. Tato metoda ovlivňuje v jakém pořadí budou vykonávány instrukce, a to je zásah dost hluboko do ISA. Znovu tedy platí, že nelze jen tak z ničeho nic přidat nebo odebrat podporu pro Delay slot.
Druhá nevýhoda je přidaná práce pro kompilátor - kompilátor musí najít instrukci, která je společná pro obě strany větve a její vykonání neovlivní chod programu (pokud naše if provádí a+b, nemůžeme do delay slotu použít instrukci, která mění hodnotu neznámé a nebo b). To samo o sobě není problém, problém je až to, když kompilátor nenalezne vhodnou instrukci - v tomto případě instrukce následující po branch bude NOP (No Operation, instrukce která doslova dělá nic), což je stejné jako promarnit jeden cyklus -> přijdeme o náš bonus v podobě snížené penalizace za mispredikci.
U delay slotu pro jednu instrukci toto není zas tak velký problém a kompilátor většinou nějakou tu instrukci najde, ale v momentě, kdy by jsme vždy vykonávali dvě, tři nebo dokonce čtyři instrukce následující po branch, kompilátor by měl často problém najít tolik vhodných instrukcí - proto se v praxi používá pouze delay slot pro jednu instrukci.

Tuto metodu využívá architektura MIPS (vykonána je vždy jedna instrukce po větvi), x86 naštěstí tuto metodu nepoužívá (vliv na výkon by byl zanedbatelný a zbytečně by se zkomplikovala pipeline).

5. Dynamická predikce

A. Single bit

Tato metoda ukládá jediný bit, který indikuje jakým směrem šla poslední větev.
Oproti statické predikci má tato metoda jasnou výhodu - "TTTTTNNNNN" bude mít 90% přesnost (první N bude špatně predikováno), oproti pouhým 50% kdyby jsme staticky predikovali 0 nebo 1.
Ale například "TNTNTNTNTNTN" bude mít 0% přesnost, místo 50%.
V něčem je tato metoda horší, v jiném lepší - z toho vyplývá i výsledek, který se svým MPKI 51,109 je na stejné úrovni jako Always Not taken.

B. 2-bit Saturating Counter

2-bit Saturating Counter je takový základní kámen, na kterém staví skoro všechny pokročilé metody predikce. 2-bit Counter by se do češtiny nejspíš přeložil jako 2 bitové počítadlo. Ony 2 bity znamenají, že máme 22 (základ 2 protože se pohybujeme v binární soustavě, exponent 2 protože máme 2 bity), tedy celkem 4 stavy. Ono Saturating znamená, že při přesažení čtvrtého stavu nezačneme počítat znovu od nuly, ale zůstane na čtvrtém stavu - běžný counter počítá 00, 01, 10, 11 - teď jsme využili všechny dostupné stavy a dojde k "overflow" (přesah) a counter pokračuje (1)00, (1)01...kdežto Saturating counter nikdy nepřesáhne stav 11. Vše pochopíte lépe z následujícího obrázku:
Obrázek
Máme celkem čtyři stavy, které se jmenují "Strongly not taken" (stav 00), "Weakly not taken" (stav 01), "Weakly taken" (stav 10) a "Strongly taken" (stav 11).
Pokud se nacházíme v levých dvou stavech (xxxx not taken), budeme predikovat 0. Pokud se nacházíme v pravých dvou stavech (xxxx taken), budeme predikovat 1.
Counter je aktualizován pomocí výsledku větve - pokud byla větev přijata, stav je posunut směrem doprava (např. z Weakly taken na Strongly taken), pokud větev nebyla přijata, stav je posunut směrem doleva.

Tento model predikce je oproti metodě Single bit více "stálejší" - single bit své rozhodnutí mění doslova ihned, kdežto 2-bit Saturating Counter je pomalejší a používá větší množství historie.
Toto umožňuje, aby "TNTNTNTNTN" mělo přesnost 50% (counter bude cestovat mezi Strongly not taken/Weakly not taken nebo Strongly taken/Weakly taken), bohužel se může stát, že se counter "zasekne" a bude cestovat mezi stavy Weakly not taken/Weakly taken - naše přesnost klesne znovu na 0%.
Za to u "TTTTTNNNNN" si pohoršíme na 80% z 90%, protože první i druhé N bude predikováno špatně (po pátém T se bude prediktor nacházet ve stavu Strongly taken, u prvního N přijde mispredikce a stav se změní na Weakly taken, znovu přijde mispredikce a stav se změní na Weakly not taken, zbylé tři větve budou predikovány správně).

A jak se posune naše přesnost? MPKI klesne na 40,012. To je stále daleko od toho, kde by jsme chtěli být, ale pomalu se posouváme dále.

Někoho možná napadne, zda lze podobně použít 3, 4, 5 bitové saturating country - nic nám nebrání zkusit to. V následujícím grafu jsou výsledky pro 2 bity, 3 bity (8 stavů, testoval jsem i omezení na 6 stavů), 4 bity (celkem 16 stavů, testoval jsem i omezení na 10, 12, 14 stavů), 5 bitů (32 stavů) a 6 bitů (64 stavů).

Obrázek

Použitím 3 bit saturating counteru jsme se vyhoupli na MPKI 35,767. Varianta se čtyřmi bity je jen o málo lepší a nejlepšího výsledku dosáhla při omezení na 12 stavů - MPKI 35,275. Při použití pěti a šesti bitů začne přesnost pomalu klesat - zvýšení počtu stavů snižuje rychlost s jakou se prediktor adaptuje na změny v chování větví - dostat se z nejzazšího stavu Not taken na první stav Taken trvá celých 32 větví.
Další možnost, jak upravit Saturating countery, je pozměnit jednotlivé stavy - můžeme mít 3 bit Saturating Counter, který bude mít 3 stavy Not taken a 5 stavů Taken (místo 4 stavů Not taken a 4 stavů Taken). Toto obvykle nepřináší nějaký smysluplný posun v přesnosti, takže to rovnou přeskočíme.

Užití 3 bitů skutečně smysl má, ale u 4 bitů je posun diskutabilní a jakákoliv vyšší hodnota už nepřináší žádné výhody - ačkoliv jsme se dočkali lepších výsledků, je jasné, že tudy naše cesta k 90% přesnosti nevede. V následujících kapitolách se zaměříme na to, jak pomocí Saturating counterů postavit ještě silnější (samozřejmě dynamické) prediktory.

6. Local prediction
Pokud se bavíme o dynamické predikci, rozeznáváme dva hlavní typy prediktorů - globální a lokální. Globální predikce hází všechny větve do "jednoho pytle", nerozeznává mezi jednotlivými větvemi. Díky tomu je globální predikce ideální, pokud potřebujeme zachytit větve, které mezi sebou korelují (závisí na sobě). Úplný opak je lokální predikce, která se zaměřuje na chování jednotlivých větví - narozdíl od globální predikce, lokální predikce nedokáže vůbec (nebo velmi špatně) zachytit korelaci mezi více větvemi.
Nelze říct, že by jeden přístup byl lepší než ten druhý - globální i lokální predikce mají své výhody a nevýhody. Naším úkolem bude najít tyto výhody/nevýhody a využít je v náš prospěch :)

Obě metody zmíněné v minulé kapitole (Single bit a 2 bit Saturating counter) fungovaly na principu globální predikce - všechny větve používaly/mapovaly se na jeden a ten samý záznam historie (bit/bity). Hlavní (ne)výhoda globální predikce byla už výše zmíněna - dokáže zachytit korelace mezi jednotlivými větvemi. Jak tato vlastnost může být pro nás nevýhodná? Když se mnoho větví mapuje na stejný záznam historie, dochází k interferenci/rušení mezi jednotlivými větvemi - větve se bijí jedna přes druhou. O vlastnostech interference (jak negativních, tak i pozitivních), jak a do jaké míry ji eliminovat se budeme bavit více do hloubky u Two level adaptive predictoru, podle mě se jedná o velmi zajímavé téma.

Nejlepší bude ukázat si rozdíl mezi globální/lokální predikcí přímo na příkladu. U 2 bit saturating counteru jsme se bavili, jak se vypořádá s patternem "TNTNTN" a došli jsme k závěru, že přinejlepším dosáhneme přesnosti 50%, ale také můžeme skončit na 0%. Toto není zrovna uspokojivá přesnost. S dovolením si tento příklad trochu upravím pro dvě větve:
01010101
Zde vidíme, jak by historie dvou prolínajících se větví vypadala z pohledu globální predikce. Jsem si jistý, že už tušíte, jak bude historie vypadat, když se na ni podíváme z pohledu lokální predikce:
0000
1111
Nyní máme dva separátní záznamy - jeden obsahuje historii první větve (žlutá), druhý obsahuje historii druhé větve (zelená).

Abych náš příklad přenesl do programátorské praxe - představte si nekonečný cyklus s podmínkou na konci (takový cyklus se tváří jako běžná větev, která má historii "1111..."), který má uvnitř podmínku "pokud dělíš 0 -> vypiš Nelze dělit nulou" - jelikož tato podmínka funguje jako preventivní opatření proti dělení nulou (matematika toto neuznává), lze předpokládat, že za běžného chodu programu tato chyba nenastane a my dostaneme historii "0000...".
Když spustíme program, bude se nám střídat cyklus a podmínka proti dělení nulou. Dostaneme náš pattern "01010101".

Nyní ale vyvstala jiná otázka - jak se vypořádat s dvěmi záznamy historie? Odpověď je tak jednoduchá, jak jen může být - prostě použijeme dva 2 bit saturating country.
Snad nebude problém určit, kam se posune přesnost, pokud "zelená" i "žlutá" větev dostane svůj vlastní 2 bit saturating counter. Jelikož se nám podařilo z poměrně problematického patternu "10101010" udělat dva primitivní a bezproblémové patterny "1111" a "0000", dosáhneme přesnosti 100%.

Teď už zbývá jediný problém - jak vlastně rozeznat jednotlivé větve. Větví může být v programu tisíce a my musíme najít způsob, jak je rozdělit mezi jednotlivé 2 bit saturating countery.
Nejjednodušší způsob je použít pro rozlišení jednotlivých větví jejich adresu (aktuální PC) - zde využíváme toho, že programy málo kdy přepisují vlastní kód. Instrukce tedy "necestují" a jejich adresa jim zůstane stejná po celou dobu běhu programu.
Už víme, jak rozeznat jednotlivé větve. Menší zádrhel představuje fakt, že PC bývá 32/64 bitový registr (záleží zda je instrukční sada a z ní vycházející procesor 32 nebo 64 bitový), to dělá ~4,3 biliónu (4,3*109) respektive ~18,5 triliónů (18,5*1018) možných adres. Pokud bychom chtěli pro každou adresu mít vlastní 2 bit saturating counter, musel by prediktor být velký ~8,6Gb = 1,1GB respektive ~37Eb (Exabitů) = 4,6EB (Exabytů).
Teď bych chtěl připomenout, že na začátku v kapitole Metodika jsme si uvedli, že i velké prediktory mají několik desítek KB. Je tedy vysoce nereálné jen uvažovat o tom, že by každá adresa dostala svůj vlastní 2 bit saturating counter.

Jak to tedy vyřešit? Programy stejně nevyužívají trilióny větví, je tedy naprosto zbytečné mít trilióny counterů. Pro adresování pole counterů použijeme pouze spodních N bitů adresy PC. Například pokud "N = 4" a "PC = ...101101101001" použijeme poslední 4 bity "1001". Stále se pohybujeme v binárce, takže 4 bitové číslo má přesně 24 kombinací = 16. Pokud tedy pro adresování pole counterů použijeme 4 spodní bity adresy PC, bude potřeba 16 counterů = 32 bitů (každý counter nás stojí 2 bity). Vše lépe ilustruje následující obrázek:
Obrázek

Spodních N bitů aktuálního PC použijeme pro výběr 2 bit saturating counteru z pole (kde je celkem 2N záznamů/counterů) a vybraný counter nám dá naši predikci.

Vzhledem k tomu, že nemáme trilióny counterů, na jeden counter se bude vždy mapovat více větví. Takže pokud se naše N rovná 4 a první větev má adresu "10010" a druhá má adresu "00010", obě větve se namapují do counteru s adresou "0010" a dojde tedy k interferenci/rušení. Pokud tomu chceme zabránit, musíme zvýšit N na 5 a tím i zvýšit cenu prediktoru.
Ani v lokálních prediktorech se tedy interference úplně nezbavíme, ale bude jí mnohem méně než u globálních prediktorů.

V následujícím grafu je na ose Y dosažená přesnost pro Single bit, 2-bit Saturating Counter a 3-bit Saturating Counter v MPKI (nižší = lepší), na ose X je naše N (počet bitů použitých pro adresování).
Obrázek

Jde vidět, že Single bit výrazně zaostává za 2/3 Bit Saturating Country. 2-Bit Saturating Counter pomalu dohání 3 bitovou variantu, ale ještě ho úplně nedohnal. MPKI se posunulo až na 10,642, což je velmi slušný výsledek. Nicméně ke konci grafu již můžeme vidět "stagnaci", počet counterů se nedá zvyšovat do nekonečna - respektive dá, ale z pohledu výkonu to nedává smysl.
Ale nesmíme zapomínat, že v grafu je porovnání podle počtu adresových bitů N, poměr cena/výkon můžeme vidět v následujícím grafu, kde je na ose X velikost v bitech:

Obrázek

Single bit má vždy horší poměr cena/výkon než naše Saturating Country. 3 bitová varianta začíná s malým předstihem, ale 2 bitová varianta ho brzo dorovnává.
Variantě s 2-Bit Saturating Country se někdy také přezdívá Bimodal predictor, toto pojmenování se v článku nejspíš ještě párkrát objeví. Uvádí se, že opravdu velké Bimodal predictory končí s přesností na nějakých 93%, což je velmi slušný výsledek, ale taky za vysokou cenu.

Všimněte si, že přesnost prediktoru zůstává skoro stejná při použití 1, 2 a 4 záznámů (začátek křivky je rovný). Příště zkusíme přijít na to, proč tomu tak je a jak se tohoto chování zbavit.
Naposledy upravil(a) dom324 dne 12 kvě 2019 20:26, celkem upraveno 3 x.



Reklama
Uživatelský avatar
Ltb
Administrátor
Master Level 8
Master Level 8
Příspěvky: 6456
Registrován: únor 03
Bydliště: Praha západ
Pohlaví: Muž

Re: Způsoby predikce větvení

Příspěvekod Ltb » 12 kvě 2019 10:27

Publikováno 8) Díky moc za zajímavý a propracovaný článek :bigups:

Turion
Level 5
Level 5
Příspěvky: 2106
Registrován: březen 16
Pohlaví: Muž

Re: Způsoby predikce větvení

Příspěvekod Turion » 12 kvě 2019 10:58

Vůbec nevím vocogo. Ale jako mladý jsem chtěl taky umět něco složitýho jako toto. Bohužel vždy po přečtení nějakého učiva vím to stejné jako před přečtením:). Holt na to musí bejt hlava a hlavně paměť, aby hlava měla z čeho brát data. Já dřív vymyslím nový programovací jazyk, než se naučím pascal podle nějaké příručky.

Voky0077
Level 1
Level 1
Příspěvky: 96
Registrován: červen 17
Pohlaví: Muž

Re: Způsoby predikce větvení

Příspěvekod Voky0077 » 12 kvě 2019 16:50

Diky za fajn clanek ;)

Uživatelský avatar
dom324
Level 5.5
Level 5.5
Příspěvky: 2768
Registrován: prosinec 16
Pohlaví: Muž

Re: Způsoby predikce větvení

Příspěvekod dom324 » 12 kvě 2019 20:14

Budu rád za každou připomínku, opravu (různých chybiček tam asi bude více), komentář nebo otázku :bigups:
Mám toho v záloze natestováno ještě dost, jen to chce vždy sebrat odvahu, dát data nějak do kupy a sepsat :)

Turion: Ono to není úplně jednoduché téma, chce to hodně logického myšlení a představivosti (šly by k tomu udělat krásné animace, ale to bych musel mít tak 3-4 krát tolik nervů a času - a ten radši věnuju rozšíření článku).
Mně tyhle věci vždycky šly a všechno mi připadalo "jasné a samozřejmé" - i když jsem se všechno v článku snažil vysvětlit jak nejlépe umím, je možné, že je tam něco popsáno krkolomně/málo do detailů a pro někoho to nemusí být stravitelné.

Turion
Level 5
Level 5
Příspěvky: 2106
Registrován: březen 16
Pohlaví: Muž

Re: Způsoby predikce větvení

Příspěvekod Turion » 12 kvě 2019 22:12

Ne, popsaný to máš určitě dobře. Já jsem blbej jak troky, takže bych musel půl roku zkoumat jak takovou informaci využít nebo k čemu to reálně je, jestli do normálního programování nebo k návrhům CPU nebo na co.
Určitě to je určený pro lidi co se tím zabývají, takže přínos pro starýho hlupáka není rozhodující. Dneska se studuje IT mnohem víc než dřív, takže lidí/čtenářů se najde určitě dost, kterým to něco dá.

Uživatelský avatar
faraon
Master Level 8
Master Level 8
Příspěvky: 6629
Registrován: prosinec 10
Pohlaví: Muž

Re: Způsoby predikce větvení

Příspěvekod faraon » 13 kvě 2019 18:18

Pokud neprogramuješ operační systémy nebo viry, tak ti tyhle informace moc nepomůžou. Při dnes běžném programování jsi od hardwaru oddělený desítkami až stovkami nejrůznějších softwarových vrstev, takže jediné co tě zajímá je, jestli tvůj program dokáže sečíst dvě reálná čísla aspoň tisíckrát za sekundu :lol: + :lol:

Ale je dobré i o tomhle aspoň něco vědět, on pak člověk lépe chápe, proč jsou některé věci udělané tak jak jsou, a proč někdy fungují jinak než by očekával. Takže díky za pěkné čtení :thumbup:
Cena opravy letadlové lodi Admirál Kuzněcov, řízené ožralými ruskými námořníky cestou do Sýrie a přitažené zpět do Ruska na laně: 70 000 000 rublů.
Cena opravy nepotopitelné fregaty KNM Helge Ingstad, řízené genderově způsobilými navigátorkami a potopené u norského pobřeží po nárazu do tankeru: 90 000 000 000 rublů.

Ňuf
nováček
Příspěvky: 1
Registrován: květen 19
Pohlaví: Nespecifikováno

Re: Způsoby predikce větvení

Příspěvekod Ňuf » včera, 13:19

Článek je zajímavý, dovolil bych si ale malou opravu - v češtině 10^9 není bilión ale miliarda (v angličtině je to billion). Taky věta "Jelikož se nám podařilo z poměrně problematického patternu "10101010" udělat dva primitivní a bezproblémové patterny "1111" a "0000", dosáhneme přesnosti 100%" byť je jasné kam směřuje, nebude v praxi pravdivá, neboť 100% úspěšnost by platila pouze za předpokladu, že by oba 2-bit saturating counters byly ve výchozím stavu (tzn. před svou první predikcí) v takovém stavu, ve kterém by jejich predikce byla správná (tzn. první counter ve stavu "Strogly not taken" nebo "Weakly not taken" a druhý naopak ve stavu "Strogly taken" nebo "Weakly taken"). To ale prediktor nemůže dopředu vědět (pokud nedostane hint od kompilátoru). Oba prediktory tak budou mít v praxi výchozí stav stejný, takže se jeden z prediktorů při první (resp. i druhé) predikci určitě splete a přesnost bude pouze 7/8 = 87,5% (resp. 6/8 = 75%).

Uživatelský avatar
dom324
Level 5.5
Level 5.5
Příspěvky: 2768
Registrován: prosinec 16
Pohlaví: Muž

Re: Způsoby predikce větvení

Příspěvekod dom324 » včera, 14:57

10^9 určitě opravím, popravdě jsem se při psaní do názvů mocnin celkem zamotal a pořád je dokola kontroloval a opravoval, očekával jsem, že tam někde bude chyba :D

V praxi to tak bude fungovat, hned potom, co se prediktor "zahřeje". V tom příkladu jsem schválně nepočítal s výchozími stavy, za prvé by to zbytečně komplikovalo, za druhé přesnost po zahřátí prediktoru je pro nás důležitější než těch pár misspredictions které nastanou na začátku.
Je to dobrá připomínka, někde tam připíšu, že se jedná o příklad již zahřátého prediktoru.


Nechtěl jsem do článku zatím motat warm up time, protože všechny zatím zmíněné metody mají relativně krátký warm up time. Tomuto tématu bych chtěl věnovat pár odstavců hned co se dostaneme k Two level adaptive predictoru, tam je tento pojem mnohem důležitější a je dobré ho zmínit.


Zpět na “Vše ostatní (hw)”

Kdo je online

Uživatelé prohlížející si toto fórum: CommonCrawl [Bot] a 0 hostů