La memoria cache
Tecniche di rimpiazzo
(1)
Problemi con le cache
°Ampiezza del blocco
°Tipi di Cache Misses
°Fully Associative Cache
°N-Way Associative Cache
°Politiche di rimpiazzo dei blocchi
(2)
Block Size
°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
• 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.
(4)
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
(5)
completamente associativa
Esempio: mappa diretta
°Cache da 4 parole
°Sequenza di accessi: 0,8,0,6,8 (dim. Blocco=1B)
Indirizzo
blocco
0
6
8
(6)
Blocco da
accedere H/M
0
M
8
M
0
M
6
M
8
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 3
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
(7)
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
(8)
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?
(9)
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 rimpiazzo.
(10)
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%
(11)
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%
Esempio
°Abbiamo una 2-way set associative
cache con 4 word di capacità totale e
blocchi da 1 word.
° Supponiamo di voler effettuare gli
accessi in memoria ai blocchi:
0, 2, 0, 1, 4, 0, 2, 3, 5, 4
Che percentuale di miss e di hit otterremo
applicando la tecnica LRU?
(12)
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
(13)
1
1