funkcionálně.cz

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

Jedna stará moudrost říká: "procesory jsou rychlé, paměť je pomalá".

Ale tahle jednoduchá poučka nedokáže popsat dramatické rozdíly mezi oběma světy. Procesory jsou totiž neuvěřitelně rychlé a většinu času čekají na paměť, která se v porovnání s nimi pohybuje tempem prastarých ledovců. Data z RAM dorazí se zpožděním přibližně 100 ns. Za tu dobu 3GHz CPU odbije 300 taktů křemíkového srdce. Ale to jsou takty, instrukcí může stihnout ještě víc - moderní procesory mají několik portů a na každém z nich může být prováděna jedna instrukce. Starší Intely mají 6 portů, nejnovější Haswelly pak rovnou 8. Taková bestie pak stihne provést až 2400 instrukcí v době, než data dorazí z paměti. Navíc některé z nich mohou být SIMD instrukce, které provádějí jednu operaci na několika položkách najednou (víc info zde a zde). CPU by dokázalo provést ohromné množství výpočtů, kdyby na data nikdy nemusel čekat a vždycky je měl po ruce (plus tohle bude exponenciálně větší problém u kvantového počítání). Procesory tyto latence, které můžou mít tragický dopad na výkon programu, maskují jak jenom mohou: několik úrovní cache, prefetching, load/store buffery, Out-of-order execution, branch prediction a spekulativní provádění kódu. Rychlosti CPU posledních několik let nijak výrazně nerostou, ale ani nemusí, protože stejně jenom většinu času zahálejí. Paměť musí zrychlit.

Abych si tohle ověřil, napsal jsem jednoduchý program, který otestuje kolik cache-miss zvládne procesor za vteřinu. Kód dělá jenom to, že ve smyčce zapisuje na náhodné indexy v poli data. Pokud je pole mnohem větší než největší cache, ke které má přístup jedno jádro procesoru, a indexy skutečně náhodné, každá operace s polem způsobí cache-miss (data nejsou v rychlé cache a musí dorazit z hlavní paměti).

Zjednodušený testovací program 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řibližně 570 ms, tedy 57 ns na jeden cache-miss a to je poněkud málo. Výsledek by měl být +- dvojnásobný.

Co se tady jenom děje?

Odpověď je jednoduchá: procesory jsou bestie a dokážou se vypořádat s tím, když jim schválně házím klacky pod nohy. CPU totiž dělá věci paralelně a spekulativně.

Už mnoho let jsou všechny procesory out-of-order (OOO), tedy nevykonají jednu instrukci a teprve až potom se posunou na další, ale instrukce do nich proudí, jsou paralelně dekódovány, řadí se do front, vykonávají se zároveň na různých portech (ne každý port dokáže vykonat každou instrukci), některé čekají, jiné jednou dál. Valí se vpřed jako lavina a procesor přesto udržuje iluzi, že se instrukce vykonávají sekvenčně (je to jako kdyby žongloval padesát míčků a motorovou pilu).

Například první dva řádky kódu se smyčce jsou na sobě závislé a tak se musí provést sekvenčně, ale obě inkrementace na ničem závislé nejsou a tak se můžou provést zároveň na volných ALU (Haswell má např. 4 ALU). A stejně tak CPU může najednou čekat na dvě probíhající load operace, které vyvolaly cache-miss.

Procesory pak také provádějí kód spekulativně, když nějaká instrukce čeká na data nebo na dokončení, CPU se snaží odhadnout, co se bude dít dál, začít dekódovat instrukce, vykonávat je s tím, že až se dokončí operace, která všechno blokuje a ukáže se, že předpoklady byly správné, spousta práce už bude hotova. Když se odhad mýlil, všechna spekulativní práce se zahodí a začne se znovu. Procesory si to můžou dovolit, protože většinu času stejně jenom na něco čekají. Takhle funguje branch prediction, který se snaží odhadnout cíl skoku (u smyček je to velice předvídatelné), nebo prefetching který spekulativně načítá data z hlavní paměti do cache, když vidí, že paměť procházím sekvenčně.

A právě souhra těchto dvou aspektů ukazuje, proč je testovací kód dvakrát rychlejší, než by měl: CPU už zná hodnotu i, může spekulovat a začít vykonávat další iteraci smyčky zatímco předchozí iterace čeká na data z paměti. Spekulativní iterace narazí na vlastní cache-miss a taky začne čekat zároveň s předchozí iterací. Tohle efektivně srazí latenci paměti na polovinu a s tím i dobu běhu programu.

Pokud se náhodou stane, že první iterace přepíše hodnotu na které spekulativní iterace závisí (např. v poli randomPositions po sobě následují dva stejné indexy), CPU to pozná, invaliduje spekulativní data a zopakuje poslední iteraci smyčky. Spekulativní práce nikdy neovlivní chování programu, protože její efekty nejsou vidět mimo pořadí.

Ještě pro úplnost několik čísel:

• Pokud má pole data délku 1 << 26 (512MB) smyčka trvá 570 ms.
• Pokud má délku 1 << 27 (1024MB) smyčka trvá 760 ms, za což nejspíš může TLB a cache-miss na tabulku stránek .
• Pokud se provádí jenom zápis, tedy data(pos) = 1 místo data(pos) += 1, trvá to jenom 390 ms.

Abych mohl zjistit skutečný čas, který trvá jeden cache-miss, musím zamezit spekulativnímu chování. To se dá udělat jednoduše tak, že se do kódu vnese datová závislost. Neinkrementuji tedy proměnnou i o jedničku, ale o 1 nebo 2 v závislosti na hodnotě načtené z pole data (které je plné náhodný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á podstatně déle: 1460 ms - 146 ns na jeden cache-miss.

Udělal jsem několik testů z různou velikostí pole data, výsledky jsou v následující tabulce (může za ně cache, stránkování paměti a TLB):

Pro srovnání ještě přidám verzi, která neskáče na náhodné indexy, ale prochází polem sekvenčně:

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

  i += 1
  iteration += 1
}

Tahle smyčka se provede za pouhých 19 ms, tedy 1.9 ns na iteraci, což odpovídá ±5 taktům CPU.

Závěr **

Doufám, že jsem tady aspoň částečně ukázal, že procesory jsou velice rafinované stroje a inženýři v Intelu a AMD strávili roky, aby implementovali celé plejády triků a optimalizací, díky kterým program běhá rychle i za velice nepříznivých podmínek. Na druhou stranu taky musí být jasné, že když chování CPU budeme znát a využijeme ho, můžou být naše programy mnohem rychlejší, ale často je tohle chování složité a komplexní a na výsledek má vliv mnoho faktorů.

Další čtení:

• What every programmer should know about memory - tenhle paper je naprostá nutnost pro všechny, kdo to s programováním myslí vážně
• A Journey Through the CPU Pipeline - článek, který přehledně vysvětlí pipeline a out-of-order execution
• Instruction latencies and throughput for AMD and Intel x86 processors
• Instruction tables Lists of instruction latencies, throughputs and micro-operation breakdowns for Intel, AMD and VIA CPUs