Partendo dal presupposto essenziale, e fondamentale, che la memoria di tipo SRAM (statica) è di un ordine di
grandezza più veloce ed efficiente della memoria di tipo DRAM (dinamica) appare anche evidente come non sia
pensabile e/o proponibile utilizzare esclusivamente della memoria statica in un sistema di elaborazione, e questo
principalmente per via dei motivi legati al suo eccessivo costo. Questa è pertanto da considerare la reale
motivazione per cui si è da sempre dovuto ricorrere ed accontentarsi dell'ausilio della più lenta memoria di tipo
dinamico.
Altro presupposto fondamentale appare, peraltro, che la memoria di tipo dinamico sia molto più lenta della velocità
espressa da una cpu, del medesimo periodo storico di riferimento, e per questo motivo già a partire dai primi anni
'60 si pensò di escogitare dei meccanismi che fossero in grado di trovare un punto d'incontro per utilizzare più
proficuamente entrambe le tipologie di memoria all'interno della medesima architettura computazionale, trovando
nella velocità della SRAM il limite superiore, seppur teorico, al miglioramento delle prestazioni in memoria.
[tab=30]Principio di località
Già in quei primi anni '60 alcuni studi teorici e dati sperimentali sulla esecuzione dei programmi posero in evidenza
che i riferimenti alla memoria godono della località di riferimento, ovvero del principio di località; a questo
proposito è utile chiarire come esistano fondamentalmente due tipi di località di riferimento: la località spaziale e
quella temporale.
La località spaziale enuncia che nell'esecuzione di un qualsiasi programma appare altamente probabile che, data
una qualsiasi istruzione in corso di esecuzione, la seguente e le successive istruzioni possano trovarsi con pressoché
ogni probabilità in posizioni realmente contigue. Questo assunto può essere facilmente verificabile in quanto il flusso
delle istruzioni non risulta quasi mai essere troppo frammentato, significando che i programmi tendono a generare
riferimenti a zone di memoria consecutive o comunque molto ravvicinate.
La località temporale, invece, partendo dal presupposto che tutti gli algoritmi contengono prevalentemente dei
cicli, porta dunque ad enunciare che le zone di memoria contenenti i cicli, vengano accedute più volte dal flusso di
istruzioni conseguente all'esecuzione di un determinato programma. In buona sostanza, accade che nel momento in
cui venga eseguita una generica istruzione, o venga fatto riferimento a un dato, appare altamente probabile come
nel futuro più prossimo possa essere nuovamente eseguita la medesima istruzione o comunque esser fatto un
riferimento al medesimo dato.
Per dare indicazioni più concrete, a fronte di statistiche reali sulla correttezza e l'impatto del principio di località,
si è giunti a determinare come in un generico programma circa l'85-90% del tempo di esecuzione della cpu viene
dedicato al solo 10-15% del proprio codice.
A seguito della considerazione, poi, di dover tenere conto dei differenti costi della memoria statica rispetto alla
dinamica, il principio di località porta a suggerire di mantenere in quella statica solo i dati o le parti di programma
che in modo inconfutabile abbiano alta probabilità di essere indirizzate o accedute nel prossimo futuro. Queste
considerazioni inducono alla convenienza di ripartire la memoria interna in una, possibilmente estesa, memoria
principale realizzata tramite componenti DRAM, e in un sensibilmente più ridotto quantitativo di memoria SRAM,
avente la particolare funzione di cache, quindi con una modalità opportunamente interposta tra la veloce cpu e la
lenta memoria centrale.
[tab=30]Criterio funzionale
Se vogliamo avere una idea più chiara dell'importanza e delle implicazioni inerenti la memoria cache, dobbiamo
per forza di cose analizzare i suoi criteri basilari di funzionamento; per semplicità di comprensione e come base
di partenza ci interesseremo alle sole operazioni di lettura, in quanto quelle di scrittura comporterebbero a
supplemento alcune complicazioni in più: lasciamo per ora queste attività supplementari a futuri approfondimenti.
Detto questo, partiamo con l'assumere che una generica operazione in lettura avviata dalla cpu, comporta i
seguenti passi:
a) la cpu genera l'indirizzo Y ed il relativo comando di lettura;
b) se il dato all'indirizzo Y della memoria centrale non risulta duplicato nella cache, si rileva un miss.
[tab=25] In questa eventualità si renderà necessario:
[tab=30] 1) leggere il dato dalla memoria principale;
[tab=30] 2) copiarlo nella cache, tenendo opportunamente traccia dell'indirizzo Y, in modo tale
[tab=50] che eventuali riferimenti futuri trovino correttamente il dato nella cache ancor prima
[tab=50] che nella memoria centrale stessa.
c) se invece il dato sarà trovato nella cache, si avrà allora un hit: in questa eventualità il dato
[tab=25] verrà letto direttamente dalla cache, senza dover accedere in alcun modo alla memoria centrale.
Le attività descritte portano ad evidenziare alcune specifiche questioni relative alla gestione e all'organizzazione
della cache. Innanzitutto l'implicazione più importante porta chiaramente a stabilire che occorrerà tener traccia
di ogni dato via via contenuto nella cache. Si rende necessario, a tale scopo, prevedere una sorta di catalogo che
consenta di cercare e recuperare il dato strettamente legato all'indirizzo generato dalla cpu: la sua struttura
dipenderà peculiarmente dal tipo di organizzazione funzionale che verrà scelta per la cache.
Un altro aspetto fondamentale è legato alla effettiva quantità di informazioni che si leggeranno dalla memoria
verranno quindi portati nella cache a seguito di un miss. In generale sembrerebbe più logico e naturale trasportare
solo il dato interessato dall'indirizzo (Y) in questione, invece per le implicazioni precedentemente descritte in
merito al principio di località spaziale, si può facilmente giungere alla determinazione dell'estrema convenienza
di portare in cache anche il blocco di celle di memoria centrale contiguo (precedente e seguente) a quello interessato,
avendo di certo il contenuto di queste una elevata probabilità di essere poi indirizzato nel futuro più prossimo.
A motivo di ciò, varrebbe la pena di considerare il blocco della memoria centrale e quello della cache come
un insieme organico di piccoli blocchi di dimensione fissa e ben determinata, identificati ed identificabili
come delle vere e proprie linee, ed in quest'ottica una linea diventerebbe così la quantità unitaria di informazioni
trasferita tra memoria principale e cache. Procedendo oltre, appare evidente come occorra anche attivare dei
meccanismi per giungere a trasferire quantomeno una completa linea alla volta, in modo da ridurre le latenze,
quindi i ritardi, dovuti al tempo medio di trasferimento di ogni singolo dato: questa tecnica verrà indicata come
trasferimento burst.
[tab=30]Organizzazione
Per quanto riguarda il modo con cui debba esser organizzata la cache, è rilevante il modo con cui risulteranno
associate le linee della memoria centrale a quelle della cache, cioè il modo con cui andrà determinato quale
posizione nella cache dovrà essere riempita da una linea letta dalla memoria centrale. Come supposizione
teorica una linea della memoria principale potrebbe esser copiata in una qualunque delle linee previste nella
cache, ed in questa eventualità si parlerebbe di una cache completamente di tipo associativo; nel caso opposto,
invece, ovvero quando una linea di memoria principale dovesse esser allocata sempre nella medesima
posizione di cache, si dovrebbe parlare di una tipologia a mappatura diretta.
Appare già chiaro come ognuna abbia delle particolarità funzionali che presentino dei particolari vantaggi,
così come d'altra parte entrambe inducano a degli importanti svantaggi operativi: per queste motivazioni
sembra più logico e conveniente adottare una organizzazione di tipo associativo a vie multiple (set associative),
detta più comunemente ad n vie, dove n sta ad indicare il numero di blocchi indipendenti previsti per
la cache.
Per convenienza, daremo per assunto in seguito di avere a che fare con una moderna cpu a 64bit, significando
più precisamente che le letture in memoria, corrispondenti al fetch delle istruzioni, attivino sempre il
trasferimento di 64bit, e soprattutto che tale lettura avvenga soltanto per parole allineate, quindi con un
indirizzo multiplo di 8, per essere coerenti con la convenzione adottata universalmente secondo la quale gli
indirizzi debbano comunque essere associati al byte.
Diverso sarebbe iul caso di letture/scritture dove sia possibile trasferire una parola intera o anche una mezza
parola o addirittura un singolo byte: se si trattasse del trasferimento di una parola, allora questa dovrebbe
comunque essere sempre allineata, al contrario di una mezza parola od un byte, laddove la cpu dovrebbe non solo
generare un indirizzo multiplo di 8, ma anche emettere degli opportuni segnali in modo tale da selezionare
correttamente la parte interessata della parola. Pertanto ancora una volta, anche nelle differenti organizzazioni
della cache, ci si riferirà alle sole operazioni di lettura.
[tab=30]Cache a mappatura diretta
La mappatura diretta prevede per definizione che una determinata linea di memoria principale venga sempre
mappata nella medesima posizione della cache. Per chiarirci le idee, possiamo assumere di avere una situazione
analoga a questa:
[tab=30] * una cache di capacità uguale a L = 2l linee;
[tab=30] * linee di P = 2p parole, ovvero una capacità di cache pari a C = L x P parole;
[tab=30] * una memoria centrale della dimensione di B = 2b blocchi, multipla ovviamente della dimensione della cache.
A seguito della mappatura diretta tutte le linee B in posizione IL, all'interno di un qualunque blocco B di
memoria vengono mappate sulla linea IL della cache come indicato nella seguente figura:
[tab=100]
[tab=100]cache a mappatura diretta
Si può notare dall'organizzazione a mappatura diretta, come in realtà la cache si debba comporre di due ben
distinti banchi di memoria:
[tab=100]
[tab=100]esempio di mappatura diretta
L'indirizzo di una parola dovrebbe allora essere previsto come di seguito descritto:
[table=][tr=]
[td=]IB (blocco) ....[/td] [td=]IL (linea) ....[/td] [td=]IP (parola)[/td]
[/tr]
[tr=]
[td=]48bit [/td] [td=]8bit [/td] [td=]8bit[/td]
[/tr][/table]
indirizzamento di una parola a 64bit
Il campo IB indica a quale blocco appartiene l’indirizzo specifico di memoria, e rappresenta la parte più
significativa dell’indirizzo.
Il campo IL dell’indirizzo permette di identificare la linea in RAM, mentre il campo IP indica la parola specifica
ed è diviso in due parti.
Se l’indirizzo è a 64bit un blocco memorizza 32 byte ossia 4 parole, e la cache deve presentare 32 linee.
L’offset di blocco ha 8bit, dei quali i 4bit meno significativi individuano il byte all’interno della parola, gli altri
4bit a sinistra individuano la parola nel blocco.
L’indirizzo di blocco è composto da 48bit che individuano il TAG mentre gli 8bit successivi meno significativi
individuano l’indice di linea.
Il banco che si trova alla destra (DATA) ha le precisa funzione di contenere i dati, mentre il banco alla sinistra
rappresenta il catalogo (CATALOG o se vogliamo indice) del banco dove i dati sono contenuti. Ogni posizione del
banco DATA corrisponde ad una linea della cache, mentre ogni posizione del banco di sinistra (CATALOG) ha una
dimensione pari a quella del campo IB dell'indirizzo generato dalla cpu: per questa motivazione il banco
CATALOG viene indicato con la definizione TAG RAM, ed allo stesso modo il banco di destra si definisce
DATA RAM.
Riferendoci alla figura soprastante, proviamo a spiegare il meccanismo che si pone alla base della mappatura
diretta.
1) il campo IL dell'indirizzo ci permette di identificare la posizione della corrispettiva linea in
[tab=30]DATA e TAG RAM;
2) il contenuto della posizione ottenuta in TAG RAM viene confrontato viene comparato con il
[tab=30]campo IB dell'indirizzo;
3) se la comparazione ottiene una uguaglianza, allora il dato ricercato si trova nella cache e può
[tab=30]essere letto direttamente dal banco DATA RAM, in quanto l'uscita della parola selezionata viene
[tab=30]abilitata dalla linea HIT verso il multiplexer interessato;
4) se la comparazione dà invece un risultato negativo, la cache non contiene copia del contenuto
[tab=30]della locazione di memoria centrale indirizzata. In questo caso la linea HIT risulta non asserita e
[tab=30]viene automaticamente ad innescarsi il processo di lettura dalla memoria, della linea contenente
[tab=30]la locazione indirizzata; il campo IB dell'indirizzo viene copiato alla linea IL nella TAG RAM,
[tab=30]e di conseguenza la linea letta viene copiata nella medesima posizione in DATA RAM.
E' utile osservare che con la mappatura diretta le ricerche in TAG e DATA RAM possono procedere assolutamente
in concomitanza, significando che al momento della lettura in TAG RAM il contenuto in DATA RAM risulta nello
stesso tempo già immediatamente pronto per la lettura, infatti se la comparazione tra IB ed il contenuto della
posizione indirizzata in TAG RAM dà esito positivo, l'apposito segnale di Output Enable, rende immediatamente
disponibile la parola letta.
La mappatura diretta rappresenta quindi la soluzione più immediata alla realizzazione di una memoria cache,
ed il vantaggio di tale organizzazione è senza dubbio l’enorme semplicità costruttiva: infatti la linea di memoria
RAM viene mappata nella stessa linea di cache. Gli svantaggi, invece, sono rappresentati dal fatto che non
esiste alcuna liberta di scelta nella dislocazione delle linee, e quindi non appare possibile sfruttare appieno la
ampiezza della cache, con la possibilità di sovrascrivere più volte un dato, aumentando quindi la percentuale dei
miss.
L'inconveniente deriva dal fatto che qualora i programmi presentano una località tale da coinvolgere due blocchi
di memoria ad ogni passaggio da un blocco all'altro, le linee di cache vanno ad essere necessariamente sostituite,
riducendo di fatto le prestazioni complessive dell'intera cache. Nonostante ciò diversi studi hanno portato alla
dimostrazione di come la bontà intrinseca della mappatura diretta sia dello stesso valore, se non superiore a
quello di altre soluzione organizzative.
[tab=30]Cache associativa
