Memoria cache

La cache è una memoria piccola e veloce (SRAM) tra CPU e memoria principale. Contiene copie dei blocchi usati di recente e sfrutta la località (vedi Gerarchia di memoria e principio di localitàCaratteristiche delle memorie (posizione, capacità, unità di trasferimento, metodo di accesso, prestazioni, volatilità); compromesso costo-capacità-velocità e gerarchia a livelli; località temporale e spaziale con esempi; hit, miss e tempo medio di accesso con calcolo svolto.Gerarchia di memoria e principio di località →). È gestita interamente dall'hardware: il programma non la vede.

Blocchi, linee, etichette

• La memoria principale è divisa in blocchi di $K$ parole contigue; il blocco è l'unità di trasferimento tra memoria e cache.
• La cache ha $m$ linee; ogni linea contiene un blocco, più un'etichetta (tag) che dice quale blocco è, un bit di validità e, con write-back, un bit sporco.
• Il numero di linee è molto minore del numero di blocchi: più blocchi competono per le stesse linee.

Se $K = 2^w$, gli ultimi $w$ bit dell'indirizzo indicano la parola dentro il blocco (campo parola), gli altri bit sono l'indirizzo del blocco. Il primo indirizzo di un blocco ha il campo parola a zero.

Nei conti, "parola" è l'unità indirizzabile: se la memoria è indirizzata al byte e la parola è un byte, il campo parola conta i byte nel blocco.

Associazione diretta

Ogni blocco può andare in una sola linea:

$$\text{linea} = (\text{indirizzo del blocco}) \bmod m$$

Indirizzo: | tag | linea ($\log_2 m$ bit) | parola ($w$ bit) |

Funzionamento: il campo linea seleziona la linea; se è vuota → miss; se è piena si confronta il tag della linea con quello dell'indirizzo: uguali → hit, diversi → miss e il blocco presente viene sostituito. Il campo parola non serve a decidere hit o miss: serve solo a scegliere la parola nel blocco da mandare alla CPU.

Esempio: memoria di 16 MB indirizzata al byte → indirizzi di 24 bit; cache di 16 K linee ($2^{14}$); blocchi di 4 byte ($w = 2$). Campi: parola 2, linea 14, tag $24 - 14 - 2 = 8$. Svolto in Esercizio 7 · campi dell'indirizzo in una cache ad associazione diretta.

Pro: semplicissima, un solo confronto. Contro: due blocchi usati alternativamente che vanno nella stessa linea si scacciano a vicenda (thrashing) anche se il resto della cache è vuoto.

Associazione completa

Un blocco può andare in qualsiasi linea. Indirizzo: | tag | parola |. Si confronta il tag con tutte le linee in parallelo (memoria associativa): costosa, usata solo per cache piccolissime (es. il TLB, vedi Memoria virtualeIndirizzi virtuali e fisici, pagine e frame; traduzione con la tabella delle pagine e calcolo dei campi; page fault e sostituzione delle pagine; TLB e tempo di accesso effettivo; protezione e condivisione; confronto con la cache.Memoria virtuale →).

Associazione a insiemi ($n$ vie)

Le $m$ linee sono divise in $v = m/n$ insiemi (set) di $n$ linee. Un blocco va in un insieme fisso, in una linea qualsiasi dell'insieme:

$$\text{insieme} = (\text{indirizzo del blocco}) \bmod v$$

Indirizzo: | tag | insieme ($\log_2 v$ bit) | parola |

"A due vie" significa due linee per insieme, non due insiemi. Con $n = 1$ è l'associazione diretta, con $n = m$ quella completa.

Esempio: indirizzi di 12 bit, parola di 1 byte, cache di 16 byte, blocchi di 2 byte, 2 vie → linee $16/2 = 8$, insiemi $8/2 = 4$ → parola 1 bit, insieme 2 bit, tag $12 - 2 - 1 = 9$ bit. Altri casi in Esercizio 12 · campi dell'indirizzo per cache a due vie.

Rimpiazzo

Con associazione a insiemi o completa, quando l'insieme è pieno si sceglie la linea da liberare:

• LRU (least recently used): quella usata meno di recente (con 2 vie basta un bit per insieme);
• FIFO: quella caricata per prima, indipendentemente dagli accessi successivi;
• LFU: quella usata meno spesso;
• casuale: sorprendentemente poco peggiore di LRU.

Se ci sono linee libere nell'insieme se ne usa una (negli esercizi si dichiara la convenzione, per esempio "la linea libera di indice minore").

Scrittura

Su miss in scrittura:

• write-allocate: si porta prima il blocco in cache, poi si scrive (tipico con write-back);
• no-write-allocate: si scrive solo in memoria (tipico con write-through).

Negli esercizi completi si traccia per ogni accesso: indirizzo, campi, hit/miss, linea e insieme coinvolti, contenuto della linea (tag, dati, bit sporco) e modifiche alla memoria.

Dimensione del blocco

Blocchi più grandi sfruttano meglio la località spaziale, ma a parità di capacità riducono il numero di linee e aumentano i conflitti; ogni miss costa anche più tempo di trasferimento. Esiste un valore ottimo intermedio: vedi Esercizio 10 · dimensione del blocco più conveniente, dove con una cache di 8 parole il blocco di 2 parole dà meno miss di quelli da 1 e da 4.

Cache multilivello e separate

• L1 piccola e velocissima, spesso separata in cache istruzioni e cache dati (così prelievo e accesso ai dati non si contendono la cache, utile nella PipelineIdea della catena di montaggio; pipeline a 5 stadi IF, ID, EX, MEM, WB; tempo di ciclo, tempo per n istruzioni in una pipeline a k stadi e speedup con esempi svolti; registri di pipeline; scrittura e lettura dei registri nello stesso ciclo; limiti (stadi sbilanciati, hazard).Pipeline →); L2 e L3 più grandi e unificate, L3 condivisa tra i core.
• Cause dei miss: obbligatori (primo accesso a un blocco), di capacità (la cache è troppo piccola per i dati in uso), di conflitto (troppi blocchi nella stessa linea o insieme; spariscono con l'associazione completa).

Esercizi: Esercizio 8 · hit e miss in cache ad associazione diretta, Esercizio 9 · cache con blocchi di due parole, Esercizio 11 · cache a due vie con rimpiazzo FIFO.

Ridurre i miss

Nessun rimedio è gratis: ognuno sposta il problema (blocchi più grandi riducono i miss obbligatori ma, a parità di capacità, riducono il numero di linee).

Quesiti tipici sui campi dell'indirizzo

Con capacità $C$, linea (= blocco) di $K$ byte, $n$ vie e memoria indirizzata al byte:

$$\text{linee} = \frac{C}{K}, \quad \text{insiemi} = \frac{\text{linee}}{n}, \quad \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$ della memoria; se è nota l'etichetta si ricava la memoria massima gestita: $2^{\text{etichetta} + \text{set} + \text{parola}}$ byte.
• Due indirizzi finiscono nella stessa linea (mappatura diretta) se hanno uguali i bit del campo linea e diversa l'etichetta; se hanno anche la stessa etichetta sono nello stesso blocco.
• Con più processori (o DMA) che scrivono lo stesso dato, la write-back crea il problema della coerenza: la memoria può avere un valore vecchio mentre una cache ha quello nuovo; si risolve invalidando o aggiornando le altre copie (vedi Processori superscalari e multicoreParallelismo a livello di istruzione: processori superscalari, esecuzione fuori ordine, ridenominazione dei registri contro WAR e WAW, speculazione; limiti dell'ILP e della frequenza (consumo); multithreading, multicore e coerenza delle cache; acceleratori.Processori superscalari e multicore →).

Svolti: Esercizio 20 · campi dell'indirizzo e capacità di una cache, Esercizio 21 · cache a due vie FIFO con write-through, Esercizio 22 · cache a due vie LRU con write-back, Esercizio 23 · cache con rimpiazzo di una linea sporca.

Errori tipici

• Confondere la dimensione della parola con l'ampiezza del campo parola: il campo parola dipende dal numero di parole nel blocco.
• Confondere il numero di vie con il numero di insiemi.
• Usare il campo parola per decidere hit o miss.
• Con write-back, dimenticare di riscrivere in memoria il blocco sporco rimpiazzato (e scriverlo tutto, non solo la parola modificata).