Dualismus hardwaru a softwaru, strojů a virtuálních strojů

René Descartes věřil v myšlenku dualismu, který se dá diletantsky vysvětlit tak, že tělo a duše jsou dvě různé vzájemně neslučitelné kategorie.

V podobném duchu se nese jiný dualismus, který je na rozdíl od Descarterových tvrzení méně metafyzický, ale zato je přítomný a hmatatelný. Oba pak mají jedno společné: Jde o falešnou dichotomii i když všichni v hloubi duši toužíme po opaku.

Pochopitelně mluvím o dualismu hardware a software, strojů a virtuálních strojů, kdy jeden dělá to, co to druhý nemůže, kdy „myslící“ program ovládá „hmotu“ stroje. Tato demarkace na první pohled působí správně a uspokojivě, jako kdyby to tak skutečně bylo. Když ale začnu problematiku zkoumat podrobněji a vezmu to oklikou přes historii CPU architektur, toto rozdělení, před chvílí ještě krystalicky jasné, najednou začíná mizet v mlhách.

Všechno, co vypadá jako neměnné pravdy vytesané do kamene, jsou jen rozhraní a úrovně abstrakce.

Už instrukční sada procesoru (ISA) není ten pomyslný pevný bod, na kterém stojí všechny ostatní želvy, ale také jen abstrakce. Téměř žádný dnešní procesor (možná s výjimkou některých jednoduchých RICSů nebo DSP) nevykonává instrukce tak, jak jsou za sebou vyskládány v binárce, ale dynamicky je v hardwaru překládá na jednodušší (RISCovější, i když tohle označení už moc neznamená) mikro operace (μops). Jedna instrukce se může rozpadnout na několik μops nebo naopak může být běžná sekvence několika instrukcí přeložena na jednu mikro operaci (tzv macro-op fusion)1. Situaci dále komplikuje mikrokód, kdy jsou některé instrukce procesorem přeloženy na malý program (například trigonometrické funkce jsou mikrokódovány, práce se denormálními floaty nebo GATHER instrukce na Haswellech, vylepšená v následujících generacích)14. Instrukce tedy není nutně nejmenší jednotka práce2 a často ani není přímo implementována v hardware.

Tato organizace není použita zbůhdarma, ale má dobrý důvod. Není totiž nutné plýtvat křemíkem na každou funkcionalitu, která je v programech používána jen okrajově. Místo toho je možné použít mikroarchitekturu s menším počet vysoce optimalizovaných funkčních jednotek, které jsou sdílené mezi instrukcemi3. Dále to zjednodušuje návrh pipeline, protože není třeba počítat s operacemi, které mají divoce rozdílné latence, a vede to k efektivnějším out-of-order jádrům, které můžou vykonávat různé μop (které trvají ±stejný počet taktů) různých CISC instrukcí najednou a využít tak dostupný ILP. Jako příklad můžu uvést stařičké VAXy. Ty například přímo podporovaly komplikovanou instrukci INDEX, která byla používána jen velice zřídka, a proto nikdo nestrávil čas optimalizací její hardwarové implementace. To došlo tak daleko, že když někdo napal stejnou funkcionalitu pomocí jednodušších operací, softwarový výsledek byl rychlejší než přímá implementace v křemíku. Víc o tom mluví Onur Mutlu v jedné ze svých skvělých přednášek o architektuře procesorů.

Jestliže instrukce jsou atomy, pak mikro operace jsou jejich kvarky.

Jako další příklad na spektru abstrakce může posloužit Transmeta. Ta v dobách své nedlouhé slávy produkovala čipy, které dokázaly rozběhat barokní x86 binárky. Sám hardware přitom neuměl nic z monstrózní x86 ISA, ale místo toho běhal na vlastní proprietární VLIW architektuře a x86 program byl za běhu překládán pomocí takzvaného Code Morphing software (CMS) do interní ISA4. Nepřekládal ale všechno. Zpočátku kód jen naivně interpretoval, když pak objevil opakovaně prováděný blok, rychle ho překompiloval z x86 do nativního VLIW formátu, když pak zjistil, že jde o skutečný hotspot, provedl důkladnou (a pomalou) kompilaci, jejímž výsledkem byl kvalitní a rychlý kód. Procesory od Transmety se tak v mnohém podobají JVM, jen s tím rozdílem, že jejich vstupem není Java bytekód, ale x86 binárka, cíl JITu není x86, ale interní nízkoúrovňový VLIW formát a hardware je specificky navržen pro tento účel.

VLIW instrukce se v mnohém podobají mikro operacím – jde o operace na velice nízké úrovni, které věrně opisují chování a mikroarchitekturu hardware5. Jsou prováděny ve statickém pořadí určeném kompilátorem (statically scheduled) a obnažují všechny interní detaily procesoru, jako jsou počty funkčních jednotek, délku pipeline a latence jednotlivých operací. To vede k problémům s přenositelností, kdy program zkompilovaný pro jeden model VLIW stroje nefunguje na novějším modelu, který má víc nebo rychlejší funkční jednotky.9 Když je však tento interní formát skryt pod jednou úrovní abstrakce (jako v případě x86 a dalších ne-VLIW ISA), může se mikroarchitektura libovolně měnit a vrstva o jednu úroveň výše se postará, aby byly všechny prostředky co nejlépe využity – nezáleží jestli jde o celkem naivní překlad v hardware, nebo dynamickou rekompilaci v software. Dokonce je teoreticky možné takto postavit stroj, který zvládá několik různých ISA najednou (třeba x86 a ARM).

V případě Transmety se interní formát měnil celkem znatelně – první generace procesorů pojmenovaná Crusoe byla široká 128 bitů a každá instrukce obsahovala 4 operace. Další generace byla dvakrát širší s dvakrát větším počtem operací v instrukci. Více informací je v oficiálním whitepaperu nebo ve dvou článcích o snahách reverzně vyinženýrovat mikroarchitekturu Transmety.

Velice podobně jako čipy už dlouho mrtvé Transmety pracují některé ARM čipy z rodiny Tegra od Nvidie založené na mikroarchitektuře Denver (nebo ruský Elbrus, když už jsem u toho). Na rozdíl od Transmety, která začala program v interpretru, Denver umí přímo vykonávat ARM kód na celkem základní úrovni. Hlavní síla čipů však spočívá v proprietární interní VLIW ISA, která je 7-wide (7 ops v instrukci). Program je zpočátku vykonáván v ARM módu s tím, že jakmile software objeví horký kus kódu, začne kompilovat. Rozpoznávání hotspotů nefunguje na úrovni základních bloků, ale na úrovni průchodů (trace), které jsou typicky tvořeny jednou iterací smyčky a můžou procházet mnoho základních bloků a dokonce i volání funkcí. Když je nalezena frekventovaná trace ARM instrukcí, je softwarově překompilována do VLIW ISA jako lineární sekvence operací, bez větvení a bez odboček. V mnohém tedy připomíná trasovací (tracing) JIT kompilátory, jako je třeba ten v PyPy (používaný i v jiných jazycích než Python), jen netrasuje nějakou formu bytekódu nebo operace interpretru (jako v případě meta-tracing JIT), ale přímo ARM instrukce.

Jako další příklad může sloužit společnost Azul, která dříve vyráběla čipy Vega specializované pro běh Java aplikací. Interně šlo o velice jednoduché a nepříliš rychlé in-order RISC procesory, které byly navrženy s ohledem na specifikaci Javy. Nepokoušely se však přímo vykonávat Javovský bytekód – lidé se o to dříve pokoušeli a zjistili, že je to velice špatný nápad. Na rozdíl od Teger a čipů Transmety měly Vegy vlastní operační systém, standardní knihovny a JVM zkompilované do nativního kódu, ale rozhraním pro uživatelské aplikace byl jedině Java bytekód. Šlo tedy o poměrně vysokou úroveň abstrakce, která návrhářům10 dala velkou míru volnosti jak společně navrhovat michroarchitekturu a JIT. Hardware se mohl mezi generacemi měnit (a také se měnil), aniž by to narušilo kompatibilitu pro uživatelské aplikace.

Úroveň abstrakce může být však i jinde, o čemž svědčí chystaný procesor Mill. Jde opět o VLIW staticaly scheduled, open pipeline stroj, který šířkou, kdy v jedné instrukci může být až 33 operací, překonává všechno ostatní. ISA je zamýšlena jako cíl pro kompilátor a bude přímo vykonána procesorem na nejnižší možné úrovni bez dalších vrstev abstrakce. Od ostatních VLIWů se Mill liší v tom, že není navrhován jako jedna architektura, ale rodina architektur s různými schopnostmi a hardwarovými prostředky.12

VLIW má problém v tom, že jde o příliš nízkou úroveň abstrakce – v podstatě představuje obnaženou mikroarchitekturu. Když se hardware změní, software se musí přizpůsobit. Mill se tohle snaží vyřešit tím, že programy nebudou distribuovány jako binárky přímo určené ke spuštění, ale budou na něco abstraktnější úrovni s tím, že se před spuštěním nebo během instalace staticky specializují pro konkrétní hardware. Na rozdíl od příkladů v minulých odstavcích by nemělo jít o nijak komplikovanou rekompilaci, ale celkem přímé mapování požadavků programu na prostředky hardware. Mill tak abstrahuje nejen možnosti daného stroje, ale i binární kódování instrukcí, které může být specifické pro každý model a přesto si zachovává výhody statického schedule, který nepotřebuje komplikovaný dekodér nebo out-of-order hardware.6

O Millu zatím nemůžu prohlašovat nic konkrétního, protože se ještě nedá koupit reálný křemík. Všechny informace pocházejí ze série velice detailních přednášek, které uspořádal Ivan Godard a ukazuje v nich všechny vlastnosti, kterými se Mill liší od běžných strojů a architektur.

Z předešlých odstavců lze vypozorovat jedno společné téma: všechno je jen abstrakce na určité úrovni. Od velice nízké jako v případě Millu, přes o něco vyšší (x86 a ARM ISA) až po relativně vysokou jako je Java bytekód. A to nemluvím o FPGA, které všechno tohle staví na hlavu, protože dovolí přímo programovat hardware. A víte jak Intel nedávno koupil Alteru? To znamená jediné: dočkáme se procesorů s integrovaný­mi FPGA.


Teď když jsem tu napsal přes 1000 slov o tom, že hranice mezi hardwarem a softwarem je mlhavější, než se na první pohled může zdát, nabízí se jedna zřejmá otázka: Neexistují nějaké principy psaní programů, které nějakým zásadním způsobem benefitují hardwarusoftwaru?

Zcela nepřekvapivě: Ano.

Jedna vlastnost, ze které profitují všichni, je předvídatelnost. Pokud se strojový kód chová předvídatelně, může hardware rozpoznat vzory jeho chování a pomoci. Sázka na předvídatelnost vedla k obohacení procesorů o branch prediction jednotky, které se snaží uhodnout zdali program skočí nebo propadne7, a branch target buffery, který předvídá cíle skoků na registr (typické při implementaci virtuálních metod), cache a prefetching.

Předvídatelnost pomáhá softwaru v tom, že dynamická prostředí, jako je JIT kompilátor v JVM, může specializovat kód pro běžné případy a ty, které nastanou jen zřídka nebo vůbec, ignorovat. Takto může devirtualizovat a inlinovat virtuální metody, což otevře dveře celé plejádě dalších optimalizací. Pro dynamické jazyky je předvídatelnost ještě důležitější, protože pokud má program rozumně statickou strukturu, virtuální stroj může objevit skryté třídy a typy argumentů funkcí a specializovat pro ně kód8. Předvídatelnost je také benefitem pro tracing JIT, které nahrávají (trasují) lineární průchod kódem, který je často prováděn, a čím méně odskoků a odboček v něm je, tím jednodušší má práci13. Stejně tak práce Maxime Chevalier-BoisvertBasic Block Versioning, ocení předvídatelnost tím, že bude potřebovat vygenerovat menší množství verzí základních bloků. Z předvídatelnosti také těží přístup založený na specializaci AST (jako je Truffle+Graal backend pro Jruby), protože (očividně) není třeba provádět takové množství specializací, což vede k menším a rychlejším několikaúrovňovým polymorfním inline cache.

Další dobrou vlastností pro všechny zúčastněné je malý a kompaktní kód. Na úrovni hardwaru je to proto, že se kód vejde do cache. Nejde jen o ty hlavní úrovně jako L3/L3/L1I, ale také L0, která na některých strojích obsahuje dekódované mikro operace. To pomůže v případech, kdy hlavním úzkým hrdlem je dekodér instrukcí. Pokud je však smyčka velice těsná (něco jako pár desítek μops na Haswell/Broad­well/Skylake x86) a celá se vejde do loop bufferu, hardware rozpozná, že si vystačí s tím, co je v loop bufferu a vůbec nebude komunikovat s cache a dekodérem. To může vést ke zrychlení programu a úsporám energie. Navíc nepředvídatelnému a nerozumně rozvětvenému kódu hrozí, že skočí na místo, které ještě není v cache a bude muset čekat.11

Virtuální stroje kompilující kód po metodách (jako typické JVM) preferují malé metody, protože jim to dává volnost v rozhodování, zdali danou metodu inlinovat nebo ne. Inlinování zvětšuje výsledný kód a proto, kdyby to JIT začal dělat příliš velkoryse, kód by nakynul a nemusel by se vejít do cache, což by vedlo ke znatelnému zpomalení. Inlinování je důležité, ale jen v rozumné míře. Když se to přežene, může to uškodit. Z toho důvodu JIT typicky vybírá kandidáty pro inlinování heuristicky a jedna z nich je velikost metody s tím, že velké metody mají jen malou šanci být inlinovány. Například JVM miluje malé metody a když se rozjede, začne je spekulativně inlinovat několik úrovní hluboko. Malé metody zároveň vedou k organizaci kódu s malými funkčními celky, které mají jasně definovanou roli, kdy každá funkce dělá jednu věc, což je obecně dobrá věc.


Nakonec to vypadá, že všechno jsou to jen virtuální stroje stojící na ramenou jiných virtuálních strojů. Dokonce i samotné Céčko, kterému se někdy říká přenositelný assembler definuje chování virtuálního stroje, který není nikde implementovaný v hardware, ale shodou náhod se na skutečný hardware dá docela pěkně napasovat. Všechny virtuální stroje se nakonec od sebe liší jen tloušťkou abstrakce, kterou je třeba překonat, aby program dokázal rozpohybovat reálné elektrony na reálném křemíku.


Dále k tématu

  1. Například poslední Intelí x86 kusy překládají sekvence některých instrukcí, jako cmp nebo aritmetické operace, následovaných skokem na jeden μop. Je tedy možné, že všechny instrukce, které řídí smyčku (inc, cmp, jXX) skončí jako jediný μop přímo implementovaný v hardware. Tohle je podle mě dobrý způsob jak utratit dostupný křemík, protože těsné smyčky jsou časté a program v nich stráví hodně času.
  2. I když některé jednoduché instrukce jsou přímo implementované v hardware. Jak je vidět z některých mikroarchitek­totických schémat, x86 CPU mají několik dekodérů z nichž většina dokáže dekódovat jen jednoduché instrukce, které jsou přeloženy na jeden μop a jeden, který překládá komplikovanější operace nebo pracuje s mikrokódem. Dekódování může pro komplikované CISC ISA představovat úzké hrdlo.
  3. Například aritmetické instrukce, které mají cíl nebe zdroj v paměti jsou přeloženy na jeden μop, který provede load/store a je neplánovaný na některou z dostupných load/store jednotek a další μop samotné aritmetické operace. Pro programátora viditelná architektura tak může být register-memory, ale mikroarchitektura je typu load-store.
  4. CMS naběhl ještě před startem operačního systému a byl to jediný kus softwaru napsaný přímo pro interní VLIW architekturu, všechno ostatní byl tradiční x86 od operačního systému až po uživatelské aplikace.
  5. Jenom s tím rozdílem, že VLIW přesně pasuje na dostupné funkční jednotky a celá dlouhá instrukce je vykonána paralelně, zatímco každý μop je na out-of-order strojích plánován a prováděn dynamicky. VLIW zachycuje statický instrukční paralelismus, μop na OOO dynamický.
  6. Mill se v mnohém podobá Itaniu, které částečně zapadá do rodiny VLIW strojů – každá instrukce je „dlouhá“ a obsahuje několik operací (v tomto případě se skupině operací říká bundle) a explicitní označení datových závislostí mezi operacemi. Pokud je mikroarchitektura dané implementace Itania dostatečně široká, stroj může vykonat pár bundlů paralelně a nemusí sám dynamicky zjišťovat závislosti mezi operacemi. Záměrem bylo dosáhnout většího ILP na novějších strojích bez nutnosti out-of-order hardwaru a se zachováním binární kompatibility.
  7. V současnosti branch predictor dosahuje úctyhodné přesnosti. Z paperu Prediction and the Performance of Interpreters je vidět, že procesor dokáže předpovídat skoky ve smyčce interpretru a svým způsobem pracuje na meta úrovni – nepředvídá skoky v kódu, ale v kódu, který interpretuje kód.
  8. Specializace se dá dotáhnout dál než skryté třídy/specializace kódu. Paper Adaptive Just-in-time Value Class Optimization se zabývá specializací kompozitních datových struktur.
  9. I některé ne-VLIW ISA odhalují interní detaily mikroarchitektury. Jde například o delay-slot.
  10. Mezi mě mimo jiné patřil Cliff Click, který měl o procesorech Vega skvělou přednášku, která kdysi, spolu s Performance Anxiety od Joshe Blocha, nasměrovala můj zájem směrem k hardwaru a procesorům.
  11. Ukazuje se, že některým serverovým úlohám nestačí instrukčí cache.
  12. Ale ani toto není nový nápad. Sám Ivan Godard říká, že Mill je rodina architektur ve stejném smyslu jako IBM System/360.
  13. Tady stojí za zmínku trace cache Pentia 4, která pracuje v duchu tracing JITu a ukládá lineární sekvenci dekódovaných mikro-operací.
  14. Podle knihy The Soul of a New Machine Tracy Kiddera stroje v sedmdesátých letech přecházely od přímé implementace instrukcí v hardware na mikrokód.

Flattr this!

This entry was posted in CPU, VM. Bookmark the permalink.

Leave a Reply

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