Gerarchie di
memoria
Paolo Meloni
Universita’ degli studi di Cagliari
Sistemi di memoria
Gerarchie di memoria
Paolo Meloni
Elettronica – Introduzione al corso
Sistemi di memoria gerarchici
“Ideally one would desire an indefinitely large
memory capacity such that any particular […]
word would be immediately available […]. We
are […] forced to recognize the possibility of
constructing a hierarchy of memories, each
of which has greater capacity than the
preceding but which is less quickly
accessible.”
A.W. Burks, H.H. Goldstine, and J. Von Neumann
Preliminary discussion of the Logical Design of an
Electronic Computing Sytem (1946)
Paolo Meloni
Elettronica – Introduzione al corso
Sistemi di memoria gerarchici
• Una delle prime necessità mostrate dagli utenti di
calcolatori elettronici, è stata quella di una illimitata
quantità di memoria velocemente accessibile.
• Per ragioni tecnologiche ed economiche tale
esigenza non può essere soddisfatta
• Tramite i sistemi di memoria gerarchici si crea
l’illusione di una memoria grande accessibile alla
stessa velocità di una memoria piccola, sfruttando il
Principio di località
Paolo Meloni
Elettronica – Introduzione al corso
Principio di località
•
•
•
•
•
Un programma non ha bisogno di accedere a tutti i dati o a
tutte le istruzioni con la stessa probabilità.
Il programma in ogni istante di tempo accede a una porzione
relativamente piccola del suo spazio di memoria.
Esistono due tipi di località:
Località temporale: se un elemento è referenziato,
generalmente mostrerà una tendenza ad essere presto
referenziato di nuovo. (per esempio loop all’interno dei
programmi)
Località spaziale: se un elemento è referenziato, gli altri elementi
corrispondenti ad indirizzi di memoria vicini al suo, mostreranno
una tendenza ad essere presto referenziati. (per esempio le
istruzioni di un programma vengono eseguite in sequenza, o gli
elementi di un array)
Paolo Meloni
Elettronica – Introduzione al corso
Gerarchie di memoria
•
•
Si può sfruttare il principio di località implementando la memoria
di un computer tramite una gerarchia di memorie caratterizzate
da diverse dimensioni e diverse velocità.
Memory Technology
Typical Access Time
$ per GB in 2004
SRAM
0,5 – 5 ns
$4000-$10000
DRAM
50 - 70 ns
$100-$200
Magnetic Disk
5000000-20000000 ns
$0,50-$2
A causa delle differenze tra i tipi di memorie in termini di facilità
di accesso e di costo, è conveniente utilizzare sistemi gerarchici
in cui i diversi livelli della gerarchia comunichino tra loro. Ciò
permette di mostrare all’utente una memoria grande quanto
quella di tipo più economico, ma veloce come quella di tipo
più costoso.
Paolo Meloni
Elettronica – Introduzione al corso
Gerarchie di memoria
Speed
CPU
Size
Cost ($/bit)
Fastest
Memory
Smallest
Highest
Highest
Smallest
Memory
Slowest
Memory
Paolo Meloni
Elettronica – Introduzione al corso
Gerarchie di memoria
CPU
Livello 1
Livelli nella gerarchia
di memorie
Livello 2
…
Livello n
Dimensione della memoria ad ogni livello
Paolo Meloni
Elettronica – Introduzione al corso
Aumento della
distanza dalla
CPU in termini di
access time
Definizioni
•
•
•
Una gerarchia può essere formata da più livelli, ma i dati sono
scambiati solo tra due livelli adiacenti per volta, quindi si può
concentrare l’attenzione solo su due livelli
Uno (quello superiore, più vicino al processore, più piccolo e
veloce, dato che usa una tecnologia più costosa
L’altro più grande ma lento
L’unità di informazione che può essere presente o meno
all’interno di uno dei due livelli (e dunque può o meno
dover essere scambiata) è detta block o line
Paolo Meloni
Elettronica – Introduzione al corso
Definizioni
•
•
•
•
La situazione in cui un dato referenziato dal processore è presente
all’interno di un blocco all’interno del livello superiore è chiamata
hit
La situazione in cui invece il dato non è presente nel livello
superiore è chiamata miss. In tal caso il blocco contente il dato
richiesto deve essere reperito tramite un accesso al secondo livello
di memoria.
La frazione del numero degli accessi in memoria che sono stati
soddisfatti accedendo solo al primo livello è chiamata hit rate.
La frazione del numero degli accessi che invece hanno richiesto
un accesso al secondo livello (1- hit rate) è detta miss rate.
Paolo Meloni
Elettronica – Introduzione al corso
Definizioni
•
Il tempo di accesso alla memoria di primo livello, comprensivo del
tempo necessario per la verifica dell’hit o del miss, è detto hit time.
• Il tempo necessario al reperimento di un dato dal livello inferiore
della gerarchia di memoria è detto miss penalty. Il miss penalty
comprende:
• Il tempo necessario al rimpiazzamento del blocco all’interno
del livello superiore
• Il tempo necessario per il trasferimento del dato richiesto al
processore
Paolo Meloni
Elettronica – Introduzione al corso
Memorie Cache - Basics
•
Consideriamo, per familiarizzare coi concetti un sistema base in cui
il processore richieda una word per volta e in cui anche la
dimensione del block sia pari a 1 word.
X4
X4
X1
X1
Xn-2
Xn-2
Xn-1
Xn-1
X2
X2
Xn
X3
Paolo Meloni
Elettronica – Introduzione al corso
X3
Memorie Cache - Basics
•
•
Come ci si accorge se un dato è nella cache?
Se c’è, come lo si trova?
•
Se ogni blocco può essere memorizzato solo in una posizione
all’interno della cache, la verifica hit/miss e la localizzazione si
compiono simultaneamente.
•
La maniera più semplice per assegnare una locazione nella cache
per ogni word in memoria consiste nell’assegnarla in base
all’indirizzo di memoria corrispondente alla word. Tale struttura è
chiamata DIRECT MAPPING
Locazione= (Block Address) mod (numero di blocchi nella cache)
Paolo Meloni
Elettronica – Introduzione al corso
Memorie Cache - Basics
•
Direct mapping access
111
110
101
01101
100
Paolo Meloni
Elettronica – Introduzione al corso
011
01001
010
00101
001
000
00001
10001
10101
11001
11101
Memorie Cache - Basics
•
•
Come sappiamo se il dato nella cache corrisponde a quello
cercato?
Alla cache viene aggiunto un insieme di tags. Ogni tag contiene
le informazioni riguradanti l’indirizzo necessarie all’identificazione
univoca del blocco contenuto nella cache (es. prec. i 2 msb).
E’ necessaria anche una informazione riguardante la validità o
meno dell’informazione contenuta in una locazione della cache,
per esempio allo start-up del sistema. Di solito vine utilizzato un bit
che viene dunque detto valid bit.
Paolo Meloni
Elettronica – Introduzione al corso
Accessing a cache
22
10110
26
11010
010
22
10110
110
26
11010
010
16
10000
000
3
00011
011
16
10000
000
18
10010
010
Paolo Meloni
Elettronica – Introduzione al corso
miss
110
Accessing a cache
Stato Iniziale
000
N
001
N
010
N
011
N
100
N
101
N
110
N
111
N
Paolo Meloni
Elettronica – Introduzione al corso
Accessing a cache
22
10110
000
N
001
N
010
N
011
N
100
N
101
N
110
S
111
N
Paolo Meloni
Elettronica – Introduzione al corso
miss
110
10
Mem(10110)
Accessing a cache
26
11010
000
N
001
N
010
S
011
N
100
N
101
N
110
S
111
N
Paolo Meloni
Elettronica – Introduzione al corso
miss
010
11
Mem(11010)
10
Mem(10110)
Accessing a cache
22
10110
000
N
001
N
010
S
011
N
100
N
101
N
110
S
111
N
Paolo Meloni
Elettronica – Introduzione al corso
hit
110
11
Mem(11010)
10
Mem(10110)
Accessing a cache
26
11010
000
N
001
N
010
S
011
N
100
N
101
N
110
S
111
N
Paolo Meloni
Elettronica – Introduzione al corso
hit
010
11
Mem(11010)
10
Mem(10110)
Accessing a cache
16
10000
miss
000
000
S
10
Mem(10000)
001
N
010
S
11
Mem(11010)
011
N
100
N
101
N
110
S
10
Mem(10110)
111
N
Paolo Meloni
Elettronica – Introduzione al corso
Accessing a cache
3
00011
miss
011
000
S
10
Mem(10000)
001
N
010
S
11
Mem(11010)
011
S
00
Mem(00011)
100
N
101
N
110
S
10
Mem(10110)
111
N
Paolo Meloni
Elettronica – Introduzione al corso
Accessing a cache
16
10000
hit
000
000
S
10
Mem(10000)
001
N
010
S
11
Mem(11010)
011
S
00
Mem(00011)
100
N
101
N
110
S
10
Mem(10110)
111
N
Paolo Meloni
Elettronica – Introduzione al corso
Accessing a cache
18
10010
miss
010
000
S
10
Mem(10000)
001
N
010
S
10
Mem(10010)
011
S
00
Mem(00011)
100
N
101
N
110
S
10
Mem(10110)
111
N
Paolo Meloni
Elettronica – Introduzione al corso
Accessing a cache
Byte off
Tag
20
Index
Index
V
Address
Tag
10
Data
0
1
2
…
…
Data
…
…
20
1021
Hit
1022
1023
=
Paolo Meloni
Elettronica – Introduzione al corso
32
Block size trade-off
•
Aumentando le dimensioni del blocco si sfrutta ovviamente meglio
la località spaziale, quindi in generale il miss rate diminuisce.
• Però:
• Blocchi più grandi, a parità di dimensione della cache,
comportano un numero inferiore di blocchi, dunque limitano la
possibilità di sfruttare la località temporale
• Blocchi più grandi richiedono più tempo per essere trasferiti,
dunque causano un aumento del miss penalty
Paolo Meloni
Elettronica – Introduzione al corso
Gestione dei cache miss
•
•
•
Nel caso in cui l’accesso in memoria sia una read, un cache miss
(read miss)è gestito stallando il processore sino a quando non è
avvenuto il trasferimento del dato (o dell’istruzione) dal livello
sottostante della memoria alla cache. Si accederà di nuovo
successivamente alla cache ottenendo stavolta un hit sulla
locazione appena caricata.
Nel caso in cui l’accesso sia una write, si propone il problema
dell’inconsistenza.
La cache e la memoria principale si dicono inconsistenti se
contengono un dato diverso corrispondente allo stesso indirizzo.
Paolo Meloni
Elettronica – Introduzione al corso
Gestione dei write miss (write through scheme)
•
•
Occorre gestire l’inconsistenza:
A) si scrive sia in caso di miss che in caso di hit sia sulla cache che
sulla memoria principale (write through scheme)
• In caso di miss
• si carica il dato che ha causato il miss
• si modifica il suo valore all’interno della cache
• Si aggiorna il dato in memoria
• Drawback:
Se per ogni write il processore deve attendere di accedere
alla memoria, gli stalli potrebbero rallentarlo in maniera drastica
Soluzione: write buffer
Paolo Meloni
Elettronica – Introduzione al corso
Gestione dei write miss (write back scheme)
•
B) Si scrive solo sulla cache(write back scheme)
• La memoria principale viene aggiornata quando il blocco nella
cache viene rimpiazzato da un altro.
• Drawback:
E’ più complicato da implementare rispetto al write through
(DIRTY BIT)
Paolo Meloni
Elettronica – Introduzione al corso