Soudržnost mezipaměti - Cache coherence

Ilustrace zobrazující více mezipaměti určité paměti, která funguje jako sdílený prostředek
Nekoherentní mezipaměti: Mezipaměti mají různé hodnoty jednoho umístění adresy.

V architektuře počítače , vyrovnávací paměti soudržnosti je rovnoměrnost sdílených dat zdroje, které skončí uložené v několika místních cache . Když klienti v systému udržují mezipaměti prostředku společné paměti, mohou nastat problémy s nekoherentními daty, což je zejména případ CPU v systému s více procesy .

Na obrázku vpravo zvažte, že oba klienti mají kopii konkrétního bloku paměti uloženou v mezipaměti z předchozího čtení. Předpokládejme, že klient v dolní části aktualizuje / mění tento blok paměti, klientovi v horní části může být ponechána neplatná mezipaměť paměti bez jakéhokoli upozornění na změnu. Soudržnost mezipaměti je určena ke správě takových konfliktů udržováním soudržného pohledu na hodnoty dat ve více mezipaměti.

Koherentní mezipaměti: Hodnota ve všech kopiích mezipaměti je stejná.

Přehled

V multiprocesorovém systému se sdílenou pamětí se samostatnou mezipamětí pro každý procesor je možné mít mnoho kopií sdílených dat: jednu kopii v hlavní paměti a jednu v místní mezipaměti každého procesoru, který o to požádal. Když se změní jedna z kopií dat, ostatní kopie musí tuto změnu odrážet. Koherence mezipaměti je disciplína, která zajišťuje, že změny v hodnotách sdílených operandů (dat) jsou v systému šířeny včas.

Níže jsou uvedeny požadavky na soudržnost mezipaměti:

Napište Propagation
Změny dat v libovolné mezipaměti musí být šířeny do jiných kopií (daného řádku mezipaměti) v mezipaměti peer.
Serializace transakcí
Čtení / zápis do jednoho paměťového místa musí být viděny všemi procesory ve stejném pořadí.

Teoreticky lze koherenci provádět při granularitě zatížení / úložiště . V praxi se to však obvykle provádí s granularitou bloků mezipaměti.

Definice

Koherence definuje chování čtení a zápisů na jedno místo adresy.

Jeden typ dat vyskytujících se současně v různých mezipaměti se nazývá soudržnost mezipaměti nebo v některých systémech globální paměť.

V systému s více procesory zvažte, že více než jeden procesor uložil do mezipaměti kopii umístění paměti X. K dosažení soudržnosti mezipaměti jsou nutné následující podmínky:

  1. Při čtení provedeném procesorem P do místa X, které následuje po zápisu stejným procesorem P na X, aniž by mezi zápisem a instrukcemi pro čtení provedenými P nedocházelo k žádným zápisům na X jiným procesorem, musí X vždy vrátit hodnotu napsal P.
  2. Při čtení prováděném procesorem P1 do místa X, které následuje po zápisu jiným procesorem P2 až X, přičemž mezi těmito dvěma přístupy nedochází k žádným dalším zápisům do X prováděným jakýmkoli procesorem a při dostatečně odděleném čtení a zápisu musí X vždy vrací hodnotu zapsanou P2. Tato podmínka definuje koncept koherentního pohledu na paměť. Šíření zápisů do umístění sdílené paměti zajišťuje, že všechny mezipaměti mají ucelený pohled na paměť. Pokud procesor P1 načte starou hodnotu X, i po zápisu P2, můžeme říci, že paměť je nekoherentní.

Výše uvedené podmínky splňují kritéria pro šíření zápisu vyžadovaná pro koherenci mezipaměti. Jsou však nedostatečné, protože nesplňují podmínku serializace transakce. Chcete-li to lépe ilustrovat, zvažte následující příklad:

Systém s více procesory se skládá ze čtyř procesorů - P1, P2, P3 a P4, které všechny obsahují kopie sdílené proměnné S v mezipaměti, jejichž počáteční hodnota je 0. Procesor P1 změní hodnotu S (ve své kopii v mezipaměti) na 10 a poté procesor P2 změní hodnotu S ve své vlastní kopii v mezipaměti na 20. Pokud zajistíme pouze šíření zápisu, pak P3 a P4 jistě uvidí změny provedené v S P1 a P2. Nicméně, P3 mohou vidět změny provedené P1 poté, co viděl změny provedené P2 a tím i návrat 10 na čtení na S . P4 na druhé straně se může vidět změny provedené P1 a P2 v pořadí, ve kterém jsou vyrobeny, a tím vrátí 20 na čtení na S . Procesory P3 a P4 mají nyní nesouvislý pohled na paměť.

Z tohoto důvodu je nutné splnit následující podmínku spolu s předchozími dvěma zmíněnými v této části, aby bylo možné uspokojit serializaci transakcí, a dosáhnout tak soudržnosti mezipaměti:

  • Zápisy do stejného umístění musí být seřazeny. Jinými slovy, pokud místo X přijalo dvě různé hodnoty A a B, v tomto pořadí, od jakýchkoli dvou procesorů, procesory nikdy nemohou číst místo X jako B a poté jej číst jako A. Místo X musí být viděno s hodnotami A a B v tomto pořadí.

Alternativní definice koherentního systému je prostřednictvím definice modelu paměti sekvenční konzistence : „koherentní systém mezipaměti se musí objevit, aby provedl načtení všech vláken a ukládal je do jednoho paměťového místa v celkovém pořadí, které respektuje pořadí programu každého vlákna“ . Jediný rozdíl mezi koherentním systémem mezipaměti a sekvenčně konzistentním systémem je tedy v počtu adresních adres, o kterých definice hovoří (jedno paměťové místo pro koherentní systém mezipaměti a všechna paměťová místa pro sekvenčně konzistentní systém).

Další definice je: „multiprocesor je konzistentní s mezipamětí, pokud jsou všechny zápisy do stejného umístění paměti prováděny v určitém pořadí“.

Zřídka, ale zejména v algoritmech, může koherence místo toho odkazovat na referenční lokalitu . V různých mezipaměti může existovat více kopií stejných dat současně a pokud mohou procesory volně aktualizovat své vlastní kopie, může dojít k nekonzistentnímu zobrazení paměti.

Mechanismy soudržnosti

Hlavní článek: Cache coherency protocols (examples)

Dva nejběžnější mechanismy zajišťující soudržnost jsou snooping a adresář , každý z nich má své vlastní výhody a nevýhody. Protokoly založené na snoopingu bývají rychlejší, pokud je k dispozici dostatečná šířka pásma , protože všechny transakce jsou požadavkem / odpovědí viděnou všemi procesory. Nevýhodou je, že snooping není škálovatelný. Každý požadavek musí být vysílán na všechny uzly v systému, což znamená, že jak se systém zvětšuje, musí se zvětšovat velikost (logické nebo fyzické) sběrnice a šířka pásma, kterou poskytuje. Adresáře na druhou stranu mají tendenci mít delší latence (s požadavkem 3 směrování / předávání / odpovídání), ale používají mnohem menší šířku pásma, protože zprávy jsou point-to-point a nevysílají. Z tohoto důvodu mnoho větších systémů (> 64 procesorů) používá tento typ koherence mezipaměti.

Špehování

Hlavní článek: Bus snooping
Poprvé představen v roce 1983, snooping je proces, při kterém jednotlivé mezipaměti monitorují adresní řádky pro přístup do paměťových míst, která uložili do mezipaměti. K zápisu znehodnotit protokoly a write-update protokoly využít tohoto mechanismu.
Pro snoopingový mechanismus snoop filtr snižuje snoopingový provoz udržováním množství záznamů, z nichž každý představuje linku mezipaměti, kterou může vlastnit jeden nebo více uzlů. Je-li požadována náhrada jedné z položek, snoop filtr vybere pro náhradu položku představující linku mezipaměti nebo linky vlastněné nejmenším počtem uzlů, jak je určeno z vektoru přítomnosti v každé z položek. K upřesnění výběru se používá dočasný nebo jiný typ algoritmu, pokud má nejméně uzlů více než jeden řádek mezipaměti.

Na základě adresáře

Hlavní článek: Koherence mezipaměti založené na adresáři
V systému založeném na adresářích jsou sdílená data umístěna do společného adresáře, který udržuje soudržnost mezi mezipaměti. Adresář funguje jako filtr, jehož prostřednictvím si procesor musí vyžádat povolení k načtení záznamu z primární paměti do jeho mezipaměti. Když se položka změní, adresář buď aktualizuje, nebo zneplatní ostatní mezipaměti s touto položkou.

Systémy distribuované sdílené paměti napodobují tyto mechanismy ve snaze zachovat konzistenci mezi bloky paměti ve volně propojených systémech.

Soudržné protokoly

Koherenční protokoly používají koherenci mezipaměti v systémech s více procesory. Záměrem je, aby dva klienti nikdy neměli vidět různé hodnoty pro stejná sdílená data.

Protokol musí implementovat základní požadavky na soudržnost. Lze jej přizpůsobit cílovému systému nebo aplikaci.

Protokoly lze také klasifikovat jako snoopy nebo adresářové. Rané systémy obvykle používaly protokoly založené na adresářích, kde by adresář sledoval sdílená data a sdílené složky. V protokolech snoopy jsou požadavky na transakce (ke čtení, zápisu nebo upgradu) odeslány všem procesorům. Všichni zpracovatelé požadavek odposlouchávají a odpovídajícím způsobem reagují.

Šíření zápisu v snoopy protokolech lze implementovat některou z následujících metod:

Zapsat-zneplatnit
Když je operace zápisu pozorována do umístění, které má mezipaměť kopii, řadič mezipaměti zneplatní svou vlastní kopii snoopované paměti, což při dalším přístupu vynutí čtení z hlavní paměti nové hodnoty.
Aktualizace zápisu
Když je operace zápisu pozorována do umístění, které má mezipaměť kopii, řadič mezipaměti aktualizuje svou vlastní kopii snoopované paměti s novými daty.

Pokud návrh protokolu uvádí, že kdykoli se změní libovolná kopie sdílených dat, všechny ostatní kopie musí být „aktualizovány“, aby odrážely změnu, pak se jedná o protokol pro aktualizaci zápisu. Pokud návrh uvádí, že zápis do mezipaměti kopií jakýmkoli procesorem vyžaduje, aby ostatní procesory zahodily nebo zneplatnily své kopie v mezipaměti, pak se jedná o protokol neplatnosti zápisu.

Škálovatelnost je však jedním nedostatkem vysílacích protokolů.

Různé modely a protokoly byly navrženy pro zachování soudržnosti, jako je MSI , Mesi (aka Illinois), MOSI , Moesi , MERSI , MESIF , write-jednou , Synapse, Berkeley, Firefly a protokol Dragon . V roce 2011 společnost ARM Ltd navrhla AMBA 4 ACE pro řešení koherence v SoC . Specifikace rozhraní AMBA CHI (Coherent Hub Interface) od společnosti ARM Ltd , která patří do skupiny specifikací AMBA5, definuje rozhraní pro připojení plně koherentních procesorů.

Viz také

Reference

Další čtení