Memoria gerarchicaModifica

La memoria gerarchica è un’ottimizzazione hardware che prende i benefici della località spaziale e temporale e può essere usata su diversi livelli della gerarchia della memoria. Il paging beneficia ovviamente della localizzazione temporale e spaziale. Una cache è un semplice esempio di sfruttamento della località temporale, perché è un’area di memoria appositamente progettata, più veloce ma più piccola, generalmente utilizzata per mantenere i dati referenziati di recente e i dati vicini ai dati referenziati di recente, il che può portare a potenziali aumenti di prestazioni.

Gli elementi di dati in una cache non corrispondono necessariamente a elementi di dati che sono spazialmente vicini nella memoria principale; tuttavia, gli elementi di dati sono portati nella cache una linea di cache alla volta. Questo significa che la localizzazione spaziale è di nuovo importante: se un elemento è referenziato, anche alcuni elementi vicini saranno portati nella cache. Infine, la località temporale gioca un ruolo al livello più basso, poiché i risultati che sono referenziati molto vicini possono essere tenuti nei registri della macchina. Alcuni linguaggi di programmazione (come il C) permettono al programmatore di suggerire che certe variabili siano tenute nei registri.

La località dei dati è una caratteristica di riferimento alla memoria tipica dei programmi regolari (anche se esistono molti modelli di accesso alla memoria irregolari). Rende vantaggiosa la disposizione gerarchica della memoria. Nei computer, la memoria è divisa in una gerarchia per accelerare gli accessi ai dati. I livelli più bassi della gerarchia di memoria tendono ad essere più lenti, ma più grandi. Così, un programma otterrà maggiori prestazioni se utilizza la memoria mentre è in cache nei livelli superiori della gerarchia di memoria ed evita di portare altri dati nei livelli superiori della gerarchia che sposteranno i dati che saranno utilizzati a breve in futuro. Questo è un ideale, e a volte non può essere raggiunto.

Gerarchia di memoria tipica (i tempi di accesso e le dimensioni della cache sono approssimazioni di valori tipici utilizzati a partire dal 2013 a scopo di discussione; i valori reali e il numero effettivo di livelli nella gerarchia variano):

• Registri della CPU (8-256 registri) – accesso immediato, con la velocità del core più interno del processore
• L1 CPU caches (da 32 KiB a 512 KiB) – accesso veloce, con la velocità del bus di memoria più interno di proprietà esclusiva di ogni core
• L2 CPU caches (da 128 KiB a 24 MiB) – accesso leggermente più lento, con la velocità del bus di memoria condiviso tra due gemelli di core
• L3 CPU caches (da 2 MiB a 32 MiB) – accesso ancora più lento, con la velocità del bus di memoria condiviso tra ancora più core dello stesso processore
• Memoria fisica principale (RAM) (da 256 MiB a 64 GiB) – accesso lento, la cui velocità è limitata dalle distanze spaziali e dalle interfacce hardware generali tra il processore e i moduli di memoria sulla scheda madre
• Disco (memoria virtuale, file system) (da 1 GiB a 256 TiB) – molto lento, a causa del canale dati più stretto (in larghezza di bit), fisicamente molto più lungo tra la scheda principale del computer e i dispositivi disco, e a causa del protocollo software estraneo necessario in cima alla lenta interfaccia hardware
• Memoria remota (altri computer o cloud) (praticamente illimitata) – la velocità varia da molto lenta a estremamente lenta

Le macchine moderne tendono a leggere blocchi di memoria inferiore nel livello successivo della gerarchia di memoria. Se questo sposta la memoria usata, il sistema operativo cerca di prevedere a quale dato si accederà meno (o più tardi) e lo sposta in basso nella gerarchia della memoria. Gli algoritmi di predizione tendono ad essere semplici per ridurre la complessità dell’hardware, anche se stanno diventando un po’ più complicati.

Moltiplicazione di matriciModifica

Un esempio comune è la moltiplicazione di matrici:

for i in 0..n for j in 0..m for k in 0..p C = C + A * B;

Cambiando l’ordine di looping per j e k, lo speedup nelle grandi moltiplicazioni di matrici diventa drammatico, almeno per linguaggi che mettono elementi contigui di array nell’ultima dimensione. Questo non cambia il risultato matematico, ma migliora l’efficienza. In questo caso, “grande” significa, approssimativamente, più di 100.000 elementi in ogni matrice, o abbastanza memoria indirizzabile tale che le matrici non entreranno nelle cache L1 e L2.

for i in 0..n for k in 0..p for j in 0..m C = C + A * B;

La ragione di questa accelerazione è che nel primo caso, le letture di A sono nella cache (poiché l’indice k è l’ultima dimensione contigua), ma B no, quindi c’è una penalità di cache miss su B. C è irrilevante, perché può essere tirato fuori dal ciclo interno — la variabile del ciclo è k.

for i in 0..n for j in 0..m temp = C for k in 0..p temp = temp + A * B; C = temp

Nel secondo caso, le letture e le scritture di C sono entrambe nella cache, le letture di B sono nella cache, e la lettura di A può essere tirata fuori dal ciclo interno.

for i in 0..n for k in 0..p temp = A for j in 0..m C = C + temp * B;

Quindi, il secondo esempio non ha penalità di cache miss nel ciclo interno, mentre il primo esempio ha una penalità di cache.

Su un processore del 2014, il secondo caso è circa cinque volte più veloce del primo caso, se scritto in C e compilato con gcc -O3. (Un attento esame del codice disassemblato mostra che nel primo caso, GCC usa istruzioni SIMD e nel secondo caso no, ma la penalità della cache è molto peggiore del guadagno SIMD.)

La località temporale può anche essere migliorata nell’esempio precedente usando una tecnica chiamata blocco. La matrice più grande può essere divisa in sottomatrici di dimensioni uguali, in modo che i blocchi più piccoli possano essere referenziati (moltiplicati) più volte mentre sono in memoria.

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE) for (kk = 0; kk < SIZE; kk += BLOCK_SIZE) for (jj = 0; jj < SIZE; jj += BLOCK_SIZE) maxi = min(ii + BLOCK_SIZE, SIZE); for (i = ii; i < maxi; i++) maxk = min(kk + BLOCK_SIZE, SIZE); for (k = kk; k < maxk; k++) maxj = min(jj + BLOCK_SIZE, SIZE); for (j = jj; j < maxj; j++) C = C + A * B;

La località temporale della soluzione di cui sopra è fornita perché un blocco può essere usato più volte prima di andare avanti, in modo da essere spostato dentro e fuori dalla memoria meno spesso. La località spaziale è migliorata perché gli elementi con indirizzi di memoria consecutivi tendono ad essere tirati su insieme nella gerarchia di memoria.

.