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: Exis­tují dvě široké rodiny pro­ce­sorů. Na jedné straně Von Ne­u­man­novy stroje a na druhé data-flow mašiny. První jme­no­vaná zpra­co­vává jednu in­strukci za druhou, druhá k pro­gramu při­stu­puje jako ke grafu zá­vis­lostí, kdy každá ope­race je zá­vislá na ně­kte­rých před­chá­ze­jí­cích a jakmile jsou všechny zá­vis­losti spl­něny, může být ope­race pro­ve­dena.

Von Ne­u­man­nova ar­chi­tek­tura je na papíře horší a mnohem méně am­bi­ci­ózní než data-flow, pro­tože je z povahy sek­venční, kdežto data-flow ar­chi­tek­tury jsou při­ro­zeně pa­ra­lelní. Jak do­kládá his­to­rie, na­ko­nec jsme skon­čili ve spá­rech Von Ne­u­manna i přesto, že data-flow nebyl jen divoký sen po­bláz­ně­ných aka­de­miků a tyto stroje se sku­tečně vy­rá­běly. Na první pohled to může vy­pa­dat jako další triumf worse is better a ví­těz­ství prů­měr­nosti. Pravda je však kom­pli­ko­va­nější a má v sobě něco málo dra­ma­tické ironie.

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

Budu uva­žo­vat, že jsem napsal ná­sle­du­jící funkci (jde o kus kódu z mých ex­pe­ri­mentů s řa­ze­ní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 vy­ko­nána na hy­po­te­tické data-flow mašině? Zajímá mě jen smyčka na konci funkce.

Je vidět, že v těle smyčky exis­tují tři ne­zá­vislé cesty, které může data-flow stroj pro­vá­dět na­jed­nou. Za­tímco dělá lo­gické ORy a SHIFTy, aby ak­tu­a­li­zo­val pro­měn­nou res, může pa­ra­lelně in­kre­men­to­vat ij. Napříč ite­ra­cemi se ote­ví­rají další mož­nosti: Pod­mínka smyčky i < end závisí jen na pro­měnné i, je možné ji tedy tes­to­vat, za­tímco stroj pro­vádí ope­race minulé ite­race. Ze sché­matu je vidět, že jeden běh smyčky zabere tolik času, kolik po­tře­buje nejdelší cesta v grafu (modulo im­ple­men­tační de­taily).

Von Ne­u­man­nova ar­chi­tek­tura je proti tomu mnohem jed­no­dušší. Pro­gram je pře­lo­žen na li­ne­ární sek­venci in­strukcí, které jsou pro­vá­děny v řadě jedna za druhou.

Moje funkce by se mohla pře­lo­žit na­pří­klad na ná­sle­du­jící pseudo-as­sem­bly:

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

Ka­no­nický Von Ne­u­mann načte jednu in­strukci, pro­vede ji a pře­sune se na další. Tělo smyčky ob­sa­huje 9 in­strukcí a to by mělo určit dobu jejího běhu1 .

Ná­vr­háři ar­chi­tek­tur jsou však vy­na­lé­zaví lidé, věčně ne­spo­ko­jení s tím, co sou­časný hard­ware dokáže, a ne­u­stále pře­mýš­lejí, jak starého Von Ne­u­manna vy­lep­šit. Došlo ke zvy­šo­vání taktů, což vedlo nejdříve k ně­ko­lika-tak­to­vým in­struk­cím a pak k pi­pe­li­no­vání. Ale stále šlo o stej­nou ar­chi­tek­turu – jedna in­strukce v jeden čas, i když se různé fáze růz­ných in­strukcí pře­krý­valy. Změ­nila se jediná věc: Ne­jed­nou bylo třeba sle­do­vat zá­vis­losti pi­pe­li­no­va­ných in­strukcí. Pokud ope­race hned po­ža­do­vala vý­sle­dek té před­chozí, musela čekat, než ta před­chozí do­končí svojí práci a zapíše vý­sle­dek do re­gis­tru2 . Kdyby ne­če­kala, pře­četla by ne­va­lidní data. Hard­ware musel na pár taktů za­sta­vit práci a v pi­pe­line se vy­skytla bub­lina (pi­pe­line 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 ]

Po­zorný čtenář si jistě všiml, že po­slední dva součty ve výpisu in­strukcí ukáz­kové funkce jsou na sobě zcela ne­zá­vislé. Je tedy možné je od­pá­lit na­jed­nou bez kom­pli­ko­vané data-flow ma­ši­né­rie, která sle­duje zá­vis­losti celého pro­gramu. Stačí jen trochu kře­míku, který ana­ly­zuje vztahy sou­se­dí­cích ope­rací. Tohle zjiš­tění vedlo ke vze­stupu su­per­ska­lár­ních/wide-issue strojů – stále Von Ne­u­man­nov­ských ar­chi­tek­tur, jen roz­ší­ře­ných o schop­nost na­jed­nou od­ba­vit ne­zá­vislé sou­se­dící in­strukce, pokud hard­ware má do­sta­tek pro­středků (v mém pří­padě dvě ALU). Může jít o dy­na­mic­kou vlast­nost, kdy třeba X86 pro­ce­sor ana­ly­zuje proud in­strukcí za běhu a nebo sta­tic­kou jako v pří­padě VLIW nebo Itania.

Wide-issue jak jsem ho popsal vy­u­žívá pa­ra­le­lismu jen v ome­ze­ných pří­pa­dech. Nemůže pa­ra­lelně pro­vá­dět ne­zá­vislé in­strukce mimo pořadí pro­gramu. Na­pří­klad tento kousek kódu

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

má vzá­jemně ne­zá­vislé ope­race na prvním a třetím řádku, ale druhý řádek závisí na vý­sledku toho prv­ního. Aby hard­ware mohl pa­ra­lelně pro­vést ne­zá­vislé in­strukce, musí dělat věci mimo pořadí pro­gramu, tedy out-of-order (OOO). Tímto směrem smě­řo­vala evo­luce cti­hod­ného Von Ne­u­man­nova stroje. OOO hard­ware sle­duje vzá­jemné zá­vis­losti po­měrně vel­kého okna in­strukcí3 a snaží se naplno vy­tí­žit všechny do­stupné funkční jed­notky pomocí spe­ku­la­tivní exe­kuce. Udr­žuje si při tom do­sta­tečné množ­ství sta­vo­vých in­for­mací, aby se do­ká­zal vrátit zpátky do kon­zis­tent­ního stavu, kdyby se spe­ku­lace uká­zaly jako příliš op­ti­mis­tické (např. kvůli špatné branch pre­diction).4

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

Ironií osudu je, že po­stup­nou evo­lucí se Von Ne­u­mann po­stupně při­bli­žo­val data-flow ar­chi­tek­tu­rám a došlo to tak daleko, že in­terní cho­vání OOO stroje je téměř k ne­ro­ze­znání od jeho data-flow bra­trance. Rozdíl je jen v tom, že OOO stroj vy­tváří graf zá­vis­lostí za běhu na po­měrně ome­ze­ném okně in­strukcí, za­tímco data-flow to dělá na celém pro­gramu v době kom­pi­lace.

OOO stroje do seg­mentu osob­ních po­čí­tačů vpadly spolu s Pen­tiem Pro v roce 1995. Von Ne­u­ma­novu ar­chi­tek­turu tedy téměř nikdo z nás ne­po­u­žívá už dvacet let.


Dále k tématu:


Pozn:

  1. Pokud tedy budu uva­žo­vat jed­no­du­chý model, kdy každá in­strukce trvá stejně dlouho a od­mys­lím si všechny ne­žá­doucí efekty jako jsou roz­díly mezi rych­lostí cache a RAM.
  2. Tyto pří­pady čás­tečně řeší tzv. Ope­rand for­war­ding, který kromě zápisu do pří­sluš­ného re­gis­tru, data pře­smě­ruje přímo do ná­sle­du­jící in­strukce.
  3. Na­pří­klad na Haswelech je to 192. Sky­lake ge­ne­race In­te­lích CPU to roz­ší­řila na 224. Nejde o x86 in­strukce, ale o de­kó­do­vané mikro-ope­race.
  4. Způ­soby zo­ta­vení ze špat­ných spe­ku­lací jsou po­psány na­pří­klad ve Fast Branch Mispre­diction Re­co­very in Out-of-order Su­per­s­ca­lar Pro­ces­sors
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články