Memoria cache

La cache è una memoria che memorizza dati temporanei "in modo silenzioso" al più alto livello di utilizzazione per un veloce riuso.^[4][5][6]

Il termine cache deriva dal francese e significa "nascosto".

Il termine cache memory o memory cache o brevemente cache senza nessun'altra specificazione, generalmente si riferisce a una memoria nascosta che memorizza un sottoinsieme del contenuto della memoria principale e più precisamente le istruzioni di un programma e i relativi dati su cui operare.

 

La logica funzionale della memoria cache è la seguente:

1. Nelle operazioni di lettura della memoria principale (MM), per prima cosa il gestore della cache verifica se il dato è memorizzato nella cache;
2. In caso di esito positivo (Hit), il dato viene trasferito immediatamente dalla cache al processore senza coinvolgere la memoria principale;
3. In caso di esito negativo (Miss), il dato viene letto dalla memoria principale e riportato nella cache seguendo i principi di località spaziale.

Il funzionamento della cache si basa principalmente su due principi di località, la località temporale e la località spaziale.

• Località temporale (temporal locality): I dati recentemente usati hanno un'alta probabilità di essere riutilizzati 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. Le 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^[7], 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 disponibili 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 contigue 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).

L'efficienza della cache è misurata in termini di "Hit Rate". L'Hit Rate rappresenta la percentuale di Hit, ovvero il numero di riferimenti alla memoria che può essere soddisfatto dalla cache rispetto al numero degli accessi totali. Per esempio, ipotizzando che su un totale di 10 riferimenti alla memoria 8 vengono soddisfatti dalla cache l'hit rate è 0,8 ovvero l'80%.

Per "Miss" si intende invece il numero di riferimenti non soddisfatti dalla cache rispetto al numero totale degli accessi alla memoria. Nel caso precedente il miss rate è 0,2 quindi il 20%, questo significa che su 10 richieste è stato necessario accedere 2 volte alla memoria principale per trovare il dato (o l'istruzione). L'efficienza della cache dipende da diversi elementi quali la dimensione della cache, la dimensione della linea di cache, il tipo, l'architettura e dalle applicazioni. Una buona figura di rendimento, per applicazioni commerciali, può essere compresa nel range di 80-95 % di hit^[8].

Ci sono tre strutture di base per le cache:

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

 

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. Come detto prima, il principale vantaggio di questa tecnologia è che il dato può essere memorizzato in qualsiasi posizione della cache, ma purtroppo è costosa in termini di hardware. Necessita di vie di accesso simultanee indipendenti ed un comparatore per ogni entry (entrata) di cache. Perciò le dimensioni di questa cache sono in genere molto piccole 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.

 

 

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). 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^[9] 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.

 

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^[10]) e 128 (POWER3^[11]), in funzione del tipo di cache (Istruzioni/Dati - vedi sotto "Tipi di cache"). Nella cache Set Associative viene usato un comparatore di indirizzi per ogni set. Una cache Direct Mapped può essere vista come una cache Set Associative con un solo set e 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.

Quando è disponibile più di una entry per memorizzare un dato, come nel caso di cache Fully Associative e Set Associative, la entry che dovrà essere rimpiazzata è selezionata in base alla "Replacement policy" adottata. Ci sono differenti politiche^[12].

Le principali sono:

• LRU - (Least Recently Used - Meno Recentemente Usato)
  • Comunemente usato per le cache Set Associative.
  • Separatamente per ciascun Set a 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°-4°-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 - (First-In First-Out - Primo ad Entrare Primo ad Uscire)
  • 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 - (Least Frequently Used - Meno Frequentemente Usato)
  • Algoritmo più efficiente ma il più costoso. Generalmente non usato.
• Round-robin (girotondo dall'uccello Round-robin - selezione ciclica)
  • 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 puntatore.
  • Semplice e poco costoso da implementare.
• Random (casuale)
  • Usato nelle cache Full Associative.
  • Round-robin aggiornato ad ogni clock/accesso invece che ad ogni rimpiazzo.
  • Semplice e poco costoso da implementare.

 

In un sistema può essere usata più di una cache. Le cache sono organizzate in livelli gerarchici. Sono possibili sino a quattro livelli, L1-L4 o più^[13]. 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 dà 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 un'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. POWER5 IBM, AMD Bulldozer). Normalmente la L1 è una cache Set Associative separata Istruzioni e Dati (vedi sotto Tipi di cache). La cache L2 può essere unificata o separata, come pure essere una cache Direct Mapped o Set Associative. Lo stesso per la cache L3.

Ci sono due tipi di cache:

• Instruction cache (cache delle istruzioni)
• Data cache (cache dei dati)

Nella memoria principale vengono memorizzate due tipi di informazioni, le istruzioni (anche chiamate codice) e i dati (come operandi o di stack - vedi Stack cache). Le cache possono essere suddivise in cache unificate e cache separate, le cache unificate memorizzano sia le istruzioni che i dati mentre nelle cache separate istruzioni e dati sono memorizzati in cache dedicate.

La cache istruzioni viene abbeviata in "I-Cache" mentre la cache dati in "D-Cache", l'utilizzo di cache separate presenta principalmente tre vantaggi:

• 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 Set Associative da 2 a 4/8-vie per le cache istruzioni, da 4 a 16-vie o più (128) per la cache dati^[11].
• 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);
• 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 Write policy e Interferenze tra Snoopy e attività del processore).

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, e 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.

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^[8]. Le stesse considerazioni possono essere fatte per la cache L3 rispetto a L2 (vedi per esempio Shanghai (AMD) vs Nehalem-EP (Intel)^[14]).

La write policy - o 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^[15])

Ci sono due tipi di politiche:

• Write through
• Write-back (o copy back)

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

Il dato è aggiornato solamente nella cache. Viene riscritto 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 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 memoria principale 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)

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.

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 un'unità aritmetica-logica (unità per operazioni aritmetiche e logiche). Per esempio in IBM POWER3^[16] 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 d 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 di essere eseguite fuori ordine per mezzo dell'uso della tecnica dei Register renaming (sostituzione di un registro già in uso con un registro diverso - cambio del nome) 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^[17][18][19]

Ci sono diverse soluzioni^[20][21]:

• Cache multi-banco
• Cache multi-porte
• Multiple copie
• Multi-porte virtuali
• Soluzione ibrida

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

Ci sono due approcci:

• Indirizzamento lineare
• Cache interleaving (cache interlacciata)

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)

 

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ù o 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^[22]), chiamati two-way, four-way o eight-way interleaving rispettivamente. La cache interleaving dà 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^[23] 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.

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

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

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é nessun'altra richiesta può essere inviata in parallelo. Poiché circa il 30% di accessi alla memoria sono scritture^[25], questa soluzione ha dei severi limiti.

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

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.

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. Nei sistemi come il multiprocessore simmetrico (SMP), il multi core e il cc-NUMA, dove viene usata una cache dedicata per ogni processore, core o nodo, si può verificare un problema di coerenza, o coerenza, dei dati quando uno stesso dato è memorizzato in più di una cache e si verifica che un dato viene modificato in una cache.

Può essere risolto in due modi:

• Invalidando tutte le copie delle altre cache (broadcast-invalidate - diffusione invalidazione);
• Aggiornando tutte le copie delle altre cache (write-broadcasting - diffusione scrittura).

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

Gli schemi si possono classificare in base a:

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

Tre approcci sono adottati per mantenere la coerenza dei dati:

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

 

Protocollo usato nei sistemi con bus, come ad esempio nei sistemi SMP. Sistema operante sotto un unico sistema operativo con due o più processori omogenei e con una memoria principale centralizzata condivisa. Ciascun processore ha una propria cache che agisce come ponte tra il processore e la memoria principale. La connessione è fatta usando un bus di sistema (system bus) o un crossbar (xbar, connessioni incrociate)^[26] o un mix dei due precedenti sistemi, bus per gli indirizzi e crossbar per i dati (data crossbar)^[27][28][29].

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

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

Stati speciali:

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

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: Due o più livelli di cache inclusive riducono queste interferenze perché circa 85-90%^[8] degli accessi del processore (per i dati) è fatto al livello più basso di cache.
• Cache istruzioni e dati 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.
• Dual-port e dual-directory: 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)^[41] 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).

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: Due o più livelli di cache inclusive riducono queste interferenze perché circa 85-90%^[8] degli accessi del processore (per i dati) è fatto al livello più basso di cache.
• Cache Istruzioni e Dati separate: 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.
• Dual-Port e Dual-Directory: 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)^[41] 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).

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

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

  Lo stesso argomento in dettaglio: Protocolli di coerenza della cache (esempi).

Protocolli:

• SI: Write Through
• MSI: Synapse^[30]
• MEI: IBM PowerPC 750^[47], MPC7400^[39]
• MES: Firefly^[30]
• MESI: Pentium II^[46], PowerPC, Intel Harpertown (Xeon 5400)
• MOSI: Berkeley^[30]
• MOESI: AMD64^[48], AMD Opteron^[26], MOESI^[43], T-MESI IBM^[40]

Terminologia usata:

• Illinois: D-VE-S-I (= MESI esteso)^[30][49]
• Write-once o Write-first: D-R-V-I (= MESI)^[30][50][51]
• Berkeley: D-SD-V-I (= MOSI)^[30]
• Synapse: D-V-I (= MSI)^[30]
• Firefly: D-VE-S (= MES) DEC^[30]
• Dragon: D-SD (SM?)-SC-VE (= MOES) Xerox^[30]
• Bull HN ISI: D-SD-R-V-I (= MOESI)^[42]
• Protocollo MERSI (IBM) / MESIF (Intel): R=Recent - IBM PowerPC G4, MPC7400^[31][39], F=Forward - Intel^[33], Intel Nehalem^[14][44][52]
• RT-MESI: T=Tagged - IBM^[40]
• HRT-ST-MESI: H=Hover, R=Recent, T=Tagged, ST=Shared-Tagged - IBM^[36][40]
• Protocollo POWER4 IBM: T-Mu-Me-M-S-S_L-I (L2 sette stati)^[24]
  • Mu = Unsolicited Modified - non Sollecitato Modificato Esclusivo - (M)^[53]
  • M = Modified Exclusive - Modificato Esclusivo
  • T = Tagged - Modificato Owner non Esclusivo (O)
  • Me = Valido Esclusivo - (E)
  • S = Shared
  • S_L = Shared Last - sourced local - (Shared Owner locale)
  • I = Invalido - (I)

È noto che i sistemi SMP hanno una limitata scalabilità. La memoria multi-banco e il crossbar dati^[27] 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^[26][33] o un mix di queste (vedi ad es. sistemi IBM Power Systems^[24][54]), intercessione via bus (es. NUMAq^[55]), crossbar, segmented bus (bus segmentato - NUMA Bull HN ISI ex Honeywell^[56]), Mesh router, ecc..

Esempi di interconnessione:

 

 

 

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

 

In un sistema NUMA l'accesso di un processore a 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^[57].

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 e 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).

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^[58]. 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).^[59]

 

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^[60] e descritto anche in "The Directory-Based Cache Coherency Protocol for DASH Multiprocessor"^[61].

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 directory associata a ciascuna memoria locale (local memory directory) che tiene traccia dello stato globale di tutti i blocchi della propria memoria locale e 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^[61][62].
  • 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^[63].
• 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

 

• 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

• 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"

 

• 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^[61] e Intel QuickPath" Interconnect^[33]).

• 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"

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

 

 

Il multi-core ("multipli processori integrati"), 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)^[64][65]

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.

 

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^[44]).

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^[44], AMD Opteron^[26][33][66], MCM Interconnections POWER5 IBM^[7][54][67], ecc.)

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:
  • Supervisor/User
  • protezione delle scritture

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^[44]).

 

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.

 

 

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.

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:

• Flushing (letteralmente sciacquatura = invalidazione) della cache ad ogni context switch (cambiamento di contesto),
• 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^[68].
• 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).

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^[69]

• Prevenzione dei sinonimi (synonym prevention): Tramite il software prevenire od evitate i sinonimi
• Rilevamento dinamico dei sinonimi (dynamic synonym detection): Supporto hardware per aiutare il software di tutti o del principale "task" (programma) di mantenimento della coerenza 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.

 

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.

• Soluzione usata nei sistemi Honeywell Bull Italia^[70] - 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

 

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.

 

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 a una località spaziale molto ampia (4 KB o più rispetto, per esempio, a 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 la 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 e 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.

• Jim Handy, The cache memory book: the authoritative reference on cache design, 2ª ed., San Diego, Academic Press, 1998, ISBN 978-0-12-322980-9, SBN IT\ICCU\PAR\0727062.

• Cache
• Non-Uniform Memory Access
• Memoria (informatica)

• cache-memory, su Treccani.it – Enciclopedie on line, Istituto dell'Enciclopedia Italiana.  
• memoria cache, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.  
• (EN) cache memory, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.  

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica