Località nel tempo: quando si fa riferimento a un elemento, c'è la tendenza a fare riferimento allo stesso elemento dopo poco tempo. Immaginiamo uno studente che debba fare una ricerca in biblioteca su un certo argomento, prenderà un numero di libri dagli scaffali e li porterà sul tavolo in cui sta studiando, se li ha porta sul tavolo è perché probabilmente deve consultarli dopo poco tempo.

Da un punto di vista informatico, vediamo in un pezzo di codice ricorsivo che calcola la serie di Fibonacci dato un numero in ingresso, come funzione la località temporale:

In questo codice notiamo che l'istruzione: sd a0, 8(sp) salva nello stack il valore del registro a0.
Dopo che viene effettuata la chiamata jal fib viene caricata dalla memoria con ld t0, 8(sp), in questo caso, per non fare un nuovo accesso in memoria, si può salvare nella cache tale valore e riprenderlo all'occorrenza. Questo in base al principio della località temporale secondo cui se si accede a una determinata locazione di memoria, è molto probabile che via si acceda di nuovo dopo poco tempo.

Località nello spazio: quando si fa riferimento a un elemento, c'è la tendenza a fare riferimento poco dopo ad altri elementi che hanno l’indirizzo vicino a esso. Per esempio, quando lo studente ha prelevato il libro sulle origini dell'argomento per cui sta facendo la ricerca. Ha notato che nei pressi di quello stesso libro c'è un libro che riguarda alcuni passi storici riguardo l'argomento di ricerca. Così, ha deciso di portare sulla sua scrivania anche questo libro, in cui più tardi potrà trovare delle informazioni utili. I bibliotecari dispongono i libri su uno stesso argomento sullo stesso scaffale per aumentare la località spaziale.

Da un punto di vista informatico, vediamo nel seguente pezzo di codice, come funziona la località spaziale:

con l'istruzione lw t2, 0(a0) viene caricata un word e piazzata nel registro 2.
Subito dopo l'etichetta carryon viene incrementato a0 di 4 con l'istruzione addi a0, a0, 4.
Ogni volta che carico una word dall'indirizzo in a0 è probabile che successivamente si acceda alle locazioni immediatamente successive, infatti a0 viene incrementato di 4 per accedere alla posizione successiva. Questo rispetta il principio della località temporale secondo cui se si accede a un certa locazione di memoria, è probabile che vi si acceda alle locazioni vicine ad esse dopo poco tempo.

Come abbiamo detto la memoria cache è posta vicino al processore e sfrutta i principi di località sopra descritti. L'obiettivo è di fornire all'utente una quantità di memoria pari a quella disponibile nella tecnologia più economica, consentendo allo stesso tempo una velocità di accesso pari a quella garantita dalla memoria più veloce.

Anche i dati, come le memoria, sono organizzati in modo gerarchico, un livello più vicino al processore contiene in generale un sottoinsieme dei dati memorizzati in ognuno dei livelli sottostanti, e tutti i dati si trovano memorizzati nel livello più bassi della memoria.

Rispetto all'analogia precedente:

• lo studente ha sulla scrivania un sottoinsieme di libri della biblioteca su cui lo studente sta lavorando;
• a sua volta la biblioteca è un sottoinsieme di tutte le biblioteche dell'università.

Quindi più ci si allontana dal processore, più aumenta il tempo necessario per accedere ai dati.
Una gerarchi di memoria può essere composta da più livelli, ma il trasferimento avviene tra due livelli vicini. Quindi ci concentriamo solo tra due livelli.

Il livello più vicino al processore è più veloce e piccolo, rispetto ai livelli sottostanti è la memoria cache.

La memoria cache è suddivisa in blocchi o linee di byte: se M sono le linee di memoria, allora linee di memoria. Ogni blocco ha una dimensione di word.

La colonna tag contiene l'indirizzo del blocco preso dalla memoria e salvato in cache.

Se il dato richiesto dal processore è contenuto in uno dei blocchi presenti nella cache si dice che c'è stata una hit. Se il dato invece non viene trovato nella cache si verifica una miss. In questo seconda caso per trovare tale dato, si deve accedere al livello inferiore della gerarchia (più lontano dalla CPU).
La CPU indirizza al byte.
La cache indirizza blocchi di word.

Lo hit rate è la frazione degli accessi alla memoria nei quali il dato desiderato è stato trovato nella cache.

Il miss rate che è (1 - hit rate) è la frazione degli accessi alla memoria nei quali il dato non è stato trovato nella cache. Quando la CPU non trova in cache un certo byte, viene salvato in cache un blocco di word che contiene tale byte nella memoria del livello sottostante (RAM).

Il tempo di hit è il tempo di accesso alla cache e comprende anche il tempo necessario a stabilire se il tentativo di accesso si risolve in un successo o in un fallimento, cioè se produce una hit o una miss.

La penalità di miss è il tempo necessario a sostituire un blocco del livello superiore (cache) con un nuovo blocco, caricato dal livello inferiore della gerarchia.

Molti programmi passano la maggior parte del tempo ad accedere alla memoria, il sistema di memoria è uno degli elementi cruciali che determinano le prestazioni del calcolatore nel suo complesso.

La memoria principale viene realizzata utilizzando DRAM, mentre i livelli più vicini al processo (cache) sono composti da SRAM.

• Maggiori dimensioni implica maggiori prestazione e a sua volta costi maggiori
• Dimensione della linea di cache (in una cache di 14KB è meglio avere 1024 linee di 16 byte, o 2048 di 8 byte?)
• Come tenere traccia di quali parole di memoria sono memorizzate nella cache in un dato momento?
• Istruzioni e dati vanno messi in una cache unificata o è preferibile avere cache specializzate per dati e istruzioni in modo da parallelizzare l'accesso alle istruzioni e ai dati?
• Numero delle cache: oggi arrivano fino a tre livelli

Abbiamo detto sopra, che tramite la colonna di tag viene mantenuto l'indirizzo del blocco preso dalla memoria. In realtà il numero salvato in questa colonna non è l'intero indirizzo, ma un'indirizzo parziale.

In tale contesto viene utilizzata quella che viene detta mappatura diretta.

Ad ogni locazione della memoria principale corrisponde una e una sola locazione della cache.
Una linea di cache è word, i blocchi che salva la cache, quando si verifica una miss, sono word presi dalla memoria principale. Per evitare di mantenere tutto l'indirizzo nella colonna tag viene effettuata una operazione in modulo:
(indirizzo blocco) modulo (numero di blocchi nella cache)

Abbiamo visto una cache che usa la mappatura diretta ovvero dove un blocco di memoria principale può trovarsi solo in un blocco specifico della cache.
Un approccio opposto è la mappatura completamente associativa in cui un elemento della memoria principale può trovare in una linea qualsiasi della cache. In questo caso quando va cercato nella cache se un certo blocco è presente bisogna scorrere tutte le linee della cache (come un array).

Ci sono cache che adottano degli schemi intermedi tra la mappatura diretta e associativa e vengono chiamati cache set-associative.

In una cache set-associative ogni blocco della memoria principale può essere caricato in
un numero prefissato di posizioni alternative (almeno due), e una cache con n
possibili scelte è chiamata set-associativa a n vie.
Una cache set-associativa a n vie è costituita da un certo numero di linee (o insiemi), ciascuna costituita da n blocchi.

Ciascun blocco della memoria principale viene mappato su un'unica linea (intesa come insieme di blocchi) della cache, individuata dal campo indice, e il blocco di dati può essere scritto
in uno qualsiasi dei blocchi che formano la linea.

Quindi una cache set-associative combina la mappatura diretta con il posizionamento completamente associativo di un blocco sulla linea: un blocco di memoria principale viene associato a una linea della cache in maniera diretta, e tutti i blocchi della linea vengono esaminati
per verificare se contengono l'elemento cercato.

Quindi la cache è formata di linee, ogni linea è formata da più blocchi. Una linea è individuata in maniera diretta, ma il blocco può essere presente in uno tra i diversi blocchi della linea in cui si sta cercando. In maniera diretta si trova la linea, in maniera associativa si cerca il blocco al suo interno.

Per la mappatura diretta avevamo:
(indirizzo blocco) modulo (numero di blocchi nella cache)

Per questo schema invece abbiamo:
(indirizzo blocco) modulo (numero delle linee nella cache)

Dove, lo ripetiamo, per linea in questo schema si intende un'insieme di blocchi (o linee).

Essendoci più blocchi all'interno di una linea, si ripetono le colonne di tag e dato.

La gestione di miss e hit necessita di una modifica all'unità di controllo del processore (ALU).
Miss della cache (istruzioni):

1. inviare il valore originale del program counter alla memoria;
2. comandare alla memoria principale di eseguire un'operazione di lettura e attendere che la memoria completi la lettura;
3. scrivere la word che proviene dalla memoria nella posizione opportuna del blocco della cache, aggiornare il campo tag corrispondente scrivendovi i bit più significativi dell'indirizzo presi direttamente della ALU e impostare a 1 il bit di validità;
4. far ripartire l'esecuzione dell'istruzione dall'inizio, ripetendo la fase di fetch, che questa volta troverà l'istruzione all'interno della cache.