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

Evgeny Morozov v knize To Save Everything Click Here mluvil o epochalismu a ahistorickém myšlení. Epochalismus říká, že žijeme ve výjimečných časech a současná doba je diametrálně odlišná od všech minulých a nic staré už neplatí. Ahistorické myšlení s epochalismem velice úzce souvisí - v podstatě jde o systematické ignorování historie a všeho, co jsme se z ní mohli naučit.

Přestože Morozov psal o "Internetu" a digitální debatě obecně, stejný trend lze vycítit v IT komunitě. Zdá se, že dominantní myšlenkový proud tvrdí, že se všechno neustále mění a vyvíjí, že co jsme se naučili včera bude zítra zastaralé, že co jsme věděli přestane platit a všechno se musí co nevidět od základů změnit. Cynik by ukázal na seznam JavaScriptovch frameworků a namítl, že nic jako pokrok neexistuje a že jen opakujeme stejné chyby a občasný skok vpřed nastane, když znovuobjevíme zapadlou akademickou práci ze sedmdesátých let.

Já tak daleko nechci zajít, protože popírat samotnou myšlenku pokroku je šílené. Zdá se však, že iluze totální disrupce je v oboru, o kterém by cynik prohlásil, že je poháněn vpřed výhradně nesmysly, marketingem a popíráním minulosti, nevyhnutelná.

S tímhle na mysli jsem se začal zajímat, kdy a kde byly vynalezeny všechny techniky organizace a architektury používané v současných procesorech. Kdyby ahistorická hypotéza platila, všechno na čem jsou soudobá CPU postavená, se diametrálně liší od všeho minulého a jde jen o dočasnou bublinu, která co nevidět splaskne. Pokud je to pravda, nemá valný smysl současný hardware sledovat.


Všechno začalo dvěma systémy: ILLIAC II (1962) a IBM Stretch (1956-1961), jejichž tvůrci přišli s naprostou většinu architekturálních technik a způsobů organizace procesorů.

Tyto dva stroje uvedly cache, instrukční pipeline, multitasking, virtuální paměť, ochranu paměti, osmibitový bajt, prefetch a prokládání paměti (který je bohatě používán např. v GPU).

Po těchto naprosto zásadních strojích následoval systém CDC 6600 (1965) a výzkumný projekt IBM ACS-1 (později přejmenovaný na ACS-360, 1961-1969). Ty uvedly všechno ostatní. Jmenovitě: dekódování a vykonání několika instrukcí v jednom taktu (superskalární CPU), branch target buffer, multithreading implementovaný v hardware, out-of-order execution, přejmenovávání registrů, predication.

Současné procesory obsahují tohle všechno a nic víc. Poslední generace hardware jsou jen sny designérů šedesátých let dovedené k dokonalosti.

Je však třeba dodat, že i když byla nějaká technika přivedena k životu před padesáti lety, neznamená to, že byla celou dobu aktivně využívána. Velká část postupů byla na dlouhá léta opuštěna, protože se dařilo výkon dostatečně zvyšovat prostým nárůstem frekvence. Nebylo třeba dělat nic chytrého, stačilo se nechat unášet vlnami Moorova zákonu a stále pokročilejší litografií. Až s postupem času (ale stále dlouho před zastavením růstu frekvence1 ) začali návrháři čipů využívat rostoucí množství tranzistorů k agresivním implementacím chytrých a pokročilých technik.

Ve zbývajících odstavcích projdu jednotlivé architektonické vzory a jejich stručnou historii.

Instrukční pipeline

Instrukční pipeline byla použita už ve strojích ILLIAC II a IBM Stretch. První nasazení je však o mnoho let starší a sahá až k mechanickým a elektromechanickým počítačům Z1 (1939) a Z3 (1941). Pipeline poté začala být používána v superpočítačích sedmdesátých let a je spjata s přechodem od jednotaktových instrukcí k mnohataktovým instrukcím.

Cache

Už ILLIAC II měl rychlou a pomalou paměť. Pomalá paměť měla přístupovou dobu 2 µs, rychlá, které by se dnes říkalo cache, 0.25 µs.

Rozdíl mezi rychlostí procesorů a pamětí začal narůstat v osmdesátých letech. Paměť, která byla předtím dostupná v jednom taktu, přestávala stíhat CPU a čtení a zápis začal trvat víc jak jeden takt.

První cache byly TLB, které se objevily krátce po příchodu virtuální paměti ve strojích GE 645 (1968) a IBM 360/67 (1967).

Datová cache jako taková se poprvé objevila ve stroji IBM S/360 M85 v roce 1968.

Dedikovaná instrukční cache měla premiéru v Motorole 68010 (1982), do které byl přidán "loop mode" pro 2 instrukce těsné smyčky. Pozdější Motorola 68020 (1984) přidala 256 bajtovou I-cache, Motorola 68030 (1987) přidala stejně velkou D-cache. První x86 procesor s instrukční cache bylo dvacetimegahertzové 386 (1987).

Superskalární CPU

Už CDC 6600 z roku 1965 byl superskalární stroj. Prvními komerčními jednočipovými superskalárními procesory byly až Motorola MC88100 (1988), Intel i960 (1989) a AMD 29000 (1990, viz). Pentium se v roce 1993 stalo prvním superskalárním x86 procesorem. Více méně všechny procesory vyrobené přibližně po roce 1998 jsou superskalární.

Nx586, Pentium Pro a AMD K5 byly první x86 superskalární procesory, které překládaly složité CISC instrukce na jednodušší RISC operace, kterých pak mohly vykonat víc najednou.

Out-of-order

Prvním OOO strojem byl CDC 6600 z roku 1965. Avšak podle dnešních standardů nešlo o plnohodnotné OOO, protože používal scoreboarding, který dovoloval pouze dokončení (retire) instrukcí out-of-order, začínat musely stále v pořadí programu. To umožňovalo začít rychlé a pomalé operace najednou s tím, že ty pomalé nevytvořily bublinu v pipeline, ale hardware je prováděl souběžně a potom přerovnal jejich výsledky tak, aby odpovídaly sekvenčnímu programu.

Skutečný OOO stroj uvedl až big blue a byl jím IBM 390/91 z roku 1966 implementující Tomasulo algoritmus, který sleduje závislosti mezi instrukcemi a dynamicky je plánuje mimo pořadí. Ale i tady to mělo jeden háček: OOO logika byla použita jen pro floating point část procesoru. To bylo nejspíš proto, že FP operace byly drahé a FP logika zabírala velkou část čipu a bylo třeba zařídit, aby se za každou cenu efektivně využila. Jak je popsáno v originálním Tomasulově článku, OOO logika měla na starosti jen dvě funkční jednotky, FP násobičku a FP sčítačku (první měla 2 reservation station, druhá 3 RS), instrukční okno mělo délku 8 instrukcí.

Pak se třicet let nic nedělo a prvním moderním OOO mikroprocesorem se stal až POWER1 (1990), který také OOO aplikoval jen na floating point operace. O tři roky později IBM uvedl PowerPC (1993), který už uměl plné OOO. To rozpoutalo bouři a mnoho architektur začalo přecházet: Sparc (1995), Pentium Pro (1995), R10000 od MIPS/SGI (1996) PA-RISCový PA-8000 od HP (1996), AMD K5 (1996) a nakonec Alpha (1998).

Branch prediction

Už IBM Stretch měl jednoduchý statický branch predictor, který vždycky předpokládal, že podmíněný skok nebude použit a kód propadne (predict untaken)2 . Po tomto experimentu IBM nepoužívala branch predictor ve velkých systémech až do roku 1985. Pravděpodobně to nebylo třeba, protože cena špatného odhadu byla s krátkou pipeline malá nebo byly k dispozici predikované instrukce, případě delay sloty

Branch prediction se objevuje v systémech jiných společností: Burroughs B4900 (1982) nebo VAX 9000 (1989). První komerční RISCy (1986) po vzoru Stretche a měly statický prediktor predict untaken. Branch prediktor začal být velice důležitý po roce 1993 pro superskalární procesory s hlubokou pipeline, kde cena špatného rozhodnutí začínala narůstat. Pentium, Alpha 21064, R8000 a POWER také začaly nasazovat branch predictior.

Multicore

Překvapivé je, že i několikajádrové procesory nejsou tak nové, jak by se zdálo. První kousek vyrobil v polovině osmdesátých let Rockwell, když zkombinoval dva 6502 čipy do jednoho pouzdra. Po roce 2000 se staly mnohojádrové procesory běžnými artikly.

SMT/HyperThreading

Hardwarový multi-threading (SMT) byl poprvé implementován v prototypu ACS-360 (1968), který nebyl nikdy dokončen.

Procesor Alpha 21464 (ohlášený 1999, plánovaný na 2003, nakonec zrušen), měl být prvním SMT mikroprocesorem, měl zvládat 8-wide issue (8 instrukcí v jednom taktu) a 4 souběžná vlákna v každém jádře. Pentium 4 (2002) se stalo prvním moderním desktopovým CPU s podporou SMT. SMT v podání Intelu (překřtěné na HyperThreading) zvládá jen dvě vlákna na jednom jádře. Další na řadě byl POWER5 (2004) od IBM.

SIMD

Vývoj vektorových procesorů, které spadají do kategorie SIMD, začal v šedesátých letech (např. ILLIAC IV). Konkrétní stroje se začaly objevovat v letech sedmdesátých a šlo především o různé architektury Cray (viz).


Jak je vidět, všechny techniky organizace a architektury procesorů jsou velice staré. Naprostá většina zažila debut na přelomu padesátých a šedesátých let. Cynik by mohl namítat, že se v tomto oboru od osmdesátých let nestalo nic skutečně nového a nebyl by daleko od pravdy. Dalo by se říct, že v procesorech je za posledních padesát let to samé, jen je tam toho víc.6 Protože jsou tyto principy s námi od samého počátku, dá se předpokládat, že na nich něco bude a budou mít určitou univerzální platnost. Jinými slovy: když budeme optimalizovat pro současný hardware, neznamená to nutně, že podléháme diktátu podivností poslední várky křemíku z továren Intelu, ale široké množině procesorů, které mají velkou cache, hlubokou pipeline, chytrý branch predictor, agresivní OOO engine a neuvěřitelně pomalou DRAM. Do této kategorie spadá skoro všechno od největších serverových bestií až po mobilní procesory. Ona poslední generace mobilních procesorů se skoro vůbec neliší od těch desktopových a třeba papírová specifikace Apple Cyclone se až nepříjemně podobá číslům Haswellu.3

Některé z těchto principů nejsou jen výsledky snah hardwarových designérů napravit hříchy našich otců4 , ale důsledky fyzikálních principů. Cache je například důsledkem toho, že v prostoru může být jen omezené množství věcí blízko procesoru (rychlá cache) a obrovské množství daleko (pomalá DRAM). Datová závislost je potom manifestací kauzality, kdy pointer neukazuje jen na místo v paměti, ale zároveň udává pořadí operací.

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

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

Na paměti s malou latencí nejspíš můžeme zapomenout. Tahle bitva je už dávno prohraná. Místo toho se můžeme dočkat strojů s velikou paměťovou propustností. Každý přenos zabere dlouhou dobu, ale hardware jich může provádět hodně najednou, podobně jako to dělají grafické karty nebo ThreadStorm architektura. Tenhle datově paralelní model funguje nejlépe, když jsou operace relativně přímočaré a vzájemně nezávislé. To ale není pravda o obecném kódu, který je plný podmíněných skoků, polymorfismu a často vyžaduje jemnou synchronizaci a koordinaci. GPU mají problém s podmíněnými skoky, alokacemi a rekurzí, tedy s tím, čeho je general purpose kód plný. Realita bude tedy nejspíš taková, že obecné procesory budou mít u sebe paměť s velkou propustností, ale jednotlivá jádra budou celkem obyčejná jádra podobná těm, jaké máme v současnosti, jen možná o něco jednodušší, možná s širším SMT nebo hardwarovým přepínáním vláken.

Pokrok můžou přinést levné nevolatilní paměti (NVRAM), které fungují jako RAM, ale data přežijí výpadek napájení a restart systému (jako 3D XPoint od Micronu/Intelu nebo memristorová paměť od HP5 ). Mnoho lidí je z nich nadšených, protož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, znamená také, že porušená data přežijí restart a chyby můžou přetrvat. Někdo může jásat nad tím, že nebude třeba dělat nic speciálního pro uložení souboru, protože data jsou v paměti a paměť je persistentní. Pokud tohle přijmu, musím uvažovat, co se stane, když systém spadne v průběhu jedné operace. Najednou můžou být data zapsána částečně a kdo ví, co to bude dělat, až systém znovu naběhne. V tomto případě je třeba mít transakční protokol úplně všude a ne jen v místech, které se starají o ukládání dat. Z tohoto důvodu možná nějaká paměť nebude tolik persistentní jako jiná. Když přihlédnu k prezentovaným číslům, která naznačují, že NVRAM může být rychlá asi jako DRAM, ale přesto o něco pomalejší, některé systémy budou mít na palubě jak NVRAM tak i DRAM. Nakonec to nemusí být technologie, která nás všechny spasí, ale jen jeden druh z celého spektra pamětí: páska, HDD, SDD, NVRAM, DRAM, SRAM.

Když zajdu do jiného oboru a podívám se na řadící algoritmy je situace až nepříjemně podobná: Všichni stále používáme quicksort, na který v roce 1959 přišel Tony Hoare (publikováno v roce 1961 jako Algorithm 64: Quicksort), merge sort, jehož autorem byl sám John von Neumann (1945), nebo Radix sort, jehož kořeny sahají až do roku 1897. Kromě nich nepoužíváme skoro nic jiného. To ale neznamená, že se nic neděje. Všechny zmíněná algoritmy jsou postupně vylepšovány, vylaďovány a přizpůsobovány hardwarové realitě doby, jako využití SIMD bitonických sítí pro merge sort, skosený quicksort nebo různá schémata paralelizace všech sortů. Ale pořád platí, že znalost základních verzí těchto algoritmů nikdy nezastarala.

Naproti tomu svět databází se otřásá v základech. Tedy to tak aspoň vypadá na první pohled. Současné RDMS v některých případech přestávají stačit požadavkům na ně kladeným a proto se začaly ozývat hlasy k zapovězení relačních databází a přechodu na něco drasticky jiného a lepšího. Dokonce i Stonebraker tvrdí, že doba jedné databáze pro všechno je u konce a je efektivnější přejít na in-memory databázi na OLTP, sloupcovou na OLTP a něco jako Hadoop/Spark na ostatní věci. V tomto kontextu není těžké pochopit hlasy, které tvrdí, že relační databáze jsou zastaralé a morálně špatné. To ale nic nemění na tom, že byly více než dostačující posledních 40 let, od doby, kdy Codd publikoval seminální paper o relační algebře. Navíc techniky použité pod kapotou se příliš neliší mezi (některými) relačními dinosaury a (některými) moderními key-value NoSQL datastory. Konec konců chci někam uložit hromadu bitů a chci ji taky dostat rychle zpátky.

V dlouhodobém měřítku všechno jednou zastará a jediné, co můžeme chtít, je pár let jízdy plnou rychlostí, než to strhneme do škarpy a zmizíme v explozi slávy. Proto ale nemá smysl tvrdit, že dočasná znalost nemá žádnou hodnotu. Jestliže to, co se dneska naučíme o hardware, bude platit následující dekádu, bude to víc než bychom si mohli přát. Onen pomyslný cynik by jistě ukázal na hořící hromadu JavaScriptových frameworků a dodal by, že je to víc než bychom si zasloužili.


Dále k tématu:

Pozn:

  1. viz známý článek The Free Lunch Is Over.
  2. Z toho se dá usoudit, že předpokládal, že smyčky budou začínat skokem ven a na konci bude nepodmíněný skok na začátek smyčky. Kdyby předpokládal opak (predict taken), znamenalo by to, že smyčce bude končit podmíněným skokem na začátek.
  3. O tom také svědčí fakt, že mnoho firem plánuje uvést vlastní ARM serverové čipy. Jsou to třeba AMD, Qualcomm, Tilera, EZchip, Cavium, Aplied Micro nebo Broadcom.
  4. viz bizarní kódování x86, které vede k masivním CISC -> RICS dekodérům, L0 cache, LSB a dalším snahám jak rozlámat instruction stream a nakrmit hladové funkční jednotky.
  5. Pro úplnost se sluší dodat, že NVRAM je dostupná už teď, jen není vůbec levná (MRAM, FRAM). Příslib NVRAM je v tom, že bude jak nevolatilní, tak i velká.
  6. Podle přednášky The Chip Design Game at the End of Moore's Law se mezi roky 1980 a 2010 zvýšil takt procesorů 3500x a změny v architektuře a mikro-architektuře mohly přidat další padesátinásobné zvýšení rychlosti. Z toho plyne, že se skutečně něco děje a všechny ty staré principy se skutečně vylepšují a vylaďují k dokonalosti.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články