1.Memoria cache - Aspetti Generali

Il tempo di accesso per la cache è almeno 10 volte più piccolo di quello della memoria principale. A causa della sua tecnologia molto costosa, le dimensioni sono limitate. Per raggiungere alte prestazioni gli indirizzi hanno bisogno di essere allocate il più delle volte nella cache. La terminologia utilizzata per l’efficienza della cache è “Hit rate” (l’hit rate rappresenta il rapporto tra il numero di indirizzi ai quali la cache accede e il numero totale di indirizzamenti durante un determinato tempo). L’opposto dell’hit rate è chiamato “Miss Rate” che può essere determinato dalla formula Miss Rate = 1 – Hit Rate.

Fig.1 Data Transfer

Fig.2 Speed Access

2.Come valutare le prestazioni della memoria cache?

Accesso -> operazioni di lettura/scrittura
Hit -> il dato si trova nella cache
Miss -> il dato no si trova nella cache, accesso ad una memoria più lenta
Miss_Rate -> n. di miss / n. di accessi
Hit_Rate -> n. di hit / n. di accessi

Esempio:
Tempo di accesso (cache) = 1ns
Tempo di accesso (memoria principale) = 10ns
Hit_Rate = 90% ( su 100 accessi, 90 sono nella cache)
Tempo di accesso (con la cache) = 90*1+10*1 = 100ns
Tempo di accesso (senza la cache) = 100*10 = 1000ns
Incremento di velocità = 100/10 = 10
Aumenta l’hit rate -> aumentano le prestazioni della cache -> diminuisce il consumo di energia -> aumenta la velocità di esecuzione.

3. Tipi di Miss
Compulsory miss – inizialmente la cache è vuota e il primo accesso è sempre un miss. Il programma ha bisogno di eseguire alcuni cicli fino a che la cache sarà piena e questo tipo di miss non si verificherà più.
Conflict miss – questo tipo si verifica solo sulle cache di tipo direct-map e solitamente avviene perché il dato si trova in diverse locazioni della cache.
Capacity miss – avviene perché la cache è piena e necessira di fare spazio per i dati attuali eliminando altri dati dalla cache; nella maggior parte dei casi sono dati vecchi.

Fig.3 CPU Die

4.Architetture della cache

La cache è suddivisa in “linee” che hanno 4 componenti:
- Valid bit: è posto a 1 quando dati validi sono memorizzati nella cache.
- Dirty Bit: è posto a 1 quando i dati vengono modificati e non avviene un aggiornamento nella memoria principale allo stesso tempo.
- Tag: questo campo indica quale indirizzo è presente in quella linea.
- Data: i dati prelevati dalla memoria principale.
Direct Mapped – ogni blocco dalla memoria principale può occupare solo un particolare blocco nella cache, non importa se quel blocco è vuoto o meno. Questo modello di organizzazione della cache non richiede una politica di sostituzione.
Fully Associative – ogni blocco dalla memoria principale può occupare qualunque blocco della cache. Se la cache è piena allora una politica di sostituzione ha bisogno di decidere quali dati devono essere rimossi dalla cache per fare spazio a questo nuovo blocco di dati.
Set Associative – la cache è divisa in vari insiemi. Il nuovo dato può occupare solo i blocchi di un particolare insieme, determinato da alcuni bit dell’indirizzo. In pratica è la più usata a causa di un ottimo rapporto tra implementazione ed efficienza.

5.Gestione della cache
La memoria cache ha piccole dimensioni comparata alla memoria principale di un qualunque sistema. Sapendo che il tempo di accesso della cache è 10 volte più piccolo della memoria esterna, prelevare dati dalla cache è un enorme vantaggio. Il processo di eliminare dati dalla cache per farne spazio a nuovi è chiamato “Algoritmo di sostituzione della cache”.

Oggi ci sono molti tipi di algoritmi che sono implementati nei controller delle cache. Alcuni di essi sono:
-LRU (Least Recently Used – usati meno recentemente) – Sostituisce i dati che non sono stati utilizzati per il periodo più lungo. LRU è implementato con una lista linkata.
-LFU (Least Frequently Used – usati meno frequentemente) – Ogni linea della cache ha un contatore che è incrementato ogni volta che il dato viene richiesto dalla cache.
- FIFO (First In First Out – il primo ad entrare è l primo ad uscire) – E’ molto semplice da implementare, ma ha un problema quando la memoria fisica è maggiore (Anomalia di Belady).
ARC (Adaptive Replacement Cache – Rimpiazzamento adattativo della cache) – combina le soluzioni LRU e LFU e dinamicamente si regola tramite queste due.

6.Ottimizzazione della cache

Usare un algoritmo per la gestione delle prestazioni della cache può essere significativamente incrementata usando i vantaggi di altri due princìpi:
-Località spaziale – Il dato richiesto dalla cache è posizionato vicino il dato precedente usato nella memoria fisica.
-Località temporale – I dati richiesti dalla cache sono recentemente usati o riutilizzati.

Alcune soluzioni molto spesso usano questi due metodi sono il prefetching, il loop blocking e la fusione, l’array pudding e l’array merging.

Leggi la versione Inglese: Memory Cache - Overview by RarCod