funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Branch prediction moderních procesorů

24. 11. 2014

Před nějakou dobou jsem narazil na článek z roku 2010, který testoval, jak si branch prediction procesorů té doby poradí s různými opakujícími se vzory skoků v programu. Došel k závěru, že když procesor nedokáže skoky předvídat, může být výsledný program až 6x pomalejší, než když předvídá perfektně. Rozhodl jsem se test zopakovat a zjistit, jak je na tom současný hardware.

Rychlost branch instrukce (neboli podmíněného skoku) závisí na tom, jestli je její podmínka předvídatelná. Pokud procesor dokáže správně uhodnout, zdali má skočit na jiné místo programu nebo pokračovat s následující instrukcí, je skok skoro zadarmo. Ale pokud procesor neví nebo uhodne špatně, následuje takzvaný pipeline stall, kdy CPU zahodí všechnu rozdělanou práci a začne číst, dekódovat a vykonávat instrukce ze správného místa.

Toto chování souvisí s faktem, že všechny současné procesory jsou pipelinované. Každá instrukce vyžaduje několik nezávislých kroků, typicky to jsou fetch, decode, execute a write-back, kdy je instrukce načtena z paměti, dekódována, vykonána a výsledky zapsány zpátky do paměti. Kdysi dávno procesory vzaly jednu instrukci, vykonaly sekvenčně všechny čtyři fáze a teprve potom se posunuly na další. V honbě za vyšším výkonem CPU začala provádět všechny fáze najednou pro různé instrukce. Zatímco jedna instrukce zapisuje do paměti, následující se vykonává, následující je dekódována a následující je načítaná z paměti. Najednou se v procesoru nachází několik instrukcí za letu. Současné procesory mají pipeline s více kroky než jsou ony čtyři a navíc jsou superskalární, což znamená, že v každém taktu dokážou zpracovat několik instrukcí. Z těchto důvodů je počet instrukcí "za letu" je mnohem vyšší. Délka pipeline souvisí s navyšováním taktu: Čím vyšší frekvence, tím méně času má signál dostat se skrz jednu fázi pipeline, když se zvýší počet kroků, každý může být o něco kratší. Současné x86 mají něco mezi 12-15 fázemi a když je hezky zvládnout zpracovat 4 instrukce za takt, Itanium zvládne stabilně 12 a chystaný Mill až 33.

Teď si představte, že se v tomto perfektním soustrojí vyskytne podmíněný skok. Část CPU, která načítá instrukce na začátku pipeline, se musí rozhodnout, jestli načte následující instrukci, nebo tu na kterou branch může skočit. Podmínka, která to určuje, není zatím vykonána a ještě několik taktů nebude, dokud se neprobojuje na druhý konec pipeline. To je však příliš dlouhá doba a procesor si nemůže dovolit čekat. V ten okamžik na scénu nastoupí branch predictor a pokusí se to uhodnout. Když se trefí, všechno jede jako na drátkách, když se zmýlí, nastane pipeline stall, procesor musí zahodit všechnu práci do které se spekulativně pustil a začít načítat instrukce ze správného místa a prohnat je skrz celou pipeline a tedy ztratit množství času odpovídající délce pipeline.

Naštěstí je většina skoků v programu velice dobře předvídatelná. Například smyčky, které projedou mnoho iterací a během každé z nich branch instrukce skočí na začátek, kromě té poslední, kdy propadne. Procesory používají mnoho různých variant branch predictorů, které zaznamenávají minulé chování podmíněných skoků a předpokládají, že se stejné nebo podobné chování bude opakovat i v budoucnu. Někdy mají několik různých predictorů a jeden meta-predictor, který učiní finální rozhodnutí. Tímto způsobem dosahují impresivních výsledků, kdy mají skoro vždycky pravdu.

Branch predictor je velice důležitá část CPU, protože v typických programech představují skoky každou šestou až osmou instrukci a pipeline stall znamená obrovské zdržení. Například Pentium-Pro, Pentium 2 a Pentium 3 měly pipeline s více jak 12 fázemi, mispredict stál něco mezi 10 a 15 takty a i když měly pokročilý dynamický branch predictor, který fungoval s 90% přesností, ztrácely 30% výkonu kvůli těm 10 zmýleným procentům. Pentium 4 měl pipeline dlouhou 31 taktů a to pravděpodobně způsobovalo jeho nepřesvědčivé výkony.

V současných velkých procesorech jen přibližně 6 až 8 procent plochy čipu skutečně provádí výpočty, zbytek se stará, aby tento zlomek křemíku měl stále co na práci. Jde o branch predition jednotky, několik úrovní cache, out-of-order engine, virtuální registry, spekulace, prefetching a další hardware, který bojuje proti latenci a zrychluje běžný kód, který je typický tím, že obsahuje hodně skoků.

Zpátky ke zmíněnému článku. Ten testoval rychlost skoků na kódu, který vypadal nějak takto:

for (int i = 0; i < max; i++) if (<condition>) sum++;

Podmínka měla tvar (i & constant) == 0. Volbou různé konstanty se dá snadno vytvořit krátký opakující se vzor. Původní výsledky zkombinované s těmi mými vypadají následovně:

|-------------------------------------------------------------------------------------
| Condition              | Pattern     |   2010  |  Intel Atom      | Intel Haswell i5
|                                      |         |     -O0 |    -O3 |    -O0 |   -O3
|-------------------------------------------------------------------------------------
| (i & 0x80000000) == 0  | TTTTTTTT    |  322 ms |  388 ms | 374 ms | 211 ms | 86 ms
| (i & 0xffffffff) == 0  | FFFFFFFF    |  276 ms |  334 ms | 374 ms | 218 ms | 86 ms
| (i & 1) == 0           | TFTFTFTF    |  760 ms |  602 ms | 371 ms | 216 ms | 86 ms
| (i & 3) == 0           | TFFFTFFF    |  513 ms |  427 ms | 378 ms | 219 ms | 86 ms
| (i & 2) == 0           | TTFFTTFF    | 1675 ms |  441 ms | 373 ms | 213 ms | 85 ms
| (i & 4) == 0           | TTTTFFFF    | 1275 ms |  642 ms | 378 ms | 214 ms | 85 ms
| (i & 8) == 0           | 8T 8F ...   |  752 ms |  546 ms | 370 ms | 214 ms | 85 ms
| (i & 16) == 0          | 16T 16F ... |  490 ms |  446 ms | 377 ms | 214 ms | 85 ms
| xorshift rand len 8    | random      |  ---    | 1212 ms | 680 ms | 234 ms | 86 ms
| xorshift rand len 16   | random      |  ---    | 1284 ms | 676 ms | 230 ms | 86 ms
| xorshift rand len 32   | random      |  ---    | 1328 ms | 679 ms | 228 ms | 86 ms
| xorshift rand len 64   | random      |  ---    | 1428 ms | 676 ms | 227 ms | 86 ms
| xorshift rand len 128  | random      |  ---    | 1475 ms | 676 ms | 227 ms | 86 ms
| xorshift rand len 256  | random      |  ---    | 1560 ms | 679 ms | 229 ms | 85 ms

Sloupec 2010 ukazuje časy naměřené v onom článku na neznámém procesoru a s neznámým počtem iterací. Z toho důvodu nevěnujte žádnou pozornost rozdílu v absolutních číslech mezi těmito a mými časy. V následujících sloupcích jsou časy na Atomu reprezentující low-end všech low-endů a na desktopovém i5 Haswellu, reprezentujícím rozumný křemík. V obou případech byl testovací kód kompilovaný gcc s příznaky -O0 (bez optimalizací) a -O3 (maximální optimalizace). K tomu jsem přidal pár pseudo-náhodných testů, ve kterých se opakoval náhodný vzor určité délky (vygenerovaný přes xorshift RNG).

Jak je z výsledků vidět, tak i prachobyčejný levný Atom určený do netbooků v nejhorším případě běží 2x pomaleji a současné rozumné procesory v žádném z testů nepocítí žádné zpomalení. Branch prediction jednotky doznaly znatelného zlepšení a dokáží perfektně detekovat dlouhé opakující se vzory, pokud jsou přítomny. Když má skok skutečně náhodný charakter, nepomůže ani svěcená voda.

Zajímavé jsou také výsledky -O3 optimalizace. Na Haswellu kód s -03 je jenom rychlejší, ale na Atomu smaže rozdíly mezi ideálními a neideálními případy a všechno najednou běží tak, jako kdyby branch predictor vždycky uhodl správně. Kouzlo spočívá v tom, že GCC se rozhodlo if (<condition>) sum++ nekompilovat jako podmíněný skok, ale jako instrukci CMOV neboli conditional move. Ta funguje tak, že přesune data mezi dvěma místy, ale jen pokud je splněná určitá podmínka. CMOV je vykonána v každém případě, ale může nebo nemusí mít svůj efekt. Protože nejde o podmíněný skok, procesoru nehrozí pipeline stall a kód běží stabilní rychlostí. Pokud je skok nepředvídatelný, zrychlení může být znatelné (jak je vidět tak pro náhodné vzory je to až 2.5x), ale to není zas tak běžný případ.

Pro úplnost: -O0 vygeneruje následující instrukce:

test   %eax,%eax        ; kontrola podmínky
jne    40065a           ; skočí za následující instrukci, pokud podmínka neplatí
addl   $0x1,-0x8(%rbp)  ; inkrementuje sum

-O3 vygeneruje něco na způsob tohoto:

test   %edx,%eax        ; kontrola podmínky
cmove  %ecx,%ebx        ; pokud podmínka platí, přesune ecx do ebx
lea    0x1(%ebx),%ecx   ; ecx ← ebx + 1

CMOV je jediná podmíněná x86 instrukce, ale například 32bitový ARM nebo Itanium má podmíněné skoro všechno a může tedy dělat například podmíněné aritmetiku. ARM to má kvůli chybějícím/slabým branch predictorům, Itanium proto, že bylo navrženo pro masivní ILP a software pipelining (z toho důvodu má 64 1-bitových predikátových registrů a rotující registry).

Když se podívám na podrobné informace vygenerované programem perf, který poskytuje přístup k interním čítačům CPU, dostanu velice podrobný pohled, co se děje pod kapotou.

|------------------------------------------------------------------------------------------------------
| Condition              | Intel Atom
|                        | -O0                                  | -O3
|                        |    time | branch-miss | instr |  IPC |   time | branch-miss | instr |  IPC
|------------------------------------------------------------------------------------------------------
| (i & 0x80000000) == 0  |  388 ms |       0,01% |   893 | 1,41 | 374 ms |       0.02% |   600 | 0,98
| (i & 0xffffffff) == 0  |  334 ms |       0,01% |   799 | 1,48 | 374 ms |       0.02% |   599 | 0,99
| (i & 1) == 0           |  602 ms |       0,02% |   851 | 0,86 | 371 ms |       0.02% |   600 | 0,99
| (i & 3) == 0           |  427 ms |       0,01% |   823 | 1,18 | 378 ms |       0.02% |   600 | 0,97
| (i & 2) == 0           |  441 ms |       0,01% |   850 | 1,18 | 373 ms |       0.02% |   599 | 0,98
| (i & 4) == 0           |  642 ms |       0,02% |   849 | 0,81 | 378 ms |       0.02% |   598 | 0,97
| (i & 8) == 0           |  546 ms |       6,27% |   850 | 0,95 | 370 ms |       0.02% |   600 | 0,99
| (i & 16) == 0          |  446 ms |       3,15% |   846 | 1,16 | 377 ms |       0.02% |   599 | 0,98
| xorshift rand len 8    | 1212 ms |       0,04% |  1625 | 0,82 | 680 ms |       0,03% |   901 | 0.81
| xorshift rand len 16   | 1284 ms |       4,15% |  1637 | 0,78 | 676 ms |       0,03% |   900 | 0.81
| xorshift rand len 32   | 1328 ms |       7,53% |  1645 | 0,75 | 679 ms |       0,03% |   901 | 0.81
| xorshift rand len 64   | 1428 ms |      12,87% |  1653 | 0,70 | 676 ms |       0,03% |   900 | 0.81
| xorshift rand len 128  | 1475 ms |      15,43% |  1658 | 0,68 | 676 ms |       0,03% |   900 | 0.81
| xorshift rand len 256  | 1560 ms |      20,32% |  1650 | 0,64 | 679 ms |       0,03% |   900 | 0.81

|------------------------------------------------------------------------------------------------------
| Condition              | Intel Haswell i5
|                        | -O0                                  | -O3
|                        |    time | branch-miss | instr |  IPC |  time  | branch-miss | instr |  IPC
|------------------------------------------------------------------------------------------------------
| (i & 0x80000000) == 0  |  211 ms |       0.00% |   800 | 1,07 |  86 ms |       0.00% |   600 | 1.99
| (i & 0xffffffff) == 0  |  218 ms |       0.00% |   701 | 0,91 |  86 ms |       0.00% |   600 | 1.99
| (i & 1) == 0           |  216 ms |       0.00% |   751 | 0,99 |  86 ms |       0.00% |   600 | 1.99
| (i & 3) == 0           |  219 ms |       0.00% |   725 | 0,94 |  86 ms |       0.00% |   600 | 1.99
| (i & 2) == 0           |  213 ms |       0.00% |   750 | 1,00 |  85 ms |       0.00% |   600 | 1.99
| (i & 4) == 0           |  214 ms |       0.00% |   750 | 0,99 |  85 ms |       0.00% |   600 | 1.99
| (i & 8) == 0           |  214 ms |       0.00% |   750 | 0,99 |  85 ms |       0.00% |   600 | 1.99
| (i & 16) == 0          |  214 ms |       0.00% |   750 | 0,99 |  85 ms |       0.00% |   600 | 1.99
| xorshift rand len 8    |  234 ms |       0.00% |  1625 | 1,96 |  86 ms |       0.01% |   900 | 2.98
| xorshift rand len 16   |  230 ms |       0.00% |  1638 | 2,01 |  86 ms |       0.01% |   900 | 2.99
| xorshift rand len 32   |  228 ms |       0.00% |  1644 | 2,04 |  86 ms |       0.01% |   900 | 2.99
| xorshift rand len 64   |  227 ms |       0.00% |  1652 | 2,06 |  86 ms |       0.01% |   900 | 2.99
| xorshift rand len 128  |  227 ms |       0.06% |  1657 | 2,06 |  86 ms |       0.01% |   900 | 2.99
| xorshift rand len 256  |  229 ms |       0.01% |  1649 | 2,05 |  85 ms |       0.01% |   900 | 2.99

Sloupec branch-miss ukazuje kolik podmíněných skoků bylo špatně předpovězeno, instr počet vykonaných instrukcí a IPC počet instrukcí vykonaných v jednom taktu. Jak je vidět úplně napravo, v tomto testu rozumný procesor dneška zvládá vykonat dvě až tři instrukce každý takt a téměř žádný skok není chybně předpovězen.

Dále k tématu:

@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články