Cache e memoria virtuale - mappatura e tabelle delle pagine

Le memorie hanno un compromesso capacità-velocità: più sono grandi, meno sono veloci. SRAM piccole e velocissime, DRAM più grandi e lente, dischi molto grandi e lenti (Memorie ROM e RAM - SRAM, DRAM e organizzazione dei chipUna memoria è un insieme di celle (word da più bit) con circuiteria di controllo. Classificazioni: sola lettura (ROM) o lettura/scrittura; ad accesso casuale (RAM), seriale (SAM) o ibrido (Flash); volatile (SRAM, DRAM) o non volatile. Una RAM $2^k\times n$ ha $k$ bit di indirizzo (indipendenti da $n$), $n$ bit dati, read/write e chip select. SRAM: cella bistabile (latch), veloce, senza refresh; DRAM: condensatore, più densa, con refresh. Organizzazione: decoder di riga e colonna (coincident selection), uscite tri-state, array di chip (più chip per più parole, più bit per più linee dati).Memorie ROM e RAM - SRAM, DRAM e organizzazione dei chip →). Per avere velocità e capacità si usa una gerarchia di memorie. Per i dettagli generali: 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à →, 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 →, 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 →.

Gerarchia e località

La gerarchia funziona perché la CPU:

• usa spesso gli stessi dati (località temporale);
• usa spesso dati vicini (località spaziale), per esempio operazioni su vettori, i cui elementi sono in locazioni contigue.

Formula (tempo medio di accesso alla memoria). Perché la gerarchia sia efficace la CPU deve trovare i dati necessari il più possibile nella cache: cache hit = il dato è nella cache; hit rate = percentuale di hit. Altrimenti si ha un cache miss (miss rate) e i dati vanno recuperati in blocco dalle altre memorie. Un modello standard del tempo medio di accesso è $t_{medio}=t_{hit}+\text{miss rate}\cdot t_{\text{penalità}}$: per $t_{hit}=1$ ns, miss rate $5\%$ e penalità $50$ ns si ha $1+0{,}05\cdot50=3{,}5$ ns.

Esempio. Con $t_{hit}=2$ ns, miss rate $10\%$ e penalità $40$ ns: $t_{medio}=2+0{,}10\cdot40=6$ ns.

Tipi di cache

La cache contiene una copia di alcune locazioni della memoria principale. Il problema è dove mettere un dato della memoria principale. Tre soluzioni.

Mappatura diretta

Definizione (cache a mappatura diretta). Gruppi di locazioni contigue della memoria principale vengono mappate direttamente in una locazione della cache; i bit più significativi dell'indirizzo identificano il gruppo trasferito (tag). Semplice, ma l'hit rate non è molto elevato.

Esempio. Cache da $8$ word ($8\times32$ bit), indirizzo di cache a $3$ bit; memoria principale da $256$ word ($1$ KB), indirizzo di word a $8$ bit. Gli ultimi tre bit dell'indirizzo di word sono l'indice della cache (la locazione), i $5$ bit più significativi sono il tag, memorizzato con il dato. All'accesso: si usa l'indice per scegliere la riga, si confronta il tag memorizzato con il tag dell'indirizzo: se uguali (e la riga è valida) hit, altrimenti miss: i dati sono trasferiti dalla memoria alla cache sostituendo la riga.

Esempio di accessi (indirizzi di word: $19,20,19,51,19,51,83,19$; indice $=a\bmod8$, tag $=\lfloor a/8\rfloor$):

Un solo hit su $8$. Con la mappatura diretta, se il programma accede continuamente a due locazioni con gli stessi 3 bit di indirizzo meno significativi (19, 51, 83 hanno tutti indice 3) si verificano miss continui (conflict miss).

Completamente associativa

Definizione (cache completamente associativa). L'associazione tra locazioni della memoria principale e della cache è arbitraria: qualunque dato può stare in qualunque riga. Il tag è l'indirizzo completo. Prestazioni ottime ma complessità alta: confrontare in sequenza tutti i tag non è fattibile, quindi si usa una memoria associativa che esegue il confronto in parallelo: la scrittura è convenzionale, la lettura è in parallelo; il segnale di match di ciascuna riga pilota la sua word line e l'OR di tutti i match è il segnale di hit/miss.

Esempio. Con indirizzi di word a $8$ bit il tag è l'indirizzo completo ($8$ bit) e viene confrontato in parallelo con quello di tutte le righe.

Parzialmente associativa a $k$ vie

Definizione (cache associativa a $k$ vie). È una via di mezzo. Per ogni valore dei bit di ordine minore (indice dell'insieme) c'è un numero limitato $k$ di locazioni disponibili (per esempio $k=2$): la logica di match si semplifica molto. Una word può trovarsi solo in $k$ locazioni della cache (le $k$ vie dell'unico insieme che le corrisponde); buffer three-state collegano l'uscita appropriata al bus. Quindi in una cache a $2$ vie un dato proveniente dalla memoria centrale può essere immagazzinato in 2 locazioni distinte.

Esempio. Cache da $8$ righe a $2$ vie: $8/2=4$ insiemi, quindi insieme $=a\bmod4$; l'indirizzo $19$ va nell'insieme $3$ con tag $\lfloor19/4\rfloor=4$.

Stessa sequenza di accessi su una cache a $2$ vie (8 righe = 4 insiemi da 2; insieme $=a\bmod4$, tag $=\lfloor a/4\rfloor$, sostituzione LRU = si sostituisce la meno recente):

3 hit su 8: l'associatività elimina i conflitti tra 19 e 51.

Località spaziale e blocchi. Per sfruttare la località spaziale si portano in cache più locazioni contigue per volta (nell'esempio di una cache a 2 vie con blocchi da 4 word); le memorie dati della cache vengono replicate per i 4 word. Una cache da $256$ K ha un diagramma a blocchi con memorie tag, memorie dati, comparatori e MUX di uscita.

Memoria virtuale

Oltre che veloce, la memoria disponibile deve essere grande. Il concetto di memoria virtuale permette di mostrare a tutti i programmi l'intera dimensione della memoria principale e del disco: i programmi possono usare gli stessi indirizzi senza interferire. Un hardware dedicato esegue la mappatura tra memoria virtuale e fisica, garantendo la separazione dei processi. La gestione è facilitata dalla suddivisione della memoria in pagine.

Tabella delle pagine

Definizione (tabella delle pagine). La mappatura tra pagine virtuali e pagine fisiche è nella tabella delle pagine. Ogni riga ha, oltre al numero di pagina fisica (frame):

• valid: se $0$, la pagina non corrisponde a codice o dati effettivi in memoria;
• dirty: se $1$, c'è stata almeno una scrittura (la pagina andrà copiata su disco prima di essere sostituita);
• used: serve a gestire la sostituzione delle pagine.

Esempio di traduzione. Pagine da $4$ KB: l'indirizzo virtuale a 16 bit è diviso in numero di pagina (4 bit alti) e offset (12 bit); la traduzione sostituisce il numero di pagina con il frame, lasciando invariato l'offset. Tabella: pagina 0 $\to$ frame 2 (valid); pagina 1: non valida; pagina 2 $\to$ frame 7 (valid, dirty); pagina 3 $\to$ frame 5 (valid).

Tabella a due livelli, TLB e page fault

Con una struttura a due livelli (directory e tabella delle pagine) per recuperare un dato servono tre accessi alla memoria: la directory entry, la page table entry e infine l'operando o l'istruzione: troppo lento. Si introduce il Translation Lookaside Buffer (TLB), simile a una cache per la mappatura tra indirizzi virtuali e fisici: contiene le traduzioni delle pagine usate più di recente e, se la pagina è lì, la traduzione è immediata.

Definizione (page fault). Il page fault si ha quando la pagina richiesta non è in memoria (bit valid a 0): deve essere recuperata dal disco, con un tempo enormemente superiore a quello di una DRAM, per cui il sistema operativo gestisce il fault e sostituisce una pagina (se dirty la salva prima).

Esempio. Con la tabella dell'esempio, l'accesso a un indirizzo della pagina $1$ (valid $=0$) provoca un page fault: la pagina va caricata dal disco.

Errori comuni

• Dire che in una cache a mappatura diretta un dato può stare in più locazioni: sta in una sola.
• Confondere il tag con l'indice: l'indice è nei bit meno significativi (sceglie la riga), il tag nei più significativi (si confronta).
• Considerare un cache miss e un page fault equivalenti: il miss è risolto dalla memoria principale, il page fault dal disco.
• Dimenticare che l'offset non cambia nella traduzione virtuale $\to$ fisica.
• Credere che una cache veloce come la memoria principale sia utile: non ha senso, serve solo se è più veloce (a parità di prestazioni è inutile).