MESI-protokoll
MESI -protokollet är ett Invalidate-baserat cachekoherensprotokoll och är ett av de vanligaste protokollen som stöder återskrivningscacher . Det är också känt som Illinois-protokollet (på grund av dess utveckling vid University of Illinois i Urbana-Champaign ). Skriv tillbaka cache kan spara mycket bandbredd som vanligtvis slösas bort på en genomskrivningscache . Det finns alltid ett smutsigt tillstånd i återskrivningscachen som indikerar att data i cachen skiljer sig från den i huvudminnet. Illinois-protokollet kräver en cache för att cache-överföring vid en miss om blocket finns i en annan cache. Detta protokoll minskar antalet huvudminnestransaktioner i förhållande till MSI-protokollet . Detta markerar en betydande förbättring av prestanda.
stater
Bokstäverna i akronymen MESI representerar fyra exklusiva tillstånd som en cache-rad kan markeras med (kodad med två extra bitar ):
- Modifierad (M)
- Cacheminnet finns endast i den aktuella cachen och är smutsig - den har modifierats (M-tillstånd) från värdet i huvudminnet . Cachen krävs för att skriva tillbaka data till huvudminnet någon gång i framtiden, innan man tillåter någon annan läsning av huvudminnets (ej längre giltiga) tillstånd. Återskrivningen ändrar raden till delat tillstånd(S).
- Exklusiv (E)
- Cacheminnet finns bara i den aktuella cachen, men är ren - den matchar huvudminnet. Den kan när som helst ändras till delad status som svar på en läsbegäran. Alternativt kan den ändras till modifierad status när du skriver till den.
- Delad (S)
- Indikerar att denna cache-rad kan lagras i andra cachar på maskinen och är ren - den matchar huvudminnet. Linjen kan kasseras (ändras till Invalid state) när som helst.
- Ogiltig (I)
- Indikerar att denna cache-rad är ogiltig (oanvänd).
För ett givet par cacher är de tillåtna tillstånden för en given cache-linje följande:
| M | E | S | jag | |
|---|---|---|---|---|
| M |
|
|
|
|
| E |
|
|
|
|
| S |
|
|
|
|
| jag |
|
|
|
|
När blocket är markerat med M (modifierat) eller E (exklusivt), markeras kopiorna av blocket i andra cacher som I (Ogiltigt).
Drift
MESI-protokollet definieras av en maskin med ändligt tillstånd som övergår från ett tillstånd till ett annat baserat på 2 stimuli.
Den första stimulansen är den processorspecifika läs- och skrivbegäran. Till exempel: En processor P1 har ett Block X i sin cache, och det finns en begäran från processorn att läsa eller skriva från det blocket.
Den andra stimulansen ges genom bussen som förbinder processorerna. I synnerhet kommer "Busside-förfrågningarna" från andra processorer som inte har cacheblocket eller uppdaterade data i sin cache. Bussförfrågningarna övervakas med hjälp av Snoopers , som övervakar alla busstransaktioner.
Följande är de olika typerna av processorförfrågningar och förfrågningar på busssidan:
Processorbegäranden till cache inkluderar följande operationer:
- PrRd: Processorn begär att läsa ett cacheblock.
- PrWr: Processorn begär att skriva ett cacheblock
Förfrågningar på busssidan är följande:
- BusRd: Snoopad begäran som indikerar att det finns en läsbegäran till ett cacheblock som begärts av en annan processor
- BusRdX: Snoopad begäran som indikerar att det finns en skrivbegäran till ett cacheblock som begärts av en annan processor som inte redan har blocket.
- BusUpgr: Snoopad begäran som indikerar att det finns en skrivbegäran till ett cacheblock som begärts av en annan processor som redan har det cacheblocket i sin egen cache .
- Flush: Snoopad begäran som indikerar att ett helt cacheblock skrivs tillbaka till huvudminnet av en annan processor.
- FlushOpt: Snoopad begäran som indikerar att ett helt cacheblock är placerat på bussen för att förse det till en annan processor (cache-till-cache-överföringar).
( Sådana cache-till-cache-överföringar kan minska läsmiss- latensen om latensen för att ta blocket från huvudminnet är mer än från cache- till cache-överföringar, vilket generellt är fallet i busbaserade system. Men i flerkärniga arkitekturer, där koherensen hålls på nivån för L2-cache, det finns en L3-cache på chipet, kan det vara snabbare att hämta det missade blocket från L3-cachen snarare än från en annan L2 )
Snoopoperation : I ett snoopingsystem övervakar alla cachar på en buss alla transaktioner på den bussen. Varje cache har en kopia av delningsstatusen för varje block av fysiskt minne som den har lagrat. Blockets tillstånd ändras enligt tillståndsdiagrammet för det använda protokollet. (Se bilden ovan för MESI-tillståndsdiagram). Bussen har snokare på båda sidor:
- Snooper mot processor/cache-sidan.
- Snokningsfunktionen på minnessidan görs av Memory Controller.
Förklaring:
Varje cacheblock har sin egen 4-tillståndsmaskin ( se bild 1.1). Tillståndsövergångarna och svaren vid ett visst tillstånd med avseende på olika indata visas i Tabell 1.1 och Tabell 1.2
| Initialtillstånd | Drift | Svar |
|---|---|---|
| Ogiltig (I) | PrRd |
|
| PrWr |
|
|
| Exklusiv(E) | PrRd |
|
| PrWr |
|
|
| Delad(S) | PrRd |
|
| PrWr |
|
|
| Ändrad (M) | PrRd |
|
| PrWr |
|
| Initialtillstånd | Drift | Svar |
|---|---|---|
| Ogiltig (I) | BusRd |
|
| BusRdX/BusUpgr |
|
|
| Exklusiv(E) | BusRd |
|
| BusRdX |
|
|
| Delad(S) | BusRd |
|
| BusRdX/BusUpgr |
|
|
| Ändrad (M) | BusRd |
|
| BusRdX |
|
En skrivning får endast utföras fritt om cacheraden är i Modifierat eller Exklusivt tillstånd. Om den är i läget Delat måste alla andra cachade kopior ogiltigförklaras först. Detta görs vanligtvis genom en sändningsoperation som kallas Request For Ownership (RFO) .
En cache som håller en rad i modifierat tillstånd måste snoop (fånga upp) alla försök till läsning (från alla andra cachar i systemet) av motsvarande huvudminnesplats och infoga data som den innehåller. Detta kan göras genom att tvinga läsningen att backa (dvs. försök igen senare), sedan skriva data till huvudminnet och ändra cache-raden till delat tillstånd. Det kan också göras genom att skicka data från Modifierad cache till cachen som utför läsningen. Notera, snooping krävs endast för läsmissar (protokollet säkerställer att Modified inte kan existera om någon annan cache kan utföra en lästräff).
En cache som har en linje i delat tillstånd måste lyssna efter ogiltiga eller begärande om äganderättssändningar från andra cachar och kassera linjen (genom att flytta den till Ogiltigt läge) på en match.
De Modifierade och Exklusiva tillstånden är alltid exakta: dvs de matchar den verkliga situationen för cache-linjeägande i systemet. Det delade tillståndet kan vara oprecist: om en annan cache kasserar en delad rad, kan denna cache bli ensam ägare till den cacheraden, men den kommer inte att flyttas upp till Exklusivt tillstånd. Andra cachar sänder inte meddelanden när de kasserar cache-rader, och denna cache kunde inte använda sådana meddelanden utan att upprätthålla en räkning av antalet delade kopior.
I den meningen är det exklusiva tillståndet en opportunistisk optimering: Om CPU:n vill modifiera en cache-linje i tillstånd S, är en busstransaktion nödvändig för att ogiltigförklara alla andra cachade kopior. Tillstånd E möjliggör modifiering av en cache-linje utan busstransaktion.
Illustration av MESI-protokolloperationer
Låt oss anta att följande ström av läs/skrivreferenser. Alla referenser är till samma plats och siffran refererar till processorn som utfärdar referensen.
Strömmen är: R1, W1, R3, W3, R1, R3, R2.
Initialt antas det att alla cacher är tomma.
| Lokal förfrågan | P1 | P2 | P3 |
Genererad
Bussförfrågan |
Dataleverantör | |
|---|---|---|---|---|---|---|
| 0 | Initialt | - | - | - | - | - |
| 1 | R1 | E | - | - | BusRd | Mem |
| 2 | W1 | M | - | - | - | - |
| 3 | R3 | S | - | S | BusRd | P1:s cache |
| 4 | W3 | jag | - | M | BusUpgr | - |
| 5 | R1 | S | - | S | BusRd | P3:s cache |
| 6 | R3 | S | - | S | - | - |
| 7 | R2 | S | S | S | BusRd | P1/P3:s cache |
Obs: Termen snooping som hänvisas till nedan är ett protokoll för att upprätthålla cachekoherens i symmetriska multibearbetningsmiljöer. Alla cachar på bussen övervakar (snoopar) bussen om de har en kopia av datablocket som efterfrågas på bussen.
- Steg 1: Eftersom cachen initialt är tom, så förser huvudminnet P1 med blocket och det blir exklusivt tillstånd.
- Steg 2: Eftersom blocket redan finns i cachen och i ett exklusivt tillstånd så ändras det direkt utan någon bussinstruktion. Blocket är nu i ett modifierat tillstånd.
- Steg 3: I detta steg läggs en BusRd upp på bussen och snokaren på P1 känner av detta. Den rensar sedan data och ändrar dess tillstånd till delad. Blocket på P3 ändrar också sitt tillstånd till delat eftersom det har tagit emot data från en annan cache. Data skrivs också tillbaka till huvudminnet.
- Steg 4: Här postas en BusUpgr på bussen och snokaren på P1 känner av detta och ogiltigförklarar blocket eftersom det kommer att modifieras av en annan cache. P3 ändrar sedan sitt blocktillstånd till modifierat.
- Steg 5: Eftersom det aktuella tillståndet är ogiltigt, kommer det att lägga upp en BusRd på bussen. Snokaren på P3 kommer att känna av detta och kommer därför att spola ut data. Tillståndet för båda blocken på P1 och P3 kommer att delas nu. Observera att det är då även huvudminnet kommer att uppdateras med tidigare modifierade data.
- Steg 6: Det finns en träff i cachen och den är i delat tillstånd så ingen bussförfrågan görs här.
- Steg 7: Det finns cachemiss på P2 och en BusRd läggs upp. Snokaren på P1 och P3 känner av detta och båda kommer att försöka en spolning. Den som får tillgång till bussen först kommer att göra den operationen.
Läs för ägande
A Read For Ownership (RFO) är en operation i cache-koherensprotokoll som kombinerar en läsning och en ogiltig sändning. Operationen utfärdas av en processor som försöker skriva in i en cache-rad som är i delade (S) eller ogiltiga (I) tillstånden för MESI-protokollet. Operationen får alla andra cachar att ställa in tillståndet för en sådan rad till I. En läs för ägandetransaktion är en läsoperation med avsikt att skriva till den minnesadressen. Därför är denna operation exklusiv. Den för data till cachen och ogiltigförklarar alla andra processorcacher som innehåller denna minneslinje. Detta kallas "BusRdX" i tabellerna ovan.
Minnesbarriärer
MESI i sin naiva, enkla implementering uppvisar två speciella prestandaproblem. För det första, när man skriver till en ogiltig cache-rad, blir det en lång fördröjning medan raden hämtas från andra CPU:er. För det andra är det tidskrävande att flytta cache-rader till det ogiltiga tillståndet. För att mildra dessa förseningar implementerar CPU:er butiksbuffertar och ogiltigförklarar köer.
Butiksbuffert
En lagringsbuffert används när man skriver till en ogiltig cache-rad. Eftersom skrivningen kommer att fortsätta hur som helst, utfärdar CPU:n ett läs-ogiltigt meddelande (därav den aktuella cacheraden och alla andra CPU:ers cache-rader som lagrar den minnesadressen är ogiltiga) och skjuter sedan in skrivningen i lagringsbufferten för att exekveras när cacheraden äntligen kommer till cachen.
En direkt konsekvens av lagringsbuffertens existens är att när en CPU begår en skrivning, skrivs den skrivningen inte omedelbart i cachen. Därför, närhelst en CPU behöver läsa en cache-rad, skannar den först sin egen lagringsbuffert efter existensen av samma rad, eftersom det finns en möjlighet att samma rad skrevs av samma CPU tidigare men ännu inte har skrivits i cachen (föregående skrivning väntar fortfarande i lagringsbufferten). Observera att medan en CPU kan läsa sina egna tidigare skrivningar i sin lagringsbuffert, kan andra processorer inte se dessa skrivningar förrän de tömts till cachen - en CPU kan inte skanna lagringsbufferten för andra processorer.
Ogiltigförklara köer
När det gäller ogiltiga meddelanden implementerar CPU:er ogiltiga köer, varigenom inkommande ogiltigförfrågningar omedelbart bekräftas men inte omedelbart åtgärdas. Istället går ogiltighetsmeddelanden helt enkelt in i en ogiltighetskö och deras bearbetning sker så snart som möjligt (men inte nödvändigtvis omedelbart). Följaktligen kan en CPU vara omedveten om det faktum att en cache-rad i dess cache faktiskt är ogiltig, eftersom ogiltigförklaringskön innehåller ogiltigheter som har tagits emot men som ännu inte har tillämpats. Observera att, till skillnad från butiksbufferten, kan CPU:n inte skanna ogiltigförklaringskön, eftersom den CPU och ogiltigförklaringskön är fysiskt placerade på motsatta sidor av cachen.
Som ett resultat krävs minnesbarriärer. En lagringsbarriär kommer att spola lagringsbufferten, vilket säkerställer att alla skrivningar har applicerats på den CPU:ns cache. En läsbarriär kommer att tömma ogiltigförklaringskön, vilket säkerställer att alla skrivningar från andra CPU:er blir synliga för den spolande CPU:n. Dessutom skannar inte minneshanteringsenheter lagringsbufferten, vilket orsakar liknande problem. Denna effekt är synlig även i enkelgängade processorer.
Fördelar med MESI framför MSI
Den mest slående skillnaden mellan MESI och MSI är det extra "exklusiva" tillståndet som finns i MESI-protokollet. Detta extra tillstånd lades till eftersom det har många fördelar. När en processor behöver läsa ett block som ingen av de andra processorerna har och sedan skriva till det, kommer två busstransaktioner att ske i fallet med MSI. Först utfärdas en BusRd-begäran för att läsa blocket följt av en BusRdX-begäran innan man skriver till blocket. BusRdX-begäran i detta scenario är värdelös eftersom ingen av de andra cacharna har samma block, men det finns inget sätt för en cache att veta om detta. Således övervinner MESI-protokollet denna begränsning genom att lägga till ett Exklusivt tillstånd, vilket resulterar i att en bussförfrågan sparas. Detta gör en enorm skillnad när en sekventiell applikation körs. Eftersom endast en processor arbetar på en bit data kommer alla åtkomster att vara exklusiva. MSI presterar mycket sämre i det här fallet på grund av de extra bussmeddelandena. Även i fallet med en mycket parallell applikation med minimal delning av data är MESI mycket snabbare. Att lägga till det exklusiva tillståndet är också utan kostnad eftersom 3 tillstånd och 4 tillstånd båda kan representeras med 2 bitar.
Nackdel med MESI
Om kontinuerliga läs- och skrivoperationer utförs av olika cacher på ett visst block, måste data spolas till bussen varje gång. Således kommer huvudminnet att dra detta vid varje spolning och förbli i ett rent tillstånd. Men detta är inte ett krav och är bara en extra omkostnad som orsakas av att använda MESI. Denna utmaning övervanns av MOESI-protokollet .
I fallet med S (delat tillstånd) kan flera snokare svara med FlushOpt med samma data (se exemplet ovan). F-staten i MESIF tar itu med denna redundans.
Se även
- Koherensprotokoll
- MSI-protokoll , det grundläggande protokollet från vilket MESI-protokollet härleds.
- Write-once (cache coherency) , en tidig form av MESI-protokollet.
- MOSI-protokoll
- MOESI-protokoll
- MESIF-protokoll
- MERSI-protokoll
- Dragon protokoll
- Firefly protokoll