funkcionálně.cz

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

Tak jak je to s tou rychlostí procesorů a pamětí?

25. 9. 2013 — k47

Jedna stará moud­rost říká: „pro­ce­sory jsou rychlé, paměť je pomalá“.

Ale tahle jed­no­du­chá poučka ne­do­káže popsat dra­ma­tické roz­díly mezi oběma světy. Pro­ce­sory jsou totiž ne­u­vě­ři­telně rychlé a vět­šinu času čekají na paměť, která se v po­rov­nání s nimi po­hy­buje tempem pra­sta­rých le­dovců. Data z RAM dorazí se zpož­dě­ním při­bližně 100ns. Za tu dobu 3GHz CPU odbije 300 taktů kře­mí­ko­vého srdce. Ale to jsou takty, in­strukcí může stih­nout ještě víc – mo­derní pro­ce­sory mají ně­ko­lik portů a na každém z nich může být pro­vá­děna jedna in­strukce. Starší Intely mají 6 portů, nej­no­vější Haswelly pak rovnou 8. Taková bestie pak stihne pro­vést až 2400 in­strukcí v době, než data dorazí z paměti. Navíc ně­které z nich mohou být SIMD in­strukce, které pro­vá­dějí jednu ope­raci na ně­ko­lika po­lož­kách na­jed­nou (víc info zdezde). CPU by do­ká­zalo pro­vést ohromné množ­ství vý­po­čtů, kdyby na data nikdy ne­mu­sel čekat a vždycky je měl po ruce (plus tohle bude ex­po­nen­ci­álně větší pro­blém u kvan­to­vého po­čí­tání). Pro­ce­sory tyto la­tence, které můžou mít tra­gický dopad na výkon pro­gramu, mas­kují jak jenom mohou: ně­ko­lik úrovní cache, pre­fet­ching, load/store bu­f­fery, Out-of-order execu­tion, branch pre­diction a spe­ku­la­tivní pro­vá­dění kódu. Rych­losti CPU po­sled­ních ně­ko­lik let nijak vý­razně ne­ros­tou, ale ani nemusí, pro­tože stejně jenom vět­šinu času za­há­lejí. Paměť musí zrych­lit.


Abych si tohle ověřil, napsal jsem jed­no­du­chý pro­gram, který otes­tuje kolik cache-miss zvládne pro­ce­sor za vte­řinu. Kód dělá jenom to, že ve smyčce za­pi­suje na ná­hodné indexy v poli data. Pokud je pole mnohem větší než nej­větší cache, ke které má pří­stup jedno jádro pro­ce­soru, a indexy sku­tečně ná­hodné, každá ope­race s polem způ­sobí cache-miss (data nejsou v rychlé cache a musí do­ra­zit z hlavní paměti).

Zjed­no­du­šený tes­to­vací pro­gram zde:

val size     = 1 << 26  // == 64M x 8B long == 512MB
val sizeMask = size - 1

val iterations = 10000000 // 10M

val data            = Array.fill(size) { util.Random.nextInt(2) } // 0 - 1
val randomPositions = Array.fill(size) { util.Random.nextInt(size) }

var iteration = 0
var i = 0

while (iteration < iterations) {
  // polem randomPositions procházím sekvenčně
  // prefetcher procesoru se postará, že požadovaná data budou v cache
  val pos = randomPositions(i & sizeMask)

  // instrukce load, add, store
  // load vždy způsobí cache miss
  data(pos) += 1

  i += 1
  iteration += 1
}

Vý­sledný čas while smyčky na mém starém Core2 E6300 s 2MB L2 cache a DDR2 je při­bližně 570ms, tedy 57ns na jeden cache-miss a to je po­ně­kud málo. Vý­sle­dek by měl být +- dvoj­ná­sobný.

Co se tady jenom děje?

Od­po­věď je jed­no­du­chá: pro­ce­sory jsou bestie a do­ká­žou se vy­po­řá­dat s tím, když jim schválně házím klacky pod nohy. CPU totiž dělá věci pa­ra­lelně a spe­ku­la­tivně.

Už mnoho let jsou všechny pro­ce­sory Out-of-order (OOO), tedy ne­vy­ko­nají jednu in­strukci a teprve až potom se po­su­nou na další, ale in­strukce do nich proudí, jsou pa­ra­lelně de­kó­do­vány, řadí se do front, vy­ko­ná­vají se zá­ro­veň na růz­ných por­tech (ne každý port dokáže vy­ko­nat každou in­strukci), ně­které čekají, jiné jednou dál. Valí se vpřed jako lavina a pro­ce­sor přesto udr­žuje iluzi, že se in­strukce vy­ko­ná­vají sek­venčně (je to jako kdyby žong­lo­val pa­de­sát míčků a mo­to­ro­vou pilu).

Na­pří­klad první dva řádky kódu se smyčce jsou na sobě zá­vislé a tak se musí pro­vést sek­venčně, ale obě in­kre­men­tace na ničem zá­vislé nejsou a tak se můžou pro­vést zá­ro­veň na vol­ných ALU (Haswell má např. 4 ALU). A stejně tak CPU může na­jed­nou čekat na dvě pro­bí­ha­jící load ope­race, které vy­vo­laly cache-miss.

Pro­ce­sory pak také pro­vá­dějí kód spe­ku­la­tivně, když nějaká in­strukce čeká na data nebo na do­kon­čení, CPU se snaží od­had­nout, co se bude dít dál, začít de­kó­do­vat in­strukce, vy­ko­ná­vat je s tím, že až se do­končí ope­race, která všechno blo­kuje a ukáže se, že před­po­klady byly správné, spousta práce už bude hotova. Když se odhad mýlil, všechna spe­ku­la­tivní práce se zahodí a začne se znovu. Pro­ce­sory si to můžou do­vo­lit, pro­tože vět­šinu času stejně jenom na něco čekají. Takhle fun­guje branch pre­diction, který se snaží od­had­nout cíl skoku (u smyček je to velice před­ví­da­telné), nebo pre­fet­ching který spe­ku­la­tivně načítá data z hlavní paměti do cache, když vidí, že paměť pro­chá­zím sek­venčně.

A právě souhra těchto dvou aspektů uka­zuje, proč je tes­to­vací kód dva­krát rych­lejší, než by měl: CPU už zná hod­notu i, může spe­ku­lo­vat a začít vy­ko­ná­vat další ite­raci smyčky za­tímco před­chozí ite­race čeká na data z paměti. Spe­ku­la­tivní ite­race narazí na vlastní cache-miss a taky začne čekat zá­ro­veň s před­chozí ite­rací. Tohle efek­tivně srazí la­tenci paměti na po­lo­vinu a s tím i dobu běhu pro­gramu.

Pokud se ná­ho­dou stane, že první ite­race pře­píše hod­notu na které spe­ku­la­tivní ite­race závisí (např. v poli randomPositions po sobě ná­sle­dují dva stejné indexy), CPU to pozná, in­va­li­duje spe­ku­la­tivní data a zo­pa­kuje po­slední ite­raci smyčky. Spe­ku­la­tivní práce nikdy ne­o­vlivní cho­vání pro­gramu, pro­tože její efekty nejsou vidět mimo pořadí.

Ještě pro úpl­nost ně­ko­lik čísel: Pokud má pole data délku 1 << 26 (512MB) smyčka trvá 570ms. Pokud má délku 1 << 27 (1024MB) smyčka trvá 760ms, za což nej­spíš může TLB a cache-miss na ta­bulku strá­nek (well fuck!). Pokud se pro­vádí jenom zápis, tedy data(pos) = 1 místo data(pos) += 1, trvá to jenom 390ms.


Abych mohl zjis­tit sku­tečný čas, který trvá jeden cache-miss, musím za­me­zit spe­ku­la­tiv­nímu cho­vání. To se dá udělat jed­no­duše tak, že se do kódu vnese datová zá­vis­lost. Ne­in­kre­men­tuji tedy pro­měn­nou i o jed­ničku, ale o 1 nebo 2 v zá­vis­losti na hod­notě na­čtené z pole data (které je plné ná­hod­ných čísel):

while (iteration < iterations) {
  val pos = randomPositions(i & sizeMask)
  val d = data(pos)
  data(pos) = d + 1

  // datová závislost, o kolik se posune i závisí na hodnotě na kterou se čeká
  i += (if ((d & 1) == 0) 1 else 2)
  iteration += 1
}

Teď už smyčka trvá pod­statně déle: 1460ms – 146ns na jeden cache-miss.

Udělal jsem ně­ko­lik testů z různou ve­li­kostí pole data, vý­sledky jsou v ná­sle­du­jící ta­bulce (může za ně cache, strán­ko­vání paměti a TLB):

délka ve­li­kost doba
1 << 27 1024MB 1700ms
1 << 26 512MB 1460ms
1 << 25 256MB 1320ms
1 << 24 128MB 1240ms
1 << 23 64MB 1200ms
1 << 22 32MB 1130ms
1 << 21 16MB 1000ms
1 << 20 8MB 770ms
1 << 19 4MB 415ms
1 << 18 2MB 200ms

Pro srov­nání ještě přidám verzi, která ne­skáče na ná­hodné indexy, ale pro­chází polem sek­venčně:

while (iteration < iterations) {
  // pos je sekvenční
  val pos = i & sizeMask
  data(pos) += 1

  i += 1
  iteration += 1
}

Tahle smyčka se pro­vede za pou­hých 19ms, tedy 1.9ns na ite­raci, což od­po­vídá +- 5 taktům CPU.


Závěr **

Doufám, že jsem tady aspoň čás­tečně ukázal, že pro­ce­sory jsou velice ra­fi­no­vané stroje a in­že­nýři v Intelu a AMD strá­vili roky, aby im­ple­men­to­vali celé plejády triků a op­ti­ma­li­zací, díky kterým pro­gram běhá rychle i za velice ne­pří­z­ni­vých pod­mí­nek. Na druhou stranu taky musí být jasné, že když cho­vání CPU budeme znát a vy­u­ži­jeme ho, můžou být naše pro­gramy mnohem rych­lejší, ale často je tohle cho­vání slo­žité a kom­plexní a na vý­sle­dek má vliv mnoho fak­torů.


Další čtení:

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