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.
Problema di coerenza della cache (cache coherency)
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:
invalidando tutte le copie delle altre cache (broadcast-invalidate - diffusione invalidazione); 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: Bus watching o Snooping: generalmente usato per i sistemi SMP o Sistema Multiprocessore Simmetrico/multi-core basati sul bus; 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; Shared cache (cache condivisa): generalmente usata nei sistemi multi-core.
Bus watching o Snooping
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 cacheArchibald, J. and Baer, J. 1986 - Cache coherence protocols: evaluation using a multiprocessor simulation model. ACM Trans. Comput. Syst. 4, 4 (Sep. 1986), 273-298) - https://ctho.org/toread/forclass/18-742/3/p273-archibald.pdf. 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.
Stati della cache 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, MESIF - IntelAn Introduction to the Intel® QuickPath Interconnect - http://www.intel.ie/content/dam/doc/white-paper/quick-path-interconnect-introduction-paper.pdf). 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 (SL)BM PowerPC 476FP L2 Cache Core Databook - . 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-MESICache Ccoherency Protocol Including an HR State - IBM patent - https://www.google.com/patents/US6275908. Tutti i protocolli che usano questo stato saranno riferiti come R-MESI type. H=Hover - H-MESI (stato addizionale del protocollo MESI) 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-MESICache-coherency protocol with recently read state for data and instructions - IBM patent - https://www.google.com/patents/US5996049Cache Coherency Protocol with Tagged State for Modified Values - IBM patent - https://www.google.com/patents/US6334172
Operazioni di coerenza Snoopy
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) 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 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, 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