Apri il menu principale

1leftarrow blue.svgVoce principale: Memoria cache.

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.

Indice

Stati della cacheModifica

  • 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[1], MESIF - Intel[2][3]). 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)[4][5]. 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[6][7]. Tutti i protocolli che usano questo stato saranno riferiti come R-MESI type.
  • H=Hover - H-MESI (stato addizionale del protocollo MESI)[8]
    • 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 ad 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[6][9][10]

Protocollo MESIModifica

 
MESI Protocol - State Transaction Diagram

  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[11])
- 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[12])
- 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 nessuna altra azione
- altrimenti il dato è scritto in cache ed una transazione di invalida è inviata sul bus per invalidare tutte le altre cache
- La cache è settata M
  • Write Miss
- Una 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
- 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

 
MOESI Protocol - State Transaction Diagram

Protocollo MOESIModifica

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

- 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 nessuna 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
- Una 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
- 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

 
Illinois State Transaction Diagram

Protocollo IllinoisModifica

  Stati MESI = D-R-V-I[13]

- Caratteristiche:
- È una 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

 
Write-Once Protocol - State Transaction Diagram

Protocollo Write-Once (or Write-First)Modifica

  States D-R-V-I (MESI)[13][14][15]

- 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 nessuna 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
- 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

 
Bull HN ISI Protocol - State Transaction Diagram

Protocollo Bull HN ISIModifica

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

- 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 nessuna 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), ma l'unico che non ha transazioni M-I (D-I) ed è anche l'unico che fa uso della Write-no-allocate su miss.

 
Synapse Protocol - State Transaction Diagram

Protocollo SynapseModifica

  Stati D-V-I (MSI)[13]

- 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 nessuna 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)
- 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
- 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

 
Berkeley Protocol - State Transaction Diagram

Protocollo BerkeleyModifica

  Stati D-SD-V-I (MOSI)[13]

- 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 nessuna 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
- Una 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
- 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

 
Firefly Protocol - State Transaction Diagram

Protocollo Firefly (DEC)Modifica

  Stati D-VE-S (MES)[13]

- 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 nessuna 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

 
Dragon Protocol - State Transaction Diagram

Protocollo Dragon (Xerox)Modifica

  Stati D-SD-VE-SC (MOES)[13] 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 nessuna altra azione. La cache è settata (o rimane) D
- altrimenti SD o SC (sharing) il dato è scritto in cache ed 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

 
MERSI - MESIF Protocol - State Transaction Diagram

Protocollo MERSI (IBM) / MESIF (Intel)Modifica

  Stati MERSI o R-MESI   Stati MESIF   Protocolli brevettati - IBM (1997)[9] - Intel (2002)[17]

- 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 vs MOESIModifica

MESI e MOESI sono i protocolli più popolari È comune opinione che MOESI sia una 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 nessuna altra modifica avviene nel frattempo. Tuttavia questo è un limite minore rispetto ad 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"[18]) 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.


 
RT-MESI Protocol - State Transaction Diagram

Protocollo RT-MESIModifica

  States RT-MESI   protocollo brevettato IBM[6][10]

- 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 nessuna 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
- 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

Protocollo RT-ST-MESIModifica

È un miglioramento del protocollo RT-MESI[10] ed è un subset del protocollo HRT-ST-MESI[6]

ST = 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 ST. In caso di Read Miss il precedente T è settato ST invece di S. ST sarà il candidato per rimpiazzare la ownership in caso di deallocazione di T. La transazione di "Copy Back" di T è bloccata da ST (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 ST e precedente ST è cambiato in S.

Un miglioramento aggiuntivo può essere ottenuto usando più di uno stato ST, ST1, ST2 ,… STn.

- In Read Miss, T è cambiato in ST1 e gli indici degli altri STi sono incrementati di "1"
- In caso di deallocazione di T, ST1 blocca la transazione di "Copy Back" e cambia il suo stato in T e tutti gli indici degli STi sono decrementati di "1".
- In caso di una deallocazione, per es. di STk, la catena sarà interrotta e tutti gli STi con indice maggiore di "k" saranno automaticamente persi in termini di ST, e saranno considerati de facto solamente come stati S, anche se essi manterranno lo stato ST. Tutto ciò perché solo ST1 interviene per bloccare e sustituirsi a T. Per es. se si ha una situazione tipo T, ST1, ST3, ST4 con ST2 rimpiazzato, se T sarà rimpiazzato la nuova situazione sarà T, ST2, ST3 senza nessun ST1.

 
HRT-ST-MESI Protocol - State Transaction Diagram

Protocollo HRT-ST-MESIModifica

Protocollo IBM brevettato HRT-ST-MESI completo[6][10] - 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.


Protocollo POWER4 IBMModifica

  Stati M-T-Me-S-I -Mu-SL = RT-MESI+Mu[4]

- Uso della "shared line"
- Usato in Sistemi multi-core/moduli - multi-cache L2[4]
- Questo protocollo è equivalente al protocollo RT-MESI per sistemi con cache L2 multiple su sistemi multi moduli.
  • SL - "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 SL è 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-SL = M-O-E-SL
- Write Invalidate
- Copy-Back: rimpiazzo di M-T
- Nota: T e SL - Intervento solo locale al modulo

NoteModifica

  1. ^ Ravi Kumar Arimilli, John Steven Dodson e John Michael Kaiser, Cache-coherency protocol with recently read state for data and instructions, US5996049 A, 30 novembre 1999. URL consultato il 28 febbraio 2017.
  2. ^ An Introduction to the Intel® QuickPath Interconnect - http://www.intel.ie/content/dam/doc/white-paper/quick-path-interconnect-introduction-paper.pdf
  3. ^ Herbert H. J. Hum e James R. Goodman, Forward state for use in cache coherency in a multiprocessor system, US6922756 B2, 26 luglio 2005. URL consultato il 28 febbraio 2017.
  4. ^ a b c "POWER4 System Microarchitecture", http://www.cc.gatech.edu/~bader/COURSES/UNM/ece637-Fall2003/papers/TDF02.pdf
  5. ^ BM PowerPC 476FP L2 Cache Core Databook - Copia archiviata (PDF), su www-01.ibm.com. URL consultato il 1º novembre 2016 (archiviato dall'url originale il 18 dicembre 2014).
  6. ^ a b c d e Cache Ccoherency Protocol Including an HR State - IBM patent - https://www.google.com/patents/US6275908
  7. ^ Ravi Kumar Arimilli, John Steven Dodson e Jerry Don Lewis, Cache coherency protocol with tagged state for modified values, US6334172 B1, 25 dicembre 2001. URL consultato il 28 febbraio 2017.
  8. ^ Ravi Kumar Arimilli, John Steven Dodson e Jerry Don Lewis, Cache coherency protocol including an HR state, US6275908 B1, Aug 14, 2001. URL consultato il 28 febbraio 2017.
  9. ^ a b Cache-coherency protocol with recently read state for data and instructions - IBM patent - https://www.google.com/patents/US5996049
  10. ^ a b c d e Cache Coherency Protocol with Tagged State for Modified Values - IBM patent - https://www.google.com/patents/US6334172
  11. ^ Optimizing the MESI Cache Coherence Protocol for Multithreaded Applications on Small Symmetric Multiprocessor Systems - Copia archiviata, su tibrewala.net. URL consultato il 9 ottobre 2016 (archiviato dall'url originale il 22 ottobre 2016).
  12. ^ Pentium Pro and Pentium II System Architecture pg. 160 - Di T. Shanley - http://books.google.it/books?id=MLJClvCYh34C&pg=PA160&lpg=PA160&dq=Pentium+protocol+cache&source=bl&ots=gaOu-EvaTy&sig=QQEM1krp-H_0KUhi5Ti2bmxU2kU&hl=it&sa=X&ei=Zt6KT7icG8TE4gShzaDwCQ&ved=0CDcQ6AEwAg#v=onepage&q=Pentium%20protocol%20cache&f=false
  13. ^ a b c d e f Archibald, J. and Baer, J. 1986 - Cache coherence protocols: evaluation using a multiprocessor simulation model. ACM Trans. Comput. Syst. 4, 4 (Sep. 1986), 273-298) - http://ctho.org/toread/forclass/18-742/3/p273-archibald.pdf
  14. ^ Using cache memory to reduce processor-memory traffic". Proceedings of the 10th annual international symposium on Computer architecture - ISCA '83. International Symposium on Computer Architecture: Stockholm, Sweden, June 13–17, 1983.pp. 127-128 - http://courses.cs.vt.edu/cs5204/fall11-kafura/Papers/TransactionalMemory/Goodman-SnoopyProtocol.pdf
  15. ^ Advanced Computer Architecture, 2E pg. 301 - Di Hwang - http://books.google.it/books?id=m4VFXr6qjroC&pg=PA301&lpg=PR10&focus=viewport&dq=Multiprocessors+and+Multicomputers+7.2+Cache+Coherence+and+Synchronization&hl=it
  16. ^ Cache memory and related consistency protocol, Inventor Ferruccio Zulian, Bull HN ISI - https://www.google.com/patents/EP0396940B1?cl=en
  17. ^ Forward state for use in cache coherency in a multiprocessor system - Intel -https://www.google.com/patents/US6922756
  18. ^ Comparing Cache Architectures and Coherency Protocols on x86-64 Multicore SMP Systems - https://people.freebsd.org/~lstewart/articles/cache-performance-x86-2009.pdf
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica