Salta al contenuto
Note per Studenti Gerarchia di memoria e principio di località

Gerarchia di memoria e principio di località

In questa pagina 5
In questa pagina 4

Caratteristiche di una memoria

Caratteristica Possibilità
posizione registri (CPU), interna (cache, principale), esterna (dischi, nastri)
capacità in byte o in parole
unità di trasferimento parola (tra CPU e memoria), blocco (tra cache e memoria principale, tra memoria e disco)
metodo di accesso sequenziale (nastro), diretto (disco: salto alla zona e poi ricerca), casuale (RAM: tempo uguale per ogni indirizzo), associativo (per contenuto: cache)
prestazioni tempo di accesso, tempo di ciclo, velocità di trasferimento
tecnologia semiconduttore, magnetica, ottica
caratteristiche fisiche volatile / non volatile, riscrivibile / sola lettura

Il compromesso

Più una memoria è veloce, più costa per bit; più è grande, più è lenta. Soluzione: una gerarchia di livelli.

Livello Capacità tipica Tempo di accesso tipico
registri centinaia di byte < 1 ns
cache L1, L2, L3 da decine di KB a decine di MB 1–20 ns
memoria principale (DRAM) GB 50–100 ns
SSD centinaia di GB – TB 25–100 µs
disco magnetico TB 5–10 ms

Scendendo: costo per bit minore, capacità maggiore, tempo di accesso maggiore, frequenza di accesso da parte della CPU minore. Ogni livello contiene un sottoinsieme dei dati del livello sotto; i dati passano tra livelli adiacenti in blocchi.

Principio di località

La gerarchia funziona perché i programmi non accedono alla memoria a caso:

  • località temporale: un dato usato da poco sarà probabilmente riusato presto (variabili di un ciclo, istruzioni del corpo di un ciclo);
  • località spaziale: dopo un indirizzo è probabile che si usino quelli vicini (istruzioni in sequenza, elementi consecutivi di un array).

Esempio: in for (i = 0; i < n; i++) s += a[i]; le istruzioni del ciclo e s hanno località temporale, a[i] località spaziale. Portando in cache un blocco di più parole, il primo accesso a a[0] porta anche a[1], a[2], a[3].

Hit, miss e tempo medio di accesso

  • Hit: il dato è nel livello superiore; miss: non c'è e va prelevato dal livello inferiore.
  • Hit rate hh: frazione degli accessi che sono hit; miss rate 1−h1 - h.

Se un miss costa l'accesso alla cache più quello alla memoria:

Tmedio=h⋅T1+(1−h)(T1+T2)=T1+(1−h) T2T_{medio} = h \cdot T_1 + (1 - h)(T_1 + T_2) = T_1 + (1 - h)\,T_2

Esempio: cache 1 ns, memoria 100 ns, h=0,95h = 0{,}95 → Tmedio=1+0,05⋅100=6T_{medio} = 1 + 0{,}05 \cdot 100 = 6 ns. Con h=0,99h = 0{,}99 → 22 ns. Senza cache sarebbe 100 ns: anche un hit rate apparentemente "alto" fa molta differenza.

Se invece la richiesta va in parallelo a cache e memoria e il miss costa solo T2T_2: Tmedio=h T1+(1−h) T2T_{medio} = h\,T_1 + (1-h)\,T_2.

Con due livelli di cache: Tmedio=TL1+mL1 (TL2+mL2 Tmem)T_{medio} = T_{L1} + m_{L1}\,(T_{L2} + m_{L2}\,T_{mem}), con mm i miss rate locali.

La realizzazione concreta è in 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 → (tra CPU e memoria principale) e in 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 → (tra memoria principale e disco).

Errori tipici

  • Usare la formula sbagliata per TmedioT_{medio}: leggere bene nel testo se il tempo di miss include o no il tentativo in cache.
  • Pensare che la località valga per ogni programma: accessi casuali a grandi strutture dati (es. tabelle hash enormi) ne hanno poca.

Versione ripasso

Caratteristiche di una memoria

Posizione (registri, interna, esterna); capacità; unità di trasferimento (parola, blocco); accesso sequenziale (nastro), diretto (disco), casuale (RAM), associativo (cache); prestazioni (tempo di accesso, tempo di ciclo, velocità); volatile o no.

Gerarchia

Più veloce ⇒\Rightarrow più costosa per bit; più grande ⇒\Rightarrow più lenta. Livelli: registri (< 1 ns), cache L1-L3 (1-20 ns), DRAM (50-100 ns), SSD (25-100 µs), disco (5-10 ms). Scendendo: costo per bit minore, capacità e tempo maggiori, frequenza di accesso minore. I dati passano tra livelli adiacenti in blocchi.

Località

  • Temporale: un dato usato da poco sarà riusato presto (variabili e istruzioni di un ciclo).
  • Spaziale: dopo un indirizzo si usano i vicini (istruzioni in sequenza, array). Un blocco porta in cache anche a[1], a[2], a[3].

Hit, miss, tempo medio

Hit: dato nel livello superiore; miss: va prelevato da quello inferiore; hh = hit rate. Tmedio=h T1+(1−h)(T1+T2)=T1+(1−h) T2T_{medio} = h\,T_1 + (1-h)(T_1 + T_2) = T_1 + (1-h)\,T_2 Cache 1 ns, memoria 100 ns: h=0,95→1+0,05⋅100=6h = 0{,}95 \to 1 + 0{,}05 \cdot 100 = 6 ns; h=0,99→2h = 0{,}99 \to 2 ns; senza cache 100 ns. Se la richiesta va in parallelo: h T1+(1−h) T2h\,T_1 + (1-h)\,T_2. Due livelli: TL1+mL1(TL2+mL2Tmem)T_{L1} + m_{L1}(T_{L2} + m_{L2}T_{mem}).

Realizzazioni: 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 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 →.

Errori tipici: formula sbagliata di TmedioT_{medio} (leggere se il miss include il tentativo in cache); credere che la località valga sempre (accessi casuali a grandi tabelle ne hanno poca).

Lezioni in cui compare

Teoria collegata