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 — k47

Před ně­ja­kou dobou jsem na­ra­zil na článek z roku 2010, který tes­to­val, jak si branch pre­diction pro­ce­sorů té doby poradí s růz­nými opa­ku­jí­cími se vzory skoků v pro­gramu. Došel k závěru, že když pro­ce­sor ne­do­káže skoky před­ví­dat, může být vý­sledný pro­gram až 6x po­ma­lejší, než když před­vídá per­fektně. Roz­hodl jsem se test zo­pa­ko­vat a zjis­tit, jak je na tom sou­časný hard­ware.

Rych­lost branch in­strukce (neboli pod­mí­ně­ného skoku) závisí na tom, jestli je její pod­mínka před­ví­da­telná. Pokud pro­ce­sor dokáže správně uhod­nout, zdali má skočit na jiné místo pro­gramu nebo po­kra­čo­vat s ná­sle­du­jící in­strukcí, je skok skoro za­darmo. Ale pokud pro­ce­sor neví nebo uhodne špatně, ná­sle­duje tak­zvaný pi­pe­line stall, kdy CPU zahodí všechnu roz­dě­la­nou práci a začne číst, de­kó­do­vat a vy­ko­ná­vat in­strukce ze správ­ného místa.

Toto cho­vání sou­visí s faktem, že všechny sou­časné pro­ce­sory jsou pi­pe­li­no­vané. Každá in­strukce vy­ža­duje ně­ko­lik ne­zá­vis­lých kroků, ty­picky to jsou fetch, decode, executewrite-back, kdy je in­strukce na­čtena z paměti, de­kó­do­vána, vy­ko­nána a vý­sledky za­psány zpátky do paměti. Kdysi dávno pro­ce­sory vzaly jednu in­strukci, vy­ko­naly sek­venčně všechny čtyři fáze a teprve potom se po­su­nuly na další. V honbě za vyšším vý­ko­nem CPU začala pro­vá­dět všechny fáze na­jed­nou pro různé in­strukce. Za­tímco jedna in­strukce za­pi­suje do paměti, ná­sle­du­jící se vy­ko­nává, ná­sle­du­jící je de­kó­do­vána a ná­sle­du­jící je na­čí­taná z paměti. Na­jed­nou se v pro­ce­soru na­chází ně­ko­lik in­strukcí za letu. Sou­časné pro­ce­sory mají pi­pe­line s více kroky než jsou ony čtyři a navíc jsou su­per­ska­lární, což zna­mená, že v každém taktu do­ká­žou zpra­co­vat ně­ko­lik in­strukcí. Z těchto důvodů je počet in­strukcí „za letu“ je mnohem vyšší. Délka pi­pe­line sou­visí s na­vy­šo­vá­ním taktu: Čím vyšší frek­vence, tím méně času má signál dostat se skrz jednu fázi pi­pe­line, 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ád­nout zpra­co­vat 4 in­strukce za takt, Ita­nium zvládne sta­bilně 12 a chys­taný Mill až 33.

Teď si před­stavte, že se v tomto per­fekt­ním sou­strojí vy­skytne pod­mí­něný skok. Část CPU, která načítá in­strukce na za­čátku pi­pe­line, se musí roz­hod­nout, jestli načte ná­sle­du­jící in­strukci, nebo tu na kterou branch může skočit. Pod­mínka, která to určuje, není zatím vy­ko­nána a ještě ně­ko­lik taktů nebude, dokud se ne­pro­bo­juje na druhý konec pi­pe­line. To je však příliš dlouhá doba a pro­ce­sor si nemůže do­vo­lit čekat. V ten oka­mžik na scénu na­stoupí branch pre­dic­tor a pokusí se to uhod­nout. Když se trefí, všechno jede jako na drát­kách, když se zmýlí, na­stane pi­pe­line stall, pro­ce­sor musí za­ho­dit všechnu práci do které se spe­ku­la­tivně pustil a začít na­čí­tat in­strukce ze správ­ného místa a pro­hnat je skrz celou pi­pe­line a tedy ztra­tit množ­ství času od­po­ví­da­jící délce pi­pe­line.

Na­štěstí je vět­šina skoků v pro­gramu velice dobře před­ví­da­telná. Na­pří­klad smyčky, které pro­je­dou mnoho ite­rací a během každé z nich branch in­strukce skočí na za­čá­tek, kromě té po­slední, kdy pro­padne. Pro­ce­sory po­u­ží­vají mnoho růz­ných va­ri­ant branch pre­dic­torů, které za­zna­me­ná­vají minulé cho­vání pod­mí­ně­ných skoků a před­po­klá­dají, že se stejné nebo po­dobné cho­vání bude opa­ko­vat i v bu­doucnu. Někdy mají ně­ko­lik růz­ných pre­dic­torů a jeden meta-pre­dic­tor, který učiní fi­nální roz­hod­nutí. Tímto způ­so­bem do­sa­hují im­pre­siv­ních vý­sledků, kdy mají skoro vždycky pravdu.

Branch pre­dic­tor je velice dů­le­žitá část CPU, pro­tože v ty­pic­kých pro­gra­mech před­sta­vují skoky každou šestou až osmou in­strukci a pi­pe­line stall zna­mená ob­rov­ské zdr­žení. Na­pří­klad Pen­tium-Pro, Pen­tium 2 a Pen­tium 3 měly pi­pe­line s více jak 12 fázemi, mispre­dict stál něco mezi 10 a 15 takty a i když měly po­kro­čilý dy­na­mický branch pre­dic­tor, který fun­go­val s 90% přes­ností, ztrá­cely 30% výkonu kvůli těm 10 zmý­le­ným pro­cen­tům. Pen­tium 4 měl pi­pe­line dlou­hou 31 taktů a to prav­dě­po­dobně způ­so­bo­valo jeho ne­pře­svěd­čivé výkony.

V sou­čas­ných vel­kých pro­ce­so­rech jen při­bližně 6 až 8 pro­cent plochy čipu sku­tečně pro­vádí vý­po­čty, zbytek se stará, aby tento zlomek kře­míku měl stále co na práci. Jde o branch pre­di­tion jed­notky, ně­ko­lik úrovní cache, out-of-order engine, vir­tu­ální re­gis­try, spe­ku­lace, pre­fet­ching a další hard­ware, který bojuje proti la­tenci a zrych­luje běžný kód, který je ty­pický tím, že ob­sa­huje hodně skoků.


Zpátky ke zmí­ně­nému článku. Ten tes­to­val rych­lost skoků na kódu, který vy­pa­dal nějak takto:

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

Pod­mínka měla tvar (i & constant) == 0. Volbou různé kon­stanty se dá snadno vy­tvo­řit krátký opa­ku­jící se vzor. Pů­vodní vý­sledky zkom­bi­no­vané s těmi mými vy­pa­dají ná­sle­dovně:

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

Slou­pec 2010 uka­zuje časy na­mě­řené v onom článku na ne­zná­mém pro­ce­soru a s ne­zná­mým počtem ite­rací. Z toho důvodu ne­vě­nujte žádnou po­zor­nost roz­dílu v ab­so­lut­ních čís­lech mezi těmito a mými časy. V ná­sle­du­jí­cích sloup­cích jsou časy na Atomu re­pre­zen­tu­jící low-end všech low-endů a na desk­to­po­vém i5 Haswellu, re­pre­zen­tu­jí­cím ro­zumný křemík. V obou pří­pa­dech byl tes­to­vací kód kom­pi­lo­vaný gcc s pří­znaky -O0 (bez op­ti­ma­li­zací) a -O3 (ma­xi­mální op­ti­ma­li­zace). K tomu jsem přidal pár pseudo-ná­hod­ných testů, ve kte­rých se opa­ko­val ná­hodný vzor určité délky (vy­ge­ne­ro­vaný přes xor­shift RNG).

Jak je z vý­sledků vidět, tak i pra­choby­čejný levný Atom určený do net­booků v nej­hor­ším pří­padě běží 2x po­ma­leji a sou­časné ro­zumné pro­ce­sory v žádném z testů ne­po­cítí žádné zpo­ma­lení. Branch pre­diction jed­notky do­znaly zna­tel­ného zlep­šení a dokáží per­fektně de­te­ko­vat dlouhé opa­ku­jící se vzory, pokud jsou pří­tomny. Když má skok sku­tečně ná­hodný cha­rak­ter, ne­po­může ani svě­cená voda.

Za­jí­mavé jsou také vý­sledky -O3 op­ti­ma­li­zace. Na Haswellu kód s -03 je jenom rych­lejší, ale na Atomu smaže roz­díly mezi ide­ál­ními a ne­i­de­ál­ními pří­pady a všechno na­jed­nou běží tak, jako kdyby branch pre­dic­tor vždycky uhodl správně. Kouzlo spo­čívá v tom, že GCC se roz­hodlo if (<condition>) sum++ ne­kom­pi­lo­vat jako pod­mí­něný skok, ale jako in­strukci CMOV neboli con­di­ti­o­nal move. Ta fun­guje tak, že pře­sune data mezi dvěma místy, ale jen pokud je spl­něná určitá pod­mínka. CMOV je vy­ko­nána v každém pří­padě, ale může nebo nemusí mít svůj efekt. Pro­tože nejde o pod­mí­něný skok, pro­ce­soru ne­hrozí pi­pe­line stall a kód běží sta­bilní rych­lostí. Pokud je skok ne­před­ví­da­telný, zrych­lení může být zna­telné (jak je vidět tak pro ná­hodné vzory je to až 2.5x), ale to není zas tak běžný případ.

Pro úpl­nost: -O0 vy­ge­ne­ruje ná­sle­du­jící in­strukce:

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 vy­ge­ne­ruje 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á pod­mí­něná x86 in­strukce, ale na­pří­klad 32bitový ARM nebo Ita­nium má pod­mí­něné skoro všechno a může tedy dělat na­pří­klad pod­mí­něné arit­me­tiku. ARM to má kvůli chy­bě­jí­cím/slabým branch pre­dic­to­rům, Ita­nium proto, že bylo na­vr­ženo pro masivní ILPsoft­ware pi­pe­li­ning (z toho důvodu má 64 1-bi­to­vých pre­di­ká­to­vých re­gis­trů a ro­tu­jící re­gis­try).


Když se po­dí­vám na po­drobné in­for­mace vy­ge­ne­ro­vané pro­gra­mem perf, který po­sky­tuje pří­stup k in­ter­ním čí­ta­čům CPU, do­stanu velice po­drobný pohled, co se děje pod ka­po­tou.

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

Slou­pec branch-miss uka­zuje kolik pod­mí­ně­ných skoků bylo špatně před­po­vě­zeno, instr počet vy­ko­na­ných in­strukcí a IPC počet in­strukcí vy­ko­na­ných v jednom taktu. Jak je vidět úplně na­pravo, v tomto testu ro­zumný pro­ce­sor dneška zvládá vy­ko­nat dvě až tři in­strukce každý takt a téměř žádný skok není chybně před­po­vě­zen.


Dále k tématu:

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