Memoria cache

Da Wikipedia, l'enciclopedia libera.

La memoria cache (in inglese cache memory o memory cache o qualche volta anche CPU Cache), in informatica è una memoria veloce, relativamente piccola, non visibile al software, cioè completamente gestita dall'hardware, che memorizza i dati più recentemente usati della memoria principale (MM - Main Memory) o memoria di lavoro del sistema.

CPU cache

"CPU cache" è un termine non comune ed è raramente o per niente usato sia in letteratura che negli ambienti industriali tra gli esperti del settore. Per esempio, nei documenti relativi ai brevetti (USA), il termine "CPU cache" è usato meno del 2% dei casi[1] rispetto al termine "Cache Memory" (83%)[2] e "Memory Cache" (15%)[3]. La Cache Memory è una funzione associata ad una memoria e non ad uno specifico utente di questa funzione. Questa funzione può essere usata da una CPU, o in Shared Cache da un gruppo di CPU o Core o Nodi, o anche associata a un gruppo di memorie remote nei sistemi NUMA, o in generale da qualsiasi device che può accedere ad una memoria principale. Il termine "CPU cache" è perciò troppo restrittivo e quindi inappropriato (vedi per es. Cache remota - cache delle memorie remote).

La funzione della memoria cache è di velocizzare gli accessi alla memoria principale aumentando le prestazioni del sistema. Inoltre nei sistemi multiprocessori con memoria condivisa, permette di ridurre il traffico del bus di sistema e della memoria principale che è uno dei maggiori colli di bottiglia di questi sistemi.

La memoria cache fa uso della tecnologia veloce SRAM, contro una più lenta DRAM della memoria principale, connessa direttamente al processore.

Indice

Descrizione[modifica | modifica wikitesto]

Definizione generale[modifica | modifica wikitesto]

« La Cache è una memoria che memorizza dati temporanei "in modo silenzioso" al più alto livello di utilizzazione per un veloce riuso. »

Significato del nome[modifica | modifica wikitesto]

Il termine "cache" deriva dal francese (pronuncia in francese "cascé", in inglese "kesh"), e significa "nascosto".

Questo termine ha molti significati, in dipendenza dal contesto. Esempi sono: Disk cache, TLB - Translation Lookaside Buffer (Page Table cache), Branch Prediction cache, Branch history table, Branch Target Address Cache, Trace cache, che sono memorie fisiche. Altre sono memorie gestite dal software per memorizzare dati temporanei in spazi di MM riservati (ancora Disk cache, Page cache, System cache, Application cache, Database cache, Web cache, DNS cache, Browser cache, Router cache, ecc.). Alcune di queste sono solamente "Buffers" (memorie tampone), cioè memorie non-associative con accesso sequenziale (stringhe di dati) rispetto agli accessi casuali tramite una associazioni di indirizzo memoria-cache delle classiche cache.

« Il termine "Cache Memory" o "Memory Cache" o brevemente "Cache" senza nessuna altra specificazione, generalmente si riferisce ad una memoria nascosta che memorizza un sottoinsieme del contenuto della memoria principale e precisamente le "Istruzioni" di un programma e i relativi "dati" su cui operare. »

Principi Funzionali della Cache Memory[modifica | modifica wikitesto]

Schema di funzionamento della cache
  1. Nelle operazioni di lettura della MM, per prima cosa il gestore della cache verifica se il dato è memorizzato nella cache.
  2. In caso di verifica affermativa (Hit) il dato è direttamente e velocemente trasferito dalla cache al processore senza coinvolgere la MM
  3. Altrimenti (Miss) il dato è letto dalla MM

Il funzionamento della Cache Memory si basa principalmente su due "principi di località" (vedi Locality of reference):

  • Località temporale (Temporal locality)

« Dati recentemente usati hanno un'alta probabilità di essere nuovamente usati a breve. »

Una cache memorizza solo un sottoinsieme dei dati della MM - the most recent-used - i dati più recentemente usati (MRU). I dati letti dalla MM sono temporaneamente memorizzati in cache. Se il processore richiede lo stesso dato, questo è fornito dalla cache. La cache è efficiente perché loop brevi di istruzioni e routine (piccoli programmi) sono strutture comuni di programmi e generalmente diverse operazioni sono eseguite sugli stessi dati e variabili.
  • Località spaziale (Spatial locality)

« Se un dato viene referenziato, è molto probabile che dati adiacenti siano a breve a loro volta acceduti. »

Istruzioni e i dati sono trasferiti dalla MM alla cache in blocchi fissi (cache blocks), noti come cache lines (linee di cache). La dimensione della linea di cache è nel range di 4-512 byte[4], cosicché più di un dato da processare (4/8 byte) è memorizzato in ciascuna cache entry (indirizzo di cache). Dopo il primo accesso alla MM, tutti i dati relativi alla linea di cache sono disponibile nella cache stessa.
Molti programmi sono altamente sequenziali. La successiva istruzione generalmente è all'indirizzo successivo di memoria. I dati sono generalmente strutturati e i dati in queste strutture sono normalmente memorizzati in posizioni continue di memoria (stringhe di dati, tabelle, ecc.).
Grandi linee di cache aumentano la località spaziale ma aumenta anche il numero di dati invalidati in casi di rimpiazzo della linea (vedi Replacement policy).
(Nota - Per brevità il termine "dato" sarà spesso usato al posto dei termini "linea di cache" e "blocco di cache")

Efficienza della cache[modifica | modifica wikitesto]

L'efficienza della cache è misurata in termini di "Hit Rate". L' Hit Rate rappresenta la percentuale di Hits (dato trovato in cache) rispetto al numero totale degli accessi alla cache. Il contrario di "Hit" è denominato "Miss".

L'efficienza della cache dipende da diversi elementi: dimensione della cache, dimensione della linea di cache, tipo e architettura (vedi sotto) e dalle applicazioni. Una buona figura di rendimento, per applicazioni commerciali, può essere compresa nel range di 80-95 % di hit[5].

Struttura ed organizzazione della cache[modifica | modifica wikitesto]

Ci sono tre strutture base e due (più uno) tipi di cache:

  • Cache Fully Associative (cache completamente associativa)
  • Cache Direct Mapped (cache mappata direttamente)
  • Cache Set Associative (cache parzialmente associativa)

Tipi:

  • Instruction cache (cache delle istruzioni)
  • Data cache (cache dei dati)
  • Stack cache
- una speciale "Data cache" chiamata Stack cache (vedi sotto Stack cache)

Cache Fully Associative[modifica | modifica wikitesto]

Fully Associative Cache

Ogni blocco di memoria può essere memorizzato in qualsiasi posizione della cache. È chiamata "fully associative" (completamente associativa) perché ogni dato memorizzato in cache è associato al suo indirizzo completo di memoria.

La cache è divisa in due banchi: la Directory (indice guida) e il banco Data (dati). La Directory è divisa a sua volta in due campi, data attribute bit (bit di attributo dati) o State (stato), e indirizzo dati ADD (indirizzo del blocco di memoria).

I bit di attributo dati include il Valid bit (bit di validità) e può includere anche diversi altri bit di stato come il Modified bit (M) (bit di modifica), Shared bit (S) (bit di condivisione) e altri (vedi sotto Stati della Cache). Oltre a questi bit possono essere inclusi anche i "bit di protezione" come Supervisor/User (Supervisore/Utente) e Write protection - "protezione di scrittura".

Nella cache Fully Associative viene memorizzato in cache l'indirizzo completo del blocco di memoria. Quando un dato è letto dalla cache, tutti gli indirizzi memorizzati nella "Directory" sono contemporaneamente confrontati con l'indirizzo del blocco di memoria del dato richiesto. Se un indirizzo viene trovato con dato "valido" (hit) il dato corrispondente viene letto dalla cache. In caso di miss il blocco del dato viene letto dalla MM. Il dato letto dalla MM viene anche poi memorizzato in cache che rimpiazzerà (sovrascriverà) una linea di cache scelta in accordo con la politica di rimpiazzo (Replacement policy)

La cache Fully Associative ha un'alta efficienza. Il dato può essere memorizzato in qualsiasi posizione della cache, ma è costosa in termini di circuiti. Necessita di vie di accesso simultanee indipendenti ed un comparatore per ogni entry (entrata) di cache. Perciò le dimensioni di questa cache è in genere molto piccola ed è usata solamente per casi specifici (per es. nel TLB). Normalmente non è mai usata come Cache Memory, ma vengono invece usate le Direct-Mapped e le Set-Associative cache.

Cache Direct Mapped[modifica | modifica wikitesto]

Direct Mapped Cache

Nella cache Direct Mapped - Mappata Direttamente ogni blocco di memoria può essere memorizzato in una sola entry di cache. La entry (cioè la posizione di cache) dove memorizzare il blocco è direttamente derivata dall'indirizzo di memoria (da cui il nome "Direct-Mapped" - mappata direttamente).

Cache addressing

La dimensione della cache è più piccola della MM, perciò l'indirizzo di memoria deve essere ridotto per adattarsi allo spazio di cache. Tutti i dati di memoria devono poter essere memorizzati in uno spazio più piccolo, ma ovviamente non tutti contemporaneamente. Molti algoritmi, chiamati hash coding (o hashing), sono usati per far questo. La soluzione comune[6] per ottenere l'indirizzo di cache è di usare direttamente una parte dell'indirizzo di memoria, e precisamente il campo chiamato Index (indice), cioè, escludendo l'offset, i bit meno significativi dell'indirizzo (Least significant bit - LSB), vedi fig. Cache addressing. L'offset (offset della linea) è invece il campo dell'indirizzo usato per l'indirizzamento interno della linea di cache a livello di byte. Per esempio avendo un indirizzamento di memoria a 32 bit (4 GB di spazio), e una dimensione di cache di 4 MB con una linea di cache di 256 B, i bit meno significativi (8-21), l'Index, sono usati per selezionare l'indirizzo della linea di cache. Questa soluzione di indirizzamento lineare, nella Demand-Paging Virtual memory (Memoria virtuale), (vedi anche sotto Indirizzamento Virtuale), permette la memorizzazione di una pagina completa di memoria (Memory page) nella cache.

Tutti i dati aventi lo stesso Index, chiamati sinonimi vengono memorizzati nella stessa entry, perciò solo un sinonimo alla volta può essere memorizzato nella cache (conflitto di sinonimi). I sinonimi differiscono tra loro per l' MSB (Most Significant Bits - bit più significativi dell'indirizzo).

Per distinguere i vari sinonimi l'MSB denominato Tag dell'indirizzo (targhetta dell'indirizzo) è memorizzato nella directory della cache (nell'esempio precedente i bit (22-31). Quando un dato viene letto dalla cache, l'MSB della directory della cache è confrontato con l'MSB dell'indirizzo di memoria del dato da leggere. Come per la cache Fully Associative, in caso di hit, il dato è letto dalla cache, altrimenti in caso di miss, dalla memoria.

La distanza tra due sinonimi, in termini di indirizzo, è un multiplo della dimensione della cache. Il conflitto di sinonimi diminuisce con l'aumentare della dimensione della cache perché la distanza tra sinonimi aumenta.

In questo tipo di cache una sola linea di cache alla volta viene selezionata, di conseguenza è necessario un solo comparatore.

Per minimizzare il problema dei sinonimi viene utilizzata la Set Associative cache.

Set Associative Cache

Cache Set Associative[modifica | modifica wikitesto]

La cache Set Associative (o multi-via-direct-mapped ) è una combinazione dei due approcci precedenti ed è usata per ridurre il conflitto tra sinonimi.

Questa cache è composta da un set di identiche cache Direct Mapped, indirizzate nello stesso identico modo, cosicché per ciascuna entry è disponibile un "set" (gruppo, way-vie) di alternative linee di cache per memorizzare più di un sinonimo. I sinonimi possono essere memorizzati in qualsiasi set delle entry selezionate, in funzione dell'algoritmo di ''politica di rimpiazzo'' utilizzata, generalmente LRU.

Normalmente il numero di set è nel range di 2-8/16 o più, sino a 48 (AMD Athlon[7]) e 128 (POWER3[8]), in funzione del tipo di cache (Istruzioni/Dati).

Nella cache Set Associative viene usato un comparatore di indirizzi per ogni set.

(Nota: Una cache Direct Mapped può essere vista come una cache Set Associative con un solo set ed una cache Fully Associative con n-linee come una cache Set Associative a n-vie (set) con una sola entry).

In dipendenza dalla politica di rimpiazzo "Replacement policy" adottata, la Directory può o no contenere anche i Replacement bits (bit di rimpiazzo) per selezionare la linea di cache candidata per il rimpiazzo.

Replacement Policy[modifica | modifica wikitesto]

(Politica di Rimpiazzo - deallocazione della linea di cache)

Quando è disponibile più di una entry per memorizzare un dato, come nel caso di cache Fully Assiociative e Set Assiociative, la entry che dovrà essere rimpiazzata è selezionata in base alla "Replacement policy" adottata.

Ci sono differenti politiche[9].

Le principali sono:

  • LRU - (Least Recently Used - Meno Recentemente Usato)
  • FIFO - (First-In First-Out - Primo ad Entrare Primo ad Uscire)
  • LFU - (Least Frequently Used - Meno Frequentemente Usato)
  • Round-robin (girotondo dall'uccello Round-robin - selezione ciclica)
  • Random (casuale)
- LRU
- Comunemente usato per le cache Set Associative.
- Separatamente per ciascun Set ad ogni entry è associato un "contatore di età" (replacement index). La capacità max di questo contatore è uguale al numero di Set. La linea di cache di una entry avente il più alto valore è quella che sarà rimpiazzata da una nuova linea di cache. Ogni volta che una linea di cache è acceduta il suo contatore è settato a zero, mentre gli altri contatori delle altre linee della stessa entry con valore minore della linea di cache acceduta sono aumentati di 1.
Per esempio, con una cache 4-way Set Associative e perciò due bit per contatore, con i contatori aventi i valori 0-3-2-1 (Set da 1 a 4), l'ordine di rimpiazzo sarà 4°-1°-2°-3°. Il più alto valore (3) è il più vecchio e il più basso (0) il più recente (o potrebbe anche essere viceversa in un'implementazione alternativa).
- se il Set 3 (valore 2) è acceduto, la situazione finale sarà: valore dei contatori 1-3-0-2, ordine di rimpiazzo 3°-1°--2°. Il Set 3 è spostato all'ultimo posto.
- In caso di rimpiazzo di una linea di cache, la linea sostituita sarà il Set 2 e i contatori diverranno 2-0-1-3: ordine di rimpiazzo 2°-4°-3°-1°.
- FIFO
- Usato nelle cache Set Associative
- Lo stesso algoritmo di LRU ma con la differenza che i contatori sono aggiornati solamente quando una linea di cache è rimpiazzata. La linea di cache con il valore più alto è rimpiazzata e il suo contatore è settato a zero, mentre tutti gli altri contatori sono aumentati di 1.
- LFU
- Algoritmo più efficiente ma il più costoso. Generalmente non usato
- Round-robin
- Usato nelle cache Full Associative
- Un puntatore (pointer) seleziona la linea di cache che dovrà essere rimpiazzata. Questo puntatore è aumentato di 1 ad ogni rimpiazzo di una linea di cache. Questo è fatto in modo ciclico. È necessario un solo un puntatore
- Semplice e poco costoso da implementare
- Random
- Usato nelle cache Full Associative
- Round-robin aggiornato ad ogni clock/accesso invece che ad ogni rimpiazzo.
- Semplice e poco costoso da implementare

Tipi di cache[modifica | modifica wikitesto]

Cache Istruzioni e cache Dati[modifica | modifica wikitesto]

Nella MM sono memorizzati due tipi di informazioni, le Istruzioni (anche chiamate codice) e Dati (come operandi).

  • Le cache Unificate memorizzano entrambe.
  • Nelle cache Separate, Istruzioni e Dati sono memorizzati in cache dedicate. Queste cache sono chiamate brevemente "I-Cache" per le cache Istruzioni e "D-Cache" per le cache Dati.

Ci sono tre vantaggi nelle cache separate:

1. Riduzioni delle interferenze tra due diverse strutture di dati.
- Più sequenziali le Istruzioni, più casuali i Dati. Inoltre questo approccio permette differenti tipi di implementazione. Generalmente cache Associative da 2 a 4/8-vie per le la cache Istruzioni, da 4 a 16-vie o più (128) per la cache Dati[8].
2. Permette l'implementazione dell'architettura "Harvard"
- Questo tipo di architettura aumenta il parallelismo di esecuzione del processore perché consente l'accesso alle Istruzioni successive (prefetch, accesso anticipato) in parallelo con l'accesso e l'esecuzione dei Dati relativi alle istruzioni precedenti (vie di accesso separate indipendenti).
3. Nessuna interferenza, nei sistemi multiprocessori, tra l'attività di Snoopy e l'attività del processore sulla I-Cache.
- L'attività di Snoopy è fatta generalmente solo nella D-Cache (vedi sotto Write policy e Interferenze tra Snoopy e Attività del Processore ).

Cache Non-Blocking[modifica | modifica wikitesto]

(cache non bloccante)

La maggior parte delle cache possono trattare solo una richiesta alla volta. Se una richiesta è fatta e c'è miss, la cache deve aspettare il dato dalla memoria, ed in attesa di questo, la cache rimane '"bloccata'" . Una cache non-blocking (o lock-free ) ha la possibilità di lavorare su altre richieste mentre è in attesa dei dati "miss" dalla memoria.

Write Policy[modifica | modifica wikitesto]

(Politica di scrittura)

La politica di scrittura determina come vanno gestite le scritture in memoria di dati memorizzati in cache

Generalmente solo la D-Cache è interessata, perché normalmente le istruzioni non sono auto-modificanti, e in caso di auto-modifica, il software forza la scrittura di questo codice (Istruzioni) solo in memoria senza coinvolgere la cache (vedi ad esempio AMD64 Self-Modifying Code[10])

Ci sono due tipi di politiche:

- Write Through
- Write-Back (o Copy Back)

Write Through[modifica | modifica wikitesto]

(scrittura passante)

  • Il dato viene scritto contemporaneamente sia in cache che in memoria o in cache e poi in memoria (da cui il nome)

Write-Back (or Copy Back)[modifica | modifica wikitesto]

(scrittura indietro o copia indietro)

  • Il dato è aggiornato solamente nella cache. Viene "scritto indietro" in memoria solo quando è necessario, per esempio in casi di "rimpiazzo" (sovrascrittura) della linea di cache o quando richiesto da altre cache. Questo riduce il traffico di memoria e di bus perché il successivo aggiornamento della linea di cache viene fatto solo nella cache senza coinvolgere la memoria. Nella Directory della cache, in questi casi viene attivato (settato) il bit "D" o "M" (Dirty = sporco o Modificato) - (vedi sotto Stati della Cache).

In caso di miss in scrittura si hanno due differenti soluzioni:

Write Allocate[modifica | modifica wikitesto]

(scrittura con allocazione)

Write allocate on miss (allocazione in scrittura su miss) detta anche Fetch-on-write (acquisire per scrivere) o RWITM (Read With Intent To Modify - lettura con intenzione di modifica) o Read for Write - lettura per scrittura
  • In caso di miss in scrittura, la linea di cache è letta prima dalla Main Memory o da una cache in caso di Cache Intervention (intervento di cache), poi è aggiornata (modificata) in cache con il nuovo dato (scrittura parziale della linea: byte, halfword, word o doubleword - 8, 16, 32 o 64 bit, dipendente dal parallelismo operativo intrinseco del processore)

Write no-Allocate[modifica | modifica wikitesto]

(o no-Write allocate - non allocazione)

  • Il dato è scritto direttamente in MM "by-passando" la cache
- Write allocate è normalmente associata al write-back. Write no-allocate può essere o non associata al write-through.

Livelli di Cache[modifica | modifica wikitesto]

In un sistema può essere usata più di una cache. Le cache sono organizzate in livelli gerarchici. Sono possibili sino a 4 livelli, L1-L4 o più[11].

Una cache più grande ha un hit-rate migliore ma un tempo di latenza maggiore. Una cache multi-livello garantisce un accesso veloce con un alto hit-rate.

Generalmente la cache multi-livello opera verificando prima la cache più piccola di più basso livello, il Livello 1 (L1). Se si ha hit il processore procede velocemente. Se la cache più piccola da miss, viene controllata la successiva cache più grande (L2), e così via fino al più alto livello.

Il miglioramento della tecnologia permette sufficiente spazio per implementare una piccola cache L1 all'interno del chip del processore. Una cache interna è più veloce di una esterna, ma ha un più basso hit rate dovuto alla sua minore dimensione, tipicamente nel range tra 8KB a 64KB. Per aumentare la dimensione globale della cache e così l'hit rate, si usa una cache L2 maggiore strettamente accoppiata al processore. Una dimensione tipica della cache L2 è nel range da 64KB a 8MB. La cache L2 può essere esterna o interna al chip o al package del processore. In questo ultimo caso perciò può essere usata una ulteriore cache L3 esterna ancora maggiore (4-256MB). Nei sistemi multi-core la L3 può essere implementata in un MCM (Multi-Chip Module) (vedi per es. POWER4 IBM, AMD Bulldozer).

Gerarchia delle Cache Multi-livello

Normalmente la L1 è una cache Set Associative separata Istruzioni e Dati. La cache L2 può essere unificata o separata, come pure essere una cache Direct Mapped o Set Associative. Lo stesso per la cache L3.

Funzione gerarchica delle cache multi-livello[modifica | modifica wikitesto]

- L1     →     All'interno del chip del processore. Accesso veloce.
    - Range 8KB - 64KB (POWER8[4])
- L2     →     Per aumentare la dimensione globale e per la coerenza dei dati
    - Snoopy per il multiprocessor bus-based (basato sul bus),
      shared (condivisa) per il multi-core.
    - Può essere esterna o interna al chip del processore.
    - Range 64KB - 8MB (16MB IBM RS64-IV)[4]
- L3     →     Per aumentare la dimensione globale. Usata anche come Victim cache di L2
      (vedi per es. Power5 e AMD) e per lo snoopy nei sistemi SMP.
    - Range 4MB - 128MB[4][12]. L3 è usata se L2 è interna al chip o al die
- L4     →     Cache remota per cc-NUMA - Clustering Systems
    - Range > L3 (512MB o più) dipendente dal numero di Nodi
    - usata qualche volta come Victim cache di L3 nei processori grafici (GPU)[13].

Nota: La dimensione della linea della cache di livello superiore può essere più grande od uguale a quella di livello inferiore.

Cache Inclusiva ed Esclusiva[modifica | modifica wikitesto]

La cache può essere Inclusiva o Esclusiva.

  • Inclusiva significa che il contenuto della cache L1 è incluso anche nella cache L2, cioè L1 è un sottoinsieme della L2.
  • La cache L2 memorizza una copia della L1 più i dati "espulsi " dalla L1 (dati espulsi in caso di rimpiazzo della linea).
  • La cache L2 inclusiva implica che L1 deve essere una write-through verso L2.
  • La dimensione effettiva della cache globale del sistema è eguale alla sola dimensione della L2.
Stessa relazione tra L3 inclusiva e L2, se L3 è usata.
  • Operazioni
  • Miss in L1 e Hit in L2
- La linea di cache di L2 è copiata in L1.
  • Miss in L1 e in L2
- Il dato è letto dalla memoria e memorizzato sia in L1 che in L2, rimpiazzando in L1 la stessa linea rimpiazzata in L2, se L1 ne contiene una copia, altrimenti la linea di cache da rimpiazzare in L1 sarà scelta secondo la politica di rimpiazzo utilizzata.
- Quando una linea in L2 è rimpiazzata, dovuta ad un conflitto di miss in L2, anche l'eventuale copia di L1 deve essere estromessa (evicted) per mantenere l'inclusività.
  • Esclusiva (o non Inclusiva) significa che il dato può essere memorizzato solo in una cache.
  • L2 cache contiene solo linee di cache copy-back (scritte indietro da L1 a L2), che sono state espulse dalla L1 a causa di conflitti di miss (victim lines - linee vittime). Questo tipo di cache viene perciò anche chiamata "victim cache"
(Nota - La dimensione della cache globale è la somma delle dimensioni di tutte e due le cache).
Stessa relazione tra L3 esclusiva e L2, se L3 è usata.
  • Operazioni
  • Miss in L1 e Hit in L2
- Le linee di cache di L1 e L2 vengono scambiati fra loro, cioè la linea di cache di L1 viene memorizzata in L2 e la linea di L2 in L1.
  • Miss in L1 e in L2
- Il dato letto dalla memoria è memorizzato direttamente in L1 e la linea di cache rimpiazzata di L1 (victim data) è trasferita in L2 rimpiazzando un'altra linea di cache secondo la politica di rimpiazzo usata.
  • Inclusività vs Esclusività
L'inclusività è preferibile nei sistemi multiprocessori/multi-core bus-based, cioè basati sul bus per la coerenza dei dati, altrimenti il controllo di coerenza deve essere fatto in tutte le cache (vedi sotto Interferenze tra Snoopy e Attività del Processore). L'inclusività semplifica la coerenza delle cache.
L'aspetto negativo della cache inclusiva è che la cache L2 contiene dati ridondanti, questo significa una riduzione della dimensione della cache globale. Questo è vero solo se le dimensioni delle cache L1 e L2 sono comparabili. Spesso la dimensione di L2 è un ordine di grandezza rispetto a L1, perciò la riduzione del hit-rate dovuto alla riduzione della dimensione globale può essere molto bassa (qualche percento), considerando anche che nel range di 80-95 % di hit-rate, aumentando la dimensione, il guadagno del hit-rate tende rapidamente ad essere piatto[5].
Le stesse considerazioni possono essere fatte per la cache L3 rispetto a L2 (vedi per esempio Shanghai (AMD) vs Nehalem-EP (Intel)[14]).

Shared Cache[modifica | modifica wikitesto]

(cache condivisa)

I processori possono condividere una cache comune. Le cache condivise generalmente sono usate per la coerenza dei dati nei sistemi multi-core (Multi-chip) e per la riduzione dei costi (vedi sotto Shared Cache - Protocollo di Coerenza)

Cache Multi-Banco e Multi-Porta[modifica | modifica wikitesto]

(Multi-bank e Multi-ported)

Le architetture Superscalar processor (processori superscalari = multi unità operative) sono in grado di eseguire simultaneamente istruzioni in parallelo (sfruttando il parallelismo intrinseco delle istruzioni stream / multithread - flusso continuo/multi ramificazioni). In questo genere di processori ci sono diversi unità funzionali dello stesso tipo con dei circuiti addizionali per il "dispaccio" delle istruzioni alle varie unità. Nella maggior parte di questi sistemi "superscalar" includono più di una unità aritmetica-logica (unità per operazioni aritmetiche e logiche). Per esempio in IBM POWER3[15] sino a otto istruzioni, due floating point (virgola mobile), due load/store (lettura/scrittura = spostamento dati - in inglese "move"), tre fixed point - (virgola fissa), due singolo ciclo, un multi-ciclo e un "branch" (istruzione di salto - le istruzioni vengono eseguite in modo sequenziali sino a trovare un'istruzione di "salto" che salta ad una nuova sequenza) che possono essere eseguite nello stesso ciclo. Le Istruzioni disponibili sono inviate "fuori ordine" (out of order ) dalle code di uscita, consentendo a queste istruzioni, sia dello stesso tipo che diverso, di essere eseguite fuori ordine per mezzo dell'uso della tecnica dei Register renaming (sostituzione registri) per la sincronizzazione e il riordino dei risultati.

L'esecuzione parallela delle istruzioni richiede accessi simultanei alla D-cache L1. Conflitti avvengono quando due o più richieste accedono simultaneamente allo stesso banco di cache. Questi conflitti possono parzialmente essere eliminati tramite l'uso di cache multi-banco e/o di multi-porte[16][17][18]

Ci sono diverse soluzioni[19][20]:

  • Cache Multi-banco
  • Cache Multi-porte
  • Multiple copie
  • Multi-porte Virtuali
  • Soluzione ibrida

Cache Multi-banco[modifica | modifica wikitesto]

La D-cache L1 è divisa in banchi multipli con indirizzi indipendenti.

Ci sono due approcci:

  • Indirizzamento lineare
  • Cache interleaving (cache interlacciata)

Indirizzamento lineare[modifica | modifica wikitesto]

I banchi sono indirizzati in parallelo tramite un crossbar (connessioni dirette incrociate). L'indirizzo è lineare, cioè il successivo indirizzo dell'ultimo indirizzo di un banco è il primo indirizzo del banco successivo. I banchi sono selezionati in sequenza tramite l'uso dei bit più significativi (MSB) dell' "Index" dell'indirizzo (per esempio, con 8 banchi, i tre bit 21-19 dell'esempio in Cache addressing). I banchi multipli possono supportare multiple richieste per ciclo quando queste non indirizzano lo stesso banco.

L'approccio multi-banco può essere efficiente per applicazioni che hanno una scarsa località spaziale dei dati (dati statisticamente indipendenti), ma per applicazioni con una buona località spaziale, come negli accessi consecutivi, accessi simultanei multipli non sono permessi causa "conflitti di banco" (bank collision - collisioni di banchi)

Cache interleaving[modifica | modifica wikitesto]

(cache interlacciata)

8-way Cache Interleaving

Linee di cache consecutive sono memorizzate su banchi consecutivi. L'indirizzamento delle linee di cache è "interlacciato" (distribuito orizzontalmente) tra i banchi come mostrato nella fig. a lato. I banchi sono selezionati tramite i bit più meno significativi dell' "Index" dell'indirizzo (per esempio, con una 8-way interleaving (interlacciamento a 8 vie), i bit 10-8 dell'esempio sopra in Cache addressing). Comunemente il numero di banchi varia da due, quattro od otto (vedi ad es. IBM POWER3[21]), chiamati two-way, four-way o eight-way interleaving rispettivamente.

La cache interleaving da vantaggi specialmente nelle operazioni su stringhe di dati multipli. Per esempio, avendo una cache two-way interleaving (indirizzo pari nel Banco 0 e dispari nel Banco 1) e due programmi (threads) che operano su due stringhe indipendenti, il primo programma può accedere al Banco 0 mentre il secondo al Banco 1. Nel successivo accesso, il primo programma può accedere al Banco 1 mentre il secondo al Banco 0, e così via alternativamente. In caso di "conflitto di banchi" (bank collision), cioè accesso simultaneo allo stesso banco, un programma all'inizio deve aspettare un ciclo, poi può iniziare. Anche negli accessi casuali simultanei multipli questo sistema offre vantaggi, dipendente dal numero di banchi. La probabilità di conflitto diminuiscono all'aumentare del numero di banchi.

Esempio di interleaving: la cache L1 di POWER3[22] con interleaving a 8-vie è in grado di servire due "load" (letture), una "store" (scrittura) e una rilettura (reload) di una linea di cache per ciclo.

Cache Multi-porte[modifica | modifica wikitesto]

(multi-port cache o true multi-porting o ideal multi-porting

Porte multiple permettono di fare accessi paralleli multipli alla cache nello stesso ciclo di clock, che operano in modo indipendente fra loro[4][23].

Le cache multi-porte permettono di ottenere la più alta frequenza di accesso per ciclo, ma sono complesse e perciò lente e costose. Inoltre comporta l'uso di strutture di celle non standard. Mentre una singola celle di memoria statiche richiede 6 transistor a effetto di campo (field-effect), per aver una porta doppia sono necessari 2 transistor in più. Perciò questa soluzione può essere usata per solo poche porte, normalmente due per le letture e una per le scritture (es. POWER4 IBM).

Multiple copie[modifica | modifica wikitesto]

(mirroring o cloning)

Cache con "n" identiche copie (cloni) con indirizzamento simultaneo indipendente. Limitazioni: copie replicate senza benefici di spazio di memorizzazione. Inoltre le richieste di scrittura devono essere fatte simultaneamente su tutte le copie, cosicché nessuna altra richiesta può essere inviata in parallelo. Poiché circa il 30% di accessi alla memoria sono scritture[24], questa soluzione ha dei severi limiti.

Multi-porte Virtuali[modifica | modifica wikitesto]

(time division multiplexing - divisione di tempo distribuita)

La "time division multiplexing" è una tecnica che può essere anche riferita come "cache over-clocking" cioè clock con frequenza maggiorata. Funzionamento della cache con frequenza 2x (3x, 4x) della frequenza del processore in modo che la cache può essere acceduta due (tre, quattro) volte per ciclo (clock).

Soluzione ibrida[modifica | modifica wikitesto]

Combinazione della soluzione cache interleaving con multi-porte. I banchi multipli interleaving permettono accessi paralleli a basso costo mentre le porte multiple riducono i conflitti di banco.

Coerenza della cache[modifica | modifica wikitesto]

(Cache Coherency)

Nei sistemi come SMP - Symmetric Multiprocessor System, multi core e cc-NUMA dove viene usata una cache dedicata per ogni processore, core o nodo, si può verificare un problema di consistenza dei dati quando uno stesso dato è memorizzato in più di una cache. Questo problema si verifica quando un dato 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)
- Nota: La coerenza dai dati generalmente riguarda solo i dati (come operandi) e non le istruzioni (vedi Self-Modifying Code).

Gli schemi si possono classificati in base a:

- Schema Snoopy vs Directory e vs Shared caches
- Protocollo Write through vs Write-back (basati sull'ownership - 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 addottati per mantenere la coerenza dei dati.

  1. Bus watching o Snooping - generalmente usato per i sistemi SMP - Symmetric Multiprocessor System/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 di Coerenza Snoopy[modifica | modifica wikitesto]

(protocollo di coerenza basato sullo Snoopy)

Protocollo usato nei sistemi con bus, come ad esempio nei sistemi SMP

SMP - Sistema Multiprocessore Simmetrico[modifica | modifica wikitesto]

   Sistema operante sotto un unico Sistema Operativo con due o più processori omogenei e
   con una Main Memory centralizzata condivisa.

SMP - Symmetric Multiprocessor System

Ciascun processore ha una propria cache che agisce come ponte tra il processore e la Main Memory. La connessione è fatta usando un System Bus (bus di sistema) o un crossbar (connessioni incrociate)[25] (xbar) o un mix dei due precedenti sistemi, bus per gli indirizzi e crossbar per i dati (Data crossbar)[26][27][28].

Il limite maggiore di questi sistemi è il traffico e larghezza di banda di memoria (quantità di dati al sec.). La banda può essere aumentata usando un largo canale dati, un crossbar dati, la memory interleaving e transazioni di dati fuori ordine (out of order data transaction). Il traffico può essere ridotto usando una cache che agisce da "filtro" verso la memoria condivisa, cioè la cache è un elemento essenziale nei sistemi SMP con memoria condivisa (shared-memory).

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 consistenza dati nasce quando un dato è modificato in una sola cache.

Il 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" (dal nome del cane Snoopy dei cartoni animati).

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[29].

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.

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", etc.). Il tipo di azioni sono dipendenti dall'implementazioni adottata. Protocolli aventi gli stessi stati e le stesse regole di transazioni possono essere differenti, per esempio il protocollo MESI con "shared intervention" (intervento su dati condivisi puliti (clean)) e MESI senza "intervention" (vedi sotto). 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 una implementazione diversa delle stesse funzionalità (vedi sotto)

I più comuni e popolari protocolli sono considerati il protocollo 4-stati conosciuto con l'acronimo MESI e il 5-stati MOESI, termini usati giusto per una facile pronuncia e derivati dal nome degli stati usati. 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 ad una classe di protocolli piuttosto che ad uno specifico protocollo.

Stati della Cache[modifica | modifica wikitesto]

I protocolli MESI e MOESI sono spesso chiamati con nomi differenti.

  • 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 è l' "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[30][31], MESIF - Intel[32][33]). 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)[23][34].
Nota - 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[35][36]. Tutti i protocolli che usano questo stato saranno riferiti come R-MESI type.
  • H=Hover - H-MESI (stato addizionale del protocollo MESI)[37]
- Lo stato Hover (H) (sospeso) permette ad 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[35][38][39]

Vari Protocolli di Coerenza[modifica | modifica wikitesto]

                                                                                Protocolli

  • SI                                                                       Write Through
  • MSI                                                                    Synapse[29]
  • MEI                                                                    IBM PowerPC 750[40], MPC7400[38]
  • MES                                                                   Firefly[29]
  • MESI                                                                  Pentium II[41], PowerPC, Intel Harpertown (Xeon 5400)
  • MOSI                                                                 Berkeley[29]
  • MOESI                                                              AMD64[42], AMD Opteron[25], MOESI[43], T-MESI IBM[39]

                                                                                Terminologia usata

  • Illinois                                                                 D-VE-S-I                      (= MESI esteso)[29][44]
  • Write-once o Write-first                                      D-R-V-I                         (= MESI)  [29][45][46]
  • Berkeley                                                             D-SD-V-I                      (= MOSI)  [29]
  • Synapse                                                             D-V-I                            (= MSI)    [29]
  • Firefly                                                                 D-VE-S                        (= MES) DEC[29]
  • Dragon                                                               D-SD (SM?)-SC-VE   (= MOES) Xerox[29]
  • Bull HN ISI                                                         D-SD-R-V-I                  (= MOESI)[47]
  • Protocollo MERSI (IBM) / MESIF (Intel)            R=Recent - IBM PowerPC G4, MPC7400[30][38]

                                                                                F=Forward - Intel[32] , Intel Nehalem[14][48][49]

  • RT-MESI                                                           T=Tagged - IBM[39]
  • HRT-ST-MESI                                                   H=Hover, R=Recent,T=Tagged, ST=Shared-Tagged - IBM[35][39]

- Nota: Le principali terminologie sono SD-D-R-V-I e MOESI, perciò saranno usate entrambe


  • Protocollo POWER4 IBM                                 T-Mu-Me-M-S-SL-I  (L2 sette stati)[23]

                                                                                Mu=Unsolicited Modified - non Sollecitato Modificato Esclusivo - (M) (*)

                                                                                M=Modified Exclusive - Modificato Esclusivo

                                                                                T=Tagged - Modificato Owner non Esclusivo (O)

                                                                                Me=Valido Esclusivo - (E)

                                                                                S=Shared

                                                                                SL=Shared Last - sourced local" - (Shared Owner Locale)

                                                                                I=Invalido - (I)

(*) - Stato speciale - Richiesta per una prenotazione di lettura e scrittura di un "doubleword" (implementazioni a 64-bit)


Operazioni di Coerenza Snoopy[modifica | modifica wikitesto]

- Transazioni di Bus
- Caratteristiche dei Dati
- Operazioni di Cache
Transazioni di Bus[modifica | modifica wikitesto]

Le principali operazioni sono:

- Write Through
- Write-Back
- Write Allocate
- Write no-Allocate
- Cache Intervention
- Shared Intervention
- Dirty Intervention
- Invalidation
- Write-broadcast
- Intervention-broadcasting
- 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.
- 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 Bull HN ISl[47])
- In caso di miss il dato è letto dall' "owner" o dalla MM, poi il dato è scritto in cache (aggiornato - scrittura parziale) (vedi Write Policy)
- In caso di miss il dato è scritto in MM senza coinvolgere la cache, oppure, come nel 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 (miss 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) (*) invece che dalla MM (es. protocollo MOESI, RT-MESI, …)
(*) - Non per E (R) nella proposta originale del protocollo MOESI[43] e in alcune altre implementazioni tipo-MOESI
- 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 sotto)
  • Invalidazione
- 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[48], Dragon protocol (Xerox), Firefly (DEC).
- Nota - 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 una operazione scrittura distribuita, nel secondo caso sia in lettura che scrittura.
  • Intervento-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[38]
  • 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)
- Invalidazione è la soluzione comune.
Caratteristiche dei Dati[modifica | modifica wikitesto]

Ci sono tre caratteristiche dei dati di cache

- Validità
- Esclusività
- Ownership - Proprietà
  • 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
- 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) (*) nel tipo MOESI, (es. AMD64,[43], Bull HN ISI[47] - vedi operazione di "Read Miss" sotto)

Nota: Non deve essere confusa la definizione più restrittiva di "owner" data nel protocollo in MOESI con questa più generale definizione

(*) - Dipendente dall'implementazione

Operazioni di Cache[modifica | modifica wikitesto]

Le operazioni delle cache sono:

- Read Hit
- Read Miss
- Write Hit
- Write Miss
  • Read Hit
- Il dato è letto dalla cache. Lo stato rimane inalterato
- Avvertenza: poiché questa è una 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:
  1. - Protocollo Illinois - una rete di priorità è usata per assegnare in modo arbitrario e temporaneo la "ownership" (proprietà) ad una copia S. Il dato è fornito dalla cache selezionata. La cache richiedente è settata S (shared intervention - intervento tra dati condivisi con MM clean)
  2. - 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

  1. - In tutte 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).
  1. - 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[41]), 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.

  1. - 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 ed 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 nessuna altra azione. Lo stato è settato (o rimane) M (D)
  • Write Miss
- Write Allocate
- Operazione di Read with Intent to Modified operation (RWITM)
- Come per una 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 di Coerenza[modifica | modifica wikitesto]

- Avvertenza - 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.
- Nota - 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 protocollo HRT-ST-MESI (tipo MOESI) o un sottoinsieme o un'estensione di questi.

MESI Protocol - State Transaction Diagram
Protocollo MESI[modifica | modifica wikitesto]

  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[50])
- 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[41])
- 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 MOESI[modifica | modifica wikitesto]

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

- 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)
Illinois State Transaction Diagram
  • Operazioni
- Write Allocate
- Intervention: da M-O-E (*)
- Write Invalidate
- Copy-Back: Rimpiazzo di M-O
- (*) dipendente dal tipo di implementazione per E

Protocollo Illinois[modifica | modifica wikitesto]

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

- 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 | modifica wikitesto]

  States D-R-V-I (MESI)[29][45][46]

- 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 ISI[modifica | modifica wikitesto]

  Stati D-SD-R-V-I (MOESI)

  Protocollo brevettato (F. Zulian)[47]

- 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 - aggiornamento dell' owner) 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 Synapse[modifica | modifica wikitesto]

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

- 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 Berkeley[modifica | modifica wikitesto]

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

- 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 | modifica wikitesto]

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

- 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 | modifica wikitesto]

  Stati D-SD-VE-SC (MOES)[29]

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 | modifica wikitesto]

  Stati MERSI o R-MESI   Stati MESIF

  Protocolli brevettati - IBM (1997)[38] - Intel (2002)[51]

- 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 MOESI[modifica | modifica wikitesto]

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"[14])

I sistemi più avanzati usano solamente il protocollo R-MESI type / MESIF (IBM / Intel) o i più completi RT-MESI, HRT-ST-MESI e POWER4 IBM 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-MESI[modifica | modifica wikitesto]

  States RT-MESI

  protocollo brevettato IBM[35][39]

- 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-MESI[modifica | modifica wikitesto]

È un miglioramento del protocollo RT-MESI[39] ed è un subset del protocollo HRT-ST-MESI[35]

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-MESI[modifica | modifica wikitesto]

Protocollo IBM brevettato HRT-ST-MESI completo[35][39]

- 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 IBM[modifica | modifica wikitesto]

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

- Uso della "shared line"
- Usato in Sistemi multi-core/moduli - multi-cache L2[23]
- 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

Considerazioni generali sui protocolli[modifica | modifica wikitesto]

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
- Stati di riserva dello stato Tagged (Shared-Tagged)
- Auto aggiornamento dello stato invalido H (Hover)

Interferenze tra Snoopy e Attività del Processore[modifica | modifica wikitesto]


L'attività dello Snoopy richiede l'accesso alla Directory della cache e può essere in conflitto con gli accessi concorrenti del processore. Questa interferenza fa aumentare la latenza della cache.

Per ridurre o eliminare questa interferenze possono essere usate tre soluzioni:

  • Cache multi-livello inclusive
  • Cache Istruzioni e Dati separate
  • Dual-Port e Dual-Directory
  1. - Due o più livelli di cache "inclusive" riducono queste interferenze perché circa 85-90%[5] degli accessi del processore (per i dati) è fatto al livello più basso di cache.
  2. - Cache "Separate" Istruzioni e Dati riducono l'interferenza perché lo snoopy normalmente è fatto solamente sulla cache Dati (vedi Write Policy), perciò i conflitti sulle Istruzioni vengono eliminati.
  3. - Lo snoopy spende la maggior parte del suo tempo a monitorare un traffico parassita. Una "dual-Port Directory" (Directory con due porte) o "dual-Cache" (cache con due porte - Directory+Dati) o un "dual-Directory" (doppia Directory)[52] elimina quasi completamente le interferenze. Una porta/directory è usata per lo snoopy e l'altra per il processore (i conflitti avvengono solo quando lo snoopy e il processore fanno uso della stessa entry, ma questo evento e comparativamente raro).

Coerenza della Cache Directory-based - Message-passing[modifica | modifica wikitesto]

È noto che i sistemi SMP hanno una limitata scalabilità. La memoria multi-banco e il crossbar dati[26] permettono accessi paralleli alla memoria. L'uso di grandi cache riduce il traffico sul bus di sistema ma non le write invalidate (scrittura con invalidazione) o write-broadcast (scrittura con distribuzione). La maggiore limitazione è che l'indirizzo di memoria deve essere monitorato (snoopy) usando un unico bus. Per superare questa limitazione, viene adottata una nuova architettura chiamata "cc-NUMA ".

Il sistema cc-NUMA è un insieme di sistemi SMP chiamati "Nodi" connessi via una rete di connessione che può essere un link (collegamento) formato da un singolo o doppio anello bidirezionale o multi-anello, connessioni punto-punto[25][32] o un mix di queste (vedi ad es. sistemi IBM Power Systems[23][53]), intercessione via bus (es. NUMAq[54]), crossbar, segmented bus (bus segmentato - NUMA Bull HN ISI ex Honeywell[55]), Mesh router, ecc..

Esempi di interconnessione

Double-reverse ring
Segmented Bus
Crossbar

   La caratteristica principale del sistema cc-NUMA è di avere un'unica memoria globale condivisa e distribuita in ciascun nodo
   direttamente acceduta da tutti i processori di tutti i nodi

cc-NUMA System

In un sistema NUMA l'accesso di un processore ad una memoria remota di un nodo remoto è più lento rispetto all'accesso alla propria memoria locale. Per questa ragione questo sistema è chiamato NUMA (Non Uniform Memory Access - accesso della memoria non uniforme).

L'architettura NUMA è anche chiamata Distributed Shared Memory (DSM) - memoria condivisa distribuita[56].

Normalmente ciascun nodo è un sistema SMP, dove un processore può essere un singolo processore o un multi-core, o un mix dei due, o qualsiasi altro tipo di architettura. La fig. a lato è solo un esempio.

La differenza del tempo di accesso fra una memoria locale ed una remota può anche essere di un ordine di grandezza, in dipendenza del tipo di connessione (più veloce nel segmented bus, crossbar e interconnessione punto-punto, più lenta con la connessione ad anelli seriali).

Cache Remota[modifica | modifica wikitesto]

Terminologia:

(da un punto di vista di un nodo)

  • Memoria locale            - memoria del nodo
  • Memoria remota           - memoria degli altri nodi remoti
  • Dati locali                     - dati memorizzati nella memoria locale
  • Dati remoti                   - dati memorizzati nelle memorie remote
  • Cache remota              - cache del nodo che memorizza dati letti dalle memorie remote
  • Cache locali (L1-L3)    - cache del nodo che memorizzano dati locali e remoti

Per ridurre le differenze di accesso tra dati locali e remoti, viene utilizzata una cache remota (Remote cache). Questa cache memorizza i dati letti dalle altre memorie remote. Normalmente questa cache è inclusiva-condivisa (shared inclusive) con protocollo MESI. Le cache L1-L3 possono essere tipo MESI esteso (es. R-MESI, RT-MESI, ecc.). Ogni dato remoto memorizzato nelle cache L1-L3 è anche memorizzato in questa cache (per l'inclusività). Questa cache è il 4º livello di cache del nodo per i soli dati remoti (cache delle memorie remote), mentre le cache L1-L3 memorizzano sia dati locali che remoti (cache del nodo relativo alla memoria globale). Da un punto di vista interno di un nodo la remote cache può essere vista come un'estensione della memoria locale (dati remoti memorizzati localmente).

Poiché la funzione di questa cache è di ridurre il tempo di accesso remoto almeno come il tempo di accesso della propria memoria locale, può essere usata una tecnologia ibrida - SRAM per la directory, DRAM per la cache dei dati[57]. Questa soluzione permette di implementare cache sufficientemente grandi come richiesto da questi sistemi.

La Cache remota può memorizzare sia le istruzioni (codice) che i dati (come operandi), ma normalmente solo i dati sono memorizzati. L'accesso ai dati privati, come il codice e i dati di stack, spesso possono essere elaborati localmente copiando il codice (replicazione del codice) da un altro nodo (aumento dell'efficienza).[58]

Coerenza delle Cache in cc-NUMA[modifica | modifica wikitesto]

cc-NUMA Memory Directory

La coerenza delle cache nei sistemi cc-NUMA (Cache Coherency-NUMA) è ottenuta usando il protocollo noto col nome di Directory-based - Message-passing. Questo approccio è stato proposto per la prima volta da Censier e Feaultrier[59] e descritto anche in "The Directory-Based Cache Coherency Protocol for DASH Multiprocessor"[60].

Poiché normalmente non tutti i nodi accedono nello stesso tempo agli stessi dati, il controllo di coerenza può essere molto più efficiente se fatto in modo selettivo sui soli nodi interessati.

Nei sistemi cc-NUMA la coerenza della cache a livello di sistema (inter-nodo) è perciò fatta mediante un protocollo directory-based (basato su una directory), usando una a directory associata a ciascuna memoria locale (local memory directory) che tiene traccia dello stato globale di tutti i blocchi della propria memoria locale ed un indicatore ("indicator bit") per indicare quale nodo ha il blocco memorizzato nella propria cache remota. La coerenza all'interno del nodo invece è basata sullo schema bus-snoopy.

Ciascuna entry (linea di ingresso) della directory ha N-1 bit indicatori di nodo e tre stati globali associati a ciascun blocco di memoria che sono una copia degli stati di tutte le cache remote..

  • Invalid (I) o Uncached (U) - nessun nodo ha il blocco nella cache remote. Il blocco è solo nella home, cioè nella memoria locale proprietaria del dato
  • Shared-Remote (S) - copie valide esistono negli altri nodi
  • Exclusive-Remote (E) o Dirty-Remote - il blocco è memorizzato nella cache remota di un solo nodo. Nel protocollo MESI il blocco nel nodo remoto può essere Clean-Exclusive o Dirty. Il cambiamento da Clean-Exclusive a Dirty è fatto localmente senza informare la "home directory", cioè la directory della memoria locale proprietaria del blocco. Nel protocollo MSI il blocco nel nodo remoto può essere solo nello stato Dirty anche se non modificato[60][61].

   * La cache remota memorizza i dati letti dalle memorie remote degli altri nodi.
   * La directory della memoria locale tiene traccia dei dati e del loro stato, letti dalla propria memoria locale,
     che sono memorizzati nelle cache remote degli altri nodi[62].

- Attenzione - non va confusa la directory della memoria locale con la directory della cache remota. La prima contiene informazioni sui dati locali, la seconda sui dati remoti

Ci sono quattro possibili situazioni per un nodo:

  • Lettura della memoria locale
  • Scrittura della memoria locale
  • Lettura della memoria remota
  • Scrittura della memoria remota
Lettura della memoria locale[modifica | modifica wikitesto]
cc-NUMA Local Memory Read and Invalidate
- Una transazione di lettura di memoria locale di uno stesso nodo è monitorata e gestita nello stesso modo come in un normale sistema SMP.
- L3 miss
- In caso di L1-L3 miss, la transazione è monitorata sul System Bus del proprio nodo da tutte le altre cache L3 e dalla "directory della memoria locale", in questo caso per verificare se il dato da leggere è presente nelle altre cache remote e in quali nodi. La directory della memoria locale è vista e gestita come una directory di un'extra cache e più precisamente come una "shared directory" (directory condivisa) di tutte le cache remote di tutti i nodi remoti. L'unica differenza rispetto alle cache L3 (formata da directory+dati) è che il campo dati e il "Tag" della cache non sono memorizzati nello stesso nodo della directory, ma distribuito sugli altri nodi. La comunicazione tra la directory della memoria locale e le cache remote è fatta tramite una connessione "Message-passing" (inviando un messaggio), punto-punto o distribuito usando il vettore "Indicator bit" (il campo dei bit indicatori dei nodi).
- In caso di stato E (esclusivo) nella directory della memoria locale, un messaggio è inviato all'unica cache remota del nodo dove il dato è memorizzato in attesa della risposta perché la cache potrebbe essere "Dirty".
- Se il dato è Dirty, il dato è inviato indietro alla "home" e gestita come se provenisse da una cache locale con l'eccezione che lo "Shared-Dirty" non è permesso tra nodi nel protocollo tipo MOESI. Potrebbe essere permesso solo con protocollo tipo T-Mesi con l' "owner" solo nella "home" (migrazione del "Dirty-Owner" nella home) ma normalmente il "Dirty-intervention" e il "Shared-clean intervention" tra nodi non è usato (vedi ad es. Protocollo POWER4 IBM)
- Lo stato della cache remota e lo stato delle cache L1-L3 associate sono settate "Shared" e lo stato della directory della memoria locale è cambiato in S
- Se il dato è memorizzato in una cache L3 "owner" locale, il dato è fornito da questa cache (che può essere "shared-clean owner" o "dirty-owner")
- altrimenti dalla memoria locale
Scrittura della memoria locale[modifica | modifica wikitesto]
- Hit Shared in L3
- Se c'è hit S in L3 una transazione di "Invalida" è inviata sul bus del proprio nodo per invalidare tutte le altre copie. Se nella directory della memoria locale ci sono alcuni nodi con lo stato S, una transazione di invalida è inviata, tramite l'indicatore di nodo della home directory, a ciascun nodo avente una copia
- Hit Esclusiva in L3
- La scrittura è fatta localmente in L1-L3 (per l'inclusività) come normalmente. Le cache sono settate (or rimangono) "Dirty"
- Miss
- Come con una "lettura della memoria locale miss" con un comando di invalida (RWITM), poi come con una "write hit-esclusiva"
Lettura della memoria remota[modifica | modifica wikitesto]
cc-NUMA Remote Memory Read
- Miss
- Una transazione di lettura di memoria locale (per un dato remoto) è monitorata da tutte le cache L3 e dalla cache remota del proprio nodo.
- Se c'è una cache L3 "owner", il data è fornito da questa cache
- altrimenti se "hit" nella cache remota del nodo, il dato è fornito da questa cache
- altrimenti una richiesta di lettura remota è inviata sul nodo "home" del dato. La "home" gestisce questa richiesta nello stesso modo come per una richiesta interna. L'unica differenza è che il dato è inviato invece al nodo richiedente. La cache richiedente è settata "Shared"
- In caso di dato "Dirty" in un altro nodo differente dalla "home", la "home" richiede il dato a questo nodo, come descritto nella operazione di "lettura della memoria locale miss" nel caso di stato E nella directory dalla memoria locale, poi il dato è inviato al nodo richiedente. Esempio: il nodo "A" richiede il dato alla "home" "B". "B" richiede il dato al nodo "C" che ha il dato "Dirty". Il nodo "C" invia il dato alla "home" nodo "B" (copy back), "B" lo rispedisce al nodo "A". I nodi "A" e "C" sono settati "Shared" come pure la directory dell memoria locale.
- Ci sono altre possibili varianti: per es. il nodo "C" manda il dato al nodo "B" (home) e simultaneamente al nodo richiedente "A" (vedi DASH[60] e Intel QuickPath" Interconnect[32]).
Scrittura della memoria remota[modifica | modifica wikitesto]
- Hit "Exclusive" in L3
- Il dato è processato localmente come in normale "scrittura hit-esclusiva locale"
- Hit "Shared" in L3
- Una transazione di invalida è mandata alla "home" del dato e resta in attesa per il consenso di scrittura. La "home" rinvia la transazione di invalidazione a tutti i nodi aventi il dato e poi invia il consenso di scrittura al nodo richiedente. Due scritture simultanee su differenti nodi sono così sincronizzate.
- Miss
- Come in una "Lettura remota miss" con un comando di invalida (RWITM), poi come in una "scrittura hit-esclusiva locale"

Shared Cache - Protocollo di Coerenza[modifica | modifica wikitesto]

Tipicamente usato nei sistemi Multi-core per la coerenza e per riduzione dei costi (in termini di spazio).

Sistemi Multi-core[modifica | modifica wikitesto]

(core = processore integrato)

Il Multi-core, denominato anche chip multiprocessors, multicore chips, e many-core chips, è uno speciale genere di multiprocessore dove tutti i processori sono sullo stesso chip MCM (Multi-Chip Module)[63][64]

L2 Shared Cache
L3 Shared Cache

I processori Multi-core sono dei sistemi MIMD: core differenti eseguono differenti threads (Multithread/Multiple Istruzioni - esecuzione parallela sullo stesso contesto di piccole sequenze di istruzioni programmate), operando su differenti parti di memoria (Multiple Data).

Una soluzione comune di implementazione dei sistemi Multi-core è l'uso di cache multi-livello condivise e inclusive (multi-level inclusive shared cache) per mantenere la coerenza dei dati.

L’Inclusività forza i dati ad essere coerenti. Dati memorizzati in L1 sono memorizzati anche in L2 (e in L3 se usata). Qualsiasi cambiamento in L1 deve essere riportato anche nella cache L2 e così anche in L3. Se L2 è aggiornata o invalidata anche tutte le cache L1 devono essere invalidate o aggiornate (stessa relazione tra L2-L3).

La coerenza delle cache è mantenuta mediante l'uso di un controllore centralizzato della cache condivisa. La cache condivisa può essere la L2, o L3 se L2 è una cache privata.

Il protocollo di coerenza si basa protocollo tipo point-to-point message-passing simile a quello descritto nel sistema cc-NUMA. La differenza sta solamente nella directory, che nel sistema cc-NUMA è relativo alla memoria e non alla cache condivisa.

cc-NUMA Multi-Core

Ci sono due generi di implementazione. Messaggio distribuito (message broadcasting) a tutte le cache L1 oppure solo alle specifiche cache L1 che hanno il dato memorizzato. Nel primo caso il protocollo di coerenza è di tipo snoopy. La cache condivisa agisce come ponte in sostituzione del bus di sistema, rinviando le transazioni a tutte le cache L1 per lo snooping, solo però quando è necessario, cioè quando un dato non è esclusivo nella cache condivisa. Nel secondo caso, nella directory della cache condivisa c'è un "indicator bit" per ciascuna cache L1 per indicare quale L1 può avere il dato (Intel Nehalem[48]).

cc-NUMA in Sistemi Multi-core[modifica | modifica wikitesto]

Sistemi Multi-core possono essere connessi assieme per formare un sistema NUMA. La coerenza è garantita tramite message-passing tra le L3 shared-cache dei vari nodi (vedi ad es.Intel Nehalem[48], AMD Opteron[25][32][65], MCM Interconnections Power5 IBM[4][53][66], ecc.)

Stack cache[modifica | modifica wikitesto]

(cache dello stack = pila)

Generalità[modifica | modifica wikitesto]

Stack

Nel processore che esegue le istruzioni ci sono delle piccole memorie molto veloci chiamate registri, gestiti dal software, per memorizzare dati temporanei.

In un software strutturato, è frequente l'uso routine software chiamate procedure per eseguire specifici task, subroutine o funzioni. Anche queste procedure possono a loro volta chiamare altre procedure o funzioni. Queste procedure fanno uso di alcuni registri interni in modo indipendente rispetto al programma chiamante. Perciò, prima di fare una "Call" (procedure call ), è necessario salvare questi registri e i parametri (variabili locali, return address point - indirizzo del punto di ritorno, ecc.) usati dal programma chiamante, informazioni che saranno ricuperate quando si ritornerà indietro al programma chiamante. Queste informazioni sono memorizzate dal software in memoria in un'area dedicata del segmento di processo. Questa area è chiamata Stack. Uno stack è sempre una lista impilata (informazioni messe come in una pila, una sopra l'altra), significa che una nuova richiesta entrante manda giù quella precedente rispetto al Puntatore di stack (Stack Pointer). In realtà la lista è fissa ed è il puntatore di stack che si muove, in su nelle operazioni di salvataggio, in giù nelle operazioni di ricupero. Un altro modo per vedere uno stack è che il programma prende sempre il prossimo elemento da operare dalla cima dello stack (LIFO Last in - First out - primo ad entrare primo ad uscire). Il nome Stack è mutuato dal nome dei contenitori verticali (pile) dei piatti usati all'inizio del XX secolo nei vecchi ristoranti londinesi, con una molla nel fondo cosicché era il fondo che si abbassava o alzava, mettendo o togliendo i piatti, mentre l'ultimo piatto era sempre in cima fisso.

Per velocizzare le operazioni Call/Return (chiamata e ritorno), alcune processori fanno uso dei Register windows (sPARC[67][68][69], AMD 29000, e Intel i960). In questi sistemi un set di registri (windows ) sono riservati per ciascuna Call (da 2 a 32 windows). In questi sistemi non è quindi necessario alcun salvataggio, perciò le operazioni di Call e Return sono molto veloci, cambia solo la selezione del gruppo di registri.

Implementazione della Stack Cache[modifica | modifica wikitesto]

Una soluzione alternativa è la Stack Cache[70][71][72][73][74][75]

La cache dati soffre in genere di un limitato hit rate (nel range di 80-90 % per le applicazioni business[5]) causato da accessi casuali e da dati non omogenei. Un incremento significativo di prestazioni può essere ottenuto usando cache separate per dati normali e dati di stack.

  La stack cache (S-Cache) è usata per mantenere i dati di stack separati dai dati della cache dati (D-cache) L1
  che è acceduta in modo univoco con uno stile tipo-stack.

Grazie alle caratteristiche seriali dei dati di stack, una cache stack può essere indirizzata come un "buffer" (polmone—memoria tampone) continuo di memoria, il che significa che può essere implementata come una cache direct-mapped.

La stack cache previene che i dati di stack siano rimpiazzati dai dati normali. In questo modo l'hit-rate della stack cache può essere vicino al 100%[71][76].

Un'ottimizzazione può essere ottenuta usando una cache L1 Set Associative e riservando uno dei set della cache per i dati di stack (Honeywell Bull Systems[77]). Questo set non viene riservato esclusivamente per questi dati, ma l'area variabile libera sopra lo stack pointer, non usata dai dati di stack, può essere usata per i dati normali. Questo significa che questo Set è usato per i dati normali nel consueto modo ma con la sola restrizione che i dati normali non possono rimpiazzare i dati di stack.

Indirizzamento Virtuale, Fisico e Pseudo Virtuale[modifica | modifica wikitesto]

MMU[modifica | modifica wikitesto]

L' MMU (Memory Management Unit) è l'unità di gestione degli accessi di MM. Le funzioni principali sono:

- Traduzione degli indirizzi da virtuali in fisici

- Gestione dei miss del TLB

- Controllo dei permessi di accesso alla linea di cache e alla memoria:

1. - Supervisor/User
2. - protezione delle scritture

TLB[modifica | modifica wikitesto]

La memoria virtuale è lo spazio visto da un processo. Generalmente questo spazio è molto più grande della memoria fisica. Questo spazio è segmentato in pagine di dimensione prefissata. La page table (tabella delle pagine), generalmente caricata in memoria, tiene traccia di dove le pagine virtuali vengono caricate nella memoria fisica. Il TLB (Translation Lookaside Buffer - memoria di traduzione a lato) o Page Table cache o page-translation caches - cache di traduzione delle pagine) è una cache della Page Table, cioè solamente un sottoinsieme del suo contenuto è memorizzato nel TLB. Il TLB, come per la cache di memoria può essere "separato" Istruzioni (ITLB) e Dati (DTLB) o "unificato" , come pure essere Direct Mapped o Set Associative o Fully Associative. Generalmente l'organizzazione segue l'organizzazione della cache associata, ma può essere organizzata in modo indipendente da questa (vedi TLB). Come per la cache, per aumentarne l'efficienza può essere usato anche un secondo livello di TLB aggiungendo un L2 TLB (es. Intel Nehalem[48]).

Virtual - Physical - Pseudo Virtual addressing

La cache può essere indirizzata in modo fisico o virtuale. Ci sono pro e contro per entrambe le implementazioni, ma generalmente l'indirizzamento fisico è quello normalmente usato.

Indirizzamento Virtuale[modifica | modifica wikitesto]

In fig. sotto un esempio di indirizzo virtuale con 4 GB di spazio virtuale, 4 MB cache, 4 KB di dimensione di pagina e 256 B di dimensione della linea di cache.

Virtual Space Address Structure
Virtual Addressing

Lo spazio virtuale o logico è diviso in pagine. L' MSB + PA formano l'indirizzo di pagina dello spazio virtuale VPA (Virtual Page Address). Anche la cache è divisa in pagine.

La cache memorizza un sottoinsieme delle pagine dello spazio virtuale. È indirizzata dall’Index che è formato da PA + PA Offset dove il PA (Page Address) è l'indirizzo di pagina della cache e il PA Offset è l'indirizzo della linea di cache all'interno della pagina, mentre l’Offset è l'indirizzo interno, a livello di byte, della linea di cache.

Nel indirizzamento virtuale o logico una cache è direttamente indirizzata dall'indirizzo virtuale Index senza dover prima convertire l'indirizzo virtuale in fisico. Anche i TAG sono virtuali (logical MSB ). Questo tipo di indirizzamento è denominato anche Virtual Index - Virtual TAG (VIVT).

In un ambiente multiprocessing differenti indirizzi logici di contesti (context) o processi diversi possono riferirsi ad uno stesso indirizzo fisico, e lo stesso indirizzo logico di un processo può mappare differenti indirizzi fisici causando un problema di coerenza, mentre al contrario all'interno dello stesso contesto, lo stesso indirizzo logico è sempre relativo allo stesso indirizzo fisico.

Ci sono tre possibili soluzioni:

  1. - Flushing (letteralmente sciacquatura = invalidazione) della cache ad ogni context switch (cambiamento di contesto),
  2. - Aggiungere in cache un ID (ASID - Address Space IDentifier) o un Context Number (CTX) o Process Number (identificatore dello spazio indirizzi, numero di contesto o numero di processo), per distinguere i vari processi/contesti[78].
  3. - Aggiungere in cache il corrispondente indirizzo fisico che deve essere confrontato con l'indirizzo fisico ottenuto dal TLB (acceduto in parallelo - "look aside" - visto a lato), per verificare la corretta associazione virtuale-fisica dell'indirizzo (indirizzamento Virtual Index - Physical TAG - VIPT).
Problema di coerenza[modifica | modifica wikitesto]

Poiché differenti indirizzi logici di differenti contesti possono riferisci allo stesso indirizzo fisico (dati condivisi), più di una posizione di memoria potrebbe memorizzare lo stesso dato, causando un problema di coerenza in caso di scrittura. Solamente una posizione di memoria sarebbe aggiornata.

Ci sono due soluzioni principali[79]

  1. Prevenzione dei sinonimi (synonym prevention)
    - Tramite il software prevenire od evitate i sinonimi
  2. Rilevamento dinamico dei sinonimi (dynamic synonym detection)
    - Supporto hardware per aiutare il software di tutti o del principale "task" (programma) di mantenimento della consistenza in presenza di sinonimi

In ogni caso la cache deve sempre essere invalidata quando la mappatura virtuale-fisica viene cambiata, per es. nel caso di rimpiazzo della pagina - page replacement.

Indirizzamento Fisico[modifica | modifica wikitesto]

Physical Addressing

Nell'indirizzamento fisico, per prima cosa viene indirizzato il TLB (*) usando l'indirizzo virtuale L-MSB + LPA, poi l'indirizzo fisico (PPA) ottenuto dal TLB più PPA Offset è usato per indirizzare la cache. Solamente la parte dell'indirizzo virtuale che differisce dall'indirizzo fisico è convertita, cioè "L.MSB" e "LPA".

Il TLB è una cache della Page Table cache ed è gestita come una normale cache con in aggiunta che il CTX associato all'indirizzo logico è confrontato con il CTX memorizzato nel TLB perché cambiando contesto cambia l'associazione LPA-PPA (vedi indirizzamento virtuale).

Questa soluzione (indirizzamento Physical Index - Physical TAG - PIPT) è molto più semplice ed evita qualsiasi problema di ambiguità, ma è più lenta perché prima è richiesto l'accesso al TLB.

(*) - All'inizio la dimensione della cache era piccola ed uguale alla dimensione della pagina, perciò "index" (l'indice) virtuale e fisico erano coincidenti e il TLB era acceduto in parallelo (a lato - look aside, da cui il nome) solamente per verificare gli MSB, come nell'indirizzamento virtuale.

Indirizzamento Pseudo Virtuale[modifica | modifica wikitesto]

- Soluzione usata nei sistemi Honeywell Bull Italia[77] - F. Zulian - US Patent N. 5.165.028
- Questa soluzione offre tutti i vantaggi di entrambe le precedenti soluzioni.

  Questo approccio si basa sul principio della località spaziale

Pseudo Virtual Addressing

Facendo riferimento alla fig. Virtual Space Address Structure, l'indirizzo virtuale/logico "Index" è diviso in due parti: Logical Page Address (LPA - indirizzo di pagina logica o numero di pagina) e LPA Offset (l'indirizzo della linea di cache all'interno della pagina). L’Offset è l'indirizzo interno (a livello di byte) della linea di cache.

Virtual-Physical-Pseudo Virtual Cache Access Time.svg

Il Virtual e il Physical Page Offset coincidono (come pure, ovviamente, l' Offset ). L'indirizzo virtuale e l'indirizzo fisico differiscono per l' L.MSB e per l' LPA. Il TLB converte l' L.MSB logico e la Logical Page Address (LPA), rispettivamente in P.MSB fisico e in Physical Page Address (PPA = indirizzo fisico di pagina). Nell'indirizzamento fisico, il PPA + LPA Offset formano l' Index fisico che è usato per indirizzare la cache.

Località spaziale significa che se un accesso è fatto in una pagina ci sono moltissime probabilità che il prossimo accesso (relativo allo stesso tipo) sia fatto nella stessa pagina.

Separatamente per le Istruzioni e per i Dati e i dati di Stack (se la cache Stack è usata), la probabilità che il successivo accesso sia fatto nella stessa pagina del precedente accesso è molto alta dovuta ad una località spaziale molto ampia (4 KB o più rispetto, per es., ad una molto più piccola dimensione di una linea di cache).

Il precedente indirizzo logico/virtuale di pagina (LPA) con il suo Context Number (CTX) e il corrispondente indirizzo fisico di pagina (PPA) sono memorizzati in un dedicato registro.

Nel successivo accesso, il nuovo indirizzo logico di pagina e confrontato (assieme al CTX) con l'indirizzo memorizzato precedentemente nel registro LPA. Se coincidono (hit), viene usato il corrispondente registro dell'indirizzo fisico di pagina PPA per indirizzare direttamente la cache, senza la necessità di accedere al TLB così come avviene nel caso di indirizzamento virtuale (da cui il nome Pseudo Virtual addressing- indirizzo Pseudo Virtuale).

In caso di miss, il PPA è fornito dal TLB, come nel caso di indirizzamento fisico senza alcuna penalità rispetto a quest'ultimo.

Questo approccio è efficiente se un set di registri "LPA-PPA" è riservato ciascun per tipo di funzione: uno per le istruzione, due per gli operandi (le istruzioni possono avere sino a due indirizzi di operandi) ed eventualmente uno per i dati di stack. In aggiunta per aumentare l'efficienza nei sistemi multithreading , possono essere usati un gruppo di dedicati registri "LPA-PPA" per ogni thread.

Nota - Questi registri possono essere visti come una cache L1 del TLB con una sola entry, separata per ogni tipo di dato (istruzioni, dato1, dato2, stack) e per ogni thread, cioè una cache L1 TLB fatta a registri perciò velocissima.

Con questa soluzione, praticamente senza costi aggiuntivi, nella quasi totalità dei casi, e in particolare per le istruzioni e per stringhe di dati sequenziali, l'indirizzamento è fatto in modo fisico senza però la necessità di aspettare la traslazione dell'indirizzo da virtuale a fisico, esattamente come avviene nel caso dell'indirizzamento virtuale, e senza anche la necessita, rispetto a quest'ultimo, di invalidare (flush) la cache in caso page replacement (sostituzione della pagina), eliminando qualsiasi problema di coerenza.

Note[modifica | modifica wikitesto]

  1. ^ FPO IP Research & Communities
  2. ^ FPO IP Research & Communities
  3. ^ FPO IP Research & Communities
  4. ^ a b c d e f The POWER4 Processor Introduction and Tuning Guide par. 2.4 - http://web.eecs.utk.edu/~terpstra/power4/p4Tuning.pdf
  5. ^ a b c d Architecture Analysis of Tightly Coupled Multiprocessor Systems - F. Zulian Honeywell (Bull Italia 1987)
  6. ^ Un altro possibile algoritmo di codifica hash (hash coding), però usato qualche volta solo per il TLB, è il "bit XORing " dell'indirizzo. La riduzione dell'indirizzo è ottenuta facendo un XOR (exclusive OR - OR esclusivo) tra coppie di bit. Questo metodo genera un indirizzamento pseudo-casuale.
  7. ^ (EN) Athlon II Or Phenom II: Does Your CPU Need L3 Cache?, in Tom's Hardware, 6 ottobre 2009. URL consultato il 28 febbraio 2017.
  8. ^ a b IBM RS/6000 Scientific and Technical Computing: POWER3 Introduction and Tuning Guide (Ch. 7.1 p.88)
  9. ^ Performance Evaluation of Cache Replacement Policies for the SPEC CPU2000 Benchmark Suite (PDF), su ece.uah.edu.
  10. ^ Architecture Programmer’s Manual "3.9.4 Cache Operation" - http://developer.amd.com/wordpress/media/2012/10/24593_APM_v21.pdf
  11. ^ Intel Iris Pro 5200 Graphics Review: Core i7-4950HQ Tested - http://www.anandtech.com/show/6993/intel-iris-pro-5200-graphics-review-core-i74950hq-tested/3
  12. ^ pssem13010400fa.indd
  13. ^ Anand Lal Shimpi, Intel Iris Pro 5200 Graphics Review: Core i7-4950HQ Tested. URL consultato il 28 febbraio 2017.
  14. ^ a b c Comparing Cache Architectures and Coherency Protocols on x86-64 Multicore SMP Systems - http://people.freebsd.org/~lstewart/articles/cache-performance-x86-2009.pdf
  15. ^ RS/6000 Scientific and Technical Computing: POWER3 Introduction and Tuning Guide - http://www.redbooks.ibm.com/redbooks/pdfs/sg245155.pdf (Ch. 2.1 pp. 7-8)
  16. ^ Data Caches for Superscalar Processors - http://pages.saclay.inria.fr/olivier.temam/files/eval/JNT97.pdf
  17. ^ High Bandwidth Data Memory Systems for Superscalar Processors - ftp://ftp.cs.wisc.edu/pub/techreports/1990/TR968.pdf
  18. ^ Functional Principles of Cache Memory - Multiporting., su alasir.com. URL consultato il 28 febbraio 2017.
  19. ^ Comparing Multiported Cache Schemes - http://www.researchgate.net/publication/221134115_Comparing_Multiported_Cache_Schemes/file/32bfe50fb1759c4f80.pdf
  20. ^ On High-Bandwidth Data Cache Design for Multi-Issue Processors - http://web.eecs.umich.edu/~taustin/papers/MICRO30-bwcache.pdf
  21. ^ BM RS/6000 Scientific and Technical Computing: POWER3 Introduction and Tuning Guide (Ch 7.1 p. 89) - http://www.redbooks.ibm.com/redbooks/pdfs/sg245155.pdf
  22. ^ BM RS/6000 Scientific and Technical Computing: POWER3 Introduction and Tuning Guide Ch. 2.1 p. 7 - ch 7.1 p.89 - http://www.redbooks.ibm.com/redbooks/pdfs/sg245155.pdf
  23. ^ a b c d e f "POWER4 System Microarchitecture", http://www.cc.gatech.edu/~bader/COURSES/UNM/ece637-Fall2003/papers/TDF02.pdf
  24. ^ John L. Hennessy and David A. Patterson. CompzLter Architecture: A Quantitative Approach, 2nd Edition. Morgan Kaufmann Publishers Inc., 1996.
  25. ^ a b c d AMD Opteron Shared Memory MP Systems - http://www.cse.wustl.edu/~roger/569M.s09/28_AMD_Hammer_MP_HC_v8.pdf
  26. ^ a b Multi-processor system with shared memory - http://www.freepatentsonline.com/5701413.html
  27. ^ Method for transferring data in a multiprocessor computer system with crossbar interconnecting unit - http://www.google.it/patents/EP0923032A1?cl=en
  28. ^ Specification and Verification of the PowerScale Bus Arbitration Protocol: An Industrial Experiment with LOTOS, Chap. 2, Pag. 4 - ftp://ftp.inrialpes.fr/pub/vasy/publications/cadp/Chehaibar-Garavel-et-al-96.pdftp://ftp.inrialpes.fr/pub/vasy/publications/cadp/Chehaibar-Garavel-et-al-96.pdf
  29. ^ a b c d e f g h i j k l m n o p 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
  30. ^ a b MPC7400 RISC Microprocessor User's Manual - http://pccomponents.com/datasheets/MOT-MPC7400.PDF
  31. ^ 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.
  32. ^ a b c d e An Introduction to the Intel® QuickPath Interconnect - http://www.intel.ie/content/dam/doc/white-paper/quick-path-interconnect-introduction-paper.pdf
  33. ^ 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.
  34. ^ BM PowerPC 476FP L2 Cache Core Databook - https://www-01.ibm.com/chips/techlib/techlib.nsf/techdocs/8D5342097498C81A852575C50078D867/$file/L2CacheController_v1.5_ext_Pub.pdf
  35. ^ a b c d e f Cache Ccoherency Protocol Including an HR State - IBM patent - https://www.google.com/patents/US6275908
  36. ^ 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.
  37. ^ 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.
  38. ^ a b c d e Cache-coherency protocol with recently read state for data and instructions - IBM patent - http://www.google.com/patents/US5996049
  39. ^ a b c d e f g h Cache Coherency Protocol with Tagged State for Modified Values - IBM patent - http://www.google.com/patents/US6334172
  40. ^ MPC750UM/D 12/2001 Rev. 1 MPC750 RISC Microprocessor Family User's Manual - http://www.freescale.com/files/32bit/doc/ref_manual/MPC750UM.pdf
  41. ^ a b c 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
  42. ^ AMD64 Technology - AMD64 Architecture Programmer's Manual Volume 2: System Programming - http://developer.amd.com/wordpress/media/2012/10/24593_APM_v21.pdf
  43. ^ a b c Sweazey, P., and Smith, A. J. A class of compatible cache consistency protocols and their support by the IEEE Futurebus. In Proceedings of the 13th International Symposium on Computer Architecture. IEEE. New York, 1986, pp. 414-423.) - http://pdf.aminer.org/000/419/524/a_class_of_compatible_cache_consistency_protocols_and_their_support.pdf
  44. ^ Mark S. Papamarcos and Janak H. Patel. In ISCA '84: Proceedings of the 11th annual international symposium on Computer architecture, pages 348{354, New York, NY, USA, 1984. ACM - https://web.archive.org/web/20150521112759/http://www.researchgate.net/profile/Janak_Patel4/publication/220771512_A_Low-Overhead_Coherence_Solution_for_Multiprocessors_with_Private_Cache_Memories/links/00463519b8d139e451000000.pdf
  45. ^ a b 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
  46. ^ a b 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
  47. ^ a b c d Cache memory and related consistency protocol, Inventor Ferruccio Zulian, Bull HN ISI - http://www.google.com/patents/EP0396940B1?cl=en
  48. ^ a b c d e Cache Organization and Memory Management of the Intel Nehalem Computer Architecture - Trent Rolf - http://rolfed.com/nehalem/nehalemPaper.pdf
  49. ^ David Kanter, The Common System Interface: Intel’s Future Interconnect, in Real World Tech, 28 agosto 2007, p. 5. URL consultato il 12 agosto 2012.
  50. ^ Optimizing the MESI Cache Coherence Protocol for Multithreaded Applications on Small Symmetric Multiprocessor Systems - http://tibrewala.net/papers/MESI98/
  51. ^ Forward state for use in cache coherency in a multiprocessor system - Intel -https://www.google.com/patents/US6922756
  52. ^ Handy, Jim. "Cache Memory Book", Academic Press, Inc., 1998, p. 130, p. 208 - http://books.google.it/books?hl=it&id=-7oOlb-lCpMC&q=208
  53. ^ a b IBM POWER Systems Overview - https://computing.llnl.gov/tutorials/ibm_sp/
  54. ^ SourceForge - http://lse.sourceforge.net/numa/faq/system_descriptions.html
  55. ^ Bull HN F. Zulian - A. Zulian patent - Computer system with a bus having a segmented structure - http://www.freepatentsonline.com/6314484.html
  56. ^ NUMA Architecture - http://www.dba-oracle.com/real_application_clusters_rac_grid/numa.html
  57. ^ Data-processing system with CC-NUMA (cache-coherent, non-uniform memory access) architecture and remote cache incorporated in local memory - http://www.freepatentsonline.com/6243794.html
  58. ^ Directory-based CacheCoherence – Parallel Computer Architecture par. 1.3.2 pg. 48 – http://www.dte.eis.uva.es/Docencia/ETSII/SMP/archivos/archibak/culler.pdf
  59. ^ A new Solution to Coherence Problems in Multicaches Systems - Censier and Feaultrier - http://www.cs.auckland.ac.nz/courses/compsci703s1c/resources/Censier.pdf
  60. ^ a b c Proceedings of the 17th Annual International Symposium on Computer Architecture, IEEE 1990, pages 148-159; D. Lenosky et al: The Directory-Based Cache Coherency Protocol for DASH Multiprocessor - http://www.cse.wustl.edu/~roger/569M.s09/p148-lenoski.pdf
  61. ^ Directory-based CacheCoherence - Parallel Computer Architecture ch. 8 pg. 513 - http://www.dte.eis.uva.es/Docencia/ETSII/SMP/archivos/archibak/culler.pdf
  62. ^ SourceForge - http://lse.sourceforge.net/numa/faq/
  63. ^ http://scholar.google.it/scholar_url?url=http://minds.wisconsin.edu/bitstream/handle/1793/60554/TR1593.pdf%3Fsequenc&hl=it&sa=X&scisig=AAGBfm3Tfz0tL0HBvHhv_6mCWgvMIZhsxg&oi=scholarr&ei=pXGmVPnBAsn7Uti3g7AL&ved=0CCEQgAMoADAA
  64. ^ http://scholar.google.it/scholar_url?url=http://www.itu.dk/people/jhh/thesis/references/36%2520-%2520Chip%2520Makers%2520Turn%2520to%2520Multicore%2520Processors.pdf&hl=it&sa=X&scisig=AAGBfm26PHbY3VJRZqQtLux3ac90MmK1rQ&oi=scholarr&ei=pXGmVPnBAsn7Uti3g7AL&ved=0CCIQgAMoATAA
  65. ^ Cache Coherence Techniques for Multicore Processors - Michael R. Marty - http://research.cs.wisc.edu/multifacet/theses/michael_marty_phd.pdf
  66. ^ Of NUMA on POWER7 in IBM - http://www-03.ibm.com/systems/resources/pwrsysperf_P7NUMA.pdf
  67. ^ Understanding stacks and registers in the Sparc architecture(s) - http://icps.u-strasbg.fr/people/loechner/public_html/enseignement/SPARC/sparcstack.html.pdf
  68. ^ The SPARC Architecture - Jingke Li - http://web.cecs.pdx.edu/~herb/cs322s10/Sparc_Architecture.pdf
  69. ^ The SPARC Architecture Manual Version 8 - http://www.gaisler.com/doc/sparcv8.pdf - http://web.cecs.pdx.edu/~herb/cs322s10/Sparc_Architecture.pdf - http://web.cecs.pdx.edu/~herb/cs322s10/Sparc_Architecture.pdf
  70. ^ Stack data cache having a stack management hardware with internal and external stack pointers and buffers for handling underflow and overflow stack - http://www.google.com/patents/US5107457
  71. ^ a b Understanding stacks and registers in the Sparc architecture(s) - Implementing a Stack Cache - AMD architecture - http://www.owlnet.rice.edu/~elec525/projects/SCreport.pdf
  72. ^ Register Allocation for Free: The C Machine Stack Cache - Massachusetts Institute of Technology - http://cm.bell-labs.com/cm/cs/cstr/138b.pdf
  73. ^ Stack Cache for Block-Structured Programs - http://comjnl.oxfordjournals.org/content/37/7/610.full.pdf
  74. ^ The Mechanization of a Push-down Stack" - C. B. Carlson (AFIPS Conf. Proc., V. 24, 1963)
  75. ^ Strategies for Managing the Register file in RISC" - Tamir and C. H. Sequin (IEEE Transection on Computers, Vol. C-32, No. 11, November 1983)
  76. ^ Implementing a Stack Cache - http://www.owlnet.rice.edu/~elec525/projects/SCpresentation.pdf
  77. ^ a b Cache memory having pseudo virtual addressing - Honeywell Bull Italia - https://www.google.com/patents/US5165028
  78. ^ High-speed memory and memory management system - Sun Microsystems - http://www.google.com.tr/patents/US4550368
  79. ^ Virtual-Address Caches - http://www.ece.umd.edu/class/enee646.F2007/Cekleov1.pdf

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]