Esercizio 8hit e miss in cache ad associazione diretta
In questa pagina 5
Testo (esercizio 4a, svolto in aula nella lezione del 19 ottobre 2016). Date le seguenti due sequenze di indirizzi di memoria (di parola, a 32 bit) emessi dalla CPU e una cache ad associazione diretta di 16 blocchi da una parola, dire come si scompone l'indirizzo e determinare le corrispondenti sequenze di hit e miss. Ogni sequenza parte con la cache vuota.
- 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
(In aula gli indirizzi sono dati in binario su 32 bit; qui sono scritti in decimale.)
Scomposizione dell'indirizzo
- Blocco di una parola: il campo parola ha bit. Caso estremo: l'indirizzo della parola è l'indirizzo del blocco.
- 16 linee → campo linea di 4 bit: linea = indirizzo mod 16, cioè i 4 bit meno significativi.
- Etichetta: 28 bit, cioè indirizzo div 16.
Procedura
Per ogni indirizzo: si calcola la linea; se è vuota → miss; se contiene un blocco con la stessa etichetta → hit; altrimenti → miss e il blocco presente viene sostituito (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 →).
Sequenza 1
| # | Indirizzo | Binario (8 bit bassi) | Linea | Etichetta | Esito | Note |
|---|---|---|---|---|---|---|
| 1 | 1 | 0000 0001 | 1 | 0 | miss | linea vuota |
| 2 | 134 | 1000 0110 | 6 | 8 | miss | |
| 3 | 212 | 1101 0100 | 4 | 13 | miss | |
| 4 | 1 | 0000 0001 | 1 | 0 | hit | etichetta uguale |
| 5 | 135 | 1000 0111 | 7 | 8 | miss | |
| 6 | 213 | 1101 0101 | 5 | 13 | miss | |
| 7 | 162 | 1010 0010 | 2 | 10 | miss | |
| 8 | 161 | 1010 0001 | 1 | 10 | miss | etichetta diversa: esce il blocco 1 |
| 9 | 2 | 0000 0010 | 2 | 0 | miss | esce il blocco 162 |
| 10 | 44 | 0010 1100 | 12 | 2 | miss | |
| 11 | 41 | 0010 1001 | 9 | 2 | miss | |
| 12 | 221 | 1101 1101 | 13 | 13 | miss |
1 hit, 11 miss.
Sequenza 2
| # | Indirizzo | Binario (8 bit bassi) | Linea | Etichetta | Esito | Note |
|---|---|---|---|---|---|---|
| 1 | 4 | 0000 0100 | 4 | 0 | miss | |
| 2 | 214 | 1101 0110 | 6 | 13 | miss | |
| 3 | 175 | 1010 1111 | 15 | 10 | miss | |
| 4 | 214 | 1101 0110 | 6 | 13 | hit | |
| 5 | 4 | 0000 0100 | 4 | 0 | hit | |
| 6 | 84 | 0101 0100 | 4 | 5 | miss | esce il blocco 4 |
| 7 | 65 | 0100 0001 | 1 | 4 | miss | |
| 8 | 174 | 1010 1110 | 14 | 10 | miss | |
| 9 | 64 | 0100 0000 | 0 | 4 | miss | |
| 10 | 105 | 0110 1001 | 9 | 6 | miss | |
| 11 | 85 | 0101 0101 | 5 | 5 | miss | |
| 12 | 215 | 1101 0111 | 7 | 13 | miss |
2 hit, 10 miss.
Osservazione
Quasi tutti i miss sono di primo accesso; gli unici di conflitto sono 161 e 2 nella sequenza 1 e 84 nella sequenza 2, blocchi che vanno su una linea già occupata da un altro blocco. Le varianti con blocchi più grandi e con associatività a due vie sono negli esercizi 9, 10 e 11.
Versione ripasso
Testo (esercizio 4a, svolto in aula nella lezione del 19 ottobre 2016). Date le seguenti due sequenze di indirizzi di memoria (di parola, a 32 bit) emessi dalla CPU e una cache ad associazione diretta di 16 blocchi da una parola, dire come si scompone l'indirizzo e determinare le corrispondenti sequenze di hit e miss. Ogni sequenza parte con la cache vuota.
- 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
(In aula gli indirizzi sono dati in binario su 32 bit; qui sono scritti in decimale.)
Metodo: blocco di una parola campo parola 0 bit; 16 linee linea = indirizzo mod 16 (4 bit), etichetta = indirizzo div 16 (28 bit). Linea vuota o etichetta diversa miss (e sostituzione), etichetta uguale hit (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 →).
- Sequenza 1 (indirizzo: linea, etichetta): 1: 1, 0 miss; 134: 6, 8 miss; 212: 4, 13 miss; 1 hit; 135: 7, 8 miss; 213: 5, 13 miss; 162: 2, 10 miss; 161: 1, 10 miss (esce il blocco 1); 2: 2, 0 miss (esce 162); 44: 12, 2 miss; 41: 9, 2 miss; 221: 13, 13 miss.
- Sequenza 2: 4: 4, 0 miss; 214: 6, 13 miss; 175: 15, 10 miss; 214 hit; 4 hit; 84: 4, 5 miss (esce il blocco 4); 65: 1, 4 miss; 174: 14, 10 miss; 64: 0, 4 miss; 105: 9, 6 miss; 85: 5, 5 miss; 215: 7, 13 miss.
Sequenza 1: 1 hit, 11 miss. Sequenza 2: 2 hit, 10 miss. I miss di conflitto sono 161 e 2 (sequenza 1) e 84 (sequenza 2). Varianti: 9, 10, 11.