Způsoby predikce větvení

…místo pro vaše testy…

Moderátoři: Mods_senior, Mods_junior, VIP

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

Způsoby predikce větvení

Příspěvekod dom324 » 30 led 2019 22:20

Způsoby predikce větvení

Predikce větvení (anglicky branch prediction) je jeden z hlavních prvků všech pokročilých procesorů, který značně ovlivňuje jeho 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é způsoby predikce 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. Last bit
    2. 2-bit Saturating counter


1. Metodika
Veškeré testování bylo provedeno na infrastruktuře ze soutěže Championship Branch Prediction (dostupná zde https://www.jilp.org/cbp2016/), testovací vzorek obsahuje 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).
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, budu uvádět hlavně tyto údaje. Ze začátku budu pro představu uvádět i orientační hodnoty v procentech.


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ší. Kontrolní jednotka tedy provede pipeline stall - do pipeline se nebudou načítat žádné nové instrukce do doby, než procesor zjistí, jestli bude podmínka "if" je přijata (logická 1) nebo odmítnuta (logická 0).
Adresa další instrukce, která se má zpracovávat, se často označuje "Next PC", vysvětleno níže.


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), nevíme co za instrukci jsme načetli (add, branch, jump..). Aby se naše pipeline neflákala, potřebujeme na začátku každého cyklu znát Next PC.
  2. Druhý krok, "Decoding", 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 začneme práci na jejím dekódování - zjistíme, že se jedná o branch, začneme tedy měnit hodnoty jednotlivých kontrolních signálů a načítat hodnoty z registrů (hlavně nás zajímá adresa cílové instrukce, kam má Program Counter skočit v případě že větev bude přijata.
  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. Tudíž až po tomto kroku můžeme zase začít zásobovat pipeline novými instrukcemi.
  4. Čtvrtý a pátý krok ukládají hodnoty do registrů/paměti, pro naši branch instrukci je můžeme ignorovat, jelikož ta žádná data neukládá.

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 dva cykly - během Decode se nám nepodaří získat adresu další instrukce, získáme ji až na konci Execute. Takto získané Next PC můžeme využít až během dalšího cyklu. Promarnili jsme dva cykly.
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 byla větev. Za každou z nich promarníme dva cykly, tj. celkem 400 cyklů. Naše jádro vykoná 1000 instrukcí za 1400 cyklů, větve způsobily 40% nárůst času potřebného k vykonání programu.

40% 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):
Hloubka pipeline od Fetch po Execute (penalizace za mispredikci) - 20 cyklů (toto může být trochu zavádějící parametr, protože u Out-of-Order jádra se jedná o minimální penalizaci - můžeme čekat 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ů (1000/5), ale k tomu musíme přičíst penalizaci za mispredikci, celých 4000 cyklů (20 * 200). 4200 cyklů na zpracování 1000 instrukcí.
Ukázalo se, že naše nabušené jádro je bez predikce větvení 3x pomalejší 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.
Pokud výrobci bezhlavě zvyšují počet kroků v pipeline (což vede k navýšení frekvence), dojdou nakonec k nižšímu výkonu. Je potřeba správně vybalancovat počet instrukcí, které jádro zpracovává, a mít dobrý prediktor. Jedno bez druhého vede k málo výkonnému procesoru.


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, ukládají se do něj cílové adresy větví. Když dojde k Fetch, procesor prohledá BTB, a když zde najde záznam, 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ž po ukončení kroku Decode.
My budeme BTB jakožto paměť ukládající cílové adresy úplně ignorovat, využijeme pouze možnost ukládat si historii chování větví.

3. Statická predikce
Statická predikce, jak už název napovídá, predikuje, že všechny větve půjdou jednou stranou (0 nebo 1). Jelikož tato metoda nevyužívá žádnou formu historie, většinou je to velmi levná metoda, oblíbená u nejjednodušších procesorů.
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 ve výsledcích spočívá v tom, že to jsou přesně opačné výsledky než ty, kterých bychom dosáhli v praxi (tzn. cca 70% pro vždy 1 a 30% pro vždy 0).

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 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ů.

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 zjištění cílové adresy instrukce. 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 v kroku Execute se rozhodne, která strana vlastně bude přijata.gt
Je to dost brutální způsob (co se ceny provedené týče), ale dosahuje 100% přesnosti. Navíc 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. Radši než mít 4 nesmyslné kopie pipeline výrobce vyrobí jádro, které může zpracovávat 2 instrukce za takt a použije nějakou průměrnou metodu predikce - takové řešení bude mít mnohem vyšší výkon.

3. SW metody predikce
Metoda velmi často používaná u málo výkonných procesorů 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 často vyskytuje 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. A naopak, když ISA původně počítala s podporou Hint bitu, není možné později podporu jen tak odebrat. Hint bit v každé instrukci branch zabírá jeden bit, a pokud ho náš procesor nevyužívá, jedná se jen o zbytečně zabraný bit, který mohl být použit jinak (nebo mohlo dojít ke zkrácení instrukce).

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 "01010101010101", nedosáhneme nikdy vyšší přesnosti než 50%.
Existuje teoretická 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 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 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.


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, jestli by toto rozhodnutí bylo správné 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.
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.
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 bude mít kompilátor často problém najít tolik vhodných instrukcí.

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



Reklama

Zpět na “TESTOVACÍ FÓRUM”

Kdo je online

Uživatelé prohlížející si toto fórum: CommonCrawl [Bot] a 3 hosti