Esercizio 21cache a due vie FIFO con write-through

Campi dell'indirizzo e struttura della cache

• Indirizzi di 12 bit (i 12 bit del testo).
• Blocco di 4 B → parola 2 bit.
• Linee: $32 / 4 = 8$; a 2 vie → $8 / 2 = 4$ insiemi → set 2 bit.
• Etichetta: $12 - 2 - 2 = 8$ bit.

L'indirizzo 0001 0000 0100 è quindi etichetta 00010000, set 01, parola 00. Il blocco che inizia a 104 va nell'insieme $01$ (il blocco ha indirizzo $0x104 / 4 = 65$ e $65 \bmod 4 = 1$).

Regole applicate

• FIFO: in un insieme pieno esce la linea caricata per prima, a prescindere dagli accessi successivi (diverso da LRU).
• Write-through: ogni scrittura (hit o miss) scrive anche in memoria: la colonna "memoria" riporta M[indirizzo] = byte a ogni s.
• Write allocate: su miss in scrittura prima si carica il blocco dalla memoria (con i valori vecchi), poi si scrive il byte sia nella linea sia in memoria.
• La lettura di un blocco carica tutte e 4 le parole; in tabella si scrivono i 4 byte della linea dopo l'accesso.

Evoluzione

Esito: 3 hit (accessi 3, 4, 7) e 5 miss.

Dettaglio dell'accesso 8. Nell'insieme 01 ci sono la linea 0 (blocco 104, caricata al passo 1) e la linea 1 (blocco 114, passo 5). Con FIFO esce la linea 0 anche se è stata usata al passo 7: con LRU sarebbe uscita la linea 1. Poiché la politica è write-through, la linea uscente non va riscritta in memoria (la memoria è già aggiornata: M[107] = 66).

Stato finale

Memoria modificata: M[10C] = 3F, M[10D] = A9, M[11F] = 5E, M[107] = 66.

Variante dell'esempio di compitino a.a. 2015-16

Stessa cache (32 B, blocchi da 4 B, 2 vie, FIFO, write-through, write allocate), sequenza 108 l, 10C l, 10F s C9, 10D l, 118 s DD, 11F l, 10B s 67, 125 l e memoria con contenuti leggermente diversi. Con lo stesso procedimento: 3 hit (accessi 3, 4 e 7) e 5 miss (accessi 1, 2, 5, 6 e 8); le scritture portano M[10F] = C9, M[118] = DD, M[10B] = 67. Al passo 8 l'insieme 01 è ancora vuoto, quindi non c'è rimpiazzo.

Verifica con un simulatore

La tabella è stata ottenuta con un breve simulatore che applica le regole sopra (indirizzo, etichetta/insieme/parola, FIFO o LRU, write-through o write-back, write allocate) e riprodotta anche a mano. Ecco il nucleo, per chi vuole rifare la prova su altre sequenze:

def cache(accessi, memoria, byte_cache, blocco, vie, bit_ind=12):
    """Cache write-through con write allocate e rimpiazzo FIFO; accessi = [(indirizzo, 'l'|'s', valore)]."""
    insiemi = byte_cache // blocco // vie
    righe = {i: [] for i in range(insiemi)}           # per ogni insieme: lista in ordine di caricamento (la prima esce)
    esiti = []
    for a, op, val in accessi:
        s, base = (a // blocco) % insiemi, a - a % blocco
        et = a // blocco // insiemi
        linea = next((l for l in righe[s] if l["et"] == et), None)
        hit = linea is not None
        if not hit:
            if len(righe[s]) == vie:
                righe[s].pop(0)                       # FIFO: esce la più vecchia
            linea = {"et": et, "dati": [memoria.get(base + k, 0) for k in range(blocco)]}
            righe[s].append(linea)
        if op == "s":
            linea["dati"][a % blocco] = val
            memoria[a] = val                          # write-through
        esiti.append("hit" if hit else "miss")
    return esiti, righe

memoria = {}
for ind, byte4 in [(0x100, "08 D0 07 02"), (0x104, "00 00 00 00"), (0x108, "AE 13 A1 23"), (0x10C, "A1 42 90 75"),
                   (0x110, "BB 16 00 00"), (0x114, "0A 87 03 71"), (0x118, "3E 13 A1 23"), (0x11C, "A1 82 90 15"),
                   (0x120, "F9 86 A0 00"), (0x124, "E9 16 05 00")]:
    for k, b in enumerate(byte4.split()):
        memoria[ind + k] = int(b, 16)

accessi = [(0x104, "l", None), (0x10C, "s", 0x3F), (0x10F, "l", None), (0x10D, "s", 0xA9),
           (0x114, "l", None), (0x11F, "s", 0x5E), (0x107, "s", 0x66), (0x126, "l", None)]
esiti, righe = cache(accessi, memoria, 32, 4, 2)
print(esiti)                                           # ['miss', 'miss', 'hit', 'hit', 'miss', 'miss', 'hit', 'miss']
print({hex(a): hex(memoria[a]) for a in (0x10C, 0x10D, 0x11F, 0x107)})   # le quattro scritture in memoria
print([[(hex(l["et"]), l["dati"]) for l in righe[s]] for s in range(4)])  # stato finale per insieme

Errori comuni

• Usare LRU invece di FIFO: la linea usata di recente non si salva dal rimpiazzo.
• Dimenticare che il write-through scrive in memoria a ogni s, anche sugli hit; oppure dimenticare il write allocate (sui miss in scrittura il blocco va prima caricato).
• Caricare nella linea soltanto il byte e non tutto il blocco di 4 byte.
• Calcolare l'insieme con i bit sbagliati: i due bit del set sono quelli subito sopra i due bit della parola.