(1)

La memoria cache

Tecniche di rimpiazzo

(2)

Problemi con le cache°Ampiezza del blocco

°Tipi di Cache Misses

°Fully Associative Cache

°N-Way Associative Cache

°Politiche di rimpiazzo dei blocchi

(3)

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.

(4)

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.

(5)

Cache a confronto

°Cache contenente 8 blocchi

mappa diretta

tag dati

2 vie

tag dati tag dati

completamente associativa

tag dati tag dati tag dati tag dati tag dati tag dati tag dati tag dati

4 vie

tag dati tag dati tag dati tag dati

(6)

Esempio: mappa diretta

°Cache da 4 parole°Sequenza di accessi: 0,8,0,6,8 (dim. Blocco=1B)

Indirizzo blocco Blocco cache0 06 28 0

Blocco da accedere H/M Blocco 0 Blocco 1 Blocco 2 Blocco 3

0 M Mem[0]8 M Mem[8]0 M Mem[0]6 M Mem[0] Mem[6]8 M Mem[8] Mem[6]

(7)

Associativa a 2 vie

°Cache da 4 parole

°Sequenza di accessi: 0,8,0,6,8

Indirizzo blocco Blocco cache0 06 08 0

Blocco da accedere H/M Insieme 0 Insieme 0 Insieme 1 Insieme 1

0 M Mem[0]8 M Mem[0] Mem[8]0 H Mem[0] Mem[8]6 M Mem[0] Mem[6]8 M Mem[8] Mem[6]

(8)

Completamente associativa

°Cache da 4 parole

°Sequenza di accessi: 0,8,0,6,8

Blocco da accedere H/M Blocco 0 Blocco 1 Blocco 2 Blocco 3

0 M Mem[0]8 M Mem[0] Mem[8]0 H Mem[0] Mem[8]6 M Mem[0] Mem[8] Mem[6]8 H Mem[0] Mem[8] Mem[6]

(9)

Block Replacement Policy (1/2)

°Se abbiamo scelta dove andiamo a mettere un nuovo blocco?

(10)

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.

(11)

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 4 vie 8 vie

Dimensione LRU Random LRU Random LRU Random

16 KB 5.2% 5.7% 4.7% 5.3% 4.4% 5.0%

64 KB 1.9% 2.0% 1.5% 1.7% 1.4% 1.5%

256 KB 1.15% 1.17% 1.13% 1.13% 1.12% 1.12%

(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?

(13)

Example: LRU°Addresses 0, 2, 0, 1, 4, 0, ... 0 lru

1 lru

loc 0 loc 1

set 0

set 1

0 2lruset 0

set 1

lruset 0

set 1

0 41 lru

• 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)

• 4: miss, bring into set 0 (loc 1, replace 2)

• 0: hit

0 2set 0

set 1

lru

0set 0

set 1

lrulru2

lru

2set 0

set 1

01 lru

lrulru 4

lru