Soudržnost založená na adresářích - Directory-based coherence

Soudržnost založená na adresářích je mechanismus, který se má zpracovat Soudržnost mezipaměti problém v Distribuovaná sdílená paměť (DSM) aka Nestejnoměrný přístup do paměti (NUMA). Dalším populárním způsobem je použití speciálního typu počítače autobus mezi všemi uzly jako „sdílená sběrnice“ (a.k.a. Systémová sběrnice ).[1] Koherence založená na adresářích používá speciální adresář sloužit místo sdílené sběrnice v protokolech koherence založených na sběrnici. Oba tyto návrhy používají odpovídající médium (tj. Adresář nebo sběrnici) jako nástroj pro usnadnění komunikace mezi různými uzly a zaručit, že protokol soudržnosti funguje správně ve všech komunikujících uzlech. V koherenci mezipaměti založené na adresářích se to provádí pomocí tohoto adresáře ke sledování stavu všech mezipaměti bloky, stav každého bloku zahrnuje, v níž je soudržnost mezipaměti "Stát "tento blok je a které uzly tento blok v danou dobu sdílejí, což lze použít k eliminaci potřeby." přenos všechny signály do všech uzlů a odesílat je pouze do uzlů, které se zajímají o tento jeden blok.

Následuje několik výhod a nevýhod protokolu koherence protokolu založeného na adresáři:

  • Škálovatelnost: Toto je jedna z nejsilnějších motivací pro přechod k návrhům založeným na adresářích. Co tím myslíme škálovatelnost zkrátka je to, jak dobrý je konkrétní systém při zvládání rostoucího množství práce, za kterou je odpovědný. Z tohoto kritéria nemohou systémy založené na sběrnici dobře fungovat kvůli omezení způsobenému při sdílení sběrnice, kterou používají všechny uzly současně. Pro relativně malý počet uzlů mohou systémy sběrnice fungovat dobře. Zatímco počet uzlů roste, mohou v tomto ohledu nastat určité problémy. Zejména proto, že pouze jeden uzel smí používat sběrnici současně, což výrazně poškodí výkon celého systému. Na druhou stranu, pomocí systémů založených na adresářích nebude existovat takové úzké místo, které by omezovalo škálovatelnost systému.
  • Jednoduchost: Toto je jeden z bodů, kde je sběrnicový systém nadřazený. Vzhledem k tomu, že samotná struktura sběrnice může sloužit jako organizátor pro veškerý provoz, který prochází systémem, a zajistit atomicita všech procházejících signálů. Nebude tedy nutné vynakládat větší úsilí na zajištění atomicity a řazení mezi signály, jako je tomu v případě systémů založených na adresářích, což vede k několika režiím, kterým čelí pozdější návrh systému při řešení problémů, jako je konzistence.

Podle výše uvedené diskuse je jasné, že používání systémů založených na sběrnici se zdá být atraktivnější pro relativně malé systémy. Systémy založené na adresářích se však stávají zásadními, když se systém zvětší a počet uzlů roste. Existuje tedy něco jako kompromis mezi jednoduchostí a škálovatelností při porovnávání návrhů koherence mezipaměti založené na sběrnici a adresáři.[1]

Dějiny

Myšlenka adresářových systémů soudržnosti mezipaměti začala už dávno. Myšlenka POMLČKA (Dkazatelna Architecture pro SHared-memory) poprvé navrhl C.K. Tang[2] v polovině 70. let. Jeho použití na soudržnost mezipaměti však bylo navrženo o několik let později, konkrétně v roce 1978, kdy vědci v Stanfordská Univerzita navrhl první verzi tohoto koherenčního systému s názvem Stanford DASH, v novinách[3] který popsal systém s obtížemi a vylepšeními spojenými s takovými návrhy. Kromě tohoto přístupu bylo učiněno několik pokusů o poskytnutí škálovatelných systémů. Například, BBN Butterfly[4] který byl představen v roce 1985, a IBM PR3[5] který byl představen v roce 1987, je několik příkladů škálovatelného víceprocesorové systémy. Oba tyto systémy však mají nevýhodu; Například BBN Butterfly nemá mezipaměti. Podobně IBM PR3 neposkytuje koherenci hardwarové mezipaměti, což omezuje výkon obou těchto návrhů, zejména při použití vysoce výkonných procesorů.[6]

Omezení jiných konkurentů usnadnila systémům založeným na DASH výběr při návrhu systémů koherence mezipaměti a dalších systémů vyžadujících škálovatelnost v uzlech založených na mezipaměti. V roce 1985 James Archibald[7] a Jean-Loup Baer z University of Washington zveřejnil příspěvek[8] která navrhuje ekonomičtější, rozšiřitelnější a modulární variantu přístupu „globálního adresáře“, pokud jde o použití hardwaru v návrhu.

V roce 1992 Daniel Lenoski ze Stanfordské univerzity publikoval příspěvek[9] navrhuje pokrok v protokolech koherence mezipaměti pro adresářové systémy. V článku z roku 1996[10] představil design SGI Origin 2000, skupina serverových počítačů využívajících soudržnost mezipaměti na základě adresářů. Následné Původ 3000[11] byl představen v červenci 2000.

Protokoly

Na rozdíl od snoopy koherenční protokoly, v koherenčním přístupu založeném na adresářích se informace o tom, které mezipaměti mají kopii bloku, udržují ve struktuře zvané Adresář. V schématu založeném na adresářích zúčastněné mezipaměti nevysílají požadavky na všechny ostatní sdílené mezipaměti bloku za účelem vyhledání kopií v mezipaměti, místo toho dotazují adresář a načtou informace o tom, který blok má kopie v mezipaměti, a odešle pouze těmto konkrétním procesorům tedy úspora provozu ve srovnání s protokolem snoopy je velká. V dobře optimalizovaných aplikacích je většina sdílení dat pouze pro data, která jsou pouze pro čtení, a pro data, která jsou často čtena a zapisována, existuje jen malé sdílení. Adresářový přístup může mít za následek podstatnou úsporu provozu ve srovnání s přístupem broadcast / snoopy v takových aplikacích.

[12] Schéma přehledu schémat koherence založené na adresáři zobrazující různé aktéry a zprávy.

Jak je znázorněno v diagramu toku dat, aktéři zapojení do systému distribuované sdílené paměti implementujícího koherenční protokol založený na adresáři jsou:

  • Uzel žadatele : Tento uzel je procesor, který požaduje čtení / zápis paměťového bloku.
  • Uzel adresáře : Tento uzel udržuje informace o stavu každého bloku mezipaměti v systému a žadatel směruje své požadavky na uzel adresáře.
  • Uzel vlastníka: Uzel vlastníka vlastní nejnovější stav bloku mezipaměti. Všimněte si, že adresář nemusí být vždy aktuální s nejnovějšími daty.
  • Sharer Node: Jeden nebo více uzlů, které sdílejí kopii bloku mezipaměti.
Obrázek 1: Schéma přechodu stavu pro adresářový protokol

Uzly žadatele a vlastníka udržují svůj přechod stavu podobně jako protokoly koherence snoopy jako Protokol MESI. Na rozdíl od implementace založené na sběrnici, kde uzly komunikují pomocí společné sběrnice, používá implementace založená na adresářích předávání zpráv model pro výměnu informací potřebných pro údržbu soudržnost mezipaměti.

Uzel adresáře funguje jako serializační bod a veškerá komunikace je přes tento uzel směrována, aby byla zachována správnost.

Uzel adresáře

Uzel adresáře sleduje celkový stav bloku mezipaměti v celém systému mezipaměti pro všechny procesory. Může to být ve třech stavech:

  • Bez mezipaměti (U): Žádný procesor nemá data uložená v mezipaměti, paměť je aktuální.
  • Sdílené (S): jeden nebo více procesorů má data v mezipaměti, aktuální paměť. V tomto stavu mají adresář a sdílející uživatelé čistou kopii bloku uloženého v mezipaměti.
  • Exkluzivní / upravené (EM): jeden procesor (vlastník) má data v mezipaměti; paměť zastaralá. Všimněte si, že adresář nedokáže rozlišit blok uložený v mezipaměti ve výhradním nebo upraveném stavu u procesoru, protože procesory mohou přecházet z exkluzivního stavu do upraveného stavu bez jakékoli transakce sběrnice.

Vysvětlení přechodu stavu adresáře Konečný státní stroj (viz obrázek 1) je zachycen níže v tabulce:

Počáteční stavŽádost o autobusReakce / akceNový stát
UBusRd nebo

BusRdX

  • Načíst blok z paměti, protože adresář má aktualizovanou kopii bloku.
  • poslat blok paměti žadateli pomocí zprávy (ReplyD).
  • pokud neexistují žádní sdílející uživatelé: žadatel = první sdílející, adresář přechází do stavu EM.
EM
EMBusRd
  • Odeslat zásah (Int) majiteli
S
BusRdX
  • Odeslat zneplatnění (Inv) aktuálnímu majiteli.
-
SBusRd
  • Odpovězte žadateli pomocí paměťového bloku (ReplyD)
-
BusRdX
  • Odpovězte žadateli pomocí paměťového bloku (ReplyD)
  • Zneplatnit (Inv) všichni sdílející.
EM
BusUpgr
  • Zneplatnit (Inv) všichni sdílející.
  • Odpovězte žadateli, že může upgradovat. (Odpověď)
EM

Kromě stavu mezipaměti musí adresář sledovat, které procesory mají data, když jsou ve sdíleném stavu. To je vyžadováno pro odesílání požadavků na zneplatnění a zásah do jednotlivých mezipamětí procesoru, které mají blok mezipaměti ve sdíleném stavu. Několik populárních implementačních přístupů je:

  • Plný bitový vektor: Bitové pole pro každý procesor v uzlu adresáře je zachováno. Režijní náklady úložiště se zvyšují podle počtu procesorů.
  • Omezený ukazatel: V tomto přístupu se informace o adresáři omezeného počtu bloků uchovávají v adresáři, aby se snížila režie úložiště.

Vezměte prosím na vědomí, že výše popsaný protokol je základní implementací a podmínky závodu může nastat kvůli skutečnosti, že adresář může být synchronizován s mezipaměti a také zprávy mezi procesory se mohou překrývat. Složitější implementace jsou k dispozici jako Škálovatelné koherentní rozhraní které mají více stavů.

POMLČKA[3] cache coherence protocol je další protokol, který používá koherenční schéma založené na adresářích. Protokol DASH používá klastrovaný přístup, kde jsou procesory uvnitř klastru udržovány koherentní pomocí snoopingového schématu založeného na sběrnici, zatímco klastry jsou připojeny v adresářovém přístupu. I když různé protokoly používají pro sledování bloků mezipaměti různé implementace, koncept adresáře zůstává stejný.

Viz také

Reference

  1. ^ A b Solihin, Yan (2009). Základy paralelní počítačové architektury. 319–360.
  2. ^ Tang, C.K. Msgstr "Návrh systému mezipaměti v těsně propojeném víceprocesorovém systému". AFIPS '76 Proceedings of the June 7–10 June, 1976, National Computer Conference and Exposition.
  3. ^ A b „Protokol soudržnosti mezipaměti založený na adresáři pro multiprocesor DASH“ (PDF). Laboratoř počítačových systémů.
  4. ^ Schmidt, G.E. "Motýlí paralelní procesor". V Proc. ICS.
  5. ^ "Prototyp výzkumu IBM PR3 PR3: Úvod a architektura". Na zasedání mezinárodní konference o paralelním zpracování v roce 1985.
  6. ^ „Návrh škálovatelných multiprocesorů se sdílenou pamětí: přístup DASH“. Laboratoř počítačových systémů, Stanford University.
  7. ^ „James Archibald“. ece.byu.edu. Citováno 2016-11-15.
  8. ^ "Ekonomické řešení problému s koherencí mezipaměti". ISCA '84 Proceedings of the 11th Annual International Symposium on Computer Architecture.
  9. ^ Lenoski, Daniel; Laudon, James; Gharachorloo, Kourosh; Weber, Wolf-Dietrich; Gupta, Anoop; Hennessy, John; Horowitz, Mark; Lam, Monica S. (01.03.1992). "Stanford Dash Multiprocesor". Počítač. 25 (3): 63–79. doi:10.1109/2.121510. ISSN  0018-9162.
  10. ^ Laudon, James; Lenoski, Daniel (01.01.1997). Původ SGI: Vysoce škálovatelný server ccNUMA. Sborník 24. mezinárodního sympozia o počítačové architektuře. ISCA '97. New York, NY, USA: ACM. str. 241–251. doi:10.1145/264107.264206. ISBN  978-0897919012.
  11. ^ Corp., Silicon Graphics International. „Domovská stránka podpory“. support1-sgi.custhelp.com. Citováno 2016-11-16.
  12. ^ Solihin, Yan (2009). Základy paralelní vícejádrové architektury. 319–361.