Esercizio 10dimensione del blocco più conveniente
In questa pagina 5
Testo (esercizio 4c, svolto in aula nella lezione del 19 ottobre 2016). 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 (esercizio 4c, svolto in aula nella lezione del 19 ottobre 2016). 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.