Esercizio 11cache a due vie con rimpiazzo FIFO
In questa pagina 3
Testo (assegnato il 19 ottobre e svolto in aula nella lezione del 24 ottobre 2016). Ripetere l'esercizio 8 nel caso di una cache associativa a due vie in grado di memorizzare 16 blocchi, ognuno costituito da una parola. Usare la politica FIFO per il rimpiazzo dei blocchi.
- 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
Scomposizione dell'indirizzo
- Campo parola: 0 bit (blocchi di una parola).
- 16 linee raggruppate a due a due → insiemi → campo insieme 3 bit: insieme = indirizzo mod 8.
- Etichetta: 29 bit.
Convenzione per le linee libere (da dichiarare nella soluzione): si usa la linea libera di indice minore, prima la [0] poi la [1]. 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 | Insieme | Esito | Linea usata | Note |
|---|---|---|---|---|---|
| 1 | 1 | 001 | miss | [0] | |
| 2 | 134 | 110 | miss | [0] | |
| 3 | 212 | 100 | miss | [0] | |
| 4 | 1 | 001 | hit | [0] | l'etichetta della linea [0] coincide |
| 5 | 135 | 111 | miss | [0] | |
| 6 | 213 | 101 | miss | [0] | |
| 7 | 162 | 010 | miss | [0] | |
| 8 | 161 | 001 | miss | [1] | la linea [0] contiene il blocco 1, ma c'è la [1] libera: niente rimpiazzo |
| 9 | 2 | 010 | miss | [1] | idem con il blocco 162 |
| 10 | 44 | 100 | miss | [1] | idem con il blocco 212 |
| 11 | 41 | 001 | miss | [0] | insieme pieno (blocchi 1 e 161): FIFO rimpiazza il primo entrato, il blocco 1 |
| 12 | 221 | 101 | miss | [1] | la [0] contiene 213, la [1] è libera |
1 hit, 11 miss. Rispetto all'associazione diretta l'esito è lo stesso, ma i blocchi 1 e 162 non vengono più scacciati da 161 e 2: se fossero richiesti di nuovo darebbero hit.
Sequenza 2
| # | Indirizzo | Insieme | Esito | Linea usata |
|---|---|---|---|---|
| 1 | 4 | 100 | miss | [0] |
| 2 | 214 | 110 | miss | [0] |
| 3 | 175 | 111 | miss | [0] |
| 4 | 214 | 110 | hit | [0] |
| 5 | 4 | 100 | hit | [0] |
| 6 | 84 | 100 | miss | [1] |
| 7 | 65 | 001 | miss | [0] |
| 8 | 174 | 110 | miss | [1] |
| 9 | 64 | 000 | miss | [0] |
| 10 | 105 | 001 | miss | [1] |
| 11 | 85 | 101 | miss | [0] |
| 12 | 215 | 111 | miss | [1] |
2 hit, 10 miss. Gli insiemi 001, 100, 110 e 111 arrivano ad avere entrambe le linee occupate, ma la politica FIFO non serve mai: nessun blocco viene rimpiazzato.
Versione ripasso
Testo (assegnato il 19 ottobre e svolto in aula nella lezione del 24 ottobre 2016). Ripetere l'esercizio 8 nel caso di una cache associativa a due vie in grado di memorizzare 16 blocchi, ognuno costituito da una parola. Usare la politica FIFO per il rimpiazzo dei blocchi.
- 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: parola 0 bit, insiemi insieme = indirizzo mod 8 (3 bit), etichetta 29 bit. Linea libera: quella di indice minore (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: insieme): 1: 1 miss [0]; 134: 6 miss; 212: 4 miss; 1 hit; 135: 7 miss; 213: 5 miss; 162: 2 miss; 161: 1 miss [1] (linea libera); 2: 2 miss [1]; 44: 4 miss [1]; 41: 1 miss, insieme pieno (1 e 161): FIFO rimpiazza il primo entrato, il 1; 221: 5 miss [1].
- Sequenza 2: 4: 4 miss; 214: 6 miss; 175: 7 miss; 214 hit; 4 hit; 84: 4 miss [1]; 65: 1 miss; 174: 6 miss [1]; 64: 0 miss; 105: 1 miss [1]; 85: 5 miss; 215: 7 miss [1]. Nessun rimpiazzo.
Sequenza 1: 1 hit, 11 miss; sequenza 2: 2 hit, 10 miss. Gli esiti coincidono con la mappatura diretta, ma i blocchi 1 e 162 non vengono più scacciati da 161 e 2.