Esercizi sulle memorie Cache

Esercizio 1
Fare gli esercizi 26, 27 e 28 del Capitolo 4 del Tanenbaum.

Soluzione 26. (By Salvatore Fede)

Soluzione 28. (By Francesco Caponnetto)

Esercizio 2
Si supponga di avere un calcolatore con 2^32 byte di memoria e dimensione di bloc co di 4 byte.
Quanti bit sono necessari per una cache diretta che contenga 64K byte di dat i?

Soluzione.

Esercizio 3
Si consideri una cache diretta con 64 slot di 16 byte ciascuno.
A quale indirizzo di slot corrisponde il byte di indirizzo 1200?
(abbiamo indirizzamento al byte)

Soluzione.

Esercizio 4
A prima vista pare che la presenza o l'assenza della cache non abbia influenza sulla decisione di utilizzare un I/O a mappa di memoria o meno.
Puo' creare invece potenziali problemi?

Soluzione.

Esercizio 5
La tabella sotto riportata rappresenta la struttura di una memoria cache a mappatura diretta composta da 8 linee, ciascuna avente porzione Dati di 4 parole.
Si supponga che inizialmente la cache sia vuota e che il processore indirizzi byte della RAM mediante indirizzi di 9 bit abcdefghi aventi il seguente formato: i bit ab per il tag, i bit cde per la linea, i bit fg per la parola, i bit hi per il byte. Si supponga che il processore esegua la seguente sequenza di indirizzamenti: 100011000, 100111001, 110011000, 101010011, 100000000, 110010011, 001010001, 110100011, 010001100, 011010011 (a) Si completi la tabella in modo che rappresenti lo stato della cache dopo che il processore abbia eseguito l'intera sequenza di indirizzamenti (supponendo che nel frattempo nessun evento esterno influenzi i bit di validita'). Per la porzione Dati si indichi semplicemente con M[abcde], dove abcde e' l'indirizzo della linea di RAM caricata nella linea cde di cache.

        Valida
          |
Linea     v   Tag   Dati   
        -------------------
000     | 0 |     |        |
        -------------------
001     | 0 |     |        |
        -------------------
010     | 0 |     |        |
        -------------------
011     | 0 |     |        |
        -------------------
100     | 0 |     |        |
        -------------------
101     | 0 |     |        |
        -------------------
110     | 0 |     |        |
        -------------------
111     | 0 |     |        |
        -------------------

Soluzione.

Esercizio 6(non banale)
Fare l'esercizio 34 del Capitolo 4 del Tanenbaum.

Esercizio 7
Ci sono tre memorie cache, ciascuna composta da 32 parole per la parte dati. Ogni blocco di memoria e' composto da 8 parole. L'indirizzamento in memoria e' al byte.
Una cache e' ad indirizzamento diretto, la seconda set-associativa a due vie, la terza set-associativa a quattro vie.
Nell'ipotesi che la politica di sostituzione selezioni sempre il blocco util izzato meno di recente, trovare il numero di fallimenti per le tre diverse cache, data la seguente sequenza di indirizzi:

Soluzione. (By By Riela e Narzisi)

Esercizio 7
Un sistema di cache ha un rapporto di successi del 95%, un tempo di accesso di cache di 100nsec e un tempo di accesso in memoria centrale di 800nsec.
Qual'e' il tempo effettivo medio di accesso?

Soluzione. (By Francesco Caponnetto)

Esercizio 8

Indicare, ove possibile (e cioe' quando i dati sono disponibili nella cache), il valore corrispondente ai seguenti indirizzi, quando venga usata una cache set-associativa a dieci vie e con un unica linea di cache, con blocchi di 8 celle, il cui contenuto e' riportato sotto.
Indirizzi: 800, 40, 3204, 10


 Validita' N.Blocco                 Contenuto
                      0     1     2     3     4     5     6     7
     ---------------------------------------------------------------
     | 0 |  327    | 0   | 0   | 0   | 0   | 0   | 0   | 0   | 0   |
     | 1 |  328    | 10  | 11  | 12  | 13  | 14  | 15  | 16  | 17  |
     | 1 |  400    | 255 | 100 | 128 | 150 | 73  | 255 | 32  | 101 |
     | 0 |  1      | 100 | 200 | 100 | 200 | 100 | 200 | 100 | 200 |
     | 0 |  2      | 101 | 100 | 99  | 98  | 97  | 96  | 95  | 94  |
     | 1 |  329    | 102 | 200 | 202 | 188 | 134 | 10  | 7   | 120 |
     | 1 |  10     | 50  | 51  | 52  | 53  | 54  | 55  | 56  | 57  |
     | 1 |  700    | 50  | 60  | 70  | 80  | 90  | 100 | 110 | 120 |
     | 0 |  330    | 0   | 1   | 2   | 3   | 4   | 5   | 6   | 7   |
     | 1 |  3      | 2   | 33  | 0   | 0   | 222 | 32  | 128 | 77  |
     ---------------------------------------------------------------

Soluzione. (By Francesco Caponnetto and Peppe Morreale)

Esercizio 9

Si intende progettare una memoria cache con i seguenti vincoli:

2³² byte di memoria principale
K slot di cache
dimensioni di blocco di 32 byte

Si giustifiche la seguente asserzione: "Con questi vincoli ogni entry di una cache a mappa diretta con una sola linea di cache a molte vie (entry) necessita di 284 bit, mentre per uno slot di una cache a mappa diretta sono sufficienti 274 bit".

Soluzione. (By E. Laviano)

Esercizio 10
Scrivere una bella domanda intelligente che riguardi le cache e la cui risposta sia "write through".

Esercizio 11
In presenza di memorie cache, la scrittura di una parola di memoria deve essere gestita con tecniche opportune. Perche', quali problemi comporta?
Descrivere brevemente tali tecniche.

Esercizio 12
Cache a corrispondenza diretta (Direct-Mapped Cache): discuterne.
Descrivere in dettaglio come viene cercata una parola di memoria in una cache a corrispondenza diretta.

Esercizio 13
Si supponga di avere una memoria cache a corrispondenza diretta (direct-mapped cache) composta da 8 linee, ciascuna avente porzione Dati di 4 parole.
Supponiamo che il processore indirizzi i byte della memoria principale mediante indirizzi di 9 bit abcdefghi aventi il seguente formato: i bit ab per il tag, i bit cde per la linea, i bit fg per la parola, i bit hi per il byte. Si supponga inoltre che inizialmente la cache sia vuota (tutti i bit di validita', Valid, a 0) e che il processore esegua la seguente sequenza di indirizzamenti: 100011000, 100111001, 110011000, 101010011, 100000000, 110010011, 001010001, 110100011, 010001100, 011010011 Dire, giustificando la risposta, se, ed in quali casi, avviene un cache hit.

Esercizio 14
Cosa avviene in una memoria cache a corrispondenza diretta (direct-mapped cache) in caso di cache miss?
Si supponga di avere una memoria cache a corrispondenza diretta composta da 8 linee, ciascuna avente porzione Dati di 4 parole.
Supponiamo che il processore indirizzi i byte della memoria principale mediante indirizzi di 9 bit abcdefghi aventi il seguente formato: i bit ab per il tag, i bit cde per la linea, i bit fg per la parola, i bit hi per il byte. Si supponga inoltre che inizialmente la cache sia vuota (tutti i bit di validita', Valid, a 0) e che il processore esegua la seguente sequenza di indirizzamenti: 100011000, 100111001, 110011000, 101010011, 100000000, 110010011, 001010001, 110100011, 010001100, 011010011 Per ogni indirizzamento della sequenza dire, giustificando la risposta, se avviene un cache hit o un cache miss.

Esercizi sulla Memoria Virtuale

(Anni Precedenti)

Esercizio 1
Fare gli esercizi 1, 2, 3, 16 del Capitolo 6 del Tanenbaum.

Soluzione 2. (By P. Morreale)

Soluzione 3. (By P. Morreale)

Esercizio 2
Descrivere del similarita' e le differenze tra le Memorie Cache e le Memorie Virtuali.

Soluzione 2. (By G. Narzisi)

Esercizio 3
E' possibile implementare una memoria virtuale utilizzando lo stesso meccanismo delle cache a mappa diretta per realizzare il mapping tra indirizzi virtuali e fisici?

Esercizio 4.0
In figura 6-17 del Tanenbaum a sinistra e' mostrato come un indirizzo virtuale della memoria virtuale dell'UltraSPARC per pagine di dimensione 8K, sia suddivisibile in un numero di pagina di 51 bit e in un offset di 13 bit.
Poi pero' nel testo, quando inizia a parlare delle TLB si dice che per pagine di dimensione 8K il numero di pagine virtuali e' 2^31 (non 2^51!).
C'e' un errore? perche'?

Esercizio 4
Supponete di avere un sistema dotato di una memoria virtuale composta da 32 pagine di 8 celle ciascuna, ed una memoria principale composta da 16 pagine.
Si supponga che la tabella dei frames sia la seguente:

     ------------
  31 | 0 |  111 |
  30 | 0 |  110 |
  29 | 1 |  011 |
  28 | 0 |  110 |
  27 | 1 |  010 |
  26 | 0 |  000 |
  25 | 1 |  111 |
  24 | 0 |  111 |
  23 | 1 |  001 |
  22 | 0 |  000 |
  :  : : :  :   :
  :  : : :  :   :
  :  : : :  :   :
   9 | 0 |  001 |
   8 | 1 |  000 |
   7 | 0 |  010 |
   6 | 1 |  100 |
   5 | 0 |  100 |
   4 | 0 |  100 |
   3 | 0 |  100 |
   2 | 1 |  101 |
   1 | 1 |  110 |
   0 | 0 |  100 |
     ------------

Supponete di avere anche una memoria cache a mappa diretta composta da 4 linee di cache di 4 celle ciascuna descritta nella seguente figura.

 Validita'   Tag           Contenuto
                      0     1     2     3  
     ---------------------------------------
3    | 0 |  111    | 0   | 0   | 0   | 0   | 
2    | 1 |  011    | 10  | 11  | 12  | 13  | 
1    | 1 |  010    | 255 | 100 | 128 | 150 | 
0    | 0 |  100    | 100 | 200 | 100 | 200 | 
     ---------------------------------------

Si supponga ora di voler leggere la cella di indirizzo virtuale 10111001.
Tale lettura:

causera un page fault ?

causera' un cache miss ?

la parola cercata e' nella cache? dove?

la parola cercata e' in memoria principale? dove?

dove si trova in memoria virtuale ?

come sara' la cache dopo la lettura ?

Soluzione.