Pipelining

Pipelining, zřetězené zpracování či překrývání strojových instrukcí je způsob zvýšení výkonu procesoru současným prováděním různých částí několika strojových instrukcí. Základní myšlenkou je rozdělení zpracování jedné instrukce mezi různé části procesoru a tím i umožnění zpracovávat více instrukcí najednou. Fáze zpracování je rozdělena minimálně na 2 úseky:

  1. Načtení a dekódování instrukce
  2. Provedení instrukce a případné uložení výsledku

To vedlo k vytvoření procesoru složeného ze dvou spolupracujících subprocesorů (skalární architektura), kdy každá část realizuje danou fázi zpracování. Procesor má části – EU (Execution Unit) a BIU (Bus Interface Unit). Zřetězení se stále vylepšuje a u novějších procesorů se již můžeme setkat stále s více řetězci rozpracovaných informací (více pipelines). Z toho vyplývá, že je možno dokončit více než 1 instrukci za 1 hodinový cyklus (takt procesoru).

Zřetězené zpracování je technika používaná při návrhu počítačů pro zvýšení jejich instrukčního průchodu (počet instrukcí, které mohou být vykonány za jednotku času). Základní instrukční cyklus je rozdělen na série zvané vedení. Místo zpracovávání každé instrukce postupně (dokončení jedné instrukce před začátkem další), každá instrukce je rozdělena na sled kroků, takže různé kroky mohou být vykonány současně a paralelně (jiným okruhem).

Zřetězení zvyšuje instrukční průtok prováděním více operací současně, ale nesnižuje instrukční latenci (čas pro provedení instrukce od začátku do konce), jelikož stále musí provést všechny kroky. Vskutku, může to zvyšovat latenci kvůli přídavné režii z rozdělení výpočtů na oddělené kroky a hůře, zřetězení se může zdržet (případně potřebovat proplach), což dále zvyšuje latenci. Zřetězení tedy zvyšuje průtok za cenu latence a je často používáno v CPU, ale nikoliv v realtime systémech, které jsou na latenci těžce závislé.

Každá instrukce je rozdělena do posloupnosti závislých kroků. Prvním krokem je vždy načtení instrukce z paměti, posledním krokem je většinou zápis výsledku do registru nebo paměti. Zřetězení se snaží umožnit procesoru pracovat na tolika instrukcích zároveň, kolik je závislých kroků, stejně jako montážní linka sestavuje několik vozidel současně, místo aby čekala, až jedno projde celou linkou, než začne s dalším. Stejně jako cílem montážní linky je udržet každou součást produktivní v každém okamžiku, zřetězení chce udržet každou část procesoru zaneprázdněnou s nějakou instrukcí. Zřetězení v počítači umožňuje, že čas cyklu je čas nejpomalejšího kroku a ideálně je v každém cyklu dokončena jedna strojová instrukce.

Pojem pipeline je analogií faktu, že v potrubí je v každém úseku kapalina, stejně jako je každá část procesoru zatížena prací.

Běžná riscová pipeline

Za jakýsi standard je považována pipeline s pěti stupni, implementována například v prvních procesorech MIPS, SPARC a Motorola 88000. Jedná se o následující stupně:

  1. Instruction fetch – vyzvednutí instrukce
  2. Decode – dekódování instrukce, zároveň se načítají registry
  3. Execute – provedení instrukce
  4. Access – čtení z paměti
  5. Writeback – zápis výsledku do paměti

Rizika

Model sekvenčního provedení předpokládá, že se každá instrukce dokončí předtím, než se začne vykonávat další. V případě zřetězeného procesoru tento předpoklad neplatí. Situace, kdy očekávaný výsledek je problematický, je známá jako hazard. Představme si následující dvě registrové instrukce k hypotetickému procesoru RISC.

1: add 1 to R5

2: copy R5 to R6

V případě, že procesor má 5 kroků, by první instrukce byla v čase t1 doručena procesoru a byla provedena v čase t5. Druhá instrukce by byla doručena v čase t2 a provedena v čase t6. První instrukce může uložit číslo do registru R5 v pátém kroku v čase t5. Ale druhá instrukce může dostat číslo z registru R5 (kopírovat do R6) ve svém druhém kroku v čase t3. Zdá se, že by první instrukce nezvýšila tou dobou hodnotu. Výše uvedený kód vyvolá hazard.

Psaní počítačových programů v kompilovaném jazyce nemusí tyto obavy vyvolávat, protože kompilátor by mohl být navržený tak, aby generoval strojový kód tak, aby se vyhnul hazardu.

Řešení

Zřetězené procesory běžně používají tři techniky, aby pracovaly tak jak se očekává, když programátor předpokládá, že každá instrukce je dokončena předtím, než začne další:

  • Procesory, které mohou počítat přítomnost rizika, mohou zastavit, zpozdit zpracování druhé instrukce dokud hodnoty, které jsou vyžadovány jako vstup, nejsou připraveny. Tím se vytvoří bublina ve zřetězení, tím se částečně negují výhody zřetězení.
  • Některé procesory mohou nejen počítat přítomnost rizika, ale mohou také kompenzovat to, že mají další datové cesty, které poskytují potřebné vstupy výpočetního kroku před tím, než by je spočítala následující instrukce.
  • Některé procesory mohou rozhodnout, jestli instrukce jiné než následující jsou závislé na těch současných a mohou být provedeny bez rizika.

Predikce skoku

Jedním z problémů pipeliningu je fakt, že instrukce následující po skoku se vyzvedává dřív než je skok dokončen. Primitivní implementace vyzvedává vždy následující instrukci, což vede k tomu že se vždy mýlí, pokud je skok nepodmíněný. Pozdější implementace mají jednotku předpovídání skoku, která vždy správně předpoví (tedy předem dekóduje) nepodmíněný skok a s použitím cache se záznamem předchozího chování programu se pokusí předpovědět i cíl podmíněných skoků nebo skoků s adresou v registru nebo paměti.

V případě, že se predikce nepovede, bývá nutné vyprázdnit celou pipeline a začít vyzvedávat instrukce ze správné adresy, což znamená relativně velké zdržení.

Souvisejícím problémem je přerušení. Softwarová přerušení a výjimky jsou z hlediska procesoru skoky a je možné je predikovat, i když složitěji než obyčejné skoky. Hardwarová přerušení mohou oproti tomu dorazit kdykoliv bez předchozího upozornění, na druhou stranu v mnoha případech je možné „podvádět“ tak, že se přerušení nezačne provádět okamžitě, ale zařadí se na konec fronty, jakoby přišlo o několik instrukcí později. Znamená to ale další komplikaci při selhání predikce skoku – musí se totiž zrušit instrukce mezi skokem a přerušením, ale ne samotné přerušení, a cílovou adresu skoku uložit na zásobník pro návrat z přerušení.

Pipeline v x86

Na architektuře x86 se pipeline objevila u procesoru Intel 80286, kde měla tři stupně (Bus Unit, Instruction Unit, Execution Unit). Procesor Intel Pentium má jako první dvě pipeline (U-pipe a V-pipe a obě používají zřetězené zpracování instrukcí). Zde se poprvé objevuje pojem superskalární procesor – tzn. zřetězené zpracování instrukcí se provádí ve více než jedné frontě (konkrétně u Pentia se provádí v U-pipe i V-pipe, tzn. obě nejprve vyberou instrukci (prefetch), obě ji pak předají k dekódování (decode) atd.). Další procesory se dále komplikovaly: Intel Pentium 4 má pipeline s 31 stupni, ale je otázkou, zda toto číslo má smysl. Hlavním rozdílem totiž je, že od Pentium Pro (a AMD K5) fungují procesory x86 na principu překladu CISCových instrukcí na RISCové. První fáze tedy spočívají ve vyzvednutí instrukcí z paměti a jejich překladu na RISCové, které se pak provádějí mimo pořadí a paralelně. Může se stát i to, že jedna CISCová instrukce se rozdělí na dvě RISCové, z nichž jedna je již dokončena, zatímco druhá čeká na výkonnou jednotku.

I nejmodernější 64bitové procesory navazují na x86, ovšem zaručují, že z pohledu programátora se instrukce vykonávají sekvenčně a přerušení jsou doručena tak, že všechny instrukce před přerušením jsou dokončeny a žádná instrukce po přerušení následující neovlivnila stav procesoru. Co při vylepšování procesorů padlo jsou tabulky „ceny“ (tedy času trvání) instrukcí: spočítat, jak rychle se na moderním procesoru vykoná nějaká sekvence instrukcí je velmi obtížné a závisí na příliš mnoha parametrech, které se navíc v každém modelu procesoru liší. V dnešních procesorech jsou možná i paradoxní chování typu funkce, která trvá déle pokud z ní smažete část kódu.

Pipeline u GPU

V 3D počítačové grafice, podmínka grafické pipeline nebo renderovacích pipeline se často vztahuje na současný stav metody rasterization-based rendering.

Implementace

S vyrovnávací pamětí, synchronní řetězení

Konvenční mikroprocesory jsou synchronní obvody využívající synchronní jednotky zřetězení s vyrovnávací pamětí. V těchto řetězících jednotkách jsou mezi fáze pipeline vloženy „pipeline registry“ řízené hodinovým taktem. Čas mezi každým hodinovým taktem je nastaven na vyšší hodnotu než je hodnota nejdelší prodlevy mezi fázemi pipeline, aby při řízení registrů hodinovým taktem byla data do nich zapsána jako výsledek předchozí fáze.

S vyrovnávací pamětí, asynchronní řetězení

Asynchronní pipeline jsou použity v asynchronních obvodech a jejich jednotky řetězení jsou časovány asynchronně. Obecně řečeno, využívají systém typu žádost/potvrzení, v němž každá fáze může detekovat, zda je hotovo. Jako ukázka této implementace je procesor AMULET.

Řetězení bez vyrovnávací paměti

Toto zřetězené zpracování, často zvané „vlnové zpracování“ neobsahuje registry jako mezičlánek fází. Namísto toho, zpoždění ve zpracování je vyváženo. Pro každou fázi je minimalizována diference mezi prvním a posledním stabilizovaným výstupem dat.