Algoritmus Tomasulo - Tomasulo algorithm

Algoritmus Tomasulo je hardwarový algoritmus počítačové architektury pro dynamické plánování pokynů, který umožňuje provádění mimo pořadí a umožňuje efektivnější využití více prováděcích jednotek. Byl vyvinut společností Robert Tomasulo ve společnosti IBM v roce 1967 a byl poprvé implementován v jednotce s pohyblivou řádovou čárkou systému IBM System/360 Model 91 .

Mezi hlavní inovace Tomasulova algoritmu patří přejmenování registru v hardwaru, rezervační stanice pro všechny prováděcí jednotky a společná datová sběrnice (CDB), na které vysílané hodnoty vysílají všem rezervačním stanicím, které je mohou potřebovat. Tento vývoj umožňuje vylepšené paralelní provádění pokynů, které by se jinak zastavily při použití tabulek nebo jiných dřívějších algoritmů.

Robert Tomasulo obdržel v roce 1997 Cenu Eckert – Mauchlyho za práci na algoritmu.

Implementační koncepty

Tomasulova jednotka s plovoucí desetinnou čárkou

Níže jsou uvedeny koncepty nutné k implementaci Tomasulova algoritmu:

Společná datová sběrnice

Common Data Bus (CDB) spojuje rezervační stanice přímo s funkčními jednotkami. Podle Tomasula „zachovává přednost a podporuje souběžnost“. To má dva důležité efekty:

1. Funkční jednotky mají přístup k výsledku jakékoli operace bez zapojení registru s plovoucí desetinnou čárkou, což umožňuje více jednotkám čekajícím na výsledek pokračovat bez čekání na vyřešení sporu o přístup k portům pro čtení souborů.
2. Distribuce detekce nebezpečí a provádění kontroly. Rezervační stanice kontrolují, kdy může být spuštěna instrukce, nikoli jedinou vyhrazenou nebezpečnou jednotku.

Instrukční pořadí

Instrukce jsou vydávány postupně, takže účinky sekvence instrukcí, jako jsou výjimky vyvolané těmito instrukcemi, se vyskytují ve stejném pořadí jako u procesoru v pořadí, bez ohledu na to, že jsou prováděny mimo provoz pořadí (tedy nesekvenčně).

Zaregistrujte přejmenování

Tomasulův algoritmus používá přejmenování registru, aby správně provedl spuštění mimo pořadí. Všechny registry univerzálních a rezervačních stanic mají buď skutečnou hodnotu, nebo zástupnou hodnotu. Pokud je skutečná hodnota v cílovém registru ve fázi vydání nedostupná, použije se původně hodnota zástupného symbolu. Hodnota zástupného symbolu je značka označující, která rezervační stanice vytvoří skutečnou hodnotu. Když jednotka dokončí a vysílá výsledek na CDB, zástupný symbol bude nahrazen skutečnou hodnotou.

Každá funkční jednotka má jednu rezervační stanici. Rezervační stanice obsahují informace potřebné k provedení jediné instrukce, včetně operace a operandů. Funkční jednotka začne zpracovávat, když je volná a když jsou všechny zdrojové operandy potřebné pro instrukci skutečné.

Výjimky

Prakticky řečeno, mohou existovat výjimky, pro které není k dispozici dostatek stavových informací o výjimce. V takovém případě může procesor vyvolat zvláštní výjimku, nazývanou „nepřesná“ výjimka. V implementacích v pořadí nemohou nastat nepřesné výjimky , protože stav procesoru se mění pouze v pořadí programu (viz výjimky RISC Pipeline ).

Programy, které zažívají „přesné“ výjimky, kde lze určit konkrétní instrukci, která výjimku převzala, se mohou restartovat nebo znovu spustit v místě výjimky. Ty, u kterých se vyskytnou výjimky „nepřesné“, však obecně nelze restartovat ani znovu spustit, protože systém nemůže určit konkrétní instrukci, která výjimku přijala.

Životní cyklus instrukce

Tři níže uvedené fáze jsou fázemi, kterými každá instrukce prochází od okamžiku, kdy byla vydána, do doby, kdy je její provedení dokončeno.

Zaregistrujte legendu

• Op - představuje operaci prováděnou na operandech
• Qj, Qk - rezervační stanice, která bude produkovat příslušný zdrojový operand (0 znamená, že hodnota je ve Vj, Vk)
• Vj, Vk - hodnota zdrojových operandů
• A - slouží k uchování informací o adrese paměti pro načtení nebo uložení
• Zaneprázdněn - 1, pokud je obsazen, 0, pokud není obsazen
• Qi - (Pouze registrační jednotka) rezervační stanice, jejíž výsledek by měl být uložen v tomto registru (pokud je prázdný nebo 0, pro tento registr nejsou určeny žádné hodnoty)

Fáze 1: problém

Ve fázi vydání jsou vydány pokyny k provedení, pokud jsou všichni operandové a rezervační stanice připraveni, nebo jsou zablokováni. Registry jsou v tomto kroku přejmenovány, čímž se eliminuje nebezpečí VÁLKY a WAW.

• Získejte další instrukci z hlavy fronty instrukcí. Pokud jsou operandy instrukce aktuálně v registrech, pak
  • Pokud je k dispozici odpovídající funkční jednotka, vydejte pokyny.
  • Jinak, protože není k dispozici žádná funkční jednotka, zastavte instrukci, dokud není stanice nebo vyrovnávací paměť volná.
• Jinak můžeme předpokládat, že operandy nejsou v registrech, a použít tedy virtuální hodnoty. Funkční jednotka musí vypočítat skutečnou hodnotu, aby bylo možné sledovat funkční jednotky, které produkují operand.

if (RegisterStat[rs].Qi¦0) {
	RS[r].Qj ← RegisterStat[rs].Qi
}
else {
	RS[r].Vj ← Regs[rs];
	RS[r].Qj ← 0;
}
if (RegisterStat[rt].Qi¦0) { 
	RS[r].Qk ← RegisterStat[rt].Qi;
}
else {
	RS[r].Vk ← Regs[rt]; 
	RS[r].Qk ← 0;
}
RS[r].Busy ← yes;
RegisterStat[rd].Qi ← r;

if (RegisterStat[rs].Qi¦0) {
	RS[r].Qj ← RegisterStat[rs].Qi;
}
else {
	RS[r].Vj ← Regs[rs];
	RS[r].Qj ← 0;
}
RS[r].A ← imm;
RS[r].Busy ← yes;

RegisterStat[rt].Qi ← r;

if (RegisterStat[rt].Qi¦0) {
	RS[r].Qk ← RegisterStat[rt].Qi;
}
else {
	RS[r].Vk ← Regs[rt];
	RS[r].Qk ← 0
};

Příklad Tomasulova algoritmu

Fáze 2: Spusťte

Ve fázi provádění se provádějí instrukční operace. Pokyny jsou v tomto kroku zpožděny, dokud nejsou k dispozici všechny jejich operandy, což eliminuje nebezpečí RAW. Správnost programu je udržována prostřednictvím efektivního výpočtu adresy, aby se zabránilo rizikům v paměti.

• Pokud jeden nebo více operandů ještě není k dispozici, pak: počkejte, až bude operand k dispozici na CDB.
• Když jsou k dispozici všechny operandy, pak: pokud je instrukce načíst nebo uložit
  • Vypočítejte efektivní adresu, když je k dispozici základní registr, a umístěte ji do vyrovnávací paměti načítání/ukládání
    • Pokud je instrukce zátěž, proveďte: proveďte ihned, jakmile bude k dispozici paměťová jednotka
    • Jinak, pokud je instrukce úložiště, pak: počkejte, až bude hodnota uložena, než ji odešlete do paměťové jednotky
• Jinak je instrukce operací aritmetické logické jednotky (ALU) a poté: proveďte instrukci na odpovídající funkční jednotce

(RS[r].Qj = 0) and (RS[r].Qk = 0)

RS[r].A ← RS[r].Vj + RS[r].A;

Fáze 3: zapište výsledek

Ve fázi Výsledek zápisu jsou výsledky operací ALU zapsány zpět do registrů a operace ukládání jsou zapsány zpět do paměti.

• Pokud byla instrukce operací ALU
  • Pokud je výsledek k dispozici, pak: napište jej na CDB a odtud do registrů a všech rezervačních stanic čekajících na tento výsledek
• Jinak, pokud byla instrukce úložiště, pak: během tohoto kroku zapište data do paměti

	∀x(if (RegisterStat[x].Qi = r) {
		regs[x] ← result;
		RegisterStat[x].Qi = 0
	});
	∀x(if (RS[x].Qj = r) {
		RS[x].Vj ← result;
		RS[x].Qj ← 0; 
	});
	∀x(if (RS[x].Qk = r) {
		RS[x].Vk ← result;
		RS[x].Qk ← 0;
	});
	RS[r].Busy ← no;

	Mem[RS[r].A] ← RS[r].Vk;
	RS[r].Busy ← no;

Vylepšení algoritmů

Koncepty rezervačních stanic, přejmenování registrů a společné datové sběrnice v Tomasulově algoritmu představují významné pokroky v konstrukci vysoce výkonných počítačů.

Rezervační stanice přebírají odpovědnost za čekání na operandy za přítomnosti závislostí na datech a dalších nesrovnalostí, jako je různá doba přístupu k úložišti a rychlosti obvodů, čímž se uvolní funkční jednotky. Toto vylepšení překonává dlouhá zpoždění s pohyblivou řádovou čárkou a přístupy do paměti. Algoritmus je zejména tolerantnější vůči chybám v mezipaměti. Programátoři jsou navíc osvobozeni od implementace optimalizovaného kódu. To je výsledek společné datové sběrnice a rezervační stanice, které spolupracují na zachování závislostí a podpoře souběžnosti.

Algoritmus sledováním instrukcí operandů na rezervačních stanicích a přejmenováním registrů v hardwaru minimalizuje čtení po zápisu (RAW) a eliminuje rizika počítačové architektury zápisu po zápisu (WAW) a zápisu po čtení (VAR) . To zlepšuje výkon tím, že se zkracuje ztráta času, který by jinak byl u stánků vyžadován.

Neméně důležitým vylepšením algoritmu je, že design není omezen na konkrétní strukturu potrubí. Toto vylepšení umožňuje, aby byl algoritmus více přijímán procesory s více problémy. Algoritmus je navíc snadno rozšířitelný, aby umožňoval spekulace větví.

Aplikace a dědictví

Tomasulův algoritmus mimo společnost IBM nebyl několik let po implementaci v architektuře System/360 Model 91 používán. V 90. letech však došlo k obrovskému nárůstu využití ze 3 důvodů:

1. Jakmile se mezipaměti staly samozřejmostí, stala se v procesorech cenná schopnost algoritmu Tomasulo udržovat souběžnost během nepředvídatelných dob načítání způsobených chybami mezipaměti.
2. Dynamické plánování a spekulace větví, že algoritmus umožňuje vyšší výkon, protože procesory vydávaly další a další pokyny.
3. Šíření softwaru pro masový trh znamenalo, že programátoři by nechtěli kompilovat pro konkrétní strukturu potrubí. Algoritmus může fungovat s jakoukoli architekturou potrubí, a proto software vyžaduje několik úprav specifických pro architekturu.

Mnoho moderních procesorů implementuje schémata dynamického plánování, která jsou odvozena od původního algoritmu Tomasulo, včetně populárních čipů Intel x86-64 .

Viz také

• Znovu objednat vyrovnávací paměť (ROB)
• Paralelizmus na úrovni instrukcí (ILP)

Reference

Další čtení

• Savard, John JG (2018) [2014]. „Pipelined a out-of-Order Execution“ . quadibloc . Archivováno od originálu dne 2018-07-03 . Citováno 2018-07-16 .

externí odkazy

• Dynamic Scheduling - Tomasulo's Algorithm at the Wayback Machine (archivováno 25. prosince 2017)
• MÁTE simulaci Tomletova algoritmu pro Java