Protocolli di coerenza della cache (esempi)

Vengono qui elencati esempi dei protocolli di coerenza per la memoria cache. Per semplicità tutte le transazioni di stato di Read e Write "miss" che ovviamente provengono dallo stato I (o miss di Tag), nei diagrammi non sono mostrate. Sono mostrate direttamente sul nuovo stato. Molti dei seguenti protocolli hanno solo valore storico. Al momento i principali protocolli usati sono i protocolli R-MESI type / MESIF (tipo MESI) e il HRT-ST-MESI (tipo MOESI) o un sottoinsieme o un'estensione di questi.

Nei sistemi come il multiprocessore simmetrico (SMP), il multi core e il cc-NUMA, dove viene usata una cache dedicata per ogni processore, core o nodo, si può verificare un problema di coerenza dei dati quando uno stesso dato è memorizzato in più di una cache viene modificato in una cache. Può essere risolto in due modi:

1. invalidando tutte le copie delle altre cache (broadcast-invalidate - diffusione invalidazione);
2. aggiornando tutte le copie delle altre cache (write-broadcasting - diffusione scrittura).

In entrambi i casi la memoria può essere aggiornata (write through) o non aggiornata (write-back); la coerenza dai dati generalmente riguarda solo i dati (come operandi) e non le istruzioni (vedi Codice automodificante).

Gli schemi si possono classificare in base a:

• Schema Snoopy Vs Directory e Vs Shared caches;
• Protocollo Write through vs Write-back (basati sull'ownership o proprietà);
• Protocollo Update Vs Invalidation (aggiornamento Vs invalidazione);
• Intervention Vs non Intervention (intervento Vs non intervento);
• Protocollo dirty-sharing Vs non dirty-sharing (dati modificati condivisi Vs non condivisi - MOESI Vs MESI).

Tre approcci sono adottati per mantenere la coerenza dei dati:

1. Bus watching o Snooping: generalmente usato per i sistemi SMP o Sistema Multiprocessore Simmetrico/multi-core basati sul bus;
2. Directory-based - Message-passing: basati sulla directory e scambio di messaggi; possono essere usati in tutti i sistemi, ma tipicamente nei sistemi cc-NUMA e nei sistemi multi-core estesi;
3. Shared cache (cache condivisa): generalmente usata nei sistemi multi-core.

Protocollo usato nei sistemi con bus, come ad esempio nei sistemi SMP. Sistema operante sotto un unico sistema operativo con due o più processori omogenei e con una memoria principale centralizzata condivisa. Nei sistemi multiprocessori con cache separate che condividono una memoria comune, uno stesso dato può essere memorizzato in più di una cache. Un problema di coerenza nei dati nasce quando un dato è modificato in una sola cache. I protocolli per mantenere la coerenza fra processori multipli sono chiamati cache-coherency protocols (protocolli di coerenza delle cache). Generalmente nei sistemi SMP la coerenza si basa sull'approccio chiamato Bus watching (sorveglianza del bus) o Snoopy. In un sistema basato sullo snoopy, tutte le cache controllano le transazioni del bus per intercettare i dati e verificare se ha una copia nella propria cache. Vari protocolli di coerenza sono usati per mantenere la coerenza dei dati tra cache^[1]. Questi protocolli sono generalmente classificati solo in base agli stati della cache (da 3 a 5 e 7 o più) e le transazioni tra questi, ma questo potrebbe creare qualche confusione in quanto la definizione di un protocollo così fatta è incompleta perché mancante di importanti ed essenziali informazioni come le azioni che questi producono; queste azioni possono essere indotte dal processore o dal bus (esempio "intervention", "invalidation", "broadcasting", "updating", ecc.). Il tipo di azioni sono dipendenti dalle implementazioni adottate. Protocolli aventi gli stessi stati e le stesse regole di transazioni possono essere differenti, per es. il protocollo MESI con "shared intervention" (intervento su dati condivisi puliti (clean)) e MESI senza "intervention". Protocolli con stati differenti possono essere praticamente lo stesso protocollo, per esempio i protocolli 4-stati MESI Illinois e 5-stati MERSI (IBM) / MESIF-Intel sono solo un'implementazione diversa delle stesse funzionalità. I più comuni protocolli sono il protocollo 4-stati conosciuto con l'acronimo MESI e il 5-stati MOESI. Altri protocolli usano gli stessi stati - o un sottoinsieme di questi - ma con differenti implementazioni e spesso con una differente ma equivalente terminologia. Con il termine MESI o MOESI, o un sottoinsieme di questi, generalmente si fa riferimento a una classe di protocolli piuttosto che a uno specifico protocollo.

• M=Modified (modificato) o D=Dirty (sporco/alterato) o DE=Dirty-Exclusive (sporco esclusivo) o EM=Exclusive Modified (esclusivo modificato)
  • modificato o sporco, cioè modificato solo in una cache - write-back in caso di rimpiazzo (replacement); il dato è memorizzato in una sola cache, ma il dato in memoria non è aggiornato (invalido);
• O=Owner (proprietario/responsabile) o SD=Shared Dirty (sporco condiviso) o M=Shared Modified (sporco modificato) o T=Tagged (etichettato/contrassegnato)
  • modificato, potenzialmente condiviso, proprietario - write-back in caso di rimpiazzo; il dato può essere memorizzato in più di una cache, ma il dato in memoria non è aggiornato (invalido). Solamente una cache è "owner" (proprietario), le altre cache sono marcate "shared" (condivise). In caso di una richiesta di lettura sul bus, il dato viene fornito dall'owner anziché dalla memoria.
• E=Exclusive o R=Reserved o VE=Valid-Exclusive o EC=Exclusive Clean o Me=Exclusive
  • esclusivo o riservato o valido esclusivo o esclusivo pulito; il dato è memorizzato solo in una cache e clean (pulito, cioè valido) in memoria.
• S=Shared (condiviso) o V=Valid (valido) o SC=Shared Clean (condiviso pulito)
  • Dato potenzialmente condiviso con altre cache. Il dato può essere clean o dirty. Il termine "clean" in SC è fuorviante perché può essere anche dirty (vedi Protocollo Dragon)
• I=Invalid
  • Linea di cache invalida. Se la linea di cache non è presente (tag non corrispondente) è equivalente a linea invalida, perciò dato invalido significa dato presente ma invalido oppure non presente in cache

Stati speciali

• F=Forward (in avanti) o R=Recent (recente)
  • stati addizionali del protocollo MESI. L'ultimo dato letto. È uno speciale stato "Valido" che è l'owner per dati condivisi non modificati, usato in alcuni protocolli estesi di MESI (MERSI o R-MESI IBM^[2][3], MESIF - Intel^[4][5]). Lo stato R/F è usato per permettere l' "Intervention" quando il dato è "Valido" ma condiviso con le altre cache. Questa cache è responsabile per l'intervention (shared intervention). Su una richiesta di lettura del bus, il dato viene fornito da questa cache invece che dalla memoria. MERSI e MESIF sono lo stesso protocollo solo con una differente terminologia (F al posto di R). Qualche volta R è riferito anche come "Shared Last " - ultimo condiviso (S_L)^[6][7]. Lo stato R (Recent) è usato non solamente nel protocollo MERSI = R-MESI ma in diversi altri protocolli. Questo stato può essere usato in combinazione con altri stati. Per esempio RT-MESI, HR-MESI, HRT-MESI, HRT-ST-MESI^[8][9]. Tutti i protocolli che usano questo stato saranno riferiti come R-MESI type.
• H=Hover - H-MESI (stato addizionale del protocollo MESI)^[10]
  • Lo stato Hover (H) (sospeso) permette a una cache di mantenere un indirizzo nella directory anche se il corrispondente valore della linea di cache è una copia invalida. Se il valore corrispondente appare sul bus (Tag dell'indirizzo coincidente) dovuto a una "Read" o "Write" valida, il dato della linea di cache è aggiornato con una copia valida e il suo stato è cambiato in S. Questo stato può essere usato in combinazione con altri stati, per es. HR-MESI, HT-MESI, HRT-MESI, HRT-ST-MESI^[8][11][12]

Si distinguono tre operazioni: transazioni di bus, caratteristiche dei dati e operazioni di cache:

• Transazioni di bus: le principali operazioni sono:
  • Write Through: la linea di cache è aggiornata sia in cache che in MM o solo in MM (write no-allocate); semplice da implementare, alta occupazione di banda. Va bene per scritture singole.
  • Write-Back: il dato è scritto solo in cache. Il dato è scritto indietro in MM (Write-Back) solo quando sarà rimpiazzato (replacement) o quando richiesto dalle altre cache (vedi Write Policy); soluzione intermedia: Write Through per la prima scrittura, Write-Back per le successive (protocolli Write-once e Protocollo Bull HN ISI^[13])
  • Write Allocate: in caso di miss il dato è letto dall'"owner" o dalla MM, poi il dato è scritto in cache (aggiornato - scrittura parziale) (vedi Write Policy)
  • Write no-Allocate: in caso di miss il dato è scritto in MM senza coinvolgere la cache, oppure, come nel protocollo Protocollo Bull HN ISI, è scritto nell '"owner" , cioè nella D o SD cache (owner updating - aggiornamento dell'Owner), se è presente, altrimenti in MM; Write-no-Allocate normalmente è associato al Write Through.
  • Cache Intervention (o brevemente "intervention " - intervento)
    • Shared Intervention: shared-clean intervention (intervento su dati non modificati); in caso Read Miss (mancanza di lettura) il dato viene fornito dall' "owner" - E o R/F o anche S invece che dalla MM (vedi protocolli Illinois, IBM R-MESI type and Intel MESIF):
    • Dirty Intervention (intervento su dati modificati): in caso di Read Miss il dato è fornito dagli "owner" M (D) o O (SD) o E (R) (Non per E (R) nella proposta originale del protocollo MOESI^[14] e in alcune altre implementazioni tipo-MOESI) invece che dalla MM (es. protocollo MOESI, RT-MESI, …)
    • L'"Intervento" è una soluzione migliore rispetto al "non-Intervento" perché le transazioni cache-to-cache (da cache a cache) sono molto più veloci rispetto all'accesso alla MM, e in più si riduce il traffico di memoria (aumento di banda). MESI esteso Illinois e R-MESI type / MESIF sono perciò molto più efficienti rispetto al protocollo MOESI (vedi MESI vs MOESI)
  • Invalidation: in caso di Write Hit con stato S (V) o O (SD) (shared) una transazione di bus è inviata per invalidare tutte le copie delle altre cache (Write-invalidate)
  • Write-broadcast (Write-update): (scrittura distribuita), in caso di "Write Hit" con stato S (V) o O (SD) (shared) una scrittura di aggiornamento è inviata a tutte le altre cache per aggiornare le loro copie (es. Intel Nehalem^[15], Dragon protocol (Xerox), Firefly (DEC). L'operazione di aggiornamento delle altre cache è a volte chiamata anche Snarfing (arraffare, impadronirsi). Le cache monitorizzano (snoopy) il bus e se si ha hit la cache si impadronisce del dato che transita sul bus e aggiorna la propria cache. Anche l'aggiornamento dello stato H in (H-MESI) può essere definito come snarfing. Nel primo caso avviene solo in un'operazione scrittura distribuita, nel secondo caso sia in lettura che scrittura.
  • Intervention-broadcasting: (Intervento con aggiornamento distribuito): in caso di una transazione di intervento, una cache con stato H (H-MESI) aggiorna la sua copia invalida con il valore inviato sul bus e il suo stato è cambiato in S^[11]
  • Write Invalidate vs broadcast: write Invalidate è migliore in caso di scritture multiple, tipicamente scritture parziali, fatte da un processore prima che la linea di cache sia letta da un altro processore. Write-broadcast (aggiornamento) è migliore quando si ha un produttore singolo a molti consumatori del dato, ma è peggiore quando una cache è aggiornata con un dato che non sarà più successivamente utilizzato (inutile aumento di traffico sul bus e aumento delle interferenze di cache). L'invalidazione è la soluzione comune.
• Caratteristiche dei dati: ci sono tre caratteristiche dei dati di cache:
  • Validità: Qualsiasi linea di cache non invalida, cioè stati MOES / D-SD-R-V
  • Esclusività: il dato è valido solo su una cache (dato non condiviso) in stato M (D) o E (R), con la MM non aggiornata (dirty) in caso di M (D) e aggiornata (clean) in caso di E (R);
  • Ownership - Proprietà^[16]: la cache che è responsabile di fornire il dato richiesto in sostituzione della MM (Intervento). - Dipendente dal protocollo, la cache che deve fare l'intervento può essere S-E-M in MESI Illinois, o R/F-E-M in R-MESI type / MESIF o M (D) o O (SD) o anche E (R) (dipendente dall'implementazione) nel tipo MOESI, (es. AMD64,^[14], Bull HN ISI^[13] - vedi operazione di "Read Miss" sotto).
• Operazioni di cache: le operazioni delle cache sono:
  • Read Hit: il dato è letto dalla cache. Lo stato rimane inalterato; poiché questa è un'operazione ovvia, in seguito non sarà più considerata, anche nei diagrammi di transazione di stato
  • Read Miss: la richiesta di lettura dato è inviata sul bus; ci sono diverse situazioni:
    • Dato memorizzato solamente in MM: il dato è letto dalla MM; la cache è settata E (R) o S (V); E (R) se una speciale linea di bus (Shared line) è usata per indicare "nessun dato condiviso " (no data sharing). Usato in tutti i protocolli aventi lo stato E (R) eccetto per i protocolli Write-once e Bull HN ISI (vedi "Write Hit" sotto).
    • Dato memorizzato in MM e in una o più cache in stato S (V) oppure in R/F nel protocollo R-MESI type / MESIF: Ci sono tre situazioni:
      • Protocollo Illinois - una rete di priorità è usata per assegnare in modo arbitrario e temporaneo la "ownership" (proprietà) a una copia S. Il dato è fornito dalla cache selezionata. La cache richiedente è settata S (shared intervention - intervento tra dati condivisi con MM clean);
      • Protocollo R-MESI type / MESIF con una cache in stato R/F - shared owner ("owner" delle cache condivise); il dato è fornito dalla cache R/F. La cache che fornisce il dato è cambiata in S e la cache richiedente è settata R/F (in read miss la "ownership" è sempre presa dalla cache richiedente) - shared intervention;
      • In tutti gli altri casi il dato è fornito dalla MM e la cache richiedente è settata S (V).
    • Dato memorizzato in MM e in una sola cache in stato E (R): il dato è fornito dalla cache E (R) o dalla MM, in funzione del protocollo; fornito da E (R) in MESI esteso (es. Illinois, Pentium (R) II^[17]), R-MESI type / MESIF e in alcune implementazioni di MOESI (es. AMD64); la cache richiedente è settata S (V), o R/F nel protocollo R-MESI type / MESIF e la cache E (R) è cambiata in S (V) o in I nel protocollo MEI. In tutti gli altri casi il dato è fornito dalla MM

• Dato modificato in una o più cache con MM non aggiornata:

• Protocollo tipo MOESI - Dato memorizzato in M (D) o in O (SD) e le altre cache nello stato S (V): il dato è inviato alla cache richiedente dall' "owner" M (D) o O (SD). La cache richiedente è settata S (V) mentre M (D) è cambiato in O (SD); la MM rimane non è aggiornata.
• Protocollo tipo MESI o MEI - Dato memorizzato in M (D) e le altre cache nello stato S (V); ci sono due soluzioni:

1. il dato è inviato dalla cache M (D) alla cache richiedente e contemporaneamente in MM (per es. Illinois)
2. l'operazione è fatta in due passi: la transazione richiedente è temporaneamente sospesa. Si ha il "Copy Back" del dato M (D) in MM, poi la transazione in attesa prosegue leggendo il dato dalla MM (es. protocolli MESI e MSI Synapse)

Tutte le cache sono settate S (V)

• • Write Hit: il dato è scritto in cache; ci sono diverse situazioni:
    • Cache in stato S (V) o R/F o O (SD) (cache condivise)
      • Write invalidate
        • Copy back: il dato è scritto in cache e una transazione di invalida è inviata sul bus per invalidare le altre cache; la cache è settata M (D)
        • Write Through (Write-once, Bull HN ISI): il dato è scritto in cache e in MM invalidando tutte le altre cache. La cache è settata R (E)
      • Write broadcasting (es. Firefly, Dragon); il dato è scritto in cache e una transazione di "broadcasting" è inviata sul bus per aggiornare tutte le altre cache aventi una copia; la cache è settata M (D) se la linea "shared line" non è attiva, altrimenti è settata O (SD). Tutte le altre cache sono settate S (V)
    • Cache con stato E(R) o M(D) (esclusività): la scrittura può essere fatta localmente senza nessun'altra azione. Lo stato è settato (o rimane) M (D)
  • Write Miss
    • Write Allocate
      • Operazione di Read with Intent to Modified operation (RWITM): Come per un'operazione di Read più un comando di invalida, successivamente la cache è scritta (aggiornata); la cache richiedente è settata M (D) e tutte le altre cache sono invalidate
      • Write broadcasting (es. Firefly, Dragon): come per una Read Miss; se la "shared line" non è attiva il dato è scritto in cache e settato M (D), altrimenti come per una Write Hit - Write broadcasting
    • Write-no-Allocate: il dato è inviato alla MM, oppure come nel protocollo Bull HN ISI, solamente alle cache D (M) o SD (O) se presenti, bypassando la cache.

	Protocolli
SI	Write Through
MSI	Synapse[1]
MEI	IBM PowerPC 750[18], MPC7400[11]
MES	Firefly[1]
MESI	Pentium II[17], PowerPC, Intel Harpertown (Xeon 5400)
MOSI	Berkeley[1]
MOESI	AMD64[19], AMD OpteronAMD Opteron[20], MOESI[14], T-MESI IBM[12]

Terminologia usata
Illinois	D-VE-S-I (= MESI esteso)[1][21]
Write-once o Write-first	D-R-V-I (= MESI)  [1][22][23]
Berkeley	D-SD-V-I (= MOSI)  [1]
Synapse	D-V-I (= MSI)    [1]
Firefly	D-VE-S (= MES) DEC[1]
Dragon	D-SD (SM?)-SC-VE   (= MOES) Xerox[1]
Bull HN ISI	D-SD-R-V-I (= MOESI)[13]
Protocollo MERSI (IBM) / MESIF (Intel)	R=Recent - IBM PowerPC G4, MPC7400[2][11] F=Forward - Intel[4] , Intel Nehalem[24][15][25]
RT-MESI	T=Tagged - IBM[12]
HRT-ST-MESI	H=Hover, R=Recent,T=Tagged, ST=Shared-Tagged - IBM[8][12]
Protocollo POWER4 IBM	Mu-Me-M-T-S-SL-I  (L2 sette stati)[6] Mu=Unsolicited Modified - non Sollecitato Modificato Esclusivo - (M)[26] M=Modified Exclusive - Modificato Esclusivo (D) T=Tagged - Modificato Owner non Esclusivo (O) Me=Valido Esclusivo - (E) S=Shared SL=Shared Last - sourced local" - (Shared Owner Locale) I=Invalido - (I)

---

  Stati MESI = D-R-V-I

- Uso della linea "shared line" per determinare copie condivise (shared) sulle altre cache

• Operazioni del Processor

• Read Miss

Ci sono due implementazioni alternative: MESI standard (senza intervento) e MESI esteso (con intervento)

1. MESI "no Intervention" (senza intervento) (es. PowerPC 604^[27])

- Se si ha una copia M in una cache, la transazione viene fermata e rimane in attesa sino a quando la cache M aggiornerà la MM, poi la transazione continuerà leggendo il dato dalla MM. Lo stato di tutte e due le cache è settato S

- altrimenti il dato è letto dalla MM. Se la linea "shared line" è "on" la cache è settata S altrimenti E

2. MESI "Intervention" da M e da E (es. Pentium (R) II^[17])

- Se si ha una copia M o E in una cache (esclusività), il dato è fornito alla cache richiedente da M o da E (intervento). Se è inviato da M il dato è contemporaneamente scritto anche in MM (copy back). Tutte le cache sono settate S

- altrimenti il dato è letto dalla MM. Se la linea "shared line" è "on" la cache è settata S altrimenti E

• Write Hit

- Se la cache è M o E (esclusività), la scrittura può essere fatta localmente senza nessun'altra azione

- altrimenti il dato è scritto in cache e una transazione di invalida è inviata sul bus per invalidare tutte le altre cache

- La cache è settata M

• Write Miss

- Un'operazione RWITM è inviata sul bus. L'operazione è fatta in due step: "Read Miss" con un comando di "invalida" per invalidare tutte le altre cache, poi come in una "Write Hit" con cache in stato M (vedi Operazioni di Cache-Write Miss).

• Transazioni di Bus

• Bus Read

- se M e "no Intervento" il dato è inviato alla MM (Copy Back)

- se M e "Intervento" il dato è inviato alla cache richiedente e alla MM (Copy Back)

- se E (*) e "Intervento" il dato è inviato alla cache richiedente

- Lo stato è cambiato (o rimane) in S

• Bus Write - (RWITM)

- Come in caso di "Bus Read"

- La cache è settata "Invalida" (I)

• Transazione di Bus di Invalida

- La cache è settata "Invalida" (I)

• Operazioni

- Write Allocate

- Intervento: da M - E (*)

- Write Invalidate

- Copy-Back: Rimpiazzo di M

(*) - MESI esteso

---

  Stati MEOSI = D-R-SD-V-I = T-MESI IBM^[12]

- Uso della linea "shared line" per determinare copie condivise (shared) sulle altre cache

• Operazioni del Processor

• Read Miss

- Se c'è una copia in un'altra cache in stato M o O o E (*), il dato è fornito da questa cache (Intervention). La cache richiedente è settata S , M è cambiato in O e E in S

- altrimenti il dato è letto dalla MM

- Se la "shared line" è "on" la cache richiedente è settata S altrimenti E

• Write Hit

- Se la cache è M o E (esclusività), la scrittura può essere fatta localmente senza nessun'altra azione

- altrimenti O o S (sharing) una transazione di invalida è inviata sul bus per invalidare le altre cache.

- Lo stato è cambiato (o rimane) in M

• Write Miss

- Un'operazione di RWITM è inviata sul bus

- Il dato è fornito dall' "owner" o dalla MM come nella Read Miss, poi il dato è scritto in cache (aggiornato = scrittura parziale)

- La cache è settata M e le altre cache sono settate I

• Transazioni di Bus

• Bus Read

- Se la cache è M o O o E (*) il dato è inviato alla cache (intervention). Se la cache è E lo stato è cambiato in S, altrimenti è settato (o rimane) O

- altrimenti lo stato è cambiato in S

• Bus Write - (RWITM)

- Se la cache è M o O o E (*) il dato è inviato alla cache (intervention)

- La cache è settata "Invalida" (I)

• Transazione di Bus di Invalida

- La cache è settata "Invalida" (I)

• Operazioni

- Write Allocate

- Intervention: da M-O-E (*)

- Write Invalidate

- Copy-Back: Rimpiazzo di M-O

- (*) dipendente dal tipo di implementazione per E

---

  Stati MESI = D-R-V-I^[1]

- Caratteristiche:

- È un'estensione del protocollo MESI

- Uso di una rete di priorità per il shared intervention (intervento su dati condivisi)

- Differenze da MESI: intervento oltre che da E e M anche da S (vedi Operazioni di Cache-Read Miss - punto 1)

• Operazioni

- Write Allocate

- Intervention: da M-E-S

- Write Invalidate

- Copy-Back: Rimpiazzo di M

---

  States D-R-V-I (MESI)^[1][22][23]

- Caratteristiche:

- Non uso della "shared line" (protocollo per bus standard o bus non modificabile)

- Write Through sulla prima Write Hit in stato V, poi Copy Back

• Operazioni del Processor

• Read Miss

- Se c'è una copia D in un'altra cache, il dato è fornito da questa cache (intervention) e contemporaneamente è anche scritto in MM (Copy-Back) .

- altrimenti il dato è letto dalla MM

- tutte le cache sono settate V

• Wiite Hit

- Se la cache è D o R (esclusività), la scrittura è fatta localmente senza nessun'altra azione e lo stato è settato (o rimane) D

- altrimenti V (prima Write Hit) il dato è scritto in cache e in MM (Write Through) invalidando tutte le altre cache (Write-Invalidate). La cache è settata R

• Wiite Miss

- Come per la Read Miss con un comando di "invalida" (RWITM) più una Write Hit in stato D (updating). La cache è settata D e tutte le altre cache "Invalide" (I)

- Nota - La Write Through è fatta solamente in "Write Miss". È da notare che in questo caso una transazione di bus è comunque necessaria per invalidare le altre cache e perciò si può approfittare di questo fatto per aggiornare anche la MM. In "Write Miss" invece non è necessaria nessuna transazione in più per cui una Write Through diventerebbe un'inutile operazione nel caso in cui la cache fosse nuovamente aggiornata.

• Transazioni di Bus

• Bus Read

- Se la cache è D il dato è inviato da questa cache alla cache richiedente (intervention) e anche alla MM (copy-back). La cache è settata V

- altrimenti lo stato è cambiato (o rimane) in V

• Bus Write - (RWITM)

- Se la cache è D il dato è inviato alla cache richiedente (intervention)

- La cache è settata "Invalida" (I)

• Transazione di Bus di Invalida

- La cache è settata "Invalida" (I)

• Operazioni

- Write Allocate

- Intervention: da D

- Write Through: prima Write Hit in stato V

- Write Invalidate

- Copy-Back: Rimpiazzo di D

---

  Stati D-SD-R-V-I (MOESI)   Protocollo brevettato (F. Zulian)^[13]

- Caratteristiche:

- MOESI - estensione del protocollo Write-once

- Write-no-allocate su miss con aggiornamento di D o SD

- Non uso di RWITM

- Non uso della "shared line"

• Operazioni del Processor

• Read Miss

- Come per MOESI con "shared line" "on" ed intervento solo dall' "owner" D o SD e non da R

• Wiite Hit

- Se la cache è D o R, come per MOESI, la scrittura è fatta localmente senza nessun'altra azione. La cache è settata (o rimane) D

- Se SD o V (prima scrittura), come per Write-Once, il dato è scritto in cache e in MM (Write Through) invalidando tutte le altre cache (Write-Invalidate). La cache è settata R

• Write Miss

- Il dato è inviato sul bus bypassando la cache (Write-no-allocate)

- Se c'è una copia "owner" D o SD, l' "owner" è aggiornato (vedi Write-no-Allocate) mentre le altre cache sono invalidate. L' "owner" è settato (o rimane) D. La MM rimane "dirty" (non aggiornata)

- altrimenti il dato è inviato alla MM invalidando le altre cache (Write-Invalidate)

• Transazioni di Bus

• Bus Read

- Come per MOESI con intervento solo dall' "owner" D o SD

• Bus Write (Write Update / Write Invalidate)

- Se la cache è D o SD, la cache è aggiornata, altrimenti è settata "Invalida" (I)

• Operazioni

- Write-no-allocate: su miss

- Write update: su miss

- Write Through: per la prima scrittura, poi copy back

- Write Update / Write Invalidate

- Intervention: da SD-D

- Copy-Back: rimpiazzo di D o di SD con invalida

Oss. - Questo è l'unico protocollo che ha transazioni O-E (SD-R) ed è anche l'unico che fa uso della Write-no-allocate su miss.

---

  Stati D-V-I (MSI)^[1]

- Caratteristiche:

- La caratteristica di questo protocollo è di avere, per ciascuna linea di cache, un tag singolo-bit in MM, indicando una linea di cache è in stato D.

- Questo bit previene una possibile Race condition (condizione di corsa) se la cache D non risponde sufficientemente veloce per inibire la MM dal rispondere immediatamente prima di essere stata aggiornata.

- Il dato proviene sempre dalla MM

- Non uso della "shared line"

• Operazioni del Processor

• Read Miss

- Se c'è una copia D in un'altra cache, la transazione di lettura è rifiutata. La copia D è scritta indietro in MM e cambia il suo stato in V, poi la cache richiedente rimanda una nuova transazione di lettura e il dato è letto dalla MM.

- altrimenti il dato è letto dalla MM.

- La cache è settata V

• Write Hit

- Se la cache è D, la scrittura può essere fatta localmente senza nessun'altra azione.

- altrimenti V, come in caso di Read Miss, includendo anche un trasferimento di dati dalla memoria con in più un comando di invalida (RWITM). Questo è fatto solo per invalidare le altre copie V perché questo protocollo non supporta una transazione di invalida.

- La cache è settata D. Tutte le altre cache sono settate "Invalide" (I)

• Write Miss (RWITM)

- Come per la Read Miss, ma con un comando di invalida. La linea di cache è letta dalla MM, poi la cache è scritta (aggiornata). La cache è settata D. Tutte le altre cache sono settate "Invalide" (I).

• Transazioni di Bus

• Bus Read

- Se la cache è D il dato è inviato indietro alla MM (Copy Back). La cache è settata V

- altrimenti lo stato rimane in V

• Bus Write (RWITM)

- Se la cache è D il dato è inviato indietro alla MM (Copy Back)

- La cache (D o V) è settata "Invalida" (I)

• Operazioni

- Write Allocate

- Intervention: nessun intervento

- Write Invalidate: RWITM

- No transazione di invalida

- Copy-Back: rimpiazzo di D

---

  Stati D-SD-V-I (MOSI)^[1]

- Caratteristiche:

- Come per MOESI senza lo stato E

- Non uso della "shared line"

• Operazioni del Processor

• Read Miss

- Ii dato è fornito dall' "owner", e cioè da D o da SD altrimenti dalla MM. D è cambiato in SD

- La cache è settata V

• Wiite Hit

- Se la cache è D (esclusività), la scrittura è fatta localmente senza nessun'altra azione

- altrimenti (SD o V), una transazione di invalida è inviata sul bus per invalidare le altre cache.

- La cache è settata (o rimane) D

• Write Miss

- Un'operazione di RWITM è inviata sul bus

- Come per la Read Miss, il dato è fornito dall' "owner", e cioè da D o SD o dalla MM, poi la cache è aggiornata

- La cache è settata D. Tutte le altre cache sono settate I

• Transazioni di Bus

• Bus Read

- Se la cache è D o SD il dato è inviato alla cache richiedente (intervento). La cache è settata (o rimane) in SD

- altrimenti la cache rimane in V

• Bus Write (RWITM)

- Se la cache è D o SD il dato è inviato sul bus (Intervento)

- La cache è settata "Invalida" (I)

• Transazione di Bus di Invalida

- La cache è settata "Invalida" (I)

• Operazioni

- Write Allocate

- Intervention: da D-SD

- Write Invalidate

- Copy-Back: rimpiazzo di D e SD

---

  Stati D-VE-S (MES)^[1]

- Caratteristiche:

- Non uso di stato "Invalido"

- Write-broadcasting +Write Through

- Uso della "shared line"

- Write-broadcasting evita la necessità dello stato "Invalido"

- Simultaneo intervento da tutte le cache (shared e dirty Intervention - su dati non modificati che modificati)

- Questo protocollo richiede un bus sincrono

• Operazioni del Processor

• Read Miss

- Ogni cache è l' "owner", cioè tutte le altre cache con una copia inviano simultaneamente il dato sul bus (intervento simultaneo - la temporizzazione del bus è fissa cosicché le cache rispondono nello stesso ciclo), altrimenti il dato è fornito dalla MM.

- Se c'è una cache D, il dato è inviato simultaneamente anche in MM (Copy Back)

- Se c'è una copia nelle altre cache la "Shared line" è settata "on"

- Se la "Shared line" è "off" tutte le altre cache sono settate S altrimenti la cache richiedente è settata VE.

• Write Hit

- Se la cache è D o VE (esclusività), la scrittura è fatta localmente senza nessun'altra azione e la cache è settata D

- altrimenti S, una Write-broadcasting è inviata sul bus per aggiornare tutte le altre cache e la MM (Write Through)

- Se c'è una copia in un'altra cache, la "Shared line" è settata "on". Se la "Shared line" is "off" la cache è settata VE altrimenti tutte le cache sono settate S

• White Miss

- L'operazione è fatta in due step. Read Miss seguita da una Write Hit.

- Se il dato proviene da una cache (Shared Line "on") una Write-broadcasting è inviata sul bus per aggiornate tutte le altre cache e la MM (Write Through). Tutte le cache sono settate S

- altrimenti la cache è settata D

• Transazioni di Bus

• Bus Read

- Se hit (D o VE o S) il dato è inviato sul bus (intervento) e in caso di D il dato è scritto anche in MM. La cache è settata S

• Bus Write

- Se hit (D o VE o S) il dato è inviato sul bus (Intervento).

- Tutte le cache sono settate S

• Write Broadcasting

- La cache è aggiornata con il nuovo dato. Lo stato rimane S

• Operazioni

- Write Allocate

- Intervention: da D-VE-S (da tutte le cache "valide")

- Write-broadcasting - Write through

- Copy-Back: rimpiazzo di D e su qualsiasi transazione con una cache D

---

  Stati D-SD-VE-SC (MOES)^[1] Nota - lo stato SC, nonostante il termine "clean", può essere "clean" o "dirty" come lo stato S degli altri protocolli. SC e S sono equivalenti.

- Caratteristiche:

- Non uso di stato "Invalido"

- Write-broadcasting (non Write Through)

- Uso della "shared line"

- Write-broadcasting evita la necessità dello stato "Invalido"

• Operazioni del Processor

• Read Miss

- Ii dato è fornito dall' "owner", vale a dire da D o da SD altrimenti dalla MM. D è cambiato in SD

- Se la "shared line" è "on" la cache è settata SC altrimenti VE

• Wiite Hit

- Se la cache è D o VE (esclusività), la scrittura è fatta localmente senza nessun'altra azione. La cache è settata (o rimane) D

- altrimenti SD o SC (sharing) il dato è scritto in cache e una Write-broadcasting è inviata sul bus per aggiornare tutte le altre cache - La MM non è aggiornata (non Write through)

- Se c'è una copia in un'altra cache, la "Shared line" è settata "on"

- Se la "Shared Line" è "on" la cache è settata SD, altrimenti D. Tutte le altre eventuali copie sono settate SC

• Wiite Miss

- Come per la Read Miss, il dato è inviato dall' "owner", D o SD o MM, poi la cache viene aggiornata.

- Se c'è una copia in un'altra cache, la "Shared line" è settata "on"

- Se la "Shared Line" è "on" il dato aggiornato è distribuito alle altre cache e lo stato è settato SD. Tutte le altre cache sono settate SC

- altrimenti la cache è settata D

• Transazioni di Bus

• Bus Read

- SE la cache è D o SD il dato è inviato alla cache richiedente (intervention). La cache è settata (o rimane) SD

- altrimenti la cache rimane SC

• Bus Write

- Se la cache è D o SD il dato è inviato sul bus (Intervention)

- La cache è settata SC

• Write Broadcasting

- La cache è aggiornata con il nuovo dato. La cache rimane SC

• Operazioni

- Write Allocate

- Intervention: da D-SD (ma non da VE)

- Write-broadcasting

- Copy-Back: rimpiazzo di D-SD

---

  Stati MERSI o R-MESI   Stati MESIF   Protocolli brevettati - IBM (1997)^[11] - Intel (2002)^[28]

- MERSI e MESIF sono lo stesso identico protocollo (solamente lo stato del nome è differente, F invece di R)

- Caratteristiche:

- Le stesse funzionalità del protocollo Illinois

- Un nuovo stato R (Recent) / F (Forward) è l' "owner " per i dati shared-clean" (condivisi).

- La "shared ownership" (l'owner delle cache condivise "clean" - non modificate) non è assegnata da una rete di priorità come con Illinois, ma è sempre assegnata all'ultima cache con Read Miss, settando il suo stato R/F

- La "shared ownership" è temporaneamente persa nel caso di rimpiazzo della linea R/F. La "ownership" è riassegnata alla prima successiva Read Miss con cache "shared" non modificate

- Uso della "shared line"

• Operazioni

- Write Allocate

- Intervention: da M-E-R/F

- Write Invalidate

- Copy-Back: rimpiazzo di M

---

MESI e MOESI sono i protocolli più popolari È comune opinione che MOESI sia un'estensione del protocollo MESI e perciò più sofisticato e più performante. Questo è vero solamente se confrontato con MESI standard, cioè con MESI senza intervento tra cache condivise "clean" (dato non modificato rispetto alla MM). MESI con intervento tra cache condivise "clean", come MESI Illinois o gli equivalenti protocolli 5-stati MERSI / MESIF, sono molto più performanti del protocollo MOESI. In MOESI, le operazioni cache-cache sono fatte solamente su dati modificati. Invece nei protocolli tipo MESI Illinois e MERSI / MESIF, le operazioni cache-cache sono sempre fatte" sia su dati "clean" che su dati modificati. Nel caso di dati modificati, l'intervento è fatto dall' "owner" M, ma l'ownership non è persa perché essa migra in un'altra cache (la R/F in MERSI / MESIF o in una cache selezionata come nell caso di Illinois. L'unica differenza è che la MM deve essere aggiornata. In ogni caso anche in MOESI questa transazione dovrà più tardi comunque essere fatta in caso di rimpiazzo dell' "owner", se nessun'altra modifica avviene nel frattempo. Tuttavia questo è un limite minore rispetto a una transazione di memoria dovuta ad un non intervento, come nel caso di dati non modificati (clean) per il protocollo MOESI. (vedi per es. "Performance evaluation between MOESI (Shanghai) and MESIF Nehalem-EP"^[24]) I sistemi più avanzati usano solamente il protocollo MERSI / MESIF|R-MESI type / MESIF (IBM / Intel) o i più completi RT-MESI, HRT-ST-MESI e MERSI / MESIF che sono l'unione evoluta dei protocolli MESI e MOESI. Nota: Trasferimenti cache-cache sono soluzioni efficienti per sistemi multiprocessor/multicore connessi direttamente tra loro, ma meno nei sistemi con Cache remota come nei sistemi NUMA dove è preferibile MESI standard. Esempio nel Protocollo POWER4 IBM lo "shared intervention" è fatto solo "localmente" e non tra moduli remoti.

---

  States RT-MESI   protocollo brevettato IBM^[8][12]

- Caratteristiche:

- Unione di MESI e MOESI

- Shared Intervention + Dirty Intervention (sia tra cache "clean" che tra cache con dati modificati)

- Stesse funzionalità del protocollo R-MESI con un nuovo stato T = Tagged, equivalente allo stato O

- Migrazione del "Dirty-Owner"

- L' "owner" (sia Shared che Dirty) è sempre l'ultima cache richiedente (il nuovo "owner" (LRU) ha meno probabilità di essere deallocato a breve rispetto a quello più vecchio)

- Gli "owner" sono T, M, E, R (tutti eccetto S)

- Uso della "shared line"

• Operazioni del Processor

• Read Miss

- Se c'è una copia M o T (dirty-ownership) in un'altra cache, il dato è fornito da questa cache (dirty-intervention). La cache richiedente è settata T e i precedenti M o T sono cambiati in S

- Se c'è una copia E o R (shared-ownership) in un'altra cache, il dato è fornito da questa cache (shared-intervention). La cache richiedente è settata R e i precedenti E o R sono cambiati in S

- altrimenti il dato è letto dalla MM e la cache è settata R.

• Write Hit

- Se la cache è M o E (esclusività), la scrittura è fatta localmente senza nessun'altra azione

- altrimenti T o R o S (sharing) una transazione di "Invalida" è inviata sul bus per invalidare tutte le altre cache.

- La cache è settata (o rimane) M e tutte le altre cache sono settate I

• Write Miss

- Un'operazione di RWITM è inviata sul bus

- Il dato è fornito dall' "owner" o dalla MM come nella Read Miss, poi il dato è scritto (aggiornato) in cache

- La cache è settata M e tutte le altre cache sono settate I

• Transazioni di Bus

• Bus Read

- Se la cache è T o M o R o E il dato è inviato alla cache richiedente (intervention).

- La cache è settata (o rimane) S

• Bus Write - (RWITM)

- Se la cache è T o M o R o E il dato è inviato alla cache richiedente (intervention)

- La cache è settata "Invalida" (I)

• Transazione di Bus di Invalida

- La cache è settata "Invalida" (I)

• Operations

- Write Allocate

- Intervention: da T-M-R-E

- Write Invalidate

- Copy-Back: rimpiazzo di T-M

---

È un miglioramento del protocollo RT-MESI^[12] ed è un subset del protocollo HRT-ST-MESI^[8]

S_T = Shared-Tagged

- L'uso dello stato "Shared-Tagged" permette di mantenere l' "intervention" dopo una deallocazione di una linea di cache "Tagged"

- Nel caso di rimpiazzo di T (deallocazione della linea di cache), il dato deve essere scritto indietro in MM e così perdere la "ownershisp". Per evitare ciò può essere usato un nuovo stato S_T. In caso di Read Miss il precedente T è settato S_T invece di S. S_T sarà il candidato per rimpiazzare la ownership in caso di deallocazione di T. La transazione di "Copy Back" di T è bloccata da S_T (la memoria non è aggiornata) che cambia il suo stato in T. Nel caso di una nuova Read MIss da un'altra cache, quest'ultima è settata T, il precedente T è cambiato in S_T e precedente S_T è cambiato in S.

Un miglioramento aggiuntivo può essere ottenuto usando più di uno stato S_T, S_T1, S_T2 ,… S_Tn.

- In Read Miss, T è cambiato in S_T1 e gli indici degli altri S_Ti sono incrementati di "1"

- In caso di deallocazione di T, S_T1 blocca la transazione di "Copy Back" e cambia il suo stato in T e tutti gli indici degli S_Ti sono decrementati di "1".

- In caso di una deallocazione, per esempio di S_Tk, la catena sarà interrotta e tutti gli S_Ti con indice maggiore di "k" saranno automaticamente persi in termini di S_T, e saranno considerati de facto solamente come stati S, anche se essi manterranno lo stato S_T. Tutto ciò perché solo S_T1 interviene per bloccare e sostituirsi a T. Per es. se si ha una situazione tipo T, S_T1, S_T3, S_T4 con S_T2 rimpiazzato, se T sarà rimpiazzato la nuova situazione sarà T, S_T2, S_T3 senza nessun S_T1.

---

Protocollo IBM brevettato HRT-ST-MESI completo^[8][12] - Stato I = Tag invalido (*) - Dati Invalidi - Stato H = Tag Valido - Dati Invalidi - Lo stato I è settato all'inizializzazione e il suo stato cambia solo dopo una Read o Write miss del processor. Poi non tornerà più in questo stato. - H ha le stesse funzionalità dello stato I ma con in più la capacità di catturare le transazioni del bus aventi lo stesso Tag della directory e aggiornare la cache dati. - Dopo la prima utilizzazione I viene rimpiazzato da H nelle sue funzioni

- Le principali funzioni sono:

- Write Back

- Intervento sia su dati dirty che shared-clean - da T-M-R-E

- Stati di riserva del Tagged (Shared-Tagged)

- Auto aggiornamento dello stato invalido H (Hover)

(*) - Nota: Il Tag per definizione è sempre valido, ma sino al primo aggiornamento della linea di cache è considerato invalido per non aggiornare la cache anche quando questa linea non è ancora stata richiesta e usata.

---

  Stati M-T-Me-S-I -Mu-S_L = RT-MESI+Mu^[6]

- Uso della "shared line"

- Usato in Sistemi multi-core/moduli - multi-cache L2^[6]

- Questo protocollo è equivalente al protocollo RT-MESI per sistemi con cache L2 multiple su sistemi multi moduli.

• S_L - "Shared Last" equivalente a R nel RT-MESI protocollo
• Me - "Valid Exclusive" = E (valido esclusivo)
• Mu - unsolicited modified state - stato modificato esclusivo non sollecitato

- stato speciale - richiesta di prenotazione scrittura e lettura "doubleword" (per l'implementazione a 64-bit)

- "Shared intervention" da S_L è fatto solo tra cache L2 dello stesso modulo

- "Dirty intervention" da T è fatto solo tra cache L2 dello stesso modulo

• Operations

- Write Allocate

- Intervention: da M-T-VE-S_L = M-O-E-S_L

- Write Invalidate

- Copy-Back: rimpiazzo di M-T

- Nota: T e S_L - Intervento solo locale al modulo

Sotto certe condizioni il più efficiente e completo protocollo risulta essere il protocollo HRT-ST-MESI

- Write Back

- Intervento sia su dati dirty che shared-clean - da T-M-R-E

- Stati di riserva del Tagged (Shared-Tagged)

- Auto aggiornamento dello stato invalido H (Hover)