Paměťová disambiguace - Memory disambiguation

Paměťová disambiguace je sada technik využívaných k vysoce výkonným provedení mimo objednávku mikroprocesory které vykonávají Paměť přístup instrukce (načte a uloží) mimo pořadí programu. Mechanismy pro provádění disambiguace paměti implementované pomocí digitální logika uvnitř jádra mikroprocesoru detekovat skutečné závislosti mezi operacemi paměti v době provádění a umožnit procesoru zotavit se, když byla závislost porušena. Rovněž eliminují falešné závislosti na paměti a umožňují větší paralelismus na úrovni instrukcí povolením bezpečného provádění zátěží a skladů mimo objednávku.

Pozadí

Závislosti

Při pokusu o provedení pokynů mimo pořadí musí mikroprocesor respektovat skutečné závislosti mezi instrukce. Zvažte například jednoduchou skutečnou závislost:

1: přidat $ 1, $ 2, $ 3 # R1 <= R2 + R32: přidat $ 5, $ 1, $ 4 # R5 <= R1 + R4 (v závislosti na 1)

V tomto příkladu přidat instrukce na řádku 2 závisí na přidat instrukce na řádku 1, protože Registrovat R1 je zdroj operand operace přidání na řádku 2. The přidat na řádku 2 nelze provést, dokud přidat na řádku 1 dokončí. V tomto případě je závislost statický a snadno určitelný mikroprocesorem, protože zdroje a cíle jsou registry. Cílový registr přidat instrukce na řádku 1 (R1) je součástí kódování instrukce, a tak jej může určit mikroprocesor na začátku, během dekódovací fáze potrubí. Podobně zdrojové registry přidat instrukce na řádku 2 (R1 a R4) jsou také zakódovány do samotné instrukce a jsou určeny dekódováním. Aby byla respektována tato skutečná závislost, logika plánovače mikroprocesoru vydá tyto instrukce ve správném pořadí (nejprve instrukce 1, následovaná instrukcí 2), takže výsledky 1 jsou k dispozici, když je instrukce 2 potřebuje.

Komplikace nastanou, když závislost není staticky stanovitelná. Takové nestatické závislosti vznikají u paměťových instrukcí (načítá a ukládá), protože umístění operandu může být nepřímo specifikováno jako operand registru, nikoli přímo zadáno v samotném kódování instrukce.

1: uložit $ 1, 2 ($ 2) # Mem [R2 + 2] <= R12: načíst $ 3, 4 ($ 4) # R3 <= Mem [R4 + 4] (případně závislé na 1, možná stejná adresa jako výše)

Zde instrukce pro uložení zapíše hodnotu do paměťového místa určeného hodnotou v adrese (R2 + 2) a instrukce načtení načte hodnotu v paměťovém místě určeném hodnotou v adrese (R4 + 4). Mikroprocesor nemůže před provedením staticky určit, zda jsou umístění paměti uvedená v těchto dvou pokynech odlišná nebo jsou stejná, protože umístění závisí na hodnotách v R2 a R4. Pokud se umístění liší, jsou pokyny nezávislé a lze je úspěšně provést mimo pořadí. Pokud jsou však umístění stejná, pak je instrukce načítání závislá na úložišti, které produkuje jeho hodnotu. Toto je známé jako nejednoznačná závislost.

Mimořádné provádění a operace přístupu do paměti

Provádění načítání a ukládání mimo pořadí může způsobit nesprávné výsledky, pokud byl závislý pár zatížení / úložiště proveden mimo pořadí. Zvažte následující fragment kódu uvedený v MIPS shromáždění:

1: div $ 27, $ 202: sw $ 27, 0 ($ 30) 3: lw $ 08, 0 ($ 31) 4: sw $ 26, 0 ($ 30) 5: lw $ 09, 0 ($ 31)

Předpokládejme, že plánovací logika vydá instrukci prováděcí jednotce, až budou připraveny všechny její operandy registru. Dále předpokládejme, že se registruje $30 a $31 jsou připraveny: hodnoty v $30 a $31 byly spočítány už dávno a nezměnily se. Předpokládejme však $27 není připraven: jeho hodnota je stále v procesu výpočtu pomocí div (integer divide) instrukce. Nakonec předpokládejme, že se registruje $30 a $31 držet stejnou hodnotu, a tak všechna načtení a uložení ve fragmentu přistupují ke stejnému slovu paměti.

V této situaci sw $ 27, 0 ($ 30) instrukce na řádku 2 není připravena k provedení, ale lw $ 08, 0 ($ 31) instrukce na řádku 3 je připravena. Pokud procesor umožňuje lw instrukce k provedení před sw, zátěž načte starou hodnotu z paměťového systému; měl by však přečíst hodnotu, kterou tam právě napsal sw. Načtení a uložení proběhlo mimo programové pořadí, ale mezi nimi byla narušena paměťová závislost.

Podobně předpokládejme tento registr $26 je připraven. The sw $ 26, 0 ($ 30) instrukce na řádku 4 je také připravena k provedení a může být provedena před předchozím lw $ 08, 0 ($ 31) na řádku 3. Pokud k tomu dojde, lw $ 08, 0 ($ 31) instrukce přečte špatně hodnota z paměťového systému, protože pozdější instrukce ukládání tam zapsala svoji hodnotu před provedením načtení.

Charakterizace závislostí paměti

Závislosti paměti mají tři příchutě:

  • Čtení a zápis Závislosti (RAW): Známé také jako skutečné závislosti, vznikají závislosti RAW, když operace načtení přečte hodnotu z paměti, která byla vytvořena poslední předchozí operací úložiště na stejnou adresu.
  • Write-After-Read Závislosti (WAR): Známé také jako anti závislosti, závislosti WAR vznikají, když operace úložiště zapíše hodnotu do paměti, kterou přečte předchozí načtení.
  • Write-After-Write Závislosti (WAW): Známé také jako výstupní závislosti, závislosti WAW vznikají, když dvě operace úložiště zapisují hodnoty na stejnou adresu paměti.

V předchozím segmentu kódu (reprodukováno pro přehlednost) jsou zobrazeny tři závislosti:

1: div $ 27, $ 202: sw $ 27, 0 ($ 30) 3: lw $ 08, 0 ($ 31) 4: sw $ 26, 0 ($ 30) 5: lw $ 09, 0 ($ 31)
  • The lw $ 08, 0 ($ 31) instrukce na řádku 3 má závislost RAW na sw $ 27, 0 ($ 30) instrukce na řádku 2 a lw $ 09, 0 ($ 31) instrukce na řádku 5 má závislost RAW na sw $ 26, 0 ($ 30) instrukce na řádku 4. Obě instrukce načtení čtou adresu paměti, kterou zapisovaly předchozí obchody. Obchody byly nejnovějšími producenty této adresy paměti a zatížení načítají hodnotu této adresy paměti.
  • The sw $ 26, 0 ($ 30) instrukce na řádku 4 má závislost WAR na lw $ 08, 0 ($ 31) instrukce na řádku 3, protože zapisuje adresu paměti, ze které čte předchozí náklad.
  • The sw $ 26, 0 ($ 30) instrukce na řádku 4 má závislost WAW na sw $ 27, 0 ($ 30) instrukce na řádku 2, protože oba obchody zapisují na stejnou adresu paměti.

Mechanismy disambiguace paměti

Moderní mikroprocesory používají následující mechanismy implementované v Hardware, vyřešit nejednoznačné závislosti a obnovit, když byla závislost porušena.

Vyhýbejte se závislostem WAR a WAW

Hodnoty z pokynů k ukládání nejsou uloženy do paměťového systému (v moderních mikroprocesorech Mezipaměť CPU ) když popraví. Místo toho jsou pokyny k ukládání, včetně adresy paměti a dat úložiště, ukládány do vyrovnávací paměti v obchod fronta dokud nedosáhnou bodu odchodu do důchodu. Když obchod odejde do důchodu, je to pak zapíše jeho hodnotu do paměťového systému. Tím se vyhnete problémům se závislostmi WAR a WAW, které se zobrazují ve fragmentu kódu výše, kde dřívější načtení obdrží nesprávnou hodnotu z paměťového systému, protože pozdějšímu úložišti bylo povoleno provést před dřívějším načtením.

Navíc ukládání do vyrovnávací paměti až do vyřazení umožňuje procesorům spekulativně provádět instrukce úložiště, které následují po pokynu, který může způsobit výjimka (například načítání špatné adresy, dělení nulou atd.) nebo a podmíněná větev instrukce, jejíž směr (zaujatý nebo nepřijatý) dosud není znám. Pokud instrukce vytvářející výjimky nebyla provedena nebo byl směr větve předpovězen nesprávně, procesor načte a provede instrukce na „nesprávné cestě“. Tyto pokyny neměly být vůbec provedeny; podmínka výjimky by měla nastat před provedením spekulativních instrukcí, nebo by se větev měla vydat opačným směrem a způsobit načtení a provedení různých instrukcí. Když procesor zjistí výjimku nebo nesprávnou předpověď větve, musí „vyhodit“ všechny výsledky špatně spekulativně provedených pokynů. Komplikace pro obchody spočívá v tom, že všechny obchody na špatné nebo nesprávně předvídané cestě by neměly své hodnoty odevzdat paměťovému systému; pokud by obchody potvrdily své hodnoty, nebylo by možné „odhodit“ potvrzení a stav paměti stroje by byl poškozen daty z instrukce úložiště, které by neměly být provedeny.

Bez ukládání do vyrovnávací paměti úložiště tedy nelze obchody provádět, dokud nebudou provedeny všechny předchozí pokyny způsobující výjimky (a nezpůsobí výjimku) a dokud nebudou známy všechny předchozí směry větví. Vynucení obchodů čekat, dokud nebudou známy směry větví a výjimky, významně snižuje agresivitu mimo pořadí a omezuje ILP (Paralela na úrovni instrukcí ) a výkon. S ukládáním do vyrovnávací paměti úložiště mohou obchody spouštět před instrukcemi větve způsobujícími výjimky nebo nevyřešené, ukládat do mezipaměti svá data ve frontě úložiště, ale nepotvrdit jejich hodnoty až do vyřazení. To zabrání tomu, aby obchody na nesprávně předvídaných nebo špatných cestách odevzdávaly své hodnoty do paměťového systému, zatímco stále nabízejí zvýšený ILP a výkon z plného provádění objednávek mimo pořadí.

Uložte pro načtení přesměrování

Ukládání do vyrovnávací paměti do vyřazení se vyhýbá závislostem WAW a WAR, ale zavádí nový problém. Zvažte následující scénář: úložiště provede a uloží do vyrovnávací paměti svou adresu a data ve frontě úložiště. O několik pokynů později se spustí zátěž, která čte ze stejné adresy paměti, na kterou právě napsal obchod. Pokud náklad načte svá data z paměťového systému, přečte starou hodnotu, která by byla přepsána předchozím úložištěm. Data získaná načtením budou nesprávná.

K vyřešení tohoto problému používají procesory tzv přesměrování mezi sklady pomocí fronty obchodů. Kromě ukládání do vyrovnávací paměti obchodů až do vyřazení slouží fronta obchodů k jinému účelu: předávání dat z dokončených, ale dosud nevyřazených („letových“) obchodů na pozdější načtení. Spíše než jednoduché FIFO fronta, fronta obchodu je opravdu Paměť adresovatelná obsahu (CAM) prohledávat pomocí adresy paměti. Když se zatížení načte, prohledá frontu obchodů obchody v letu na stejnou adresu, která je logicky dříve v pořadí programu. Pokud existuje odpovídající úložiště, načte zátěž svou datovou hodnotu z tohoto úložiště namísto paměťového systému. Pokud neexistuje odpovídající úložiště, zátěž přistupuje k paměťovému systému jako obvykle; jakékoli předchozí, odpovídající obchody musí být již vyřazeny a potvrzeny jejich hodnoty. Tato technika umožňuje načtení získat správná data, pokud jejich úložiště producentů bylo dokončeno, ale ještě nebylo vyřazeno.

Ve frontě úložišť může být přítomno více úložišť na adresu paměti zátěže. Pro zpracování tohoto případu je fronta úložiště kódováno podle priority vyberte nejnovější úložiště, které je logicky dřívější než načtení v pořadí programu. Určení, který obchod je „nejnovější“, lze dosáhnout připojením nějakého druhu časové razítko k instrukcím, jak jsou načítány a dekódovány, nebo alternativně znalostí relativní polohy (slotu) zátěže s ohledem na nejstarší a nejnovější úložiště ve frontě úložiště.

Porušení závislosti RAW

Detekce porušení závislosti na RAW

Moderní procesory mimo pořadí mohou k detekci narušení závislosti RAW použít celou řadu technik, ale všechny techniky vyžadují sledování zatížení za letu od spuštění až do vyřazení. Když se zátěž spustí, přistupuje k paměťovému systému a / nebo k úložné frontě, aby získala svou datovou hodnotu, a poté se její adresa a data ukládají do vyrovnávací paměti načíst frontu do důchodu. Fronta zatížení má podobnou strukturu a funkci jako fronta úložiště a ve skutečnosti může být v některých procesorech kombinována s frontou úložiště v jediné struktuře zvané a fronta načtení a uloženínebo LSQ. K detekci porušení závislosti na RAW se používají nebo byly navrženy následující techniky:

Načíst frontu CAM vyhledávání

S touto technikou je fronta načítání, stejně jako fronta úložiště, prohledávána CAM pomocí adresy pro přístup do paměti a sleduje všechna zatížení za letu. Když se úložiště spustí, prohledá frontu načtení pro dokončená načtení ze stejné adresy, která jsou logicky později v pořadí programu. Pokud takové odpovídající zatížení existuje, muselo být provedeno před úložištěm a tedy načíst nesprávnou starou hodnotu z fronty paměťového systému / úložiště. Veškeré pokyny, které používaly hodnotu načtení, také použily špatná data. Chcete-li se zotavit, pokud je takové porušení zjištěno, je zátěž ve vyrovnávací paměti pro vyřazení označena jako „porušena“. Úložiště zůstává ve frontě úložiště a vyrovnávací paměti pro vyřazení a normálně se vyřadí a po jeho odložení potvrdí svoji hodnotu paměťovému systému. Když však narušení načtení dosáhne bodu vyřazení, procesor propláchne kanál a restartuje provádění z instrukce načtení. V tomto okamžiku všechny předchozí obchody potvrdily své hodnoty paměťovému systému. Instrukce načtení nyní načte správnou hodnotu z paměťového systému a všechny závislé instrukce se znovu provedou pomocí správné hodnoty.

Tato technika vyžaduje asociativní vyhledávání fronty načtení při každém spuštění obchodu, které spotřebovává obvod výkon a může se ukázat jako obtížná cesta načasování pro velké fronty zatížení. Nevyžaduje však žádnou další paměť (mezipaměti ) porty nebo vytvářejte konflikty zdrojů s jinými spuštěnými načítáním nebo ukládáním.

Rozcestník při odchodu do důchodu

S touto technikou jsou instrukce načtení, které byly provedeny mimo pořadí, znovu provedeny (přistupují k paměťovému systému a podruhé načtou hodnotu z jejich adresy), když dosáhnou bodu odchodu do důchodu. Protože zátěž je nyní instrukcí pro odchod do důchodu, nemá žádné závislosti na žádné instrukci, která je ještě za letu; všechny obchody před ním odevzdaly své hodnoty paměťovému systému, a proto je zaručeno, že každá hodnota načtená z paměťového systému bude správná. Hodnota načtená z paměti v době opětovného spuštění se porovná s hodnotou získanou při prvním spuštění zátěže. Pokud jsou hodnoty stejné, byla původní hodnota správná a nedošlo k žádnému porušení. Pokud se hodnota opětovného provedení liší od původní hodnoty, došlo k narušení RAW a potrubí musí být vyprázdněno, protože instrukce závislé na zatížení použily nesprávnou hodnotu.

Tato technika je koncepčně jednodušší než hledání fronty načtení a eliminuje druhý CAM a jeho hledání náročné na moc (fronta načtení může nyní být jednoduchá FIFO fronta). Vzhledem k tomu, že zátěž musí znovu přistupovat k paměťovému systému těsně před vyřazením, musí být přístup velmi rychlý, takže toto schéma závisí na rychlé mezipaměti. Bez ohledu na to, jak rychlá je mezipaměť, ale druhý přístup k paměťovému systému pro každou instrukci načítání mimo pořadí zvyšuje vyřazení instrukce latence a zvyšuje celkový počet přístupů do mezipaměti, které musí procesor provést. Další přístup do mezipaměti v důchodu lze uspokojit opětovným použitím existujícího portu mezipaměti; to však vytváří spor o prostředky portu s jinými načteními a úložišti v procesoru, který se pokouší provést, a tak může způsobit snížení výkonu. Alternativně lze přidat další port mezipaměti pouze pro rozložení zátěže, ale to zvyšuje složitost, sílu a oblast mezipaměti. Některé nedávné práce (Roth 2005) ukázaly způsoby, jak odfiltrovat mnoho zátěží před opětovným provedením, pokud je známo, že nemohlo dojít k žádnému narušení závislosti RAW; taková technika by pomohla nebo eliminovala takovou latenci a spory o zdroje.

Drobnou výhodou tohoto schématu (ve srovnání s vyhledáváním ve frontě zatížení) je to, že neoznačí narušení závislosti RAW a nespustí splachování potrubí pokud má obchod, který by způsobil narušení závislosti RAW (adresa obchodu odpovídá adrese načtení za letu), má hodnotu dat, která odpovídá hodnotě dat již v mezipaměti. Ve schématu hledání fronty zatížení by bylo nutné přidat další datové srovnání do hardwaru pro vyhledávání fronty zatížení, aby se zabránilo takovému vyprázdnění kanálu.

Vyhněte se porušení závislosti na RAW

CPU, které plně podporují provádění zátěží a úložišť mimo pořadí, musí být schopné detekovat narušení závislosti RAW, když k nim dojde. Mnoho procesorů se však tomuto problému vyhne vynucením všech načtení a uložení provést v pořadí nebo podporou pouze omezené formy provedení načtení / uložení mimo pořadí. Tento přístup nabízí nižší výkon ve srovnání s podporou plného spuštění / uložení out-of-order provedení, ale může výrazně snížit složitost jádra a mezipaměti provádění.

První možnost, která zajistí, že zatížení a úložiště přejdou do pořadí, se vyhne závislostem RAW, protože není možné, aby se zatížení provedlo před jeho výrobcem a získalo nesprávná data. Další možností je efektivně rozdělit zatížení a úložiště na dvě operace: generování adres a přístup do mezipaměti. S těmito dvěma samostatnými, ale propojenými operacemi může CPU umožnit nákladům a obchodům přístup k paměťovému systému pouze poté, co všechny předchozí zátěže a obchody mají svou adresu vygenerovanou a uloženou do vyrovnávací paměti v LSQ. Po vygenerování adresy již neexistují žádné nejednoznačné závislosti, protože jsou známy všechny adresy, a tak závislé načtení nebude provedeno, dokud nedojde k dokončení jejich odpovídajících úložišť. Toto schéma stále umožňuje určitou „nepřítomnost“ - operace generování adres pro jakékoli načítání a obchody za letu mohou být prováděny mimo pořadí a po vygenerování adres může přístup do mezipaměti pro každý náklad nebo úložiště stane se v jakémkoli pořadí, které respektuje (nyní známé) skutečné závislosti.

Další problémy

Predikce závislosti na paměti

Procesory, které plně podporují provedení načítání / ukládání mimo pořadí, mohou použít další související techniku, tzv predikce závislosti na paměti, pokusit se předpovědět skutečné závislosti mezi zatíženími a obchody před jejich adresy jsou známy. Použitím této techniky může procesor zabránit načtení, o nichž se předpokládá, že budou záviset na úložišti za letu, před provedením tohoto úložiště, čímž se vyhne narušení závislosti RAW a vyhne se tak vyplavení potrubí a penalizaci výkonu. Další informace najdete v článku predikce závislosti na paměti.

Viz také