Techniky zvýšení výkonu mikroprocesorů 2

Obsah

1. Skalární architektura
2. Překonání omezení daných skalární architekturou
3. Superskalární architektura
4. Prediktory skoků – jedna z cest k vyřešení problémů se zřetězeným zpracováním instrukcí
5. Záhadné zkratky SISD, SIMD, MISD, MIMD
6. Architektura SISD
7. Architektura SIMD
8. Architektura MISD
9. Architektura MIMD

1. Skalární architektura

Převážná část osmibitových a šestnáctibitových mikroprocesorů i první generace mikroprocesorů třicetidvoubitových byla postavena na takzvané skalární architektuře. Tímto termínem jsou označovány mikroprocesory, které v jednou taktu načtou maximálně jednu instrukci a provedou na základě jejího operačního kódu pouze jednu aritmetickou či logickou operaci s jednoduchou (skalární) hodnotou. I náš ukázkový mikroprocesor popsaný v předchozích částech tohoto seriálu má typicky skalární architekturu. Teoretická maximální rychlost zpracování instrukcí u této architektury je jedna načtená (a provedená) instrukce v jednom taktu a to ještě pouze za předpokladu, že se použije zřetězené zpracování instrukcí (pipelining), nebo je frekvence hodinového signálu tak nízká, že mikroprocesor celou instrukci stihne provést za jeden hodinový takt (to ovšem znamená, že se v tomto případě uvnitř mikroprocesoru hodinový signál rozkládá na ještě kratší impulzy, například na základě jeho náběžných a sestupných hran).

Bez použití pipeliningu nebo v případě menšího množství řezů instrukční pipeliny se jedna instrukce na skalární architektuře zpracovává ve více taktech. Tato vlastnost byla typická pro většinu osmibitových mikroprocesorů (Intel 8080, MOS 6502, Zilog Z80 a další slavná jména), které jednu instrukci dokázaly provést například ve třech až dvanácti taktech. Mikroprocesor Motorola 6800 dokázal nejjednodušší instrukce, například součet akumulátoru s konstantou, provést ve dvou taktech a instrukci nejsložitější, což v tomto případě byl skok do podprogramu, v taktech osmi, přičemž nebylo použito žádné zřetězené provádění instrukcí (to se také nedá od mikroprocesoru této kategorie očekávat). Z typicky skalárních mikroprocesorů do dnešní doby přežila stále poměrně populární typová řada mikrořadičů Intel 8051 (některé varianty vyráběla v minulosti i naše Tesla) a Motorola 68HC11.

Všechny CISCové mikroprocesory firmy Intel řady x86 od ještě z poloviny osmibitového 8088 až do modelu 486 (včetně) jsou postavené na skalární architektuře, stejně jako velké množství mikrořadičů či signálových procesorů (DSP – Digital Signal Processor). Mezi přednosti skalární architektury patří především jednoduchý řadič, který může být buď mikroprogramový (Intel 8086) či nanoprogramový (Motorola 68000) nebo pevně zapojený (Motorola 6809). Nevýhodou ovšem je, že rychlost načítání a tím i zpracování instrukcí je shora omezena a že ani s využitím velmi dlouhé pipeliny se nedá překonat limit jedné zpracovaná instrukce za jeden takt. Příliš velké množství řezů (slices) pipeline má naopak i své zápory, především při zpracování skoků, návratů z podprogramů či odezvy na přerušení – ve všech těchto případech je nutné vyřešit problém, co se má udělat s instrukcemi, které se nachází v rozpracovaném stavu v pipeline (mohou se buď zahodit nebo naopak dokončit, podle toho, jakým způsobem byl lineární běh programu přerušen).

Známý osmibitový mikroprocesor Motorola 6809

2. Překonání omezení daných skalární architekturou

Jednou z možností urychlení vykonávání instrukcí je použití již minule popsané architektury VLIW (Very Long Instruction Word). Mikroprocesory založené na VLIW sice dokážou v jednom taktu zpracovat větší množství instrukcí (tj. provést více operací), ovšem za tu cenu, že je program vždy znovu nutné přeložit přímo pro daný typ mikroprocesoru a není tak zaručena binární kompatibilita se staršími typy mikroprocesorů. Pro některé aplikace to není na závadu (signálové procesory použité ve vestavěných zařízeních), ovšem na osobních počítačích, u kterých je z různých důvodů požadována binární kompatibilita, není možné VLIW přímo použít. Navíc je instrukční slovo málokdy využito stoprocentně, což zbytečně zvyšuje nároky na kapacitu i rychlost operační paměti. Z těchto důvodů (a samozřejmě ve snaze v co nejvyšší míře urychlit vykonávání instrukcí) se začala prosazovat takzvaná superskalární architektura, která bude popsaná v následující kapitole.

I poslední verze mikroprocesoru 486 měla skalární architekturu

3. Superskalární architektura

Mikroprocesory postavené na superskalární architektuře dokážou, podobně jako procesory typu VLIW, v jednom taktu začít vykonávat více než jednu instrukci, přičemž současně vykonávané instrukce (resp. současně vykonávané stejné fáze instrukcí) používají samostatné moduly na mikroprocesoru.

V praxi to například může znamenat to, že mikroprocesor obsahuje dvě aritmeticko-logické jednotky (ALU), dvě jednotky pro adresaci s využitím indexových registrů, dvě jednotky umožňující provedení skoků atd. V některých případech není tato duplikace (či dokonce multiplikace, protože je možné mít klidně i čtyři nezávislé ALU) výkonných jednotek mikroprocesoru zcela symetrická, protože mikroprocesor například může obsahovat pouze jednu jednotku pro provádění operací v pohyblivé řádové čárce (FPU) či jen jednu násobičku atd. To je i případ prvních superskalárních mikroprocesorů řady x86 – Intel Pentium, které obsahovaly dvě pipeliny (ve skutečnosti se jednalo u superskalární mikroprocesor se zřetězeným zpracováním instrukcí) nazvané U a V, které ovšem nebyly zcela symetrické – ne všechny instrukce bylo možné v první pipelině zpracovat. Čím se však superskalární architektura liší od architektury VLIW, když základní myšlenka, tj. zvýšení počtu paralelně a nezávisle na sobě pracujících jednotek, je stejná?

První procesor kompatibilní s řadou x86 se superskalární architekturou

Zásadní rozdíl spočívá v tom, že zatímco u VLIW je paralelní spouštění instrukcí založeno na instrukčním slovu, ve kterém se nachází jednotlivé operační kódy současně prováděných operací (explicitní instrukční paralelismus), rozhoduje u superskalární architektury o paralelním provádění operací až řadič na základě toho, jak vyhodnotí obsazení pracovních registrů a strukturu programu. Operační kódy instrukcí jsou tedy načteny z fronty instrukcí (ta byla minule popsaná) a teprve řadič rozhodne, zda a jak je možné instrukce zpracovávat paralelně. Toto řešení s sebou přináší několik předností i záporů. První přednost je zřejmá – je zachována binární kompatibilita, tj. i strojový kód určený pro starší mikroprocesory téže řady (například x86) může být provozován na superskalárních mikroprocesorech a to nezávisle na tom, kolik paralelně pracujících jednotek tyto mikroprocesory obsahují. Zatímco mikroprocesory 486 měly jednu pipelinu pro zpracování instrukcí, u Pentií se objevily pipeliny dvě, poté čtyři atd.

Mezi nevýhody této architektury patří složitější řadič, který kromě své běžné činnosti, tj. řízení pipeliny a jednotlivých funkčních jednotek mikroprocesoru, ještě musí rozhodovat o tom, které instrukce je možné párovat a spouštět současně. Také – i když je zaručena zpětná binární kompatibilita – je většinou žádoucí upravit strojový kód programu tak, aby co nejvíce instrukcí bylo možné spouštět paralelně, k čemuž je již potřebná znalost jednotlivých závislostí mezi instrukcemi a jejich operandy (například manuál k párování instrukcí na prvních Pentiích měl skoro sto stran a to byly použity pouze dvě instrukční pipeliny). To je ostatně také jeden z důvodů, proč je ten stejný program přeložený nejprve v režimu kompatibility s 386 a posléze přeložený pro Pentium ve druhém případě prováděn na stejném mikroprocesoru i konfiguraci celého počítače rychleji (zcela jiným důvodem urychlení některých algoritmů je rozšířená instrukční sada, například MMX a SSE, tou se však budeme podrobněji zabývat až v další části tohoto seriálu).

Většinou se pro tento účel používají překladače vyšších programovacích jazyků, které potřebné optimalizace v určité míře provádí. Ovšem ve speciálních případech je zapotřebí sáhnout k ruční optimalizaci programů na úrovni assembleru či strojového kódu, protože v této oblasti sice mohou optimalizující překladače velmi pomoci, ale nejsou samospasitelné (překladač totiž nemá k dispozici stejné množství informací jako programátor). Také mnohé just-in-time překladače (JIT), tj. překladače spuštěné v době běhu programu, který dynamicky překládají, jež jsou použité například u platformy Java, mohou provádět optimalizace, a to v některých případech ještě lépe než běžné překladače, protože JIT mohou využít statistické informace získané z běžícího programu, optimalizovat přímo pro daný mikroprocesor atd. Tato technika, která se začíná objevovat i u běžných překladačů (optimalizace na základě výsledků několikerého běhu profileru), se v pozitivním slova smyslu projeví především u dlouho běžících aplikací, například na serverech.

4. Prediktory skoků – jedna z cest k vyřešení problémů se zřetězeným zpracováním instrukcí

V předchozím textu jsme si řekli, že maximální rychlost zpracování u skalárních mikroprocesorů je jedna instrukce za jeden takt (nezávisle na taktovací frekvenci a bitové šířce). U superskalárních mikroprocesorů se maximální rychlost zvyšuje se stejnou mírou, jakou stoupá počet instrukčních pipeline. Například první Pentia s dvojicí pipeline dokázaly zpracovat maximálně dvě instrukce v jednom taktu. Ovšem to jsou výsledky dosažitelné za ideálních podmínek, které není možné v reálných programech vždy stoprocentně splnit. Mezi vlivy, které reálnou rychlost zpracování instrukcí snižují, patří především přepínání kontextů (změna běžící úlohy, která ovšem nastává relativně zřídka, například 100× za sekundu, což je z hlediska mikroprocesoru velmi dlouhá doba), nedostupnost instrukcí či operandů ve vyrovnávací paměti (výpadek cache), příchod přerušení a v neposlední řadě také provedení skoku, ať už přímého, nepřímého, absolutního, relativního, podmíněného či nepodmíněného. Mezi skok se počítá i vstup do podprogramu a návrat z podprogramu.

Při výskytu skoku se totiž musí vyřešit problém, co se má udělat s instrukcemi, které se nachází v rozpracovaném stavu uvnitř pipeline. Většinou nastává nejhorší případ, kdy se tyto instrukce musí zahodit a po provedení skoku se musí pipeline znovu naplnit, tentokrát jinými instrukcemi. To má samozřejmě za následek snížení výpočetního výkonu, které může být někdy velmi radikální (například Pentium 4 má pipeline rozdělenou na více než 30 řezů, tj. může se v ní nacházet třicet rozpracovaných instrukcí). Je tedy vhodné nějakým způsobem skoky co nejvíce omezit či snížit jejich negativní dopad na rychlost běhu programu. První metoda, tj. omezení skoků, je záležitostí překladače či ruční optimalizace kódu. Používají se různé postupy, například inline funkce (kód funkce je přímo vložen na dané místo kódu, aby se funkce nemusela volat) či rozbalování smyček (loop unrolling). To však není zdaleka vše, používají se i další techniky. Některé procesory místo podmíněných skoků nabízí podmíněné instrukce, u instrukcí skoků lze – opět pouze u některých mikroprocesorů – jedním bitem naznačit, zda je pravděpodobnější provedení podmíněného skoku či naopak jeho neprovedení atd.

Velmi zajímavou technologií jsou prediktory skoků. Ty slouží, jak ostatně jejich název napovídá, k tomu, že dopředu odhadnou, zda se skok provede či nikoli a na základě toho začnou do instrukční pipeline vkládat (a postupně zpracovávat) buď instrukce, které se nachází ihned za skokem či naopak v cíli skoku. U jednotlivých skoků nahrazujících konstrukci typu if je samozřejmě predikce spíše loterií, ovšem známé pravidlo 90/10 (nebo 80/20) nám říká, že 90 procent času běhu programu se stráví v pouhých deseti procentech kódu, tj. musí se jednat o nějaké smyčky, u kterých by bylo dobré skoky predikovat. Existuje více způsobů implementace prediktorů skoků, my si vysvětlíme prediktory jednobitové a dvoubitové.

Jednoduchý jednobitový prediktor skoků pracuje tak, že si procesor u každého skoku v jednom bitu zapamatuje, zda byl skok proveden či nikoli. Když se v instrukční pipeline znovu skok objeví (souhlasí jeho adresa), tak se procesor na základě předešlého běhu programu rozhodne, které další instrukce se pravděpodobně budou zpracovávat. Při prvním volání skoku má prediktor pouze padesátiprocentní úspěšnost, ta se potom zvyšuje. Například u smyčky, která by měla proběhnout 100× (to ovšem procesor dopředu neví) se sice při prvním průchodu prediktor splete (za což je penalizován „vysypáním“ pipeline), ovšem v dalších 98 průchodech už správně odhadne, že se skok provede. Poslední průchod je znovu odhadnut špatně, což je ovšem pochopitelné. Výsledkem je poměrně úspěšné a především rychlé provedení všech instrukcí ve smyčce, přičemž je úspěšnost predikce skvělých 98 procent (to je ovšem ideální případ).

Dvoubitový prediktor pracuje velmi podobným způsobem, ovšem pamatuje si nejenom předchozí výsledek skoku (proveden, neproveden), ale i minulý stav predikce. Pro mnoho typů podmínek je výhodnější, než jednobitový prediktor, protože i jeden špatný odhad ještě nezmění stav prediktoru. Způsob predikce u dvoubitového prediktoru skoků je možné naznačit stavovým diagramem:

5. Záhadné zkratky SISD, SIMD, MISD, MIMD

Při popisu technik vedoucích k urychlení zpracování instrukcí se nemůžeme nezmínit o zkratkách SISD, SIMD, MISD a MIMD. Jedná se o zkratky, které vyjadřují jak míru paralelnosti dané architektury (ve své podstatě nejde jen o architekturu samotného mikroprocesoru, ale celého počítače, zejména těch částí, které se týkají vlastních výpočtů), tak i způsob práce s daty. Stručný význam těchto zkratek je uveden v následující tabulce:

6. Architektura SISD

Náš ukázkový mikroprocesor byl typu SISD, neboli Single Instruction, Single Data. Každá instrukce pracovala maximálně se dvěma operandy; například u instrukce ADD se jednalo o oba sčítance. Jedná se o tu nejjednodušší prakticky použitelnou architekturu, která může být rozšířena o již popsané zřetězené zpracování instrukcí a také implementací většího množství výkonných jednotek. Stále se však jedná o architekturu, kde jedna instrukce může zpracovat velmi omezené množství dat, které odpovídají dané operaci a případný paralelismus tedy není řešen na úrovni jednotlivých instrukcí. Jde sice o nejjednodušší architekturu, která je však nejobecnější a tudíž stále používaná (někdy v kombinaci s následujícím typem).

7. Architektura SIMD

Dnes velmi populární je architektura SIMD, jejíž kořeny však sahají hluboko do minulosti (sedmdesátá léta minulého století). Jedná se o architekturu, ve které se pomocí jedné instrukce může zpracovat větší množství dat. Například u rozšířené instrukční sady MMX je možné pomocí jediné instrukce provést součet dvou vektorů číselných hodnot, například se může jednat o osm osmibitových hodnot uložených v jednom vektoru, čtyři šestnáctibitové hodnoty v jednom vektoru atd. Této vlastnosti se dá v mnoha případech využít pro urychlení běhu programů, protože některé algoritmy provádí velké množství stejných operací s rozsáhlým objemem dat – například se může jednat o aplikaci konvolučního filtru na rastrový obrázek, zpracování zvukového signálu atd. Předností SIMD je jak relativně kompaktní instrukční sada, tak i paralelní a tím i rychlý běh mnoha algoritmů, ovšem za cenu větších nároků na programátora. Většinu SIMD konstrukcí není možné zapsat v konvenčním vyšším programovacím jazyce, musí se použít buď hotová makra, ručně optimalizované knihovní funkce nebo specializované jazyky typu *Lisp.

Pentium MMX zavedlo instrukční sadu MMX, která je založena na SIMD

8. Architektura MISD

Architektura MISD umožňuje na jedny data (přečtená z pracovního registru nebo operační paměti) aplikovat více operací zapsaných ve více instrukcích za sebou; jde tedy o zobecněnou pipeline (ta ovšem pracuje na úrovni instrukčních řezů, tedy na nižší úrovni, než je tomu u MISD). Existují případy, kdy je vhodné tuto architekturu použít, je jich však méně, než u SIMD, proto není MISD u běžných (nespecializo­vaných) mikroprocesorů příliš rozšířena. Zásobníkové procesory je možné považovat za flexibilněji navrženou architekturu MISD.

9. Architektura MIMD

Největší úroveň paralelismu nabízí architektura MIMD. V procesoru nebo procesorovém poli je paralelně zpracováváno větší množství dat a to nezávisle na sobě (většinou asynchronně). V minulosti se tato architektura používala velmi často například u superpočítačů (zde byly procesory spojeny například sítí s topologií toroidu, hyperkostky či „tlustého“ binárního stromu), dnes se této úrovně paralelismu dosahuje i na běžných „stolních“ procesorech s více jádry (i když zde existuje principiální omezení počtu jader). Problémem je, že opravdu masivní paralelismus s několika desítkami, stovkami či tisíci procesorů vyžaduje i jiný přístup k programování a použití specializovaných jazyků, například „paralelního“ LISPu s všeříkajícím názvem *Lisp. Pravděpodobně nejzajímavější technologií používající MIMD, jsou slavné Connection Machine, zejména CM-5 vytvořená z RISCových procesorů SPARC (z pohledu CM jsou moderní dvoujádrové či čtyřjádrové mikroprocesory pouhé hračky, protože v CM bylo možné současně používat až 65536 procesorů :-).

Futuristický design Connection Machine 5