Esercizio 10dimensione del blocco più conveniente
In questa pagina 5
Testo. Con riferimento alle sequenze dell'esercizio 8, supponendo di avere una cache ad associazione diretta in grado di memorizzare 8 parole, quale fra le seguenti dimensioni di blocco è la più conveniente (minimizza il numero di miss): 1 parola, 2 parole, 4 parole?
- Sequenza 1: 1, 134, 212, 1, 135, 213, 162, 161, 2, 44, 41, 221
- Sequenza 2: 4, 214, 175, 214, 4, 84, 65, 174, 64, 105, 85, 215
I tre scenari
La capacità resta 8 parole: cambiando il blocco cambia il numero di linee.
| Blocco | Linee | Campo parola | Campo linea | Etichetta |
|---|---|---|---|---|
| 1 parola | 8 | 0 bit | 3 bit | 29 bit |
| 2 parole | 4 | 1 bit | 2 bit | 29 bit |
| 4 parole | 2 | 2 bit | 1 bit | 29 bit |
In tutti i casi: blocco = indirizzo div (parole per blocco), linea = blocco mod (numero di linee). Vedi Memoria cacheBlocchi, linee ed etichette; scomposizione dell'indirizzo; associazione diretta, completamente associativa e associativa a insiemi con calcolo dei campi; politiche di rimpiazzo (LRU, FIFO, casuale); politiche di scrittura (write-through, write-back con bit sporco, write-allocate); dimensione del blocco; cache multilivello e separate; come ridurre i miss; quesiti sui campi dell'indirizzo.Memoria cache →.
Scenario 1: blocchi di 1 parola, 8 linee
Linea = indirizzo mod 8.
- Sequenza 1: linee 1, 6, 4, 1 (hit), 7, 5, 2, 1, 2, 4, 1, 5. Dopo il quarto accesso ogni blocco trova la sua linea vuota o occupata da un altro blocco: 1 hit, 11 miss.
- Sequenza 2: linee 4, 6, 7, 6 (hit), 4 (hit), 4, 1, 6, 0, 1, 5, 7 → 2 hit, 10 miss.
Totale: 21 miss.
Scenario 2: blocchi di 2 parole, 4 linee
Blocco = indirizzo div 2, linea = blocco mod 4.
| Seq. 1 | 1 | 134 | 212 | 1 | 135 | 213 | 162 | 161 | 2 | 44 | 41 | 221 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| blocco | 0 | 67 | 106 | 0 | 67 | 106 | 81 | 80 | 1 | 22 | 20 | 110 |
| linea | 0 | 3 | 2 | 0 | 3 | 2 | 1 | 0 | 1 | 2 | 0 | 2 |
| esito | M | M | M | H | H | H | M | M | M | M | M | M |
| Seq. 2 | 4 | 214 | 175 | 214 | 4 | 84 | 65 | 174 | 64 | 105 | 85 | 215 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| blocco | 2 | 107 | 87 | 107 | 2 | 42 | 32 | 87 | 32 | 52 | 42 | 107 |
| linea | 2 | 3 | 3 | 3 | 2 | 2 | 0 | 3 | 0 | 0 | 2 | 3 |
| esito | M | M | M | M | H | M | M | M | H | M | H | M |
Nella sequenza 2 i blocchi 107 e 87 si contendono la linea 3 e si scacciano a vicenda (4 miss di conflitto).
Sequenza 1: 3 hit, 9 miss; sequenza 2: 3 hit, 9 miss. Totale: 18 miss.
Scenario 3: blocchi di 4 parole, 2 linee
Blocco = indirizzo div 4, linea = blocco mod 2.
| Seq. 1 | 1 | 134 | 212 | 1 | 135 | 213 | 162 | 161 | 2 | 44 | 41 | 221 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| blocco | 0 | 33 | 53 | 0 | 33 | 53 | 40 | 40 | 0 | 11 | 10 | 55 |
| linea | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| esito | M | M | M | H | M | M | M | H | M | M | M | M |
| Seq. 2 | 4 | 214 | 175 | 214 | 4 | 84 | 65 | 174 | 64 | 105 | 85 | 215 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| blocco | 1 | 53 | 43 | 53 | 1 | 21 | 16 | 43 | 16 | 26 | 21 | 53 |
| linea | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| esito | M | M | M | M | M | M | M | M | H | M | M | M |
Con due sole linee quasi tutti i blocchi della sequenza 2 finiscono sulla linea 1 e si scacciano continuamente.
Sequenza 1: 2 hit, 10 miss; sequenza 2: 1 hit, 11 miss. Totale: 21 miss.
Risposta
| Blocco | Miss totali |
|---|---|
| 1 parola | 21 |
| 2 parole | 18 |
| 4 parole | 21 |
Il blocco di 2 parole è il più conveniente. A capacità fissa, un blocco più grande sfrutta meglio la località spaziale ma riduce il numero di linee e aumenta i conflitti: il blocco da 2 parole è il compromesso migliore per queste sequenze.
Versione ripasso
Testo. Con riferimento alle sequenze dell'esercizio 8, supponendo di avere una cache ad associazione diretta in grado di memorizzare 8 parole, quale fra le seguenti dimensioni di blocco è la più conveniente (minimizza il numero di miss): 1 parola, 2 parole, 4 parole?
- Sequenza 1: 1, 134, 212, 1, 135, 213, 162, 161, 2, 44, 41, 221
- Sequenza 2: 4, 214, 175, 214, 4, 84, 65, 174, 64, 105, 85, 215
Metodo: capacità fissa a 8 parole, quindi 8, 4 o 2 linee; blocco = indirizzo div (parole per blocco), linea = blocco mod (linee) (Memoria cacheBlocchi, linee ed etichette; scomposizione dell'indirizzo; associazione diretta, completamente associativa e associativa a insiemi con calcolo dei campi; politiche di rimpiazzo (LRU, FIFO, casuale); politiche di scrittura (write-through, write-back con bit sporco, write-allocate); dimensione del blocco; cache multilivello e separate; come ridurre i miss; quesiti sui campi dell'indirizzo.Memoria cache →).
- 1 parola, 8 linee (linea = indirizzo mod 8). Seq. 1: linee 1, 6, 4, 1, 7, 5, 2, 1, 2, 4, 1, 5: 1 hit (il quarto accesso). Seq. 2: linee 4, 6, 7, 6, 4, 4, 1, 6, 0, 1, 5, 7: 2 hit (quarto e quinto). Totale 21 miss.
- 2 parole, 4 linee. Seq. 1: blocchi 0, 67, 106, 0, 67, 106, 81, 80, 1, 22, 20, 110, linee 0, 3, 2, 0, 3, 2, 1, 0, 1, 2, 0, 2: hit agli accessi 4, 5, 6 (3 hit, 9 miss). Seq. 2: blocchi 2, 107, 87, 107, 2, 42, 32, 87, 32, 52, 42, 107, linee 2, 3, 3, 3, 2, 2, 0, 3, 0, 0, 2, 3: hit agli accessi 5, 9, 11 (107 e 87 si scacciano sulla linea 3); 3 hit, 9 miss. Totale 18 miss.
- 4 parole, 2 linee. Seq. 1: blocchi 0, 33, 53, 0, 33, 53, 40, 40, 0, 11, 10, 55, linee 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1: hit agli accessi 4 e 8 (2 hit, 10 miss). Seq. 2: blocchi 1, 53, 43, 53, 1, 21, 16, 43, 16, 26, 21, 53, quasi tutti sulla linea 1: solo l'accesso 9 è hit (1 hit, 11 miss). Totale 21 miss.
Risposta: il blocco da 2 parole (18 miss, contro 21 e 21). A capacità fissa blocchi più grandi sfruttano la località spaziale ma riducono le linee e aumentano i conflitti.