Von Neumannovy lži

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/wi­de-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:

  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

Pozn:

Flattr this!

This entry was posted in CPU. Bookmark the permalink.

5 Responses to Von Neumannovy lži

  1. W says:

    > zatímco data-flow to dělá na celém programu v době kompilace.

    Hmm, nemá to pak nevýhodu třeba při polymorfismu?

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

    Z hlavy to přesně nevím, ale mám za to, že třeba některé úspornější ARMy jsou in-order. V podstatě to je – pokud to dobře chápu – in-order von Neumann s pipeliningem.

      1. Polymorfní metody tvoří datovou závislost tak jako tak. Rozdíl udělá hardware (jako je BTB), který se snaží odhadnout cíl skoku a současné OOO stroje jsou v tom velice dobré.
      2. Myslel jsem to pro kategorii notebooky/des­ktopy/servery a jiných velkých procesorů, kde jde o výkon. Samozřejmě bokem existuje spousta procesorů s nízkou spotřebou, které jsou velice jednoduché.
      • v6ak says:
        1. To jo, ale pokud bychom to chtěli dělat staticky jako v data flow machine, tak pohoříme (uděláme to genericky a ne vždy optimálně), dynamické řešení tu má výhodu.
        2. Tam, kde jde o výkon, tak jo. Pokud ale vím, tak notebooky s Atomy (aspoň některé) a snad třeba Snapdragon 808 v rámci big.LITTLE kombinuje in-order a out-of-order jádra, aby mohl podle aktuálních potřeb vyhovět jak vysokému výkonu, tak nízké spotřebě (pokud jsem to dobře pochopil). Tzn. in-order není jen otázkou mikrocontrollerů do klávesnic a podobných zařízení.
        • Pravda. Dynamický přístup má výhody, protože může agresivně spekulovat. Hlavní příslib staticky sheduled (jaký je překlad do Češtiny?) strojů jako tohle nebo VLIW je v tom, že spoustu práce udělá kompilátor a oni nepotřebují mít tenhle dynamický hardware a proto můžou být menší, levnější a s menší spotřebou. Taková je aspoň teorie.

          • v6ak says:

            Když nad tím tak přemýšlím:

            • Není překvapením, že se statická varianta neuchytila na desktopu. Vyžaduje to, aby se SW trošku přizpůsobil HW, a tedy změna v architektuře HW spíše ovlivní SW. Pokud ale dnes stále na majoritní platformě běžně potkáváme 32b aplikace, bylo by naivní očekávat takovouto podporu. Na Linuxu by to možná bylo o něco reálnější, záleželo by ale, kolik takových instrukčních sad by vzniklo.
            • Kromě embedded systémů by to mělo smysl i tam, kde máme JIT s cacheováním. Třeba Android 7.
            • JIT a cache má ještě jednu výhodu, řeší i problém s podporou ze strany vývojářů. Teda kompilátor by bylo potřeba přizpůsobit, ostatní by se ale tím přizpůsobilo samo. Tady by to mohlo docela dávat smysl…

Leave a Reply

Your email address will not be published. Required fields are marked *