Esercizio 22cache a due vie LRU con write-back

Campi e struttura

• Blocco di 2 B → parola 1 bit.
• Linee: $32 / 2 = 16$; a 2 vie → $16 / 2 = 8$ insiemi → set 3 bit.
• Etichetta: $12 - 3 - 1 = 8$ bit.

(La soluzione allegata al testo scrive "4 set, ognuno di 2 linee" ma indica correttamente i campi etichetta 8 bit, set 3 bit, parola 1 bit: con 3 bit di set gli insiemi sono 8, ciascuno di 2 linee da 2 B; i risultati dell'esempio sono quelli che si ottengono con 8 insiemi.)

L'indirizzo 0001 0000 1001 ha etichetta 00010000 (10 esadecimale), set 100 (4), parola 1.

Regole applicate

• LRU: nell'insieme pieno esce la linea usata meno di recente (un accesso, in lettura o scrittura, "usa" la linea).
• Write-back: la scrittura modifica solo la cache e mette a 1 il bit sporco (nella tabella un * dopo il contenuto). La memoria si aggiorna solo quando una linea sporca viene rimpiazzata, e allora si riscrive l'intero blocco.
• Write allocate: su miss in scrittura il blocco viene prima caricato, poi modificato in cache (e resta sporco).

Evoluzione

Esito: 1 hit (accesso 5) e 7 miss. Nessun rimpiazzo: in nessun passo un insieme già pieno riceve un nuovo blocco (al più due blocchi per insieme), quindi la memoria non cambia per tutto l'esercizio: le quattro scritture (AB, 39, D4, 98) vivono solo nella cache, nelle linee marcate *. In un sistema reale quei dati arriverebbero in memoria solo al rimpiazzo della linea o con una operazione di svuotamento (flush).

Stato finale

Che cosa cambierebbe con write-through

Con write-through ogni s aggiornerebbe subito la memoria: M[10D] = AB, M[10E] = 39, M[108] = D4, M[10A] = 98 (quattro scritture di un byte, in memoria da subito); con write-back nessuna scrittura in memoria in questo esempio, ma un eventuale rimpiazzo successivo di una linea sporca costerebbe la riscrittura di 2 byte. Vedi Esercizio 21 · cache a due vie FIFO con write-through per il caso opposto.

Verifica con un simulatore

def cache_wb(accessi, memoria, byte_cache, blocco, vie):
    """LRU, write-back, write allocate. Restituisce esiti, cache e memoria."""
    insiemi = byte_cache // blocco // vie
    righe = {i: [] for i in range(insiemi)}           # per insieme: linee dal meno al più recentemente usato
    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 hit:
            righe[s].remove(linea)
        else:
            if len(righe[s]) == vie:
                v = righe[s].pop(0)                    # LRU: la prima della lista
                if v["sporca"]:
                    vb = (v["et"] * insiemi + s) * blocco
                    for k in range(blocco):
                        memoria[vb + k] = v["dati"][k]  # riscrive l'intero blocco
            linea = {"et": et, "dati": [memoria.get(base + k, 0) for k in range(blocco)], "sporca": False}
        righe[s].append(linea)                         # ora è la più recente
        if op == "s":
            linea["dati"][a % blocco] = val
            linea["sporca"] = True
        esiti.append("hit" if hit else "miss")
    return esiti, righe, memoria

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

accessi = [(0x109, "l", None), (0x10D, "s", 0xAB), (0x10E, "s", 0x39), (0x11C, "l", None),
           (0x108, "s", 0xD4), (0x11E, "l", None), (0x10A, "s", 0x98), (0x121, "l", None)]
esiti, righe, memoria = cache_wb(accessi, memoria, 32, 2, 2)
print(esiti)                                           # ['miss', 'miss', 'miss', 'miss', 'hit', 'miss', 'miss', 'miss']
print(memoria == originale)                            # True: nessuna scrittura in memoria
for s in range(8):
    print(format(s, "03b"), [(hex(l["et"]), [format(b, "02X") for b in l["dati"]], l["sporca"]) for l in righe[s]])

Errori comuni

• Applicare write-through: scrivere subito in memoria. Con write-back la memoria resta uguale finché non si rimpiazza una linea sporca.
• Dimenticare il write allocate: un s che manca va trattato come una lettura che carica il blocco e poi modifica un byte.
• Con LRU, non aggiornare l'"uso" sugli hit (nell'accesso 5 la linea 0 dell'insieme 100 diventa la più recente).
• Contare 4 insiemi invece di 8: i 3 bit di set sono dati dal rapporto $16 / 2$.
• Riscrivere solo il byte modificato al rimpiazzo di una linea sporca: va riscritto tutto il blocco.