Obsah
1. Spekulativní provádění instrukcí (speculative execution)
2. Provádění instrukcí mimo pořadí (out of order execution)
3. Masivně paralelní architektury
4. Transputery
5. Architektura NUMA a servery Origin 200/2000
6. Topologie sítě u serverů Origin 200/2000
7. Architektura Onyx2 – Infinite Reality
1. Spekulativní provádění instrukcí (speculative execution)
V předchozí části tohoto seriálu jsme si popsali jeden z velmi často používaných způsobů vedoucích k urychlení vykonávání smyček a podmíněných příkazů (tyto vyšší jazykové konstrukce jsou u většiny mikroprocesorů překládány na podmíněné skoky, popř. podmíněné přesuny). Jednalo se o technologii predikce skoků (branch prediction). Ta je prakticky na všech skalárních i superskalárních architekturách vždy doplněna o takzvané spekulativní provádění instrukcí, neboli speculative execution, protože zvyšuje efekt prediktoru na snížení času potřebného pro vykonání programu. Základní myšlenka této techniky je poměrně jednoduchá: ve chvíli, kdy nám prediktor skoků „předpoví“, zda bude podmíněný skok proveden či nikoli, je možné začít do instrukční pipeline vkládat instrukce, které se nachází – samozřejmě podle výsledku předpovědi – buď přímo za instrukcí skoku (prediktor předpoví, že se skok neprovede) či naopak v místě, do kterého skok směřuje (prediktor předpoví, že skok bude proveden).
V případě, že prediktor kroků skutečně předpoví správný výsledek skoku, jsou již v pipeline částečně či úplně zpracovány instrukce, které se mají skutečně provést a cena za skok (udávaná v počtu hodinových cyklů či zpožděním) je minimalizována. Ovšem ve chvíli, kdy se prediktor splete (což bývá v cca dvou procentech případů v závislosti na tvaru programu, použitém prediktoru i dalších vlivech), musí se tyto předzpracované instrukce z instrukční pipeline odstranit, včetně zajištění jejich vlivu na příznakové bity či obsah pracovních registrů. V tomto případě je cena za skok velká; v praxi se může jednat i o několik desítek taktů, které mikroprocesor stráví tím, že vyprázdní instrukční pipeline, obnoví všechny pracovní registry (z takzvaných registrů stínových, shadow registers) a do vyprázdněné instrukční pipeline začne načítat nyní už známou sekvenci instrukcí. Čím větší počet řezů má instrukční pipeline, tím více je její vyprazdňování náročné.
Ukažme si chování prediktorů skoků i spekulativního provádění instrukcí na jednoduchém příkladu napsaném v jazyku symbolických instrukcí (assembleru). Předpokládejme, že náš „učebnicový“ mikroprocesor, který byl podrobně popsán v předchozích částech tohoto seriálu (viz odkazy za koncem článku), má instrukční pipeline, jež dokáže předzpracovat celkem čtyři instrukce a také obsahuje jednobitový prediktor skoků a technologii pro spekulativní provádění instrukcí. Co se za těchto podmínek stane při provádění následujícího programu pro hodnoty ZACATEK=0 a KONEC=10?
; jednoduchá počítaná smyčka typu "for"
LD A, ZACATEK ; počáteční hodnota smyčky
LD B, KONEC ; koncová hodnota smyčky
SMYCKA příkaz x1 ; libovolné instrukce, jejichž celková
příkaz x2 ; délka musí být menší než cca 120 bytů
příkaz x3 ; (kvůli omezení relativního skoku)
INC A ; zvýšení počitadla smyčky o jedničku
CMP A,B
JNZ SMYCKA ; příznak "Zerro flag" se nastaví při rovnosti A a B
příkaz y1 ; libovolné instrukce provedené až po ukončení smyčky
příkaz y2
příkaz y3 Jednobitové prediktory skoků jsou většinou konstruovány tak, že v první fázi (kdy daný skok ještě nebyl ani jednou spuštěn) preferují skoky směrem vzad, protože pro smyčky je typická právě tato konstrukce. Tj. při prvním průchodu smyčkou se ještě před vyhodnocením podmínky skoku začnou do pipeline znovu načítat instrukce x1, x2 a x3. Po provedení instrukce porovnání (CMP A,B) již mikroprocesor bezpečně ví, že byl prediktor skoků úspěšný a skutečně danou sekvenci instrukcí provede.
Po deseti opakováních smyčky však nastane případ, kdy je hodnota pracovního registru A rovna deseti a tím pádem instrukce CMP A,B nastaví příznak Zerro flag na logickou jedničku, což vede k NEprovedení skoku a opuštění smyčky. To ovšem prediktor skoků nemůže vědět a stále (na základě své předchozí zkušenosti, kterou si pamatuje v jednom bitu) procesoru tvrdí, že může do pipeline načítat instrukce x1, x2 a x3. To se ovšem ukáže jako mylné, proto musí být tyto instrukce odstraněny a do pipeline se naopak začnou načítat instrukce y1, y2 a y3.
2. Provádění instrukcí mimo pořadí (out of order execution)
Velmi účinnou technikou vedoucí ke snížení cyklů mikroprocesoru, ve kterých se žádná činnost neprovádí, spočívá v takzvaném provádění instrukcí mimo pořadí (out of order). U klasických in order mikroprocesorů, které mají instrukční pipeline, nastává situace, ve které musí následující instrukce čekat na provedení instrukce předchozí, většinou z toho důvodu, že předchozí instrukce modifikuje nějaký pracovní registr či příznak, který následující instrukce potřebuje ke svému zdárnému provedení. To samozřejmě znamená nežádoucí zdržení, protože se nevyužijí všechny cykly mikroprocesoru. V případě architektury out of order však není nic ztraceno, protože je možné začít provádět nějakou jinou instrukci, u níž je zaručeno, že používá jiné pracovní registry a příznaky (popř. je možné použít stínové pracovní registry). Interně se řazení instrukcí provádí na základě jejich ukládání do instrukční fronty (nazývané také rezervační stanice), ze které jsou instrukce vybírány ve chvíli, kdy jsou známy hodnoty jejich operandů.
Opět se můžeme podívat na příklad, i když poněkud umělý, protože náš učebnicový mikroprocesor obsahuje pouze dva pracovní registry (zde by bylo zavedení technologie out of order pravděpodobně pouze plýtváním plochou čipu resp. tranzistory). Následující kód je prováděn poměrně pomalu, protože každá instrukce ve čtveřici musí čekat na výsledek instrukce předchozí a tím pádem není využita instrukční pipeline:
LD A, [adresa_x]
RL A
XOR A, 0x7f
ST A, [adresa_y]
LD B, [adresa_z]
INC B
COM B
ST B, [adresa_w] Kvalitní out of order technologie by rozpoznala, že se nikde nevyužívají příznaky Zerro flag a Carry flag, takže je možné dynamicky přeskládat instrukce například do následující podoby (spojeny jsou vždy ty instrukce, které na sebe nemusí čekat):
LD A, [adresa_x]
LD B, [adresa_z]
RL A
INC B
XOR A, 0x7f
COM B
ST A, [adresa_y]
ST B, [adresa_w] Zde je nutné poznamenat, že tuto úpravu kódu by měl provést již překladač, který má na podobné optimalizační metody většinou dostatek času. Pro co nejlepší využití instrukční pipeline je důležité, aby co nejvíce instrukcí mohlo být prováděno současně či téměř současně. To lze zajistit především velkým množstvím pracovních registrů (32 a 64 u RISC procesorů jsou obvyklá čísla), kvalitním překladačem, který tyto registry využije a sníží tak riziko závislosti mezi instrukcemi a také odstraněním těch stavových informací, které jsou pro všechny instrukce společné a které závisejí na konkrétním pořadí provádění instrukcí – většinou se jedná o příznakové bity. Z tohoto důvodu nejsou například u mikroprocesorů promyšlené architektury MIPS příznakové bity vůbec použity; jeho podmíněné skoky se tak do značné míry blíží příkazu if známému z prakticky všech vyšších imperativních programovacích jazyků.
3. Masivně paralelní architektury
Vícejádrové mikroprocesory typu Core Duo představují poměrně významný krok pro vytvoření paralelní architektury i na běžných a cenově dostupných desktopových počítačích, ovšem v jejich návrhu se (alespoň prozatím) nepoužily takové technologie, které by umožnily vývoj skutečných masivně paralelních architektur s několika desítkami až stovkami jader (popravdě řečeno by však dnešní aplikace na takových architekturách neběžely příliš efektivně). Úzkým místem, které – samozřejmě v případě, že se technologie firem Intel a AMD výrazně nezmění – zabraňuje zvýšení počtu jader nad cca 8, je systém vyrovnávacích pamětí, existence jediného rozhraní k centrální operační paměti a v neposlední řadě také to, že další zařízení jsou připojována na jedinou sběrnici.
Kvůli tomu je ostatně také výrazně limitován počet prakticky připojitelných zařízení, ani ne tak z hlediska technických charakteristik sběrnice (zatížení výstupů a z toho plynoucí zkreslení signálů, odrazy signálů na konci fyzicky dlouhé sběrnice), jako spíše výrazného zpomalení až znemožnění práce většího množství zařízení, které musí být obslouženy tak, aby nedošlo ke ztrátě dat (síťové rozhraní, disky) či nereagování na nějaký neodkladný požadavek (uživatel by těžko akceptoval například vynechání zvukového výstupu).
Ukazuje se, že při datových přenosech mezi větším množstvím uzlů pomocí propojovací sítě, hraje rozhodující úlohu topologie sítě a méně již její bitová šířka či rychlost, jak tomu bývá u společných sběrnic. Proto se u výkonných systémů i grafických stanic setkáváme s různými druhy použitých topologií propojovacích sítí, které mohou být buď pevně zadané a neměnné (často se k tomuto účelu používá mřížka, krychle, hyperkrychle, torus, hypertorus atd.), nebo se topologie naopak mohou v závislosti na potřebách běžících aplikací dynamicky měnit pomocí programovatelných přepínačů (to částečně odpovídá i architektuře Connection Machine).
Masivně paralelní systémy, které mohou obsahovat například až 65536 relativně samostatně pracujících a spolu komunikujících mikroprocesorů, musí být sestaveny zcela odlišným způsobem. Pravděpodobně nejvýraznějším rozdílem je opuštění koncepce jediné centrální sběrnice a v mnoha případech také jediné operační paměti, protože tato dvě místa by tvořila úzké hrdlo celé architektury, které by způsobilo to, že by mikroprocesory neustále čekaly na čtení či zápis dat. Místo sběrnice (tj. lineární topologické struktury) je použita nějaká obecnější struktura, například v nejjednodušším případě mřížka, dále pak hyperkostka (kostka zobecněná do n dimenzí), toroid (mřížka, jejíž okrajové uzly jsou spojeny s protilehlými uzly), „tlustý“ binární strom (blízko kořenu je použito více datových cest, než v blízkosti listů) atd. U všech těchto topologických struktur jsou hrany představovány datovými linkami a uzly mikroprocesory s vyrovnávací pamětí, směrovačem (router) a někdy také částí operační paměti, která je sdílena mezi jednotlivými uzly.
I periferní zařízení jsou umístěna v uzlech, což mimo jiné znamená, že mohou komunikovat mezi sebou (přes ostatní uzly, resp. jejich směrovače). U některých masivně paralelních architektur se topologie celé struktury automaticky mění tak, aby odpovídala zpracovávanému programu.
Příkladem masivně paralelní architektury jsou už minule zmíněné systémy Connection Machine, především CM-5 založená na topologii „tlustého “ binárního stromu, která může obsahovat až 65536 mikroprocesorů.
4. Transputery
Výpočetní systémy založené na transputerech nebyly nikdy komerčně příliš úspěšné. Jedním z důvodů bylo špatné načasování jejich jednotlivých typů (cenově výhodnější osmibitové mikrořadiče na jednom konci a výkonné RISC na konci druhém), dalším důvodem to, že s příchodem architektury RISC a technologií spekulativního vykonávání instrukcí, paralelismu řízeného řadičem, superskalární architekturou apod. mikroprocesory úspěšně překonaly určitou krizi v růstu výpočetního výkonu a především bylo nutné pro transputery volit odlišné metody programování, zatímco například u superskalárních mikroprocesorů paralelismus (i když na mnohem nižší úrovni) řešil překladač v součinnosti s řadičem. Také použití extrémně jednoduchých čipů pro tvorbu transputerů se ukázalo jako ne příliš vhodné, protože dnes velkou roli v ceně čipu hraje i jeho pouzdro, vývody a způsob zapojení do základní desky. Mnohdy bylo ekonomicky výhodnější použít velmi výkonný jednojádrový mikroprocesor než pro stejnou úlohu využít například šestnáct mnohem jednodušších transputerů. Jak však uvidíme v dalších kapitolách, myšlenka transputerů byla použita i ve zcela odlišných systémech.
Atari ABAQ s transputery mělo být konkurencí k pracovním stanicím Sun
V minulosti se velké naděje vkládaly do takzvaných transputerů, což jsou (zjednodušeně řečeno) mikrořadiče, které na jednom čipu obsahují i komunikační rozhraní schopné se připojit k dalším čtyřem až třiceti dvěma sousedním transputerům. Důležité je, že přímo v instrukční sadě transputerů jsou obsaženy instrukce pro komunikaci se sousedními uzly a i celý program obsahuje velké množství implicitně či explicitně zadaných „komunikačních“ operací. Počet uzlů se může v závislosti na struktuře počítače pohybovat od několika desítek až do několika tisíc. Typickým programovacím jazykem pro transputery je occaml, který obsahuje jak instrukce pro komunikaci mezi jednotlivými uzly (? a !), tak i konstrukci pro paralelní provádění příkazů.
5. Architektura NUMA a servery Origin 200/2000
Firma Silicon Graphics Inc. (SGI) byla předním výrobcem výpočetních systémů postavených na architektuře NUMA. Název této architektury pochází z celého označení Non-Uniform Memory Access, čímž je naznačeno, jakým způsobem je provedeno vzájemné uspořádání procesorů a operační paměti.
Architektura NUMA byla vytvořena za účelem propojení velkého množství procesorů, které mezi sebou musí určitým způsobem sdílet data. Při malém množství procesorů je možné použít takzvaný symetrický multiprocessing – SMP, kdy existuje pouze jedna hlavní paměť a procesory na tuto paměť přistupují přes vhodnou propojovací strukturu, která obsahuje i arbitr. Na bázi SMP jsou vystavěny i víceprocesorové osobní počítače a jednodušší servery (včetně Core Duo a spol.). Vždy se však jedná o propojení dvojic, maximálně čtveřic procesorů, rozumný limit je osm jader. Blokové schéma architektury SMP je naznačeno na dalším obrázku.
Blokové schéma architektury SMP
Architektura SMP je poměrně jednoduchá, proto je také snadná její implementace. Potíže však nastávají při připojení více procesorů. Už při čtyřech současně běžících procesorech se ukazuje, že propojovací struktura se stává úzkým hrdlem této architektury, protože i přes mnohdy velikou kapacitu pamětí cache nastávají kolize při přístupu do hlavní paměti, kdy na sebe jednotlivé procesory musí čekat (blíže viz Amdahlův zákon).
Tuto vážnou nevýhodu odstraňuje architektura NUMA, která zavádí místo jednoduché lineární propojovací struktury složitější topologie, jako je mřížka, krychle, hyperkrychle, torus nebo hypertorus. V uzlech této topologické sítě se nacházejí jednotlivé procesory, operační paměť (je zde použito obecnější schéma DSM – Distributed Shared Memory – distribuovaná sdílená paměť, takže operační paměť je rozdělena mezi jednotlivé uzly) a další zařízení, mimo jiné i grafický akcelerátor či grafické akcelerátory. Ty jsou z tohoto hlediska zcela rovnocenné procesorům, na rozdíl od architektury PC.
U serverů Origin 200/2000 je použita mírná modifikace uzlů, ve kterých je místo jednoho procesoru zapojena vždy dvojice procesorů. Ke každému procesoru přináleží i několik cache pamětí – instrukční cache paměť (na dalším obrázku je označena symbolem I-c), datová cache paměť (na obrázku je označena symbolem D-c) a část sdílené paměti (označena symbolem S-cache). Blokové scéma jednoho uzlu použitého u serverů Origin je zobrazeno na následujícím obrázku.
Jeden uzel serveru Origin 200/2000
6. Topologie sítě u serverů Origin 200/2000
U serverů Origin 200/2000 se pro propojování jednotlivých uzlů používá topologie sítě založená na hyperkrychli (hypercube). Hyperkrychle vzniká zobecněním plošného čtverce či prostorové krychle do obecně libovolného počtu dimenzí. Ve vrcholu plošného čtverce se stýkají dvě hrany, ve vrcholu třírozměrné krychle tři hrany, ve vrcholu hyperkrychle ve čtyřech dimenzích čtyři hrany atd. Podle počtu uzlů je vhodně zvolena dimenze hyperkrychle (1–7), která se v běžných případech pohybuje od dvou uzlů do 128 uzlů. Tento počet sice nepředstavuje teoretické maximum, ale s dalším přidáváním uzlů se poměrně značným způsobem zvyšuje počet hran, které se stýkají v jednom vrcholu hyperkrychle, čímž se také prodlužuje předávání dat mezi jednotlivými uzly (složité routování dat).
Na dalším obrázku je ukázána propojovací topologie hyperkrychle pro několik základních konfigurací serverů Origin 200/2000. Každý uzel na obrázku přitom obsahuje dva procesory se svými cache paměťmi.
Velkou výhodou použité propojovací topologie a návrhu uzlů u serverů Origin, je vysoká škálovatelnost, která umožňuje efektivní použití až několika set procesorů. Tyto procesory se mohou využít například pro vykreslování trojrozměrných scén metodou raytracingu, neboť tato metoda je takřka ideálně paralelizovatelná (samozřejmě až na rostoucí paměťovou složitost). Další často používanou možností je připojení několika grafických akcelerátorů pro urychlení vykreslování trojrozměrné grafiky v hraniční reprezentaci, či použití těchto systémů pro také relativně snadno paralelizovatelné úlohy typu „lámání šifer“.
Propojovací topologie hyperkrychle použité u serverů Origin 200/2000
7. Architektura Onyx2 – Infinite Reality
Výkonné grafické pracovní stanice firmy SGI postavené na systému Infinite Reality, nebo jejím pokračovateli Infinite Reality 2, se vyznačují zejména masivním využitím paralelismu – ostatně mnoho algoritmů v počítačové grafice je možné paralelizovat velmi dobře, až na zvyšující se paměťové nároky (vícenásobné kopie vstupních dat, několik paralelních framebufferů atd.).
Systémy postavené na IR mohou obsahovat až 128 procesorů oblíbené produktové řady MIPS R10000. Zde je patrný rozdíl oproti často srovnávané architektury s transputery (či dokonce CM-5), která sice používá mnohem více procesorů, ale tyto procesory jsou – alespoň v porovnání s MIPS R10000 – velmi jednoduché. V případě architektury Onyx2 se jedná o stejné procesory, jaké jsou použity i v serverech Origin 200/2000, tato řada procesorů je však populární i v jiných oblastech, tedy nejenom v hi-end grafice, na kterou byla firma SGI zaměřena.
Jedná o procesory typu RISC s čtyřcestnou superskalární architekturou, které jsou optimalizované na zpracování velkého množství dat. Ke každému procesoru je připojena rychlá externí paměť cache o kapacitě plných čtyř megabytů (interní paměť cache má velikost 32kB pro kód i pro data, tato poměrně malá kapacita odpovídá roku vzniku tohoto mikroprocesoru – 1995 – a částečně také použité architektuře). Oblíbenost tohoto mikroprocesoru je dána i jeho nízkou cenou, takže při stavbě výpočetních systémů bylo možné dosáhnout velmi slušného poměru cena/výkon.
