funkcionálně.cz

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

Čím více se věci mění, tím více zůstávají stejné

21. 5. 2016 — k47

Evgeny Mo­rozov v knize To Save Eve­ry­thing Click Here mluvil o epo­cha­lismu a ahis­to­ric­kém myš­lení. Epo­cha­lis­mus říká, že žijeme ve vý­ji­meč­ných časech a sou­časná doba je di­a­me­t­rálně od­lišná od všech mi­nu­lých a nic staré už ne­platí. Ahis­to­rické myš­lení s epo­cha­lis­mem velice úzce sou­visí – v pod­statě jde o sys­te­ma­tické ig­no­ro­vání his­to­rie a všeho, co jsme se z ní mohli naučit.

Přes­tože Mo­rozov psal o „In­ter­netu“ a di­gi­tální debatě obecně, stejný trend lze vy­cí­tit v IT ko­mu­nitě. Zdá se, že do­mi­nantní myš­len­kový proud tvrdí, že se všechno ne­u­stále mění a vyvíjí, že co jsme se na­u­čili včera bude zítra za­sta­ralé, že co jsme věděli pře­stane platit a všechno se musí co ne­vi­dět od zá­kladů změnit. Cynik by ukázal na seznam Ja­vaScrip­tovch fra­meworků a namítl, že nic jako pokrok ne­e­xis­tuje a že jen opa­ku­jeme stejné chyby a ob­časný skok vpřed na­stane, když zno­vu­ob­je­víme za­pad­lou aka­de­mic­kou práci ze se­dm­de­sá­tých let.

Já tak daleko nechci zajít, pro­tože po­pí­rat sa­mot­nou myš­lenku po­kroku je šílené. Zdá se však, že iluze to­tální di­srupce je v oboru, o kterém by cynik pro­hlá­sil, že je po­há­něn vpřed vý­hradně ne­smysly, mar­ke­tingem a po­pí­rá­ním mi­nu­losti, ne­vy­hnu­telná.

S tímhle na mysli jsem se začal za­jí­mat, kdy a kde byly vy­na­le­zeny všechny tech­niky or­ga­ni­zace a ar­chi­tek­tury po­u­ží­vané v sou­čas­ných pro­ce­so­rech. Kdyby ahis­to­rická hy­po­téza pla­tila, všechno na čem jsou sou­dobá CPU po­sta­vená, se di­a­me­t­rálně liší od všeho mi­nu­lého a jde jen o do­čas­nou bub­linu, která co ne­vi­dět splaskne. Pokud je to pravda, nemá valný smysl sou­časný hard­ware sle­do­vat.


Všechno začalo dvěma sys­témy: ILLIAC II (1962) a IBM Stretch (1956-1961), je­jichž tvůrci přišli s na­pros­tou vět­šinu ar­chi­tek­tu­rál­ních tech­nik a způ­sobů or­ga­ni­zace pro­ce­sorů.

Tyto dva stroje uvedly cache, in­strukční pi­pe­line, mul­ti­tasking, vir­tu­ální paměť, ochranu paměti, os­mi­bi­tový bajt, pre­fetch a pro­klá­dání paměti (který je bohatě po­u­ží­ván např. v GPU).

Po těchto na­prosto zá­sad­ních stro­jích ná­sle­do­val systém CDC 6600 (1965) a vý­zkumný pro­jekt IBM ACS-1 (poz­ději pře­jme­no­vaný na ACS-360, 1961-1969). Ty uvedly všechno ostatní. Jme­no­vitě: de­kó­do­vání a vy­ko­nání ně­ko­lika in­strukcí v jednom taktu (su­per­ska­lární CPU), branch target buffer, mul­ti­threa­ding im­ple­men­to­vaný v hard­ware, out-of-order execu­tion, pře­jme­no­vá­vání re­gis­trů, pre­di­cation.

Sou­časné pro­ce­sory ob­sa­hují tohle všechno a nic víc. Po­slední ge­ne­race hard­ware jsou jen sny de­sig­nérů še­de­sá­tých let do­ve­dené k do­ko­na­losti.

Je však třeba dodat, že i když byla nějaká tech­nika při­ve­dena k životu před pa­de­sáti lety, ne­zna­mená to, že byla celou dobu ak­tivně vy­u­ží­vána. Velká část po­stupů byla na dlouhá léta opuš­těna, pro­tože se dařilo výkon do­sta­tečně zvy­šo­vat pros­tým ná­růs­tem frek­vence. Nebylo třeba dělat nic chyt­rého, sta­čilo se nechat unášet vlnami Mo­o­rova zákonu a stále po­kro­či­lejší li­to­gra­fií. Až s po­stu­pem času (ale stále dlouho před za­sta­ve­ním růstu frek­vence1 ) začali ná­vr­háři čipů vy­u­ží­vat ros­toucí množ­ství tran­zis­torů k agre­siv­ním im­ple­men­ta­cím chyt­rých a po­kro­či­lých tech­nik.

Ve zbý­va­jí­cích od­stav­cích projdu jed­not­livé ar­chi­tek­to­nické vzory a jejich struč­nou his­to­rii.

In­strukční pi­pe­line

In­strukční pi­pe­line byla po­u­žita už ve stro­jích ILLIAC II a IBM Stretch. První na­sa­zení je však o mnoho let starší a sahá až k me­cha­nic­kým a elek­tro­me­cha­nic­kým po­čí­ta­čům Z1 (1939) a Z3 (1941). Pi­pe­line poté začala být po­u­ží­vána v su­per­po­čí­ta­čích se­dm­de­sá­tých let a je spjata s pře­cho­dem od jedn­tak­to­vých in­strukcí k mno­ha­tak­to­vým in­struk­cím.

Cache

Už ILLIAC II měl rych­lou a po­ma­lou paměť. Pomalá paměť měla pří­stu­po­vou dobu 2 µs, rychlá, které by se dnes říkalo cache, 0.25 µs.

Rozdíl mezi rych­lostí pro­ce­sorů a pamětí začal na­růs­tat v osm­de­sá­tých letech. Paměť, která byla před­tím do­stupná v jednom taktu, pře­stá­vala stíhat CPU a čtení a zapis začal trvat víc jak jeden takt.

První cache byly TLB, které se ob­je­vily krátce po pří­chodu vir­tu­ální paměti ve stro­jích GE 645 (1968) a IBM 360/67 (1967).

Datová cache jako taková se poprvé ob­je­vila ve stroji IBM S/360 M85 v roce 1968.

De­di­ko­vaná in­strukční cache měla pre­mi­éru v Mo­to­role 68010 (1982), do které byl přidán „loop mode“ pro 2 in­strukce těsné smyčky. Poz­dější Mo­to­rola 68020 (1984) při­dala 256 baj­to­vou I-cache, Mo­to­rola 68030 (1987) při­dala stejně velkou D-cache. První x86 pro­ce­sor s in­strukční cache bylo dva­ce­ti­me­ga­her­t­zové 386 (1987).

Su­per­ska­lární CPU

Už CDC 6600 z roku 1965 byl su­per­ska­lární stroj. Prv­ními ko­merč­ními jed­no­či­po­vými su­per­ska­lár­ními pro­ce­sory byly až Mo­to­rola MC88100 (1988), Intel i960 (1989) a AMD 29000 (1990, viz). Pen­tium se v roce 1993 stalo prvním su­per­ska­lár­ním x86 pro­ce­so­rem. Více méně všechny pro­ce­sory vy­ro­bené při­bližně po roce 1998 jsou su­per­ska­lární.

Nx586, Pen­tium Pro a AMD K5 byly první x86 su­per­ska­lární pro­ce­sory, které pře­klá­daly slo­žité CISC in­strukce na jed­no­dušší RISC ope­race, kte­rých pak mohly vy­ko­nat víc na­jed­nou.

Out-of-order

Prvním OOO stro­jem byl CDC 6600 z roku 1965. Avšak podle dneš­ních stan­dardů nešlo o pl­no­hod­notné OOO, pro­tože po­u­ží­val sco­re­bo­ar­ding, který do­vo­lo­val pouze do­kon­čení (retire) in­strukcí out-of-order, za­čí­nat musely stále v pořadí pro­gramu. To umož­ňo­valo začít rychlé a pomalé ope­race na­jed­nou s tím, že ty pomalé ne­vy­tvo­řily bub­linu v pi­pe­line, ale hard­ware je pro­vá­děl sou­běžně a potom pře­rov­nal jejich vý­sledky tak, aby od­po­ví­daly sek­venč­nímu pro­gramu.

Sku­tečný OOO stroj uvedl až big blue a byl jím IBM 390/91 z roku 1966 im­ple­men­tu­jící To­ma­sulo al­go­rit­mus, který sle­duje zá­vis­losti mezi in­struk­cemi a dy­na­micky je plá­nuje mimo pořadí. Ale i tady to mělo jeden háček: OOO logika byla po­u­žita jen pro flo­a­ting point část pro­ce­soru. To bylo nej­spíš proto, že FP ope­race byly drahé a FP logika za­bí­rala velkou část čipu a bylo třeba za­ří­dit, aby byla za každou cenu efek­tivně vy­u­žita.

Pak se třicet let nic nedělo a prvním mo­der­ním OOO mi­k­ro­pro­ce­so­rem se stal až POWER1 (1990), který také OOO apli­ko­val jen na flo­a­ting point ope­race. O tři roky poz­ději IBM uvedl PowerPC (1993), který už uměl plné OOO. To roz­pou­talo bouři a mnoho ar­chi­tek­tur začalo pře­chá­zet: Sparc (1995), Pen­tium Pro (1995), R10000 od MIPS/SGI (1996) PA-RIS­Cový PA-8000 od HP (1996), AMD K5 (1996) a na­ko­nec Alpha (1998).

Branch pre­diction

Už IBM Stretch měl jed­no­du­chý sta­tický branch pre­dic­tor, který vždycky před­po­klá­dal, že pod­mí­něný skok nebude použit a kód pro­padne (pre­dict un­ta­ken)2 . Po tomto ex­pe­ri­mentu IBM ne­po­u­ží­vala branch pre­dic­tor ve vel­kých sys­té­mech až do roku 1985. Prav­dě­po­dobně to nebylo třeba, pro­tože cena špat­ného odhadu byla s krát­kou pi­pe­line malá nebo byly k dis­po­zici pre­di­ko­vané in­strukce, pří­padě delay sloty

Branch pre­diction se ob­je­vuje v sys­té­mech jiných spo­leč­ností: Burrou­ghs B4900 (1982) nebo VAX 9000 (1989). První ko­merční RISCy (1986) po vzoru Stretche a měly sta­tický pre­dik­tor pre­dict un­ta­ken. Branch pre­dik­tor začal být velice dů­le­žitý po roce 1993 pro su­per­ska­lární pro­ce­sory s hlu­bo­kou pi­pe­line, kde cena špat­ného roz­hod­nutí za­čí­nala na­růs­tat. Pen­tium, Alpha 21064, R8000 a POWER také začaly na­sa­zo­vat branch pre­dictior.

Mul­ti­core

Pře­kva­pivé je, že i ně­ko­li­ka­já­drové pro­ce­sory nejsou tak nové, jak by se zdálo. První kousek vy­ro­bil v po­lo­vině osm­de­sá­tých let Roc­kwell, když zkom­bi­no­val dva 6502 čipy do jed­noho pouz­dra. Po roce 2000 se staly mno­ho­já­drové pro­ce­sory běž­nými ar­ti­kly.

SMT/Hy­perThrea­ding

Hard­wa­rový multi-threa­ding (SMT) byl poprvé im­ple­men­to­ván v pro­to­typu ACS-360 (1968), který nebyl nikdy do­kon­čen.

Pro­ce­sor Alpha 21464 (ohlá­šený 1999, plá­no­vaný na 2003, na­ko­nec zrušen), měl být prvním SMT mi­k­ro­pro­ce­so­rem, měl zvlá­dat 8-wide issue (8 in­strukcí v jednom taktu) a 4 sou­běžná vlákna v každém jádře. Pen­tium 4 (2002) se stalo prvním mo­der­ním desk­to­po­vým CPU s pod­po­rou SMT. SMT v podání Intelu (pře­křtěné na Hy­perThrea­ding) zvládá jen dvě vlákna na jednom jádře. Další na řadě byl POWER5 (2004) od IBM.

SIMD

Vývoj vek­to­ro­vých pro­ce­sorů, které spa­dají do ka­te­go­rie SIMD, začal v še­de­sá­tých letech (např. ILLIAC IV). Kon­krétní stroje se začaly ob­je­vo­vat v letech se­dm­de­sá­tých a šlo pře­de­vším o různé ar­chi­tek­tury Cray (viz).


Jak je vidět, všechny tech­niky or­ga­ni­zace a ar­chi­tek­tury pro­ce­sorů jsou velice staré. Na­prostá vět­šina zažila debut na pře­lomu pa­de­sá­tých a še­de­sá­tých let. Cynik by mohl na­mí­tat, že se v tomto oboru od osm­de­sá­tých let ne­stalo nic sku­tečně nového a nebyl by daleko od pravdy. Dalo by se říct, že v pro­ce­so­rech je za po­sled­ních pa­de­sát let to samé, jen je tam toho víc.6 Pro­tože jsou tyto prin­cipy s námi od samého po­čátku, dá se před­po­klá­dat, že na nich něco bude a budou mít ur­či­tou uni­ver­zální plat­nost. Jinými slovy: když budeme op­ti­ma­li­zo­vat pro sou­časný hard­ware, ne­zna­mená to nutně, že pod­lé­háme dik­tátu po­div­ností po­slední várky kře­míku z to­vá­ren Intelu, ale široké mno­žině pro­ce­sorů, které mají velkou cache, hlu­bo­kou pi­pe­line, chytrý branch pre­dic­tor, agre­sivní OOO engine a ne­u­vě­ři­telně po­ma­lou DRAM. Do této ka­te­go­rie spadá skoro všechno od nej­vět­ších ser­ve­ro­vých bestií až po mo­bilní pro­ce­sory. Ona po­slední ge­ne­race mo­bil­ních pro­ce­sorů se skoro vůbec neliší od těch desk­to­po­vých a třeba pa­pí­rová spe­ci­fi­kace Apple Cyclone se až ne­pří­jemně podobá číslům Haswellu.3

Ně­které z těchto prin­cipů nejsou jen vý­sledky snah hard­wa­ro­vých de­sig­nérů na­pra­vit hříchy našich otců4 , ale dů­sledky fy­zi­kál­ních prin­cipů. Cache je na­pří­klad dů­sled­kem toho, že v pro­storu může být jen ome­zené množ­ství věcí blízko pro­ce­soru (rychlá cache) a ob­rov­ské množ­ství daleko (pomalá DRAM). Datová zá­vis­lost je potom ma­ni­festací kauza­lity, kdy poin­ter ne­u­ka­zuje jen na místo v paměti, ale zá­ro­veň udává pořadí ope­rací.

What's the score here? What's next?

Co by se muselo změnit, aby staré po­řádky pře­staly platit?

Na paměti s malou la­tencí nej­spíš můžeme za­po­me­nout. Tahle bitva je už dávno pro­hraná. Místo toho se můžeme dočkat strojů s ve­li­kou pa­mě­ťo­vou pro­pust­ností. Každý přenos zabere dlou­hou dobu, ale hard­ware jich může pro­vá­dět hodně na­jed­nou, po­dobně jako to dělají gra­fické karty nebo Thread­Storm ar­chi­tek­tura. Tenhle datově pa­ra­lelní model fun­guje nej­lépe, když jsou ope­race re­la­tivně pří­mo­čaré a vzá­jemně ne­zá­vislé. To ale není pravda o obec­ném kódu, který je plný pod­mí­ně­ných skoků, po­ly­mor­fismu a často vy­ža­duje jemnou syn­chro­ni­zaci a ko­or­di­naci. GPU mají pro­blém s pod­mí­ně­nými skoky, alo­ka­cemi a re­kurzí, tedy s tím, čeho je ge­ne­ral pur­pose kód plný. Re­a­lita bude tedy nej­spíš taková, že obecné pro­ce­sory budou mít u sebe paměť s velkou pro­pust­ností, ale jed­not­livá jádra budou celkem oby­čejná jádra po­dobná těm, jaké máme v sou­čas­nosti, jen možná o něco jed­no­dušší, možná s širším SMT nebo hard­wa­ro­vým pře­pí­ná­ním vláken.

Pokrok můžou při­nést levné ne­vo­la­tilní paměti (NVRAM), které fun­gují jako RAM, ale data pře­žijí vý­pa­dek na­pá­jení a re­start sys­tému (jako 3D XPoint od Micronu/Intelu nebo me­mris­to­rová paměť od HP5 ). Mnoho lidí je z nich nad­še­ných, pro­tože NVRAM můžou změnit úplně všechno (co se týká RAM). Na druhou stranu také nemusí změnit vůbec nic. To, že data pře­žijí pád sytému, zna­mená také, že po­ru­šená data pře­žijí re­start a chyby můžou pře­tr­vat. Někdo může jásat nad tím, že nebude třeba dělat nic spe­ci­ál­ního pro ulo­žení sou­boru, pro­tože data jsou v paměti a paměť je per­si­s­tentní. Pokud tohle přijmu, musím uva­žo­vat, co se stane, když systém spadne v prů­běhu jedné ope­race. Na­jed­nou můžou být data za­psána čás­tečně a kdo ví, co to bude dělat, až systém znovu na­běhne. V tomto pří­padě je třeba mít trans­akční pro­to­kol úplně všude a ne jen v mís­tech, které se sta­rají o uklá­dání dat. Z tohoto důvodu možná nějaká paměť nebude tolik per­si­s­tentní jako jiná. Když při­hlédnu k pre­zen­to­va­ným číslům, která na­zna­čují, že NVRAM může být rychlá asi jako DRAM, ale přesto o něco po­ma­lejší, ně­které sys­témy budou mít na palubě jak NVRAM tak i DRAM. Na­ko­nec to nemusí být tech­no­lo­gie, která nás všechny spasí, ale jen jeden druh z celého spek­tra pamětí: páska, HDD, SDD, NVRAM, DRAM, SRAM.

Když zajdu do jiného oboru a po­dí­vám se na řadící al­go­ritmy je si­tu­ace až ne­pří­jemně po­dobná: Všichni stále po­u­ží­váme quicksort, na který v roce 1959 přišel Tony Hoare (pu­b­li­ko­váno v roce 1961 jako Al­go­ri­thm 64: Quicksort), merge sort, jehož au­to­rem byl sám John von Ne­u­mann (1945), nebo Radix sort, jehož kořeny sahají až do roku 1897. Kromě nich ne­po­u­ží­váme skoro nic jiného. To ale ne­zna­mená, že se nic neděje. Všechny zmí­něná al­go­ritmy jsou po­stupně vy­lep­šo­vány, vy­la­ďo­vány a při­způ­so­bo­vány hard­wa­rové re­a­litě doby, jako vy­u­žití SIMD bi­to­nic­kých sítí pro merge sort, sko­sený quicksort nebo různá sché­mata pa­ra­le­li­zace všech sortů. Ale pořád platí, že zna­lost zá­klad­ních verzí těchto al­go­ritmů nikdy ne­za­sta­rala.

Na­proti tomu svět da­ta­bází se otřásá v zá­kla­dech. Tedy to tak aspoň vypadá na první pohled. Sou­časné RDMS v ně­kte­rých pří­pa­dech pře­stá­vají stačit po­ža­dav­kům na ně kla­de­ným a proto se začaly ozývat hlasy k za­po­vě­zení re­lač­ních da­ta­bází a pře­chodu na něco dras­ticky jiného a lep­šího. Do­konce i Sto­ne­bra­ker tvrdí, že doba jedné da­ta­báze pro všechno je u konce a je efek­tiv­nější přejít na in-memory da­ta­bázi na OLTP, sloup­co­vou na OLTP a něco jako Hadoop/Spark na ostatní věci. V tomto kon­textu není těžké po­cho­pit hlasy, které tvrdí, že re­lační da­ta­báze jsou za­sta­ralé a mo­rálně špatné. To ale nic nemění na tom, že byly více než do­sta­ču­jící po­sled­ních 40 let, od doby, kdy Codd pu­b­li­ko­val se­mi­nální paper o re­lační al­gebře. Navíc tech­niky po­u­žité pod ka­po­tou se příliš neliší mezi (ně­kte­rými) re­lač­ními di­no­saury a (ně­kte­rými) mo­der­ními key-value NoSQL da­tas­tory. Konec konců chci někam uložit hro­madu bitů a chci ji taky dostat rychle zpátky.

V dlou­ho­do­bém mě­řítku všechno jednou za­stará a jediné, co můžeme chtít, je pár let jízdy plnou rych­lostí, než to strh­neme do škarpy a zmi­zíme v ex­plozi slávy. Proto ale nemá smysl tvrdit, že do­časná zna­lost nemá žádnou hod­notu. Jestliže to, co se dneska na­u­číme o hard­ware, bude platit ná­sle­du­jící dekádu, bude to víc než bychom si mohli přát. Onen po­my­slný cynik by jistě ukázal na hořící hro­madu Ja­vaScrip­to­vých fra­meworků a dodal by, že je to víc než bychom si za­slou­žili.


Dále k tématu:

Pozn:

  1. viz známý článek The Free Lunch Is Over.
  2. Z toho se dá usou­dit, že před­po­klá­dal, že smyčky budou za­čí­nat skokem ven a na konci bude ne­pod­mí­něný skok na za­čá­tek smyčky. Kdyby před­po­klá­dal opak (pre­dict taken), zna­me­nalo by to, že smyčce bude končit pod­mí­ně­ným skokem na za­čá­tek.
  3. O tom také svědčí fakt, že mnoho firem plá­nuje uvést vlastní ARM ser­ve­rové čipy. Jsou to třeba AMD, Qual­comm, Tilera, EZchip, Cavium, Aplied Micro nebo Broad­com.
  4. viz bi­zarní kó­do­vání x86, které vede k masiv­ním CISC → RICS de­ko­dé­rům, L0 cache, LSB a dalším snahám jak roz­lá­mat in­struction stream a na­kr­mit hla­dové funkční jed­notky.
  5. Pro úpl­nost se sluší dodat, že NVRAM je do­stupná už teď, jen není vůbec levná (MRAM, FRAM). Pří­slib NVRAM je v tom, že bude jak ne­vo­la­tilní, tak i velká.
  6. Podle před­nášky The Chip Design Game at the End of Moore's Law se mezi roky 1980 a 2010 zvýšil takt pro­ce­sorů 3500x a změny v ar­chi­tek­tuře a mikro-ar­chi­tek­tuře mohly přidat další pa­de­sá­ti­ná­sobné zvý­šení rych­losti. Z toho plyne, že se sku­tečně něco děje a všechny ty staré prin­cipy se sku­tečně vy­lep­šují a vy­la­ďují k do­ko­na­losti.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články