Salta al contenuto
Note per Studenti Esercizio 23 · cache con rimpiazzo di una linea sporca

Esercizio 23cache con rimpiazzo di una linea sporca

Esame
In questa pagina 5

Testo (esempio di compitino intermedio di Architettura degli Elaboratori, UniPD, a.a. 2010-11, esercizio 8 in alternativa). Sia data la seguente sequenza di indirizzi in lettura (l) o scrittura (s) emessi dalla CPU:

# indirizzo (binario) l/s byte scritto (hex)
1 0001 0000 0000 l
2 0001 0000 1000 l
3 0001 0000 1100 s FF
4 0001 0000 1101 s AD
5 0001 0001 0000 l
6 0001 0001 0000 s 1B
7 0001 0001 0100 l
8 0000 0111 0101 l

La dimensione di parola coincide con un byte; la cache ha ampiezza 16 B, dimensione di blocco 4 B, è inizialmente vuota, a 2 vie, rimpiazzo LRU, politica di scrittura write-back, miss in scrittura con write allocate. La memoria ha il contenuto esadecimale:

indirizzo byte byte byte byte
100 08 00 07 02
104 00 00 00 00
108 AE 13 A1 23
10C A1 42 90 75
110 B9 16 00 00
114 0A 07 03 71

(Nel testo l'ultima riga è stampata "110 B9 111 16 112 00 112 00": un errore di battitura; il contenuto del blocco che inizia a 074, usato dall'ultimo accesso, non è indicato: lo si assume 00 00 00 00.) Si mostri come cambiano il contenuto della cache e quello della memoria.

Teoria: 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 →. Esercizi analoghi: Esercizio 22 · cache a due vie LRU con write-back, Esercizio 11 · cache a due vie con rimpiazzo FIFO.

Campi e struttura

  • Parola: blocco di 4 B → 2 bit.
  • Linee: 16/4=416 / 4 = 4; a 2 vie → 2 insiemi → set 1 bit.
  • Etichetta: 12−1−2=912 - 1 - 2 = 9 bit.

Il bit di set è il bit 2 dell'indirizzo: i blocchi 100, 108, 110, 118... (indirizzo del blocco pari) vanno nell'insieme 0, i blocchi 104, 10C, 114... nell'insieme 1. Con soli due insiemi i conflitti sono frequenti: è quello che fa succedere un rimpiazzo di linea sporca all'ultimo accesso.

Evoluzione

# indirizzo accesso etichetta set parola esito linea contenuto della linea dopo l'accesso memoria / note
1 100 l 020 0 0 miss 0 08 00 07 02
2 108 l 021 0 0 miss 1 AE 13 A1 23 l'insieme 0 è pieno
3 10C s FF 021 1 0 miss 0 FF 42 90 75 * write allocate: carica A1 42 90 75, scrive FF; sporca
4 10D s AD 021 1 1 hit 0 FF AD 90 75 * resta sporca
5 110 l 022 0 0 miss 0 B9 16 00 00 insieme 0 pieno: esce la linea usata meno di recente (blocco 100, usato al passo 1), pulita: niente riscrittura
6 110 s 1B 022 0 0 hit 0 1B 16 00 00 * sporca (memoria ancora B9 16 00 00)
7 114 l 022 1 0 miss 1 0A 07 03 71 l'insieme 1 è ora pieno
8 075 l 00E 1 1 miss 0 00 00 00 00 insieme 1 pieno: esce la linea 0 (blocco 10C, ultimo uso al passo 4), sporca: va riscritta in memoria prima di caricare il nuovo blocco

Esito: 2 hit (accessi 4 e 6), 6 miss.

Il rimpiazzo dell'accesso 8. Nell'insieme 1 ci sono la linea 0 (blocco 10C, sporca, ultimo uso al passo 4) e la linea 1 (blocco 114, ultimo uso al passo 7). La più vecchia è la linea 0: poiché è sporca si riscrive in memoria l'intero blocco, non solo il byte:

M[10C..10F]=FF AD 90 75M[10C..10F] = \text{FF AD 90 75}

(in memoria c'era A1 42 90 75: cambiano due byte, M[10C] = FF e M[10D] = AD, ma il trasferimento è di 4 byte). Poi nella linea 0 si carica il blocco 074..077 (tutti 00, per ipotesi).

La linea 0 dell'insieme 0 (blocco 110) è ancora sporca a fine esercizio e non è stata riscritta: la sua modifica M[110] = 1B non è ancora visibile in memoria.

Stato finale

insieme linea 0 linea 1
0 etichetta 022: 1B 16 00 00 (sporca) etichetta 021: AE 13 A1 23
1 etichetta 00E: 00 00 00 00 etichetta 022: 0A 07 03 71

Memoria modificata: solo il blocco 10C..10F, che ora vale FF AD 90 75.

Verifica

python
def cache_wb(accessi, memoria, byte_cache, blocco, vie):
    insiemi = byte_cache // blocco // vie
    righe = {i: [] for i in range(insiemi)}           # linee dal meno al più recentemente usato
    esiti, riscritti = [], []
    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)
                if v["sporca"]:
                    vb = (v["et"] * insiemi + s) * blocco
                    for k in range(blocco):
                        memoria[vb + k] = v["dati"][k]
                    riscritti.append(hex(vb))
            linea = {"et": et, "dati": [memoria.get(base + k, 0) for k in range(blocco)], "sporca": False}
        righe[s].append(linea)
        if op == "s":
            linea["dati"][a % blocco] = val
            linea["sporca"] = True
        esiti.append("hit" if hit else "miss")
    return esiti, righe, riscritti

memoria = {}
for ind, byte4 in [(0x100, "08 00 07 02"), (0x104, "00 00 00 00"), (0x108, "AE 13 A1 23"),
                   (0x10C, "A1 42 90 75"), (0x110, "B9 16 00 00"), (0x114, "0A 07 03 71")]:
    for k, b in enumerate(byte4.split()):
        memoria[ind + k] = int(b, 16)

accessi = [(0b000100000000, "l", None), (0b000100001000, "l", None), (0b000100001100, "s", 0xFF),
           (0b000100001101, "s", 0xAD), (0b000100010000, "l", None), (0b000100010000, "s", 0x1B),
           (0b000100010100, "l", None), (0b000001110101, "l", None)]
esiti, righe, riscritti = cache_wb(accessi, memoria, 16, 4, 2)
print(esiti)                      # ['miss', 'miss', 'miss', 'hit', 'miss', 'hit', 'miss', 'miss']
print(riscritti)                  # ['0x10c']: l'unico blocco sporco rimpiazzato
print([format(memoria[a], "02X") for a in range(0x10C, 0x110)])    # ['FF', 'AD', '90', '75']
print(format(memoria[0x110], "02X"))                               # B9: la linea sporca del blocco 110 è ancora in cache

Errori comuni

  • Rimpiazzare con FIFO o scegliere la linea sbagliata: con LRU all'accesso 8 esce la linea 0 dell'insieme 1 (ultimo uso al passo 4), non la linea 1 (passo 7).
  • Non riscrivere la linea sporca in memoria quando viene rimpiazzata (o riscrivere un byte solo invece del blocco di 4).
  • Riscrivere in memoria anche la linea pulita uscita all'accesso 5: non serve.
  • Scrivere subito in memoria FF, AD e 1B (comportamento da write-through).
  • Contare 4 insiemi: con 4 linee e 2 vie gli insiemi sono 2.

Versione ripasso

Esempio di compitino intermedio a.a. 2010-11: cache da 16 B, blocchi da 4 B, 2 vie, LRU, write-back, write allocate, indirizzi di 12 bit. Teoria: 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 →.

Campi: parola 2 bit; linee 16/4=416/4 = 4; insiemi 4/2=24/2 = 2 → set 1 bit; etichetta 12−1−2=912 - 1 - 2 = 9 bit.

Esito (100 l, 108 l, 10C s FF, 10D s AD, 110 l, 110 s 1B, 114 l, 075 l): miss, miss, miss, hit, miss, hit, miss, miss → 2 hit e 6 miss.

  • Accesso 5: l'insieme 0 è pieno ed esce la linea usata meno di recente (blocco 100, pulita): nessuna scrittura in memoria.
  • Accesso 8: l'insieme 1 è pieno ed esce la linea 0 (blocco 10C, ultimo uso al passo 4), sporca: si riscrive in memoria l'intero blocco 10C..10F = FF AD 90 75, poi si carica il blocco 074..077 (assunto 00).
  • La linea del blocco 110 è sporca (1B 16 00 00) e non ancora in memoria.

Errori comuni: scelta della linea sbagliata (FIFO); linea sporca non riscritta o riscritta per un solo byte; linea pulita riscritta; scritture subito in memoria; 4 insiemi invece di 2.

Teoria collegata