Architettura dei Calcolatori 11 Cache

Dispense del corso diArchitettura dei CalcolatoriArchitettura dei Calcolatori

Memorie cache

Architettura dei calcolatori a.a. 2007/2008

Gerarchia di memorie

• Organizzazione gerarchica (tipica dei calcolatori general-purpose)

• La CPU vede un solo tipo di memoria, indirizzata direttamente tramite un identificatoreLa CPU vede un solo tipo di memoria, indirizzata direttamente tramite un identificatore (indirizzo)

• L’hardware (MMU) e il sistema operativo gestiscono invece un insieme di memorie organizzate gerarchicamente che contengono repliche dei dati in modo che la CPU trovi il dato utile nella memoria piu’ veloce possibile

• Gerarchia di memorie: La memoria del calcolatore e’ organizzata gerarchicamente in modo da comprendere poche memorie a bassa capacita’ ed alti costi ma molto veloci e molta memoria più lenta e di capacita’ maggioremolta memoria più lenta e di capacita’ maggiore

memoria

CPUAddr.Data


DRAM e SRAM

• La memoria principale viene realizzata normalmente utilizzando componenti DRAM (Dynamic Random Access Memory, ovvero memoria dinamica ad accesso casuale)d a ca ad accesso casua e)

• Memorie più veloci (tipicamente usate per le Memorie Cache di cui si parlerà in questo capitolo) sono composte da SRAM (Static Random Access Memory).Access Memory).

• Il costo per bit delle DRAM è più basso di quello delle SRAM; d’altra parte, le prime sono molto più lente delle seconde. La differenza di prezzo dipende dal fatto che le memorie DRAM utilizzano menoprezzo dipende dal fatto che le memorie DRAM utilizzano meno transistori per ogni bit da memorizzare: consentono quindi di raggiungere capacità superiori a parità di area di silicio.

• Viste le differenze di costo e di velocità diventa conveniente costruire• Viste le differenze di costo e di velocità, diventa conveniente costruire una gerarchia di livelli di memoria, con la memoria più veloce posta più vicino al processore e quella più lenta, meno costosa, posta più distante.

• L’obiettivo è quello di fornire all’utente una quantità di memoria pari a• L obiettivo è quello 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 tecnologia più velocetecnologia più veloce


Principi di Località

Regole base dell'efficienza e’ rendere di massima velocità il caso comune• Sfruttamento della località spaziale e temporale

Principio di località un programma in ogni istante utilizza una porzione limitata dello spazio di indirizzamentodello spazio di indirizzamento

• Località spaziale: accedendo ad un dato e’ assai probabile che si debba accedere ad altri dati localizzati “vicino” nello spazio di indirizzamentoaccedere ad altri dati localizzati vicino nello spazio di indirizzamento

• Località temporale: accedendo ad un dato e’ assai probabile che si debba riaccedere ad esso in un tempo “vicino”

• Dati che inizialmente si trovano ad un livello più basso – (loc. temporale) conviene spostarli in memorie più veloci

(l i l ) i t h i d ti i i i– (loc. spaziale) conviene spostare anche i dati vicini

• I programmi NON vedono la gerarchia ma referenziano i dati come se fossero sempre in memoria centrale ( a parte per i registri che sono nominati p ( p p gesplicitamente) percio’ bisogna mantenere il più vicino possibile alla CPU dati utilizzati più recentementeLa gerarchia delle memorie deve prevedere in successione memorie sempre più larghe e più lente per mantenere i dati nei livelli più alti proporzionatamente allalarghe e più lente per mantenere i dati nei livelli più alti proporzionatamente alla previsione della frequenza d’uso.


Le memorie cache(Wiki di )

• DefinizioneIn informatica la cache (nascondiglio deposito segreto in inglese) è un

(Wikipedia)

– In informatica, la cache (nascondiglio, deposito segreto, in inglese) è un insieme di dati che viene memorizzato in una posizione temporanea, dalla quale possa essere recuperato velocemente su richiesta. Le parole chiave sono "temporanea" e "velocemente": in pratica questo significa che non c'èsono temporanea e velocemente : in pratica, questo significa che non c è nessuna certezza che i dati si trovino nella cache, ma che convenga comunque fare un tentativo per verificarne l'eventuale esistenza

• Funzionamento di una cache– Una cache è associata ad una memoria "principale", in cui risiedono i dati.Una cache è associata ad una memoria principale , in cui risiedono i dati.

Essa è tipicamente di capienza inferiore rispetto alla memoria principale, ma il suo utilizzo è più conveniente in termini di tempo di accesso e/o carico sul sistema. Quando è necessario l'accesso ad un dato, questo dato viene prima , q pcercato in essa. Se è presente e valido, viene utilizzata la copia presente. Viceversa, viene recuperato dalla memoria principale, e memorizzato, nel caso possa servire successivamente.


Organizzazione delle cache

• La memoria cache viene vista come organizzata in blocchi o linee(cache lines); la minima quantità di informazione che può essere trasferita fra due livelli è appunto un blocco. as e a a due e è appu o u b occo

• Se il dato richiesto dalla CPU fa parte di uno dei blocchi presenti nella cache di livello superiore si dice che la richiesta ha avuto successo (hit)cache di livello superiore, si dice che la richiesta ha avuto successo (hit).

• Se invece il dato non si trova nel livello superiore, si dice che la richiesta fallisce (miss): per trovare il blocco che contiene i dati richiesti, bisogna accedere al livello inferiore della gerarchia e trasferire il bloccoaccedere al livello inferiore della gerarchia e trasferire il blocco corrispondente al livello superiore.

• Si indica come frequenza dei successi (hit rate) la frazione di accessi alla i h h t t il d t d id t l li ll imemoria che hanno trovato il dato desiderato nel livello superiore;

spesso questo valore viene utilizzato come indice delle prestazioni della memoria gerarchica. D l t l f d i f lli ti ( i t ) i• Dualmente, la frequenza dei fallimenti (miss rate), pari a

– miss rate = (1.0 – hit rate) è la frazione di accessi alla memoria che non hanno trovato il datoè la frazione di accessi alla memoria che non hanno trovato il dato desiderato nel livello superiore.


Classificazione dei miss

• InevitabiliPrimo accesso a un bloccoPrimo accesso a un blocco

• CapacitàMiss che accadono quando si accede a un blocco sostituitoMiss che accadono quando si accede a un blocco sostituito

• ConflittoMiss che accadono poiché i blocchi sono scartati a causa di una specificaMiss che accadono poiché i blocchi sono scartati a causa di una specifica strategia di "set-mapping"


Cache

• Parametri di progettazione delle cache:

1) Piazzamento del blocco (o funzione di traduzione o mapping): dove può essere allocato il blocco al livello corrente.

2) Identificazione del blocco: come si può ritrovare il blocco a livello corrente

3) Rimpiazzamento del blocco: come si sceglie quale blocco sostituire

4) Strategia di scrittura


Piazzamento del blocco

• Consideriamo innanzitutto il problema del piazzamento di un blocco. In fase di esecuzione, la CPU può a priori tentare di accedere a una qualunque parola nello spazio totale di indirizzamento: spazio che puòqualunque parola nello spazio totale di indirizzamento: spazio che può essere qui visto come corrispondente all’intera memoria RAM (livello più basso nelle gerarchie della memoria di lavoro), ma che certamente

d di l ll di ibil ll h di li ll ieccede di gran lunga quello disponibile nella cache di livello superiore.• Occorre quindi definire le possibili modalità per consentire ad ogni

parola della memoria indirizzabile di trovare (ove necessario) una p ( )posizione della cache in cui possa essere trasferita – in altre parole, occorre definire una corrispondenza tra l’indirizzo in memoria della parola e la locazione nella cache.e la locazione nella cache.

• A questo scopo, sono state definite essenzialmente tre soluzioni diverse:– Cache a indirizzamento diretto (direct mapped)– Cache set-associativa a n vie– Cache completamente associativa


Direct mapped

• Indirizzamento nelle cache a indirizzamento diretto• Indirizzo di memoria di N bit diviso in 3 campi: tag, index, offset.

N bit i ifi ti i ( ff t) tt di i di id il i l– NO bit meno significativi (offset) permettono di individuare il singolo byte della parola nella linea di cache. Se la parola non è indirizzabile per byte O è uguale a zero

– NI bit (index) per individuare la posizione della linea di cache– NT = N-NO-NI bit di etichetta (tag) per verificare che la linea di cache

contenga esattamente l’indirizzo cercatocontenga esattamente l indirizzo cercato• Esempio

– Indirizzi di memoria a 32 bit– Cache a indirizzamento diretto con una parola di 4 byte per linea di

cache e1024 linee di cache (210)– 1024 linee di cache (210)

– Struttura dell’indirizzo di memoria:• Bit 0 e 1 per individuare il singolo byte (offset)• Bit 2-11 per individuare la linea di cache (index)• Bit 12-31 come etichetta (tag)


DIRECT MAPPED• Un blocco può essere posto in un solo indirizzo sulla cache • E’ indicato dalla parte di indirizzo detta index; la parte di offset seleziona

ll’i t d ll li l i t t di t i f t t ilall’interno della linea, la rimanente parte di tag viene confrontata con il valore della cache directory

• Baddr= (Index|Offset) mod Nb( | )• Es (tag | index | offset) (20|7|5) tutti i blocchi aventi uguali index e offset e

diverso tag sono mappati allo stesso indirizzo su cache

Tag Index Offset

OffsetIndex

address

Tag DataData Data Data= Data

Yes

No

Cache

misshit

Main MEM.


FULLY ASSOCIATIVE• Ogni blocco può essere messo ovunque nella cache memoria CAM

content addressable memory• manca la parte index (0 bit di index)manca la parte index (0 bit di index)• più costosa (tanti comparatori quante le linee)• e più efficace, no miss di conflitto

Tag Offsetaddress

Tag Data

Offset

Data Data Data= DataTag DataData Data Data= Data

g DataData Data

YesCache

=Tag DataData Data Data= Dataor

Nomisshit


SET ASSOCIATIVE (n-way)• Ogni blocco può essere messo solo in un insieme di fissati n blocchi

nella cache; l h ’ di i i bl hi/ t i di ti d i bit di i d (i d i• la cache e’ divisa in nblocchi/n set indicati dai bit di index (index minore che nel direct mapped). Ogni set e’ acceduto in modo direct mapped.

• Ogni blocco nel set e’ acceduto in modo fully associative, richiede n g y ,comparatori;

Tag Index Offsetaddress

Tag Data

OffsetIndex

Data Data Data= Data

address

tTag DataData Data Data

YesCache

= DataTag DataData Data Data= Data set

Nomisshit


Identificazione e Sostituzione del blocco

• Identificazione del blocco– Indirizzamento diretto:

• Calcolo posizione• Calcolo posizione• Verifica etichetta e verifica bit valido

– Completamente associativo:• Confronta etichetta in ogni blocco e verifica bit valido• Confronta etichetta in ogni blocco e verifica bit valido

– Set-associativo• Identifica insieme• Confronta etichette dell’insieme e verifica bit Valido• Confronta etichette dell insieme e verifica bit Valido

• Sostituzione del bloccoSostituzione del blocco– Definito dall’indirizzo nelle cache a indirizzamento diretto– Cache set associative or completamente associative:

C• Casuale• LRU (Least Recently Used)


Strategie di scrittura di un blocco

• Write through– L’informazione viene scritta sia nel blocco del livello superiore sia nel blocco

di livello inferiore della memoriadi livello inferiore della memoria• Write back

– L’informazione viene scritta solo nel blocco di livello superiore– Il livello inferiore viene aggiornato solo quando avviene la sostituzione del

blocco di livello superiore.– Per ogni blocco di cache è necessario mantenere l’informazione sulla

scrittura: Ad ogni blocco è associato un bit MODIFICA che indica se il blocco in cache è stato modificato o meno e va quindi copiato in memoria in caso di sostituzione

• Confronto:– Write Through: fallimenti in letture non si tramutano in scritture in memoriaWrite Through: fallimenti in letture non si tramutano in scritture in memoria

(penalità di fallimento più lunga)– Write Back: non si hanno aggiornamenti ripetuti delle stesse celle di

memoria L’aggiornamento avviene una volta solamemoria. L aggiornamento avviene una volta sola


Esercizio• Esercizio : Un processore a 16 bit di dati e 24 bit di indirizzo ha una cache direct mapped

di 16KByte. Ogni linea della cache ha lunghezza 2 PAROLE. Si deve:• 1)Scrivere le dimensioni di tag, index e offset.) g• 2)Si supponga che la cache sia inizialmente vuota e che debbano essere letti in sequenza i

dati A,B,C,D,E,F,G,H i cui indirizzi in memoria sono indicati in tabella.• Dato Indirizzo a) Indicare quali dati provocano una sostituzione di un dato in cache e che

dato viene sostituito• b) Indicare (possibilmente con uno schema) quali dati saranno in cache alla fine e in che

posizione della cache.• c) Indicare quali dati generano una miss (indicando se di tipo obbligatorio)e quali una hit.• A 000000H• B 000001H• C 000030H• D 004000H• E 004003H• F 000002H• G FF8033H• H 000031H


Esercizio• Soluzione esercizio 3: Ogni blocco 2 PAROLE (da 16 bit) = 4 byte 2 bit di offset• 16Kbyte direct mapped (blocchi 4 byte)= 4K sets • 12 bit di index• su 24 bit di indirizzo si ha che 24-12-2 = 10 bit di tag• Dato Indirizzo Tag Index Offset• A 000000H 0000 0000 00 00 0000 0000 00 00

B 000001H 0000 0000 00 00 0000 0000 00 01• B 000001H 0000 0000 00 00 0000 0000 00 01• C 000030H 0000 0000 00 00 0000 0011 00 00• D 004000H 0000 0000 01 00 0000 0000 00 00• E 004003H 0000 0000 01 00 0000 0000 00 11• F 000002H 0000 0000 00 00 0000 0000 00 10• G FF8033H 1111 1111 10 00 0000 0011 00 11• H 000031H 0000 0000 00 00 0000 0011 00 01

• A viene caricato nel set 0 con una miss obbligatoria, essendo la cache vuota. L’accesso di B trova già il dato presente quindi genera una hit e non provoca sostituzione. C viene caricato nel set 12 e genera una miss obbligatoria. D deve essere caricato nel set 0, ma avendo TAG diverso da quello presente in tale g , q pset, genera una miss e la sostituzione di A/B. E trova il dato quindi abbiamo una hit; F genera una miss nel set 0 e sostituisce D/E; G genera una miss nel set 12 e sostituisce C; infine H genera anch’esso una miss nel set 12 e sostituisce G.

• La situazione finale è:La situazione finale è:• Set 0: F, Set 12: H Gli altri set risultano ancora vuoti.

Architettura dei Calcolatori 11 Cache

Technology

Transcript of Architettura dei Calcolatori 11 Cache