Memoria cache

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

La funzione della memoria cache è di velocizzare gli accessi alla memoria principale aumentando le prestazioni del sistema. Nei sistemi multiprocessori con memoria condivisa permette inoltre di ridurre il traffico del bus di sistema e della memoria principale, che rappresenta 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.

Caratteristiche

Definizione La cache è una memoria che memorizza dati temporanei "in modo silenzioso" al più alto livello di utilizzazione per un veloce riuso.Questa definizione deriva direttamente dal modo intrinseco di operare della cache stessa e non ha bisogno quindi di fonti di riferimento. La cache è per definizione una memoria nascosta che sta, in genere, tra una memoria e l'utilizzatore (in genere un processore). Tra l'utilizzatore e la memoria, dove l'informazione è memorizzata, ci possono essere altri utilizzatori del dato da leggere, esempio altre cache. Il processore ricevendo un dato non è a conoscenza se proviene da una cache o dalla memoria. Lo stesso in caso di più cache in cascata. La L1 (la prima cache) non sa se il dato provienne da una seconda cache (L2) o dalla memoria. Idem per una eventuale terza cache. Per esempio la cache L3 è invisibile sia alla cache L2 che alla cache L1 e anche al processore che sono gli utilizzatori del contenuto della L3. La cache quindi è una memoria invisibile a tutti i livelli di utilizzatori superiori (in questo esempio L2, L1 e processore). Questa definizione è generale e vale per tutte le altre tipi di cache dove ci possono essere più utilizzatori in cascata

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 una copia di un sottoinsieme del contenuto della memoria principale e più precisamente le istruzioni di un programma e i relativi dati su cui operare.

Funzionamento

La logica funzionale della memoria cache è la seguente: Nelle operazioni di lettura della memoria principale (MM), per prima cosa il gestore della cache verifica se il dato è memorizzato nella cache; In caso di esito positivo (Hit), il dato viene trasferito immediatamente dalla cache al processore senza coinvolgere la memoria principale; 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 byteThe POWER4 Processor Introduction and Tuning Guide par. 2.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 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).

Efficienza 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 hitArchitecture Analysis of Tightly Coupled Multiprocessor Systems - F. Zulian Honeywell (Bull Italia 1987).

Struttura di base 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)

Cache Fully Associative

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.

Cache Direct Mapped

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 comuneUn 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. per ottenere l'indirizzo di cache è di usare direttamente una parte dell'indirizzo di memoria, e precisamente il campo chiamato index (indice), cioè, escludendo loffset, i bit meno significativi dell'indirizzo (Least significant bit - LSB), vedi fig. Cache addressing. Loffset (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), lindex, 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.

Cache Set Associative

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.