Katalogbaserad koherens
Katalogbaserad koherens är en mekanism för att hantera problem med cachekoherens i distribuerat delat minne (DSM) aka Non-Uniform Memory Access (NUMA). Ett annat populärt sätt är att använda en speciell typ av datorbuss mellan alla noder som en "delad buss" (alias Systembus ). Katalogbaserad koherens använder en speciell katalog för att tjäna istället för den delade bussen i de bussbaserade koherensprotokollen. Båda dessa konstruktioner använder motsvarande medium (dvs katalog eller buss) som ett verktyg för att underlätta kommunikationen mellan olika noder , och för att garantera att koherensprotokollet fungerar korrekt längs alla kommunicerande noder. I katalogbaserad cachekoherens görs detta genom att använda denna katalog för att hålla reda på statusen för alla cacheblock , statusen för varje block inkluderar i vilket cachekoherens " tillstånd " det blocket är och vilka noder som delar det blocket vid det tid, vilket kan användas för att eliminera behovet av att sända alla signaler till alla noder, och bara skicka den till de noder som är intresserade av detta enda block.
Följande är några fördelar och nackdelar med det katalogbaserade cache-koherensprotokollet:
- Skalbarhet : Detta är en av de starkaste motiven för att gå till katalogbaserad design. Vad vi menar med skalbarhet , kort sagt, är hur bra ett specifikt system är för att hantera den växande mängden arbete som det är ansvarigt att göra. För detta kriterium kan bussbaserade system inte klara sig bra på grund av begränsningen som orsakas av att ha en delad buss som alla noder använder samtidigt. För ett relativt litet antal noder kan bussystem klara sig bra. Men medan antalet noder växer kan vissa problem uppstå i detta avseende. Speciellt eftersom endast en nod får använda bussen åt gången, vilket avsevärt kommer att skada det övergripande systemets prestanda. Å andra sidan, med katalogbaserade system, kommer det inte att finnas någon sådan flaskhals som begränsar systemets skalbarhet.
- Enkelhet : Detta är en av punkterna där bussystemet är överlägset. Eftersom själva bussstrukturen kan fungera som en arrangör för all trafik som går genom systemet, och säkerställa atomiciteten för alla signaler som passerar igenom. Således kommer det inte att behövas mer ansträngning för att säkerställa atomicitet och ordning mellan signaler som är fallet i katalogbaserade system, vilket leder till flera overhead i den senare systemdesignen när man hanterar frågor som konsistens .
Enligt diskussionen ovan är det tydligt att användning av bussbaserade system verkar mer attraktivt för relativt små system. Katalogbaserade system blir dock avgörande när systemet skalas upp och antalet noder växer. Så det finns en sorts avvägning mellan enkelheten och skalbarheten när man jämför mellan bussbaserade och katalogbaserade cachekoherensdesigner.
Historia
Idén med katalogbaserade cachekoherenssystem började för länge sedan. Idén med DASH ( D irectory A rchitecture for SH ared-minne) föreslogs först av CK Tang i mitten av 1970-talet. Men att tillämpa det på cachekoherens föreslogs några år senare, särskilt 1978, när forskare vid Stanford University föreslog den första versionen av detta koherenssystem kallat Stanford DASH , i en artikel som beskrev systemet med de svårigheter och förbättringar som är förknippade med sådana mönster. Utöver detta tillvägagångssätt gjordes flera försök att tillhandahålla ett skalbart system. Till exempel BBN Butterfly som introducerades 1985, och IBM PR3 som introducerades 1987, några exempel på skalbara flerprocessorsystem . Båda dessa system har dock en nackdel; Till exempel har BBN Butterfly inga cacher. På samma sätt tillhandahåller IBM PR3 inte koherens i hårdvarucache, vilket begränsar prestandan för båda dessa konstruktioner, särskilt när man använder högpresterande processorer.
Andra konkurrenters begränsningar gjorde det lättare för DASH-baserade system att väljas ut när man designade cachekoherenssystem och andra system som behöver skalbarhet i cache-baserade noder. 1985 publicerade James Archibald och Jean-Loup Baer från University of Washington en artikel som föreslår en mer ekonomisk, utbyggbar och modulär variant av den "globala katalogen"-metoden när det gäller hårdvaruanvändning i designen.
1992 publicerade Daniel Lenoski från Stanford University en artikel som föreslog framsteg inom cachekoherensprotokoll för katalogbaserade system. I en artikel från 1996 introducerade han designen av SGI Origin 2000 , en familj av serverdatorer som använder katalogbaserad cachekoherens. Den efterföljande Origin 3000 introducerades i juli 2000.
Protokoll
Till skillnad från snoopy koherensprotokoll, i en katalogbaserad koherensmetod, upprätthålls informationen om vilka cacher som har en kopia av ett block i en struktur som kallas Directory . I ett katalogbaserat schema sänder deltagande cachar inte förfrågningar till alla andra delade cachar i blocket för att lokalisera cachade kopior, istället frågar den katalogen för att hämta informationen om vilket block som har cachade kopior och skickar endast till de specifika processorerna och därför är trafikbesparingen stor jämfört med ett snoopy-protokoll. I väl optimerade applikationer är de flesta datadelningar endast för data som är skrivskyddade, och det finns lite delning för data som ofta läses och skrivs. En katalogstrategi kan resultera i en avsevärd trafikbesparing jämfört med broadcast/snoopy-metoden i sådana applikationer.
Som visas i dataflödesdiagrammet är de aktörer som är involverade i ett distribuerat delat minnessystem som implementerar katalogbaserat koherensprotokoll:
- Requestor Node : Denna nod är processorn som begär en läsning/skrivning av ett minnesblock.
- Katalognod : Denna nod upprätthåller informationen om tillståndet för varje cacheblock i systemet och begäranden riktar sina förfrågningar till katalognoden.
- Ägarnod: En ägarnod äger det senaste tillståndet för cacheblocket, observera att katalogen kanske inte alltid är uppdaterad med senaste data.
- Delningsnod : En eller flera noder som delar en kopia av cacheblocket.
Begäran- och ägarnoder bibehåller sin tillståndsövergång som liknar ett snoopy koherensprotokoll som MESI-protokollet . Men till skillnad från en bussbaserad implementering där noder kommunicerar med en gemensam buss, använder katalogbaserad implementering en modell för meddelandeöverföring för att utbyta information som krävs för att upprätthålla cachekoherens .
Katalognoden fungerar som en serialiseringspunkt och all kommunikation dirigeras genom denna nod för att bibehålla korrektheten.
Katalognod
En katalognod håller reda på det övergripande tillståndet för ett cacheblock i hela cachesystemet för alla processorer. Det kan vara i tre tillstånd:
- Uncachad (U): Ingen processor har cachad data, minnet uppdaterat .
- Delad (S) : en eller flera processorer har cachad data, minnet uppdaterat. I detta tillstånd har katalogen och delarna en ren kopia av det cachade blocket.
- Exklusiv/Modifierad (EM): en processor (ägare) har cachad data; minne inaktuellt. Notera att katalogen inte kan särskilja ett block cachat i ett exklusivt eller modifierat tillstånd vid processorn eftersom processorer kan övergå från ett exklusivt tillstånd till modifierat tillstånd utan någon busstransaktion.
Förklaring av katalogtillståndsövergången Finite State Machine (se bild 1) finns nedan i tabellen:
| Initialtillstånd | Bussförfrågan | Svar/ Åtgärd | Ny stat |
|---|---|---|---|
| U |
BusRd eller BusRdX |
|
EM |
| EM | BusRd |
|
S |
| BusRdX |
|
- | |
| S | BusRd |
|
- |
| BusRdX |
|
EM | |
| BusUpgr |
|
EM |
Förutom cache-tillstånd måste en katalog spåra vilka processorer som har data när de är i delat tillstånd. Detta krävs för att sända begäran om ogiltigförklaring och ingripande till de individuella processorcachen som har cacheblocket i delat tillstånd. Några av de populära implementeringsmetoderna är:
- Full bit-vektor : Ett bitfält för varje processor vid katalognoden bibehålls. Lagringsoverheaden skalas med antalet processorer.
- Begränsad pekare: I detta tillvägagångssätt hålls kataloginformation med ett begränsat antal block i katalogen för att minska lagringskostnader.
Observera att protokollet som beskrivs ovan är den grundläggande implementeringen och tävlingsförhållanden kan uppstå på grund av att katalogen kan vara osynkroniserad med cacharna och även meddelanden mellan processorer kan överlappa. Mer komplexa implementeringar finns tillgängliga som Scalable Coherent Interface som har flera tillstånd.
DASH-cachekoherensprotokoll är ett annat protokoll som använder katalogbaserat koherensschema. DASH-protokollet använder ett klustrade tillvägagångssätt, där processorer inuti ett kluster hålls sammanhängande med hjälp av busbaserat snoopingschema, medan klustren är anslutna i en katalogmetod. Även om olika protokoll använder olika implementeringar för att spåra cacheblock, förblir konceptet med katalogen detsamma.