funkcionálně.cz

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

Von Neumannovy lži

27. 5. 2017 — k47

Asi takhle: Existují dvě široké rodiny procesorů. Na jedné straně Von Neumannovy stroje a na druhé data-flow mašiny. První jmenovaná zpracovává jednu instrukci za druhou, druhá k programu přistupuje jako ke grafu závislostí, kdy každá operace je závislá na některých předcházejících a jakmile jsou všechny závislosti splněny, může být operace provedena.

Von Neumannova architektura je na papíře horší a mnohem méně ambiciózní než data-flow, protože je z povahy sekvenční, kdežto data-flow architektury jsou přirozeně paralelní. Jak dokládá historie, nakonec jsme skončili ve spárech Von Neumanna i přesto, že data-flow nebyl jen divoký sen poblázněných akademiků a tyto stroje se skutečně vyráběly. Na první pohled to může vypadat jako další triumf worse is better a vítězství průměrnosti. Pravda je však komplikovanější a má v sobě něco málo dramatické ironie.

To by jako úvod stačilo, teď je čas se po hlavě vrhnout do zákopů.

Budu uvažovat, že jsem napsal následující funkci (jde o kus kódu z mých experimentů s řazením):

def packedTerminatedByteSlice(arr: Array[Byte], from: Int, to: Int): Long = {
  var i = from
  var j = 0
  val end = math.min(arr.length, to)
  var res = 0L

  while (i < end) {
    res |= ((1 << 8) | arr(i)) << j
    i += 1
    j += 9
  }

  res
}

Jak by tato funkce byla vykonána na hypotetické data-flow mašině? Zajímá mě jen smyčka na konci funkce.

Je vidět, že v těle smyčky existují tři nezávislé cesty, které může data-flow stroj provádět najednou. Zatímco dělá logické ORy a SHIFTy, aby aktualizoval proměnnou res, může paralelně inkrementovat i a j. Napříč iteracemi se otevírají další možnosti: Podmínka smyčky i < end závisí jen na proměnné i, je možné ji tedy testovat, zatímco stroj provádí operace minulé iterace. Ze schématu je vidět, že jeden běh smyčky zabere tolik času, kolik potřebuje nejdelší cesta v grafu (modulo implementační detaily).

Von Neumannova architektura je proti tomu mnohem jednodušší. Program je přeložen na lineární sekvenci instrukcí, které jsou prováděny v řadě jedna za druhou.

Moje funkce by se mohla přeložit například na následující pseudo-assembly:

cond = cmp i end
jump_if_less_then cond
tmp1 = mov arr(i)
tmp2 = or 256 tmp1
tmp3 = shift tmp2 j
res  = or res tmp3
i    = add i 1
j    = add j 9
jump back

Kanonický Von Neumann načte jednu instrukci, provede ji a přesune se na další. Tělo smyčky obsahuje 9 instrukcí a to by mělo určit dobu jejího běhu1 .

Návrháři architektur jsou však vynalézaví lidé, věčně nespokojení s tím, co současný hardware dokáže, a neustále přemýšlejí, jak starého Von Neumanna vylepšit. Došlo ke zvyšování taktů, což vedlo nejdříve k několika-taktovým instrukcím a pak k pipelinování. Ale stále šlo o stejnou architekturu - jedna instrukce v jeden čas, i když se různé fáze různých instrukcí překrývaly. Změnila se jediná věc: Nejednou bylo třeba sledovat závislosti pipelinovaných instrukcí. Pokud operace hned požadovala výsledek té předchozí, musela čekat, než ta předchozí dokončí svojí práci a zapíše výsledek do registru2 . Kdyby nečekala, přečetla by nevalidní data. Hardware musel na pár taktů zastavit práci a v pipeline se vyskytla bublina (pipeline bubble).

a = x + 1
b = a + 1 // závisí na a

a: [ fetch | decode | read operands | execute | write result ]
b:         [ fetch  | decode        | ------- | ------------ | read operands | execute | write result ]

Pozorný čtenář si jistě všiml, že poslední dva součty ve výpisu instrukcí ukázkové funkce jsou na sobě zcela nezávislé. Je tedy možné je odpálit najednou bez komplikované data-flow mašinérie, která sleduje závislosti celého programu. Stačí jen trochu křemíku, který analyzuje vztahy sousedících operací. Tohle zjištění vedlo ke vzestupu superskalárních/wide-issue strojů - stále Von Neumannovských architektur, jen rozšířených o schopnost najednou odbavit nezávislé sousedící instrukce, pokud hardware má dostatek prostředků (v mém případě dvě ALU). Může jít o dynamickou vlastnost, kdy třeba X86 procesor analyzuje proud instrukcí za běhu a nebo statickou jako v případě VLIW nebo Itania.

Wide-issue jak jsem ho popsal využívá paralelismu jen v omezených případech. Nemůže paralelně provádět nezávislé instrukce mimo pořadí programu. Například tento kousek kódu

tmp1 = add input 1
x    = add tmp1 1
y    = add input 2

má vzájemně nezávislé operace na prvním a třetím řádku, ale druhý řádek závisí na výsledku toho prvního. Aby hardware mohl paralelně provést nezávislé instrukce, musí dělat věci mimo pořadí programu, tedy out-of-order (OOO). Tímto směrem směřovala evoluce ctihodného Von Neumannova stroje. OOO hardware sleduje vzájemné závislosti poměrně velkého okna instrukcí3 a snaží se naplno vytížit všechny dostupné funkční jednotky pomocí spekulativní exekuce. Udržuje si při tom dostatečné množství stavových informací, aby se dokázal vrátit zpátky do konzistentního stavu, kdyby se spekulace ukázaly jako příliš optimistické (např. kvůli špatné branch prediction).4

Všimli jste si toho taky? Out-of-order procesor vypadá skoro jako data-flow stroj.

Ironií osudu je, že postupnou evolucí se Von Neumann postupně přibližoval data-flow architekturám a došlo to tak daleko, že interní chování OOO stroje je téměř k nerozeznání od jeho data-flow bratrance. Rozdíl je jen v tom, že OOO stroj vytváří graf závislostí za běhu na poměrně omezeném okně instrukcí, zatímco data-flow to dělá na celém programu v době kompilace.

OOO stroje do segmentu osobních počítačů vpadly spolu s Pentiem Pro v roce 1995. Von Neumanovu architekturu tedy téměř nikdo z nás nepoužívá už dvacet let.


Dále k tématu:


Pozn:

  1. Pokud tedy budu uvažovat jednoduchý model, kdy každá instrukce trvá stejně dlouho a odmyslím si všechny nežádoucí efekty jako jsou rozdíly mezi rychlostí cache a RAM.
  2. Tyto případy částečně řeší tzv. Operand forwarding, který kromě zápisu do příslušného registru, data přesměruje přímo do následující instrukce.
  3. Například na Haswelech je to 192. Skylake generace Intelích CPU to rozšířila na 224. Nejde o x86 instrukce, ale o dekódované mikro-operace.
  4. Způsoby zotavení ze špatných spekulací jsou popsány například ve Fast Branch Misprediction Recovery in Out-of-order Superscalar Processors
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články