Corso di Architettura
La memoria (1° parte)
(1)
Cosa faremo
°Definizione di memoria
• Indirizzamento, Allineamento
°Gerarchie di Memoria
• Direct-Mapped Cache
• Tipi di Cache-Misses
• Un bell’esempio…
(2)
Cosa è?
°Una sequenza di bit
°Bit: contiene o 0 od 1 Come faccio a
trovare le informazioni (sequenze di bit)
che cerco?
°Indirizzamento
(3)
Che cos’è
La memoria è semplicemente un grande
vettore unidimensionale, con gli indirizzi
che rappresentano l’indice del vettore a
partire da 0.
(4)
Indirizzamento: Byte vs. word (parola)
°Ogni parola di memoria ha un indirizzo,
(simile all’indice di un vettore)
Memory[0], Memory[1], Memory[2], …
Chiamati gli “indirizzi” di una parola
(5)
Indirizzamento: Byte vs. word
°Computers devono poter accedere ad 8-bit
(bytes)
°e parole (4 bytes/word)
°le macchine odierne indirizzano la memoria
al singolo byte, quindi l’indirizzo di una
parola corrisponde ad uno dei 4 bytes che
la compongono.
°quindi… gli indirizzi delle parole
differiscono di 4
Memory[0], Memory[4], Memory[8], …
(6)
Allineamento
°Il MIPS richiede che gli indirizzi delle parole
siano tutti multipli di 4
Byte nelle Word
0 1 2 3
Allineata
Non
Allineata
° Chiamato vincolo di Allineamento: gli oggetti
devono avere indirizzi che sono multipli della loro
“grandezza”.
(7)
Quindi
°La memoria è una sequenza di byte
°Quanti? In generale si decide quanti se ne
possono indirizzare, nel MIPS si decide di
avere indirizzi di 232 byte.
°Cosa è un indirizzo? Un numero….
(8)
Gerarchie di memoria (1/4)
°Processore
• esegue programmi
• la sua velocità è dell’ordine dei nanosecondi o
picosecondi
• ha bisogno di trovare in memoria i programmi
ed i dati: dove sono?
°Dischi
• Capacità GIGANTESCA (potremmo
considerarla illimitata)
• Molto LENTI: millisecondi
• Come passiamo da millisecondi a
nanosecondi?
(9)
Gerarchie di memoria (2/4)
°Memoria (DRAM)
• più piccola del disco (capacità limitata)
• contiene un sottoinsieme dei dati contenuti
nel disco: sostanzialmente la porzione del
programma che viene eseguita
• più veloce del disco: gli accessi alla memoria
rallentano il processore meno che nel caso
del disco
• Problema: la memoria è ancora troppo lenta
(centinaia di nanosecondi)
• Soluzione: aggiungiamo strati (caches)
(10)
Gerarchie di memoria (3/4)
Processore
alta
Livelli
nella
gerarchia
bassa
Livello 1
Livello 2
Aumenta la
distanza dal
Processore
diminuisce
la velocità
Livello 3
...
Livello n
Grandezza della memoria ad ogni livello
Come si scende di livello aumenta la latenza (ritardo)
e diminuisce il prezzo del bit
(11)
Gerarchie di memoria (4/4)
Tiriamo le somme
°più il livello è vicino al processore
• più è piccolo
• più è veloce
• Contiene un sottoinsieme dei dati del livello
sottostante (di solito quelli usati più
recentemente)
• Contiene tutti i dati contenuti nei livelli
soprastanti
°Il livello più basso (il disco) contiene tutti i
dati
(12)
Gerarchie di memoria
Computer
Processor
(active)
Control
(“brain”)
Datapath
(“brawn”)
Memory
(passive)
(where
programs,
data live
when
running)
Devices
Input
Output
Keyboard,
Mouse
Disk,
Network
Display,
Printer
°Fine:
• accesso rapido a grandi quantità di memoria
da parte del processore
(13)
Analogia (per le gerarchie di memoria): Biblioteca (1/2)
°State scrivendo una relazione (siete il
processore)
°La biblioteca è il disco
• Sostanzialmente senza limiti
• Per trovare il libro che serve ci mettete del
tempo (lenta)
°Il tavolo dove studiate è la memoria
• Ha meno posto…: se il tavolo è pieno dovete
restituire un libro
• Trovare il libro da usare è molto più veloce,
se l’avete già sul tavolo
(14)
Analogia (per le gerarchie di memoria): Biblioteca (2/2)
°I libri aperti sul tavolo sono la cache
• Capacità ancora più piccola: si possono avere
pochi libri aperti sul tavolo… quando sono troppi
bisogna chiuderne uno…
• Molto più veloce nel recuperare i dati
°Si vuole creare un’illusione: l’intera biblioteca
“aperta” sul tavolo. Due idee (semplici)
• Tenere aperti sul tavolo i libri usati più
recentemente (e il più a lungo possibile… è
probabile doverli riutillizzare)
• Tenere i libri sul tavolo il più a lungo possibile…
restituirli fa perdere tempo
(15)
Le basi per la gerarchia di memoria
°Il disco contiene tutto
°Quando il Processore ha bisogno di
qualche cosa, la mette in tutti i livelli di
memoria sottostanti
°La Cache contiene le copie dei dati che
vengono correntemente usati
°La Memoria contiene le copie dei dati
usati.
(16)
Come non era necessario accedere a tutti i testi
della biblioteca con la stessa probabilità, così un
programma non ha la necessità di accedere a tutto il
suo codice ed a tutti i suoi dati con egual
probabilità. In caso contrario non sarebbe possibile
rendere veloci la maggior parte degli accessi in
memoria e contemporaneamente avere grandi
quantità di memoria nei calcolatori. (come sarebbe
impossibile tenere tutti i libri sulla scrivania ed
avere qualche probabilità di trovare velocemente
l’argomento cercato).
(17)
Principi di località
Principio di località: in un dato istante di tempo i
programmi fanno accesso ad una porzione
relativamente piccola del loro spazio di
indirizzamento, così come lo studente fa accesso
ad una piccola porzione dei libri della biblioteca.
(18)
Principi di località
Località temporale: è probabile che un oggetto a cui
si è fatto riferimento venga nuovamente richiesto in
tempi brevi.
Località spaziale: è probabile che gli oggetti che si
trovano vicini ad un oggetto a cui si è fatto
riferimento vengano richiesti in tempi brevi.
(19)
Il principio di località viene appunto messo a
frutto implementando la memoria di un calcolatore
sotto forma di gerarchie di memorie.
(20)
La gerarchia di memorie, come detto, può
consistere di più livelli, ma in ogni istante di
tempo i dati sono copiati solamente tra ciascuna
coppia di livelli adiacenti per cui ci possiamo
concentrare su due livelli.
L’unità minima di informazione che può essere
presente o assente in una gerarchia a due livelli è
detto BLOCCO.
(21)
Se i dati richiesti dal processore compaiono in
qualche blocco nel livello superiore si dice che
si è verificato un successo nell’accesso
(hit…colpito).
Se il dato non è presente al livello superiore, la
richiesta viene classificata come fallimento
nell’accesso (miss…il dato manca) e si fa
accesso al livello inferiore nella gerarchia per
recuperare il blocco contenente il dato
richiesto.
(22)
Progettazione della Cache
°Come organizziamo la cache?
°Noi conosciamo indirizzi di memoria…
dove vanno a finire nella cache?
(la cache è un sottoinsieme della memoria…
vari indirizzi di memoria vanno a finire nello
stesso punto [locazione] della cache)
°Come facciamo a sapere quali elementi
sono nella cache?
°E come li troviamo?
(23)
Direct-Mapped Cache (1/2)
°In una direct-mapped cache, ogni indirizzo
di memoria address è associato ad un
blocco nella cache (a ciascuna parola di
memoria corrisponde esattamente una
locazione della cache)
• Quindi basta che guardiamo in quella
locazione nella cache per sapere se il dato c’è
nella cache
(24)
Direct-Mapped Cache (2/2)
Indirizzi di
memoria
Memoria
(25)
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
Indici
Cache
0
1
2
3
4 Byte Direct
Mapped Cache
° La locazione 0 nella Cache
può essere occupata da dati
che arrivano da :
• locazioni di Memoria 0, 4, 8, ...
• In generale: ogni locazione di
memoria che è multiplo di 4
Problemi con la Direct-Mapped Cache
1 dato che vari indirizzi di memoria vanno a
finire sullo stesso indice della cache, ci
vanno?
2 Come facciamo a dire quale c’è?
3 Cosa succede se abbiamo blocchi > 1 byte?
Soluzione: dividiamo gli indirizzi di memoria in
tre campi:
ttttttttttttttttt
tag
Controlla se c’è il
blocco corretto
(26)
iiiiiiiiii
Indice
oooo
offset
Indice all’inter- Byte all’interno della cache no del blocco
Indici
Solitamente la regola di traduzione degli indirizzi per
la cache è abbastanza semplice. Ad esempio tutte le
cache a corrispondenza diretta usano la seguente
regola:
(indirizzo del blocco) modulo (numero dei blocchi
nella cache)
Oss: se il numero di elementi della cache è una
potenza di 2, l’operazione di modulo si può calcolare
usando semplicemente alcuni dei bit meno
significativi dell’indirizzo: si usano log2(dimensione
della cache in blocchi) bit.
(27)
tag
Sono indicatori di proprietà per risolvere il fatto
che ciascuna locazione della cache può contenere
diverse locazioni di memoria e quindi non sarebbe
possibile sapere se il dato contenuto nella cache
corrisponde alla parola richiesta.
I
campi
tag
contengono
l’informazione
sull’indirizzo necessaria a determinare se una
parola nella cache corrisponde a quella richiesta.
I tag contengono solo la parte più significativa
dell’indirizzo, quella che non corrisponde ai bit
utilizzati come indice nella cache.
(28)
Terminologia della Direct-Mapped Cache
°Tutti i campi vanno intesi come numeri
senza segno (non in complemento a 2).
°Indice: specifica l’indice nella cache (in
quale riga dobbiamo guardare)
°Offset: una volta trovato il blocco corretto,
l’offset specifica il byte all’interno del
blocco che vogliamo
°Tag: gli altri bit rimanenti servono a
distinguere tra i vari indirizzi di memoria
che vanno a finire sullo stesso blocco
(29)
Esempio sulla Direct-Mapped Cache (1/3)
°Supponiamo di avere una 16KB directmapped cache con blocchi di 4 words.
°Determiniamo le dimensioni del tag, indice e
offset se usiamo un’architettura a 32-bit.
°Offset
• Serve a specificare il byte nel blocco
• Un blocco contiene
4 parole = 16 bytes =
24 bytes
• Abbiamo bisogno di 4 bits per specificare il byte
corretto
(30)
Esempio sulla Direct-Mapped Cache (2/3)
°Indice
• Spefica la riga corretta nella cache
• cache contiene 16 KB = 214 bytes
• Un blocco contiene 24 bytes (4 words)
• # righe della cache =
# blocchi della cache
(dato che c’è una
riga per blocco)
la cache ha 214 bytes = 214 bytes/24 bytes
= 210 righe
• Abbiamo bisogno di 10 bits per le righe
(indici)
(31)
Esempio sulla Direct-Mapped Cache (3/3)
°Tag
• Usiamo i bit restanti come tag
• Lunghezza del tag = lung. ind. mem
- offset
- Indice
= 32 - 4 - 10 bits
= 18 bits
• Quindi il tag è formato dai 18 bit più a
sinistra dell’indirizzo di memoria
(32)
Accedere ai dati in una direct mapped cache
°Esempio: 16KB,
direct-mapped,
blocchi da 4 parole
°abbiamo 4 indirizzi
• 0x00000014,
0x0000001C,
0x00000034,
0x00008014
Memoria
indirizzo (hex)
...
00000010
00000014
00000018
0000001C
...
00000030
00000034
00000038
°I contenuti sono sulla 0000003C
destra
...
00008010
00008014
00008018
0000801C
...
(33)
Contenuto della
Parola
...
a
b
c
d
...
e
f
g
h
...
i
j
k
l
...
Accedere ai dati in una direct mapped cache
°4 indirizzi:
• 0x00000014, 0x0000001C, 0x00000034,
0x00008014
°4 indirizzi divisi nei campi Tag, Indice e
Byte Offset
000000000000000000 0000000001 0100
000000000000000000 0000000001 1100
000000000000000000 0000000011 0100
000000000000000010 0000000001 0100
Tag
(34)
Indice
Offset
Accedere ai dati in una direct mapped cache
°Accediamo a qualche dato nella cache
• 16KB, direct-mapped, blocchi di 4 parole
°Ci sono 3 tipi di eventi:
°cache miss: non c’è niente nella cache nel
blocco…, recuperare dalla memoria
°cache hit: il blocco nella cache è Valido e
contiene l’indirizzo corretto, si può leggere la
parola desiderata
°cache miss, rimpiazzamento del blocco: il dato
sbagliato è nella cache nel blocco appropriato,
va rimosso e va recuperato il dato desiderato
dalla memoria
(35)
16 KB Direct Mapped Cache, 16B blocks
° Bit di Validità: determina se qualche cosa è stato
memorizzato nel blocco (quando accendiamo il
computer, sono tutti non Validi)
Valido
Blocco
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
...
1022
1023
(36)
...
0
0
leggiamo 0x00000014 = 0…00 0..001 0100
° 000000000000000000 0000000001 0100
Tag
Indice
Offset
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
...
1022 0
1023 0
(37)
...
Dobbiamo leggere il blocco 1 (0000000001)
° 000000000000000000 0000000001 0100
Tag
Indice
Offset
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
...
1022
1023
(38)
...
0
0
Non ci sono dati Validi
° 000000000000000000 0000000001 0100
Tag
Indice
Offset
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
...
1022
1023
(39)
...
0
0
Carichiamo il dato nella cache, inseriamo il tag e
settiamo il bit Valido
° 000000000000000000 0000000001 0100
Indice
Tag
Offset
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
a
b
c
d
1 1 0
2 0
3 0
4 0
5 0
6 0
7 0
...
1022
1023
(40)
...
0
0
Leggiamo il dato dalla cache, che è una parola
° 000000000000000000 0000000001 0100
Offset
Tag
Indice
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
a
b
c
d
1 1 0
2 0
3 0
4 0
5 0
6 0
7 0
...
1022 0
1023 0
(41)
...
Leggiamo il dato 0x0000001C = 0…00 0..001 1100
° 000000000000000000 0000000001 1100
Tag
Indice
Offset
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
a
b
c
d
1 1 0
2 0
3 0
4 0
5 0
6 0
7 0
...
1022
1023
(42)
...
0
0
Il dato è Valido, il tag OK, leggiamo l’offset e abbiamo
la parola desiderata
000000000000000000 0000000001 1100
Valido
Indice Tag
0 0
1 1 0
2 0
3 0
4 0
5 0
6 0
7 0
...
1022
1023
(43)
0x0-3
0x4-7
0x8-b
0xc-f
a
b
c
d
...
0
0
leggiamo 0x00000034 = 0…00 0..011 0100
° 000000000000000000 0000000011 0100
Tag
Indice
Offset
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
a
b
c
d
1 1 0
2 0
3 0
4 0
5 0
6 0
7 0
...
1022
1023
(44)
...
0
0
Leggiamo il blocco 3
° 000000000000000000 0000000011 0100
Tag
Indice
Offset
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
a
b
c
d
1 1 0
2 0
3 0
4 0
5 0
6 0
7 0
...
1022
1023
(45)
...
0
0
Dato non Valido
° 000000000000000000 0000000011 0100
Tag
Indice
Offset
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
a
b
c
d
1 1 0
2 0
3 0
4 0
5 0
6 0
7 0
...
1022
1023
(46)
...
0
0
Come prima: caricare il blocco e leggere il dato
000000000000000000 0000000011
Tag
Indice
Valido
0x4-7
0x8-b
0x0-3
Indice Tag
0 0
a
b
c
1 1 0
2 0
e
f
g
3 1 0
4 0
5 0
6 0
7 0
...
1022
1023
(47)
...
0
0
0100
Offset
0xc-f
d
h
leggiamo 0x00008014 = 0…10 0..001 0100
° 000000000000000010 0000000001 0100
Tag
Indice
Offset
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
a
b
c
d
1 1 0
2 0
e
f
g
h
3 1 0
4 0
5 0
6 0
7 0
...
1022
1023
(48)
...
0
0
Dobbiamo leggere il blocco 1, il dato è Valido
° 000000000000000010 0000000001 0100
Tag
Indice
Offset
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
a
b
c
d
1 1 0
2 0
e
f
g
h
3 1 0
4 0
5 0
6 0
7 0
...
1022
1023
(49)
...
0
0
Ma nel Blocco 1 il Tag non coincide (0  2)
° 000000000000000010 0000000001 0100
Tag
Indice
Offset
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
1 1 0
a
b
c
d
2 0
e
f
g
h
3 1 0
4 0
5 0
6 0
7 0
...
1022
1023
(50)
...
0
0
Miss, rimpiazzare il blocco 1 con nuovi dati & tag
° 000000000000000010 0000000001 0100
Tag
Indice
Offset
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
i
j
k
l
1 1 2
2 0
e
f
g
h
3 1 0
4 0
5 0
6 0
7 0
...
1022
1023
(51)
...
0
0
E accediamo al dato corretto
° 000000000000000010 0000000001 0100
Tag
Indice
Offset
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
i
j
k
l
1 1 2
2 0
e
f
g
h
3 1 0
4 0
5 0
6 0
7 0
...
1022
1023
(52)
...
0
0
Vediamo altri esempi. Cosa accade?
° Dovete dire cosa succede alla Cache:
Hit, Miss, Miss con rimpiazzamento
valori restituiti: a ,b, c, d, e, ..., k, l
° indirizzo 0x00000030 ? 000000000000000000
0000000011 0000
° indirizzo 0x0000001c ?
Cache
000000000000000000 0000000001 1100
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Indice Tag
0 0
i
j
k
l
1 1 2
2 0
e
f
g
h
3 1 0
4 0
5 0
6 0
7 0
(53)
...
...
Risposte
°0x00000030 hit
Indice = 3, Tag coincide,
Offset = 0, valore = e
Memoria
indirizzi
...
00000010
°0x0000001c miss
00000014
00000018
Indice = 1, Tag non coincide, 0000001c
rimpiazzare dalla memoria,
...
Offset = 0xc, valore = d
00000030
00000034
°Quindi i valori sono:
00000038
0000003c
• 0x00000030 = e
...
00008010
• 0x0000001c = d
00008014
00008018
0000801c
(54)
...
valori
...
a
b
c
d
...
e
f
g
h
...
i
j
k
l
...
Conclusioni
°Vorremmo avere dei dischi della stessa
velocita del processore: non è per ora
possibile (difficile che lo diventi)
°Creiamo una gerarchia di memorie:
• I livelli che si succedono contengono i dati
usati più recentemente dei livelli sottostanti
• Località temporale e spaziale
• Risolvere i casi comuni in fretta, non
preoccuparsi da subito delle eccezioni
(principio usato molto nel MIPS)
°La località del riferimento è una bella Idea
(55)
ripasso
°Meccanismo per il movimento transparente
dei dati tra i livelli della gerarchia di memoria
• Insieme di indirizzi/valori
• indirizzi => Indice per un insieme di candidati
• comparare l’indirizzo desiderato con il tag
• hit o miss
- Caricare un nuovo blocco e valori collegati nelle miss
indirizzi:
0
1
2
3
...
(56)
tag
Indice
offset
000000000000000000 0000000001 1100
Valido
0x4-7
0x8-b
0xc-f
0x0-3
Tag
1
0
a
b
c
d