Provedení mimo objednávku- Out-of-order execution

V počítačovém inženýrství je provádění mimo pořadí (nebo formálně dynamičtější provádění ) paradigmatem používaným ve většině vysoce výkonných centrálních procesorových jednotek k využití instrukčních cyklů, které by jinak byly zbytečné. V tomto paradigmatu procesor vykonává pokyny v pořadí, které se řídí dostupností vstupních dat a prováděcích jednotek, nikoli podle jejich původního pořadí v programu. Přitom se procesor může vyhnout nečinnosti při čekání na dokončení předchozí instrukce a mezitím může zpracovat další instrukce, které lze spustit okamžitě a nezávisle.

Dějiny

Provádění mimo pořadí je omezená forma výpočtu toku dat , která byla v 70. a na začátku 80. let hlavní výzkumnou oblastí počítačové architektury .

Důležitý akademický výzkum v tomto předmětu vedl Yale Patt a jeho simulátor HPSm . Dokument Jamese E. Smitha a AR Pleszkuna, publikovaný v roce 1985, doplnil schéma popisem, jak by bylo možné zachovat přesné chování výjimek u strojů mimo pořadí.

Pravděpodobně prvním strojem, který používá provádění mimo pořadí, je CDC 6600 (1964), který k řešení konfliktů používal srovnávací tabulku . 6600 však postrádal řešení konfliktů WAW , místo toho se rozhodl zastavit. Tuto situaci Thornton nazval „konflikt prvního řádu“. Přestože mělo řešení konfliktů RAW (označované jako „konflikt druhého řádu“) a řešení konfliktu VÁLC (označované jako „konflikt třetího řádu“), což vše postačuje k prohlášení, že je schopné plného provedení mimo pořadí, 6600 nemělo přesné zpracování výjimek. Časná a omezená forma předpovědi větve byla možná, pokud se větev nacházela na místech, která se nazývala „hromada instrukcí“, která byla omezena na hloubku sedmi slov z čítače programu.

Asi o tři roky později představil IBM System/360 Model 91 (1966) Tomasulův algoritmus , který umožňuje úplné provedení mimo pořadí. V roce 1990 představila společnost IBM první mikroprocesor mimo pořadí, POWER1 , ačkoli provedení mimo pořadí je omezeno na instrukce s plovoucí desetinnou čárkou (jak je tomu také u modelu 91).

V devadesátých letech se stále častěji objevovalo provádění mimo pořadí a bylo uvedeno v IBM / Motorola PowerPC 601 (1993), Fujitsu / HAL SPARC64 (1995), Intel Pentium Pro (1995), MIPS R10000 (1996), HP PA-8000 (1996), AMD K5 (1996) a DEC Alpha 21264 (1996). Mezi významné výjimky z tohoto trendu patří Sun UltraSPARC , HP / Intel Itanium , Intel Atom until Silvermont Architecture a IBM POWER6 .

Vysoká logická složitost techniky mimo pořadí je důvodem, že se k běžným strojům dostala až v polovině 90. let minulého století. Mnoho low-endových procesorů určených pro cenově citlivé trhy stále toto paradigma nepoužívá kvůli velké křemíkové ploše potřebné pro jeho implementaci. Nízká spotřeba energie je dalším cílem návrhu, kterého je těžší dosáhnout s provedením mimo objednávku (OoOE).

Základní koncept

Chcete-li ocenit OoO Execution, je užitečné nejprve popsat v pořadí, abyste mohli tyto dva porovnat. Pokyny nelze dokončit okamžitě: vyžadují čas (několik cyklů). Výsledky proto budou zaostávat tam, kde jsou potřeba. V pořadí stále musí sledovat závislosti. Jeho přístup je však zcela nenáročný: pokaždé se zastaví. OoO používá mnohem sofistikovanější techniky sledování dat, jak je vidět níže.

Objednávkové procesory

V dřívějších procesorech se zpracování instrukcí provádí v cyklu instrukcí, který obvykle sestává z následujících kroků:

  1. Načtení instrukcí .
  2. Pokud jsou k dispozici vstupní operandy (například v registrech procesoru), je instrukce odeslána do příslušné funkční jednotky . Pokud jeden nebo více operandů není během aktuálního hodinového cyklu k dispozici (obecně proto, že se načítají z paměti ), procesor se zastaví, dokud nejsou k dispozici.
  3. Instrukci provádí příslušná funkční jednotka.
  4. Funkční jednotka zapíše výsledky zpět do souboru registru .

Procesor v pořadí bude mít často přímý „bitový vektor“, do kterého se zaznamená, který zaregistruje potrubí, do kterého bude (nakonec) zapisovat. Pokud nějaké vstupní operandy mají v tomto vektoru nastaven odpovídající bit, instrukce se zastaví. V zásadě vektor plní značně zjednodušenou roli ochrany před nebezpečím registru. Proto pozorujeme, že mimo pořadí používá 2D matice, kde v pořadí používá 1D vektor pro zamezení nebezpečí.

Procesory mimo pořadí

Toto nové paradigma rozděluje zpracování pokynů na tyto kroky:

  1. Načtení instrukcí.
  2. Odeslání instrukce do fronty instrukcí (také nazývané instrukční vyrovnávací paměť nebo rezervační stanice ).
  3. Instrukce čeká ve frontě, dokud nejsou k dispozici její vstupní operandy. Instrukce může opustit frontu před staršími pokyny.
  4. Instrukce je vydána příslušné funkční jednotce a provedena touto jednotkou.
  5. Výsledky jsou ve frontě.
  6. Teprve poté, co budou všechny starší instrukce zapsány jejich výsledky zpět do souboru registru, pak bude tento výsledek zapsán zpět do souboru registru. Toto se nazývá fáze promoce nebo důchodu.

Klíčovým konceptem zpracování OoOE je umožnit procesoru vyhnout se třídě blokování, ke kterým dochází, když nejsou k dispozici data potřebná k provedení operace. Ve výše uvedeném přehledu se procesor OoOE vyhýbá zablokování, ke kterému dochází v kroku (2) procesoru v pořadí, když instrukce není zcela připravena ke zpracování kvůli chybějícím datům.

Procesory OoOE vyplnit tyto „sloty“ v čase s dalšími pokyny, které jsou připraveny, pak re-pořadí výsledky na konci, aby to vypadalo, že pokyny byly zpracovány jako obvykle. Způsob, jakým jsou pokyny seřazeny v původním počítačovém kódu, se nazývá programové pořadí , v procesoru se s nimi zachází v pořadí dat , v jakém pořadí jsou data, operandy, dostupná v registrech procesoru. K převodu z jednoho uspořádání na druhé a udržení logického uspořádání výstupu jsou zapotřebí poměrně složité obvody; procesor sám spouští instrukce ve zdánlivě náhodném pořadí.

Výhoda zpracování OoOE roste s tím, jak se instrukční potrubí prohlubuje a rozdíl v rychlosti mezi hlavní pamětí (nebo vyrovnávací pamětí ) a procesorem se rozšiřuje. Na moderních strojích běží procesor mnohonásobně rychleji než paměť, takže během doby, kdy procesor v pořadí tráví čekáním na příchod dat, mohl zpracovat velké množství instrukcí.

Oddělení oddělení odesílání a vydávání umožňuje problém mimo pořadí

Jedním z rozdílů vytvořených novým paradigmatem je vytváření front, které umožňují oddělení kroku odeslání od kroku vydání a stupně odstupňování od fáze spuštění. Časný název paradigmatu byl oddělená architektura . V dřívějších řadových procesorech tyto stupně pracovaly vcelku blokovaně a potrubně.

Pokyny programu nemusí být spuštěny v původně zadaném pořadí, pokud je konečný výsledek správný. Odděluje fáze načítání a dekódování od fáze spuštění v pipeline procesoru pomocí vyrovnávací paměti .

Účelem vyrovnávací paměti je rozdělit přístup k paměti a spouštět funkce v počítačovém programu a dosáhnout vysokého výkonu využíváním jemnozrnné rovnoběžnosti mezi nimi. Přitom efektivně skryje veškerou latenci paměti z pohledu procesoru.

Větší vyrovnávací paměť může teoreticky zvýšit propustnost. Pokud má však procesor nesprávnou předpověď větve, může být nutné vyprázdnit celou vyrovnávací paměť, čímž se ztrácí mnoho hodinových cyklů a snižuje účinnost. Kromě toho větší vyrovnávací paměti vytvářejí více tepla a využívají více prostoru matrice . Z tohoto důvodu návrháři procesorů dnes upřednostňují přístup s vícevláknovým designem.

Oddělené architektury jsou obecně považovány za nepoužitelné pro obecné účely, protože nezpracovávají dobře kód náročný na řízení. Mezi kódy náročné na řízení patří například vnořené větve, které se často vyskytují v jádrech operačního systému . Oddělené architektury hrají důležitou roli při plánování architektur velmi dlouhých instrukčních slov (VLIW).

Aby se předešlo závislostem na falešných operandech, které by snižovaly frekvenci, pokud by mohly být instrukce vydávány mimo pořadí, používá se technika nazývaná přejmenování registru . V tomto schématu existuje více fyzických registrů, než definuje architektura. Fyzické registry jsou označeny tak, aby mohlo existovat více verzí stejného architektonického registru současně.

Odpojení spouštění a zpětného zápisu umožňuje restart programu

Fronta výsledků je nezbytná k vyřešení problémů, jako jsou nesprávné předpovědi větví a výjimky/pasti. Fronta výsledků umožňuje restartování programů po výjimce, která vyžaduje dokončení pokynů v pořadí programů. Fronta umožňuje zahodit výsledky z důvodu chybných předpovědí u starších instrukcí větve a výjimek přijatých u starších instrukcí.

Schopnost vydávat pokyny kolem větví, které ještě nejsou vyřešeny, se nazývá spekulativní provádění .

Mikro-architektonické možnosti

  • Jsou pokyny odesílány do centralizované fronty nebo do více distribuovaných front?
Procesory IBM PowerPC používají fronty, které jsou distribuovány mezi různé funkční jednotky, zatímco jiné procesory mimo pořadí používají centralizovanou frontu. IBM pro své distribuované fronty používá termín rezervační stanice .
  • Existuje skutečná fronta výsledků nebo jsou výsledky zapsány přímo do souboru registru? U posledně jmenovaných je funkce zařazování do fronty řešena mapami registrů, které uchovávají informace o přejmenování registru pro každou letovou instrukci.
Dřívější procesory Intel mimo pořadí používají frontu výsledků nazývanou vyrovnávací paměť pro opětovné objednání , zatímco většina pozdějších procesorů mimo pořadí používá mapy registrů.
Přesněji: mikroprocesory řady Intel P6 mají jak vyrovnávací paměť pro opětovné objednání (ROB), tak tabulku aliasů registrů (RAT). ROB byl motivován hlavně obnovou chybné předpovědi pobočky.
Rodina Intel P6 byla jedním z prvních mikroprocesorů OoOE, ale byla nahrazena architekturou NetBurst . O několik let později se Netburst ukázal jako slepá ulička kvůli svému dlouhému potrubí, které předpokládalo možnost mnohem vyšších provozních frekvencí. Materiály nebyly schopny odpovídat ambiciózním hodinovým cílům návrhu kvůli tepelným problémům a pozdější návrhy založené na NetBurst, konkrétně Tejas a Jayhawk, byly zrušeny. Intel se vrátil k designu P6 jako základu mikroarchitektur Core a Nehalem . Následujícího Sandy Bridge , Ivy Bridge a Haswell microarchitectures jsou odklon od přeskupování technik používaných v P6 a zaměstnávají přeskupení technik z EV6 a P4 , ale s poněkud kratší potrubí.

Viz také

Reference

Další čtení

  • Smith, James E .; Pleszkun, AR (červen 1985). „Implementace přesných přerušení v potrubních procesorech“. Zprávy počítačové architektury ACM SIGARCH . 13 (3): 36–44. doi : 10,1145/327070,327125 .