Corso di Architettura
La memoria (2° parte)
(1)
Altri problemi con le cache
°Ampiezza del blocco Tradeoff
°Tipi di Cache Misses
°Fully Associative Cache
°N-Way Associative Cache
°Politiche di rimpiazzamento dei blocchi
(2)
Block Size Tradeoff (1/3)
°Benefici dalla località spaziale
• Località spaziale: è probabile che le parole
che si trovano vicine ad una parola richiesta
siano nuovamente richieste in tempi brevi.
• La località spaziale emerge spontaneamente
nei programmi.
(3)
Block Size Tradeoff (2/3)
• La frequenza di miss si riduce all’aumentare
della dimensione dei blocchi. (miss rate)
• Ma attenzione se la dimensione dei blocchi è
troppo grande la frequenza di miss aumenta
perchè si ridurrebbe il numero di blocchi
presenti nella cache.
• Il costo di una miss (miss penalty) aumenta al
crescere della dimensione del blocco.
°In generale, bisogna minimizzare:
Average Access Time
= Hit Time + Miss Penalty x Miss Rate
(4)
Block Size Tradeoff (3/3)
°Hit Time = tempo per cercare e recuperare
dati dal corrente livello di cache.
°Miss Penalty = tempo per trovare dati nel
corrente livello di cache (incluso la
possibilità di misses nei successivi livelli
della gerarchia della memoria)
°Hit Rate = % di richieste andate a buon fine
nel corrente livello di memoria.
°Miss Rate = 1 - Hit Rate
(5)
Block Size Tradeoff Conclusions
Miss
Rate Exploits Spatial Locality
Miss
Penalty
Fewer blocks:
compromises
temporal locality
Block Size
Average
Access
Time
Block Size
Increased Miss Penalty
& Miss Rate
Block Size
(6)
Tipi di Cache Misses (1/2)
Miss certi
• Quando un programma è all’inizio.
• La cache non contiene ancora nessun dato
di quel programma, e quindi trovare miss è
inevitabile.
• Non sono facilmente evitabili, quindi non
saranno materia di questo corso.
(7)
Types of Cache Misses (2/2)
°Miss per conflitti
• Miss che avvengono quando più blocchi
competono per lo stesso insieme.
• Problemi con le cache ad accesso diretto
• come diminuire questo effetto?
(8)
Miss per conflitti
°Soluzione 1: aumentare le dimensioni
della cache ma è comunque caro.
°Soluzione 2: è obbligatorio che ciascun
blocco possa andare in una sola posizione
della cache, come nelle cache a
corrispondenza diretta?
(9)
Fully Associative Cache (1/3)
°Campi:
• Tag: lo stesso
• Offset: lo stesso
• Index: non ne ho bisogno
°Ogni blocco può essere posto in qualsiasi
locazione della cache: è detta
completamente associativa perchè un
blocco della memoria può essere associato
a qualsiasi cella della cache.
(10)
Fully Associative Cache (2/3)
°Fully Associative Cache (e.g., 32 B block)
• Per ritrovare un dato blocco di una cache
completamente occorre cercarlo in tutte le celle;
la ricerca viene compiuta in parallelo.
4
31
0
Byte Offset
Cache Tag (27 bits long)
=
=
:
=
(11)
Cache Data
Valid
B 31
B1 B 0
:
=
Cache Tag
=
:
:
:
Fully Associative Cache (3/3)
°Aspetti positivi della Fully Assoc Cache
• Non ci sono miss per conflitto (dato che i
dati possono andare ovunque)
°Aspetti negativi della Fully Assoc Cache
• Ha bisogno di hardware per ogni singola
entrata: se abbiamo 64KB di dati in una
cache con 4B, abbiamo bisogno di 16 KB di
comparatori: very expensive. Altrimenti
aumenta il tempo di accesso, portando a
prestazioni complessive inferiori.
(12)
Terzo tipo di Cache Miss
°Miss per capacità
• I miss che sorgono quando la cache non può
contenere tutti I blocchi necessari
all’esecuzione del programma.
• I miss per capacità avvengono perchè alcuni
blocchi vengono sostituiti e devono essere
prelevati più tardi.
°Sono le miss più frequenti nella Fully
associative cache.
(13)
N-Way Set Associative Cache (1/4)
°Campi:
• Tag: come prima
• Offset: come prima
• Index: indicano la riga corretta (chiamata set)
°Vi è un numero fisso di posizioni (almeno 2) in
cui si può porre ciascun blocco; una cache
con n possibili collocazioni per ciascun
blocco è detta ad n vie (N-way)
• Ogni set contiene più blocchi
• Una volta trovato il set corretto bisogna guardare
tutti i tag per cercare il dato cercato.
• indirizzo blocco = (indirizzo memoria) modulo
(numero insiemi)
(14)
N-Way Set Associative Cache (2/4)
°Osservazioni:
• Rispetto ai set è a corrispondenza diretta.
• Ogni set è fully associative
• Praticamente
corrispondenza
parallelo.
(15)
sono
diretta
N
che
cache
lavorano
a
in
N-Way Set Associative Cache (3/4)
°Dato un indirizzo di memoria:
• Trovare l’insieme corretto.
• Confrontare il tag con tutti I tag del set.
• Se c’è un match è un hit altrimenti un miss.
• Infine usare il campo offset per cercare il
dato.
(16)
N-Way Set Associative Cache (4/4)
• Anche le 2-way set associative cache evitano
molte miss per conflitto.
• I costi dell’hardware non sono male: ho
bisogno solo di N comparatori
°In effetti una cache a M blocchi ha queste
caratteristiche:
• E’ una cache a corrispondenza diretta se è
una cache 1-way set assoc
• E’ una cache completamente associativa se è
una cache M-way set assoc
(17)
Cache a confronto
°Cache contenente 8 blocchi
tag dati
tag dati tag dati
tag dati tag dati tag dati tag dati
4 vie
2 vie
tag dati tag dati tag dati tag dati tag dati tag dati tag dati tag dati
mappa diretta
(18)
completamente associativa
Esempio: mappa diretta
°Cache da 4 parole
°Sequenza di accessi: 0,8,0,6,8
Indirizzo
blocco
0
6
8
Blocco da
accedere
0
8
0
6
8
(19)
H/M
M
M
M
M
M
Blocco 0
Mem[0]
Mem[8]
Mem[0]
Mem[0]
Mem[8]
Blocco cache
0
2
0
Blocco 1
Blocco 2
Mem[6]
Mem[6]
Blocco 2
Associativa a 2 vie
°Cache da 4 parole
°Sequenza di accessi: 0,8,0,6,8
Indirizzo
blocco
0
6
8
Blocco da
accedere
0
8
0
6
8
(20)
H/M
M
M
H
M
M
Insieme 0
Mem[0]
Mem[0]
Mem[0]
Mem[0]
Mem[8]
Blocco cache
0
0
0
Insieme 0
Mem[8]
Mem[8]
Mem[6]
Mem[6]
Insieme 1
Insieme 1
Completamente associativa
°Cache da 4 parole
°Sequenza di accessi: 0,8,0,6,8
Blocco da
accedere
0
8
0
6
8
(21)
H/M
M
M
H
M
H
Blocco 0
Mem[0]
Mem[0]
Mem[0]
Mem[0]
Mem[0]
Blocco 1
Blocco 2
Mem[8]
Mem[8]
Mem[8]
Mem[8]
Mem[6]
Mem[6]
Blocco 3
Block Replacement Policy (1/2)
°Se abbiamo scelta dove andiamo a mettere
un nuovo blocco?
(22)
Block Replacement Policy (2/2)
°Se è tutto vuoto, generalmente scriviamo
il nuovo blocco nel primo.
°Se tuttavia tutte le locazioni hanno già un
blocco valido, possiamo usare una
politica di rimpiazzamento.
(23)
Block Replacement Policy: LRU
°LRU (Least Recently Used)
• Idea: buttare fuori blocchi con accesso meno
recente.
• Pro: temporal locality => cose usate da poco
potrebbero essere riusate a breve.
Associatività:
2 vie
Dimensione
LRU
Random
16 KB
5.2%
5.7%
64 KB
1.9%
2.0%
256 KB
1.15%
1.17%
(24)
4 vie
LRU
Random
4.7%
5.3%
1.5%
1.7%
1.13%
1.13%
8 vie
LRU
Random
4.4%
5.0%
1.4%
1.5%
1.12%
1.12%
Block Replacement Example
°We have a 2-way set associative cache
with a four word total capacity and one
word blocks. We perform the following
word accesses (ignore bytes for this
problem):
0, 2, 0, 1, 4, 0, 2, 3, 5, 4
How many hits and how many misses will
there for the LRU block replacement
policy?
(25)
Block Replacement Example: LRU
°Addresses 0, 2, 0, 1, 4, 0, ...
• 0: miss, bring into set 0 (loc 0)
• 2: miss, bring into set 0 (loc 1)
• 0: hit
• 1: miss, bring into set 1 (loc 0)
loc 0 loc 1
lru
set 0
0
set 1
set 0 lru
0
lru
2
set 1
set 0 lru
0
lru
0
1
lru
2
set 1
set 0
set 1
2
lru
• 4: miss, bring into set 0 (loc 1, replace 2)
set 0 lru0 lru2
4
lru
set 1
• 0: hit
set 0 lru0 lru4
lru
set 1
(26)
1
1
Operazioni di scrittura
°Write-through
• Scrivere I dati sia nella memoria che nella
cache. (adozione di un buffer che memorizza
I dati in attesa di essere scritti nella
memoria)
°Write-back
Il nuovo valore viene scritto solamente nel
blocco della cache.
Il blocco modificato dovrà essere copiato nel
livello inferiore solo quando dovrà essere
sostituito
(27)