Memoria cache: esercizi

Calcolatori Elettronici A
a.a. 2008/2009
Memoria cache:
Esercizi
Massimiliano Giacomin
1
Esercizio: miss della cache e
collocazione dei blocchi nella cache
• Sia data la seguente sequenza di indirizzi a cui si intende fare accesso,
espressi come indirizzi di parola:
1, 4, 8, 5, 33, 66, 32, 56, 9, 11, 4, 43, 88, 6, 32
• Sia data una cache con blocchi di 4 parole e una dimensione totale di
32 parole
• Determiniamo se ciascuno degli accessi è un hit o un miss assumendo
che la cache sia inizialmente vuota, nei 3 casi seguenti:
1) cache a corrispondenza diretta
2) cache totalmente associativa, ipotizzando una sostituzione LRU
3) cache set-associativa a 2 vie, ipotizzando una sostituzione LRU
• Assumendo indirizzi a 16 bit, determiniamo anche il numero di bit
riservati all’etichetta (tag), al blocco (o insieme) e alla parola
2
Calcolo degli indirizzi di blocco
• Gli indirizzi a cui dobbiamo fare accesso sono espressi come indirizzi di
parola
• Siccome, in ogni caso, dobbiamo caricare nella cache un blocco di 4
parole, trasformiamo gli indirizzi di parola in indirizzi di blocco
• Usiamo la seguente equazione
 indirizzo di parola   indirizzo di parola 
indirizzo di blocco = 
 = 

ampiezza
di
un
blocco
4


• E quindi troviamo le seguenti corrispondenze
indirizzo di parola
1, 4, 8, 5, 33, 66, 32, 56, 9, 11, 4, 43, 88, 6, 32
indirizzo di blocco
0, 1, 2, 1, 8, 16, 8, 14, 2, 2, 1, 10, 22, 1, 8
3
Caso 1: cache a corrispondenza diretta
Indirizzi di blocco
Blocco della cache
0, 1, 2, 1, 8, 16, 8, 14, 2, 2, 1, 10, 22, 1, 8
0, 1, 2, 1, 0, 0, 0, 6, 2, 2, 1, 2, 6, 1, 0
Cache
0
1
2
3
4
5
6
7
blocco di 4 parole
Un blocco della memoria può
andare in un solo blocco della cache
Etichetta
Indirizzo
11
Blocco Parola
3
2
0 blocco di 4 parole
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Memoria
…
4
Caso 1: cache a corrispondenza diretta
Indirizzi di blocco
0, 1, 2, 1, 8, 16, 8, 14, 2, 2, 1, 10, 22, 1, 8
blocco della cache = (numero blocco memoria) modulo (numero blocchi in cache)
Blocco
1
2
3
4
5
6
7
8
0
mem[0] mem[0] mem[0] mem[0] mem[8] mem[16] mem[8] mem[8]
1
mem[1] mem[1] mem[1] mem[1] mem[1] mem[1] mem[1]
2
mem[2] mem[2] mem[2] mem[2] mem[2] mem[2]
3
4
5
6
mem[14]
7
miss
miss
miss
hit
miss
miss
miss
miss
5
Caso 1: cache a corrispondenza diretta
Indirizzi di blocco
0, 1, 2, 1, 8, 16, 8, 14, 2, 2, 1, 10, 22, 1, 8
blocco della cache = (numero blocco memoria) modulo (numero blocchi in cache)
Blocco
0
1
2
3
4
5
6
7
9
10
11
12
13
14
15
mem[8] mem[8] mem[8] mem[8] mem[8] mem[8] mem[8]
mem[1] mem[1] mem[1] mem[1] mem[1] mem[1] mem[1]
mem[2] mem[2] mem[2] mem[10] mem[10] mem[10] mem[2]
mem[14] mem[14] mem[14] mem[14] mem[22] mem[22] mem[22]
hit
hit
hit
miss
miss
hit
hit
Risultato totale degli accessi alla cache = 9 miss e 6 hit
6
Caso 2: cache completamente associativa
Indirizzi di blocco
0, 1, 2, 1, 8, 16, 8, 14, 2, 2, 1, 10, 22, 1, 8
Cache
blocco di 4 parole
Un blocco della memoria può andare
in qualsiasi blocco della cache
Etichetta
Indirizzo
14
Parola
2
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Memoria
…
7
Caso 2: cache completamente associativa
Indirizzi di blocco
0, 1, 2, 1, 8, 16, 8, 14, 2, 2, 1, 10, 22, 1, 8
Blocco
1
2
3
4
5
6
7
8
0
mem[0] mem[0] mem[0] mem[0] mem[0] mem[0] mem[0] mem[0]
1
mem[1] mem[1] mem[1] mem[1] mem[1] mem[1] mem[1]
2
mem[2] mem[2] mem[2] mem[2] mem[2] mem[2]
3
mem[8] mem[8] mem[8] mem[8]
4
mem[16] mem[16] mem[16]
5
mem[14]
6
7
miss
miss
miss
hit
miss
miss
hit
miss
8
Caso 2: cache completamente associativa
Indirizzi di blocco
Blocco
0
1
2
3
4
5
6
7
9
mem[0]
mem[1]
mem[2]
mem[8]
mem[16]
mem[14]
hit
0, 1, 2, 1, 8, 16, 8, 14, 2, 2, 1, 10, 22, 1, 8
10
mem[0]
mem[1]
mem[2]
mem[8]
mem[16]
mem[14]
11
mem[0]
mem[1]
mem[2]
mem[8]
mem[16]
mem[14]
12
mem[0]
mem[1]
mem[2]
mem[8]
mem[16]
mem[14]
mem[10]
hit
hit
miss
13
mem[0]
mem[1]
mem[2]
mem[8]
mem[16]
mem[14]
mem[10]
mem[22]
miss
14
mem[0]
mem[1]
mem[2]
mem[8]
mem[16]
mem[14]
mem[10]
mem[22]
hit
15
mem[0]
mem[1]
mem[2]
mem[8]
mem[16]
mem[14]
mem[10]
mem[22]
hit
Risultato totale degli accessi alla cache = 8 miss e 7 hit
9
Caso 3: cache set-associativa a due vie
Indirizzi di blocco
Indirizzi di insieme
0, 1, 2, 1, 8, 16, 8, 14, 2, 2, 1, 10, 22, 1, 8
0, 1, 2, 1, 0, 0, 0, 2, 2, 2, 1, 2, 2, 1, 0
Un blocco della memoria può andare in un blocco
qualsiasi all’interno dell’insieme determinato a partire
dal numero del blocco in memoria
Cache
Insieme 0
…
Insieme 1
Insieme 2
Insieme 3
Etichetta
Indirizzo
12
Insieme
2
2
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Memoria
…
Parola
10
Caso 3: cache set-associativa a due vie
Indirizzi di blocco
0, 1, 2, 1, 8, 16, 8, 14, 2, 2, 1, 10, 22, 1, 8
insieme della cache = (numero blocco memoria) modulo (numero insiemi in cache)
Insieme
1
2
3
4
5
6
7
8
0
mem[0] mem[0] mem[0] mem[0] mem[0] mem[16] mem[16] mem[16]
mem[8] mem[8] mem[8] mem[8]
1
mem[1] mem[1] mem[1] mem[1] mem[1] mem[1] mem[1]
2
mem[2] mem[2] mem[2] mem[2] mem[2] mem[2]
mem[14]
3
miss
miss
miss
hit
miss
miss
hit
miss
11
Caso 3: cache set-associativa a due vie
Indirizzi di blocco
0, 1, 2, 1, 8, 16, 8, 14, 2, 2, 1, 10, 22, 1, 8
insieme della cache = (numero blocco memoria) modulo (numero insiemi in cache)
Insiem e
9
10
11
12
13
14
15
0
m em [16] m em [16] m em [16] m em [16] m em [16] m em [16] m em [16]
m em [8] m em [8] m em [8] m em [8] m em [8] m em [8] m em [8]
1
m em [1] m em [1] m em [1] m em [1] m em [1] m em [1] m em [1]
2
m em [2] m em [2] m em [2] m em [2] m em [22] m em [22] m em [2]
m em [14] m em [14] m em [14] m em [10] m em [10] m em [10] m em [10]
3
hit
hit
hit
miss
miss
hit
hit
Risultato totale degli accessi alla cache = 8 miss e 7 hit
12
Esercizio 2
• Sia data una cache con:
- 4K blocchi
- ogni blocco ha 4 parole
- indirizzi di 32 bit
• Trovare il numero totale di bit per i tag nel caso di:
- cache a corrispondenza diretta
- cache set associativa a 4 vie
- cache completamente associativa
13
Esercizio 2
• Sia data una cache con:
- 4K blocchi
- ogni blocco ha 4 parole
- indirizzi di 32 bit
Corrispondenza diretta:
4K = 212 blocchi
TAG
12 bit
4 bit
16 bit
32 - 16 = 16
16 bit * 212 = 16*4 kbit = 64 kbit
14
Esercizio 2
• Sia data una cache con:
- 4K blocchi
- ogni blocco ha 4 parole
- indirizzi di 32 bit
Set associativa a 4 vie:
4K = 212 blocchi ⇒ 212/4 = 210 insiemi
TAG
10 bit
4 bit
14 bit
32 - 14 = 18
18 bit * 212 = 18*4 kbit = 72 kbit
15
Esercizio 2
• Sia data una cache con:
- 4K blocchi
- ogni blocco ha 4 parole
- indirizzi di 32 bit
Completamente associativa:
4K = 212 blocchi
TAG
4 bit
32 - 4 = 28
28 bit * 212 = 28*4 kbit = 112 kbit
16
Esercizio 3
• Si consideri una CPU che esegue tutte le istruzioni in 2 cicli di clock.
• Si assuma il seguente carico di lavoro:
- Tipo-R
50 %
- lw
20 %
- sw
16 %
- salti
14 %
• Si dispone di una cache con le seguenti caratteristiche:
- fmiss per le istruzioni: 2%
- fmiss per accesso ai dati: 4%
- Pmiss= 100 cicli di clock
• Confrontare le prestazioni tra il caso reale ed il caso di cache ideale
senza miss
17
Caso reale
CPI = 2 + 0.02*100+ 0.36*0.04*100 = 2 + 2 + 1.44
= 5.44
Caso ideale
CPI = 2
Dato che nei due casi Tclock non cambia,
nel caso ideale il processore sarebbe
5.44/2 = 2.72 volte più veloce
18
Esercizio 3 (continua)
• Si consideri una CPU che esegue tutte le istruzioni in 2 cicli di clock.
• Si assuma il seguente carico di lavoro:
- Tipo-R
50 %
- lw
20 %
- sw
16 %
- salti
14 %
• Si dispone di una cache con le seguenti caratteristiche:
- fmiss per le istruzioni: 2%
- fmiss per accesso ai dati: 4%
- Pmiss= 100 cicli di clock
• Si supponga raddoppiare la frequenza del processore:
quale miglioramento in termini di prestazione si ottiene?
19
Nel caso precedente:
Tes = I * 5.44 * Tclock
Raddoppiando la frequenza:
Pmiss uguale in termini di tempo ⇒ raddoppia in termini di cicli
CPI = 2 + 0.02*200+ 0.36*0.04*200 = 2 + 4 + 2.88
= 8.88
Tes = I * 8,88 * T’clock
5.44*2
8.88
= 1.23 volte più veloce
20
Commento
Quanto più il processore è veloce (Tclock o CPI bassi)
tanto maggiore è l’importanza della cache
21
Esercizio 4
Si consideri un processore con CPI=1 e frequenza di 5GHz.
Si dispone di una cache primaria con fmiss = 2% e di una memoria
DRAM con un tempo di accesso di 100ns.
Determinare quale sarebbe l’incremento di prestazioni aggiungendo
una cache secondaria con un tempo di accesso di 5ns e fmiss = 25%
22
Esercizio 4
Si consideri un processore con CPI=1 e frequenza di 5GHz.
Si dispone di una cache primaria con fmiss = 2% e di una memoria
DRAM con un tempo di accesso di 100ns.
Determinare quale sarebbe l’incremento di prestazioni aggiungendo
una cache secondaria con un tempo di accesso di 5ns e fmiss = 25%
Solo cache L1
Tclock = 1/5*109 ns = 0.2 ns
⇒ Pmiss = 100/0.2 = 500 cicli di clock
CPI = 1+0.02*500 = 11
23
Esercizio 4
Si consideri un processore con CPI=1 e frequenza di 5GHz.
Si dispone di una cache primaria con fmiss = 2% e di una memoria
DRAM con un tempo di accesso di 100ns.
Determinare quale sarebbe l’incremento di prestazioni aggiungendo
una cache secondaria con un tempo di accesso di 5ns e fmiss = 25%
Solo cache L1
Tclock = 1/5*109 ns = 0.2 ns
⇒ Pmiss = 100/0.2 = 500 cicli di clock
CPI = 1+0.02*500 = 11
Cache L1 + L2
Miss in cache primaria, hit in secondaria: 5/0.2=25 cicli
CPI = 1+0.02*(0.75*25 + 0.25*525) = 4
24
Esercizio 4
Si consideri un processore con CPI=1 e frequenza di 5GHz.
Si dispone di una cache primaria con fmiss = 2% e di una memoria
DRAM con un tempo di accesso di 100ns.
Determinare quale sarebbe l’incremento di prestazioni aggiungendo
una cache secondaria con un tempo di accesso di 5ns e fmiss = 25%
Solo cache L1
Tclock = 1/5*109 ns = 0.2 ns
⇒ Pmiss = 100/0.2 = 500 cicli di clock
CPI = 1+0.02*500 = 11
11/4=2.8 volte più veloce
Cache L1 + L2
Miss in cache primaria, hit in secondaria: 5/0.2=25 cicli
CPI = 1+0.02*(0.75*25 + 0.25*525) = 4
25
NB: si noti che nonostante il local miss rate della cache L2
sia del 25%, il global miss rate risultante è 2%*25%= 0.5%
26