Esercizio 20campi dell'indirizzo e capacità di una cache

Metodo

Per una cache con capacità $C$, linee da $K$ byte e $n$ vie, con memoria indirizzata al byte:

$$\text{linee} = \frac{C}{K}, \qquad \text{insiemi} = \frac{\text{linee}}{n}, \qquad \text{parola} = \log_2 K, \quad \text{set} = \log_2(\text{insiemi}), \quad \text{etichetta} = \text{bit dell'indirizzo} - \text{set} - \text{parola}.$$

I bit dell'indirizzo sono $\log_2(\text{dimensione della memoria})$. La dimensione del blocco è la dimensione della linea. 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 → e gli esempi in Esercizio 12 · campi dell'indirizzo per cache a due vie.

A. Memoria da 256 MB in 524 288 blocchi

• Indirizzo: $256\ \text{MB} = 2^{28}$ → 28 bit.
• Blocco: $2^{28} / 524\,288 = 2^{28} / 2^{19} = 2^9 = 512$ B → parola 9 bit.
• Linee: $16\ \text{MB} / 512\ \text{B} = 2^{24} / 2^9 = 2^{15} = 32\,768$.
• Insiemi: $32\,768 / 4 = 2^{13} = 8192$ → set 13 bit.
• Etichetta: $28 - 13 - 9 = 6$ bit.

Risposta d: etichetta 6, set 13, parola 9.

B. Due indirizzi nella stessa linea (associazione diretta)

Con blocco da $B$ byte la linea è nei bit tra il campo parola e l'etichetta. La cache ha $2^{18}$ byte: la linea è identificata dai bit $[\log_2 B,\ 17]$ dell'indirizzo (gli altri bit alti sono l'etichetta). I due indirizzi, in binario su 28 bit:

533ACFD = 0101 0011 0011 1010 1100 1111 1101
90FAF1F = 1001 0000 1111 1010 1111 0001 1111

I bit $17 \ldots 10$ (otto bit) sono uguali nei due indirizzi: 11101011 (EB in esadecimale). Con blocchi da 1 KB ($B = 2^{10}$) il campo linea è proprio quello (8 bit: $2^{18}/2^{10} = 256$ linee), perciò i due indirizzi vanno nella stessa linea 235, con etichette diverse (0x14C e 0x243): si scacciano a vicenda. Con blocchi più piccoli il campo linea comprende anche i bit 9…$\log_2 B$, che nei due indirizzi sono diversi: linee diverse (128 B: linee 1881 e 1886; 512 B: 470 e 471; 256 B: 940 e 943).

Risposta a (1 KB).

C. Cache da 8 MB a 4 vie con linee da 2 KB

• Blocco = linea = 2 KB = $2^{11}$ → parola 11 bit.
• Memoria: $2^{20}$ blocchi $\times 2^{11}$ B $= 2^{31}$ B → 31 bit di indirizzo.
• Linee: $8\ \text{MB} / 2\ \text{KB} = 2^{23} / 2^{11} = 2^{12} = 4096$; insiemi: $4096 / 4 = 1024$ → set 10 bit.
• Etichetta: $31 - 10 - 11 = 10$ bit.

Risposta a: etichetta 10, set 10, parola 11.

D. Memoria massima gestita da una cache a 256 vie

• Linee: $256\ \text{MB} / 8\ \text{KB} = 2^{28} / 2^{13} = 2^{15} = 32\,768$.
• Insiemi: $32\,768 / 256 = 128$ → set 7 bit; parola: $8\ \text{KB} = 2^{13}$ → 13 bit.
• Con etichetta di 12 bit l'indirizzo ha $12 + 7 + 13 = 32$ bit: memoria massima $2^{32}$ B $= 4096$ MB.

Risposta b.

Verifica

from math import log2

def campi(cache, linea, vie, bit_indirizzo):
    linee = cache // linea
    insiemi = linee // vie
    parola = int(log2(linea))
    set_ = int(log2(insiemi))
    return bit_indirizzo - set_ - parola, set_, parola        # etichetta, set, parola

MB, KB = 2 ** 20, 2 ** 10
blocco = 256 * MB // 524288                                   # A
print(blocco, campi(16 * MB, blocco, 4, 28))                  # 512 (6, 13, 9)
print(campi(8 * MB, 2 * KB, 4, 31))                           # C: (10, 10, 11)

linee = 256 * MB // (8 * KB)                                  # D
insiemi = linee // 256
print(12 + int(log2(insiemi)) + 13, "bit ->", 2 ** (12 + int(log2(insiemi)) + 13) // MB, "MB")   # 32 bit -> 4096 MB

a, b = 0x533ACFD, 0x90FAF1F                                   # B
for B in (1024, 128, 512, 256):
    linee = 256 * KB // B
    w = int(log2(B))
    print(B, (a >> w) % linee, (b >> w) % linee)              # 1024: 235 235 (stessa linea); gli altri: linee diverse

Errori comuni

• Dividere la capacità della cache per le vie prima di dividere per la dimensione della linea (o viceversa): si ottengono insiemi dividendo il numero di linee per le vie.
• Usare 32 bit di indirizzo senza ricavarli dalla dimensione della memoria.
• Confondere il blocco di memoria (la memoria è divisa in blocchi) con la linea di cache (che contiene un blocco): hanno la stessa dimensione.
• Nell'associazione diretta cercare la stessa etichetta: due indirizzi nella stessa linea hanno etichette diverse (altrimenti sarebbero nello stesso blocco).