Capitolo 11 La memoria cache

(1)

Calcolatori elettronici – Architettura e organizzazione

Capitolo 11

La memoria cache

Gerarchie di Memoria

• Dati sperimentali mostrano che i riferimenti alla memoria godono della proprietà di località spaziale e temporale.

• Località spaziale: tendenza a generare riferimenti a zone contigue

• Località temporale: tendenza a riprodurre riferimenti generati in precedenza

• Conviene organizzare la memoria come una gerarchia

(2)

Gerarchie di memoria

• Ai livelli più bassi memorie meno veloci e più capienti

• Ai livelli più alti memorie più veloci di modeste dimensioni – Memoria Ausiliaria: Dischi

– Memoria principale: DRAM – Cache: SRAM

– Gli stessi registri di CPU possono essere considerati come il livello più alto della gerarchia

• Organizzazione

– Il trasferimento tra livello avviene per blocchi

– Un numero predefinito di blocchi di un livello superiore costituisce un blocco del livello inferiore

La Cache

• La cache è il livello superiore alla memoria centrale

• I blocchi di cache si chiamano linee

• I blocchi della memoria centrale si chiamano pagine

• Un pagina contiene un numero predefinito di linee (ovviamente il numero è una potenza del 2)

(3)

La Cache

• Un indirizzo generato dal processore viene cercato nella memoria Cache:

• se si trova => hit e quindi viene direttamente trasmesso al processore

• Se non si trova => miss si ricerca nel livello di memoria inferiore

• tasso di hit (h) : rapporto tra il numero di hit nel livello superiore e il numero totale dei riferimenti;

• tasso di miss (m) : rapporto tra il numero di miss nel livello superiore e il numero totale dei riferimenti.

m = 1 -h

• tc : tempo di accesso alla cache

• tp : tempo di penalizzazione (tempo per accedere alla memoria centrale e per portare la linea in cache)

• t : tempo medio di accesso alla cache t= h tc + m tp

Prestazioni

(4)

• Occorre una directory per rintracciare la presenza di un dato nella cache

• Per il principio della località spaziale, conviene copiare non la singola parola indirizzata, bensì l’intera linea => la linea è l’unità di trasferimento fra Cache e memeoria principale

Tempo di penalizzazione: Tp = T_ACCM+ T _trasf Dove T_ACCMè il tempo di accesso della mem. princ.

T _trasf= è il tempo di traferimento verso la cache

La Cache

Cache a mappatura diretta

(5)

• una data linea di memoria (centrale) viene sempre mappata nella stessa posizione di cache

• La memoria centrale si suddivide (logicamente) in blocchi della stessa dimensione della cache

• Si indichi con

– W = 2^w il numero di parole per linea

– C la capacità della cache (in numero di parole) – L = 2^l il numero di linee nella cache

• Ovviamente C = L W (se una parola è di 4 byte, allora la capacità della cache misurata in numero di byte è pari a 4C)

Cache a mappatura diretta

Interpretazione dell’indirizzo (di parola) :

• La memoria centrale più essere vista come composta da B = 2^bblocchi di dimensione C

(6)

Mappatura diretta

• NB: il precedente è un modello(non corrisponde esattamente a uno schema realizzativo)

• n_Lidentifica la (posizione della) linea in DATA RAM e in TAG RAM

• Il contenuto di questa posizione di Tag RAM viene confrontato con il campo n_Bdell’ indirizzo generato dal processore

• Se il confronto indica uguaglianza (hit) la linea è in cache

• La figura precedente mostra lo schema di principio per estrarre la parola indirizzata

– Nella pratica, i due campi a destra dell’indirizzo

individuano complessivamente la parola (il byte) del blocco di lunghezza C.

(7)

Mappatura diretta

• Pregi:

– Semplicità – Velocità

• Difetti:

– Possibile alto tasso di collisioni

• Quando una qualunque linea di memoria centrale può essere portata in qualunque posizione di cache.

• Il Tag è il numero di linea entro la memoria centrale

• Comporta una memoria CAM (Content Addressable Memory)

• Il campo n_Xdell’indirizzo viene confrontato (in parallelo) con tutte le posizioni di TAG RAM

• La DATA RAM può essere indirizzata solo dopo che si è concluso il confronto con il contenuto di TAG RAM

• Vantaggio:

– Minime collisioni

• Svantaggi:

– Lenta – Costosa

Cache completamente associativa

(8)

• Cerca di prendere il meglio della soluzione a mappatura diretta e della completamente associativa:

– Efficienza (tempo di accesso) della soluzione a mappatura diretta

– Senza l’elevato tasso di collisioni di questa

• La cache è divisa in vie

• La medesima linea si mappa sulla medesima posizione di qualunque via

Cache semi-associativa

(9)

• In caso di Write-miss:

– Write-allocate: porta in cache la linea mancante

– Write-non-allocate: la linea non viene portata in cache (viene solo aggiornata la memoria centrale). Ha senso in considerazione del fatto che:

– il numero di scritture rispetto a quello delle lettureèrelativamente basso – A differenza delle operazioni di fetch (alta probabilità di letture sequenziali

contigue), è probabile che gli indirizzi di scrittura siano sparsi

• In caso di Write-hit (consistenza fra Mcache e Mprinc):

– Write-through (scrittura in memoria immediata): viene aggiornata la cache e al tempo stesso la parola di memoria

– Write-back (scrittura in memoria differita): viene aggiornata solo la cache. La memoria centrale viene aggiornata

La scrittura

(10)

Linee di cache: stato

• Validità di una linea di cache (LdC): inizialmente il contenuto di una LdC non è significativo. Man mano che vengono caricate LdC si avranno linee valide e non-valide

• Serve un bit di validità

• In caso di operazioni di I/O è possibile che linee di memoria centrale siano aggiornate.

• Corrispondente LdC (se esiste) deve transire in uno stato non valido Oppure che linee trasferite da dispositivi di I/O verso l’esterno non siano aggiornate per effetto del copy-back (ma anche nel caso di copy-through ci possono essere problemi di sincronizzazione)

• Soluzione: memoria interessata ai trasferimenti I/O viene resa non cacheable

Linee di cache: rimpiazzamento

• LRU (Least Recently Used): principio standard per le CPU attuali

• FIFO (First in First Out): non praticata

• RAND: casuale, le prestazioni sono comparabili a LRU

(11)

Prestazioni

Divisa/unificata

• Cache unica per dati e istruzioni o cache separate (per dati e istruzioni)

– Agli albori dell'impiego le cache erano unificate – Le macchine attuali hanno cache divise

• Cache divise

– Gli accessi relativi alle istruzioni hanno il livello di località alto, per queste il valore di hit è alto

– Cache istruzioni più semplici da realizzare (di solito sola lettura) – Determinano una architettura equivalente alla Harvard

– Non è detto che diano sempre le migliori prestazioni (a parità di dimensione globale (Cunif = Cdati + Cistr) sotto certe condizioni di carico la cache unificata potrebbe essere superiore)

(12)

Cache multilivello

• Rappresentano la pratica corrente

• Gerarchia di memoria più granulare, sfruttando al meglio le differenti caratteristiche tecnologiche dei componenti

• Il livello più alto (L1) ha una dimensione di un ordine di grandezza inferiore a quella del livello inferiore(L2)

• Un miss in L1 determina la ricerca della linea in L2; se la linea non è neanche in L2:

– Viene letto un blocco di linee (contigue) da M e portate in L2 – La linea indirizzata (appartenente al blocco) viene trasferita in L1

Cache multilivello -prestazioni

• t_c tempo medio di accesso alla cache

• h₁/ h₂ tassi di hit (L1/L2)

• m₁ tasso di miss L1

• m₂ tasso di miss L2 (n. fallimenti/n. accessi a L2)

• t_c1 tempo di accesso alla cache L1

• t_c2 tempo di accesso alla cache L2 (comprende anche il tempo per trasferire la linea da L2 a L1)

• t_p tempo di penalizzazione su L2 ( tempo di accesso a L2 più tempo necessario a portare il blocco in L2)

t= h tc + m tp =>

t_c₌h₁t_{c1 +}m₁(h₂t_c2+m₂t_p)

(13)

Confronto livelli di Cache

• La tabella ha valore indicativo

Posizionamento

(14)

Posizionamento

• Cache fisica: quando è posta a valle del meccanismo di traduzione degli indirizzi logici (virtuali)

– Più semplici

• Cache virtuale: quando è posta a monte del

meccanismo di traduzione degli indirizzi (più efficienti) – Se il dato è in cache non c'è bisogno di passare attraverso la

traduzione degli indirizzi

– Ha il problema dell'Alias: lo stesso indirizzo virtuale può

appartenere a due distinti processi (con spazi di indirizzi diversi)

• Invalidazione di tutta la cache (cache flush) quando c’è un cambio di contesto (processo)

• Aggiungere al Tag il “Tag di processo”, in modo da verificare se l'indirizzo appartiene al processo correntemente in esecuzione.