Esercizi di riepilogo sulle gerarchie di memoria
Esercizio 1 (Allocazione dinamica della memoria)
Dato il seguente frammento di programma C:
double* make(double val, unsigned size) {
double* v = malloc(size*sizeof(double));
while (size--) v[size] = val;
return v;
}
double *x, *y, *z, *w;
x = make(3.14, 2);
y = make(7.2, 3);
z = make(10.0, 1);
w = make(10.0, 1);
free(x);
free(z);
x = make(6.28, 3);
Si assuma che l'allocatore parta da un heap inizialmente vuoto. L'allocatore cercherà di soddisfare ogni richiesta utilizzando lo spazio libero a partire dagli indirizzi più in basso, altrimenti espanderà l'heap del minimo indispensabile.
1) Come è partizionato l'heap dopo ogni malloc/free?
Assumiamo che = indichi 4 byte in uso mentre - 4 byte liberi allocati in precedenza.
Heap dopo le quattro
make:
|====|======|==|==|
x y z w
Heap dopo le due
free:
|----|======|--|==|
y w
Heap dopo la
make finale:
|----|======|--|==|======|
y w x
2) Si genera frammentazione durante l'esecuzione? Se sì, di che tipo?
Si osserva frammentazione esterna in corrispondenza dell'ultima
make: vi sono complessivamente 24 byte liberi, pari alla richiesta effettuata, ma non essendo contigui l'allocatore deve estendere l'heap (in particolare di 24 byte).
3) Heap size in uscita?
80 byte
Esercizio 1 - Variante
Dato il seguente frammento di programma C:
short* alloc(short val, unsigned size) {
short* v = malloc(size*sizeof(short));
while (size--) v[size] = val;
return v;
}
short *x, *y, *z, *w;
x = alloc(3, 2);
y = alloc(7, 3);
z = alloc(10, 1);
w = alloc(10, 1);
free(y);
free(w);
y = alloc(6, 2);
w = alloc(6, 2);
Si assuma che l'allocatore abbia le stesse caratteristiche descritte per l'esercizio originario.
1) Come è partizionato l'heap dopo ogni malloc/free?
Assumiamo che = indichi 1 byte in uso mentre - 1 byte liberi allocati in precedenza.
Heap dopo le quattro
alloc:
|====|======|==|==|
x y z w
Heap dopo le due
free:
|====|------|==|--|
x z
Heap dopo la successiva
alloc:
|====|====|--|==|--|
x y z
Heap dopo la
alloc finale:
|====|====|--|==|====|
x y z w
2) Si genera frammentazione durante l'esecuzione? Se sì, di che tipo?
Si osserva frammentazione esterna in corrispondenza dell'ultima
alloc: vi sono complessivamente 4 byte liberi, pari alla richiesta effettuata, ma non essendo contigui l'allocatore deve estendere l'heap (soltanto di 2 byte, dato che in coda vi sono già 2 byte liberi).
3) Heap size in uscita?
16 byte
Esercizio 2 (Calcolo cache hit e miss)
Dato il seguente frammento di programma C:
int somma(short* A, int n) {
int sum = 0, i, j;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
sum += A[i*n+j];
return sum;
}
Si assuma un sistema di calcolo con una cache L1 dati da 32 KB e una cache L2 da 256 KB, con linee di cache da 64 byte per entrambe. Inoltre, si assuma che le variabili siano mantenute nei registri della CPU, che l'indirizzo di A sia allineato a 64 byte, e che n=1000.
1) Determinare numero di accessi a memoria effettuati
Per ciascuna iterazione del ciclo interno viene effettuato un accesso a memoria all'array A. Trattandosi di un doppio ciclo, conteggiamo 1000000 (=1000x1000) iterazioni, che per il pattern
i*n+j accedono all'array in un ordine
sequenziale.
2) Determinare numero di hit e miss per la cache L1
Essendo A composto da elementi di tipo short, contiamo 32 elementi per linea di cache; inoltre l'allineamento a 64 byte dell'indirizzo di A fa sì che l'inizio dell'array delimiti anche l'inizio di una linea di cache. Osserviamo un cache miss ogni qual volta si accede al primo elemento di una linea: ovvero, trattandosi di un accesso sequenziale ordinato, avremo un miss ogni 32 elementi.
Il numero di miss L1 è quindi pari al numero di linee di cache da caricare, ossia 1000000/32=31250.
Per ottenere il numero di hit L1, sottraiamo dal numero totale di accessi a memoria il numero di miss L1: 1000000-31250=968750.
3) Determinare numero di hit e miss per la cache L2
Il numero di miss L2 è pari al numero di miss L1, perché ogni linea di cache L2 viene trasferita in L1 esattamente una volta: di conseguenza il numero di hit L2 è pari a 0. Infatti, la cache L1 non richiede mai che gli venga trasferita di nuovo una linea acceduta in precedenza.
4) Discutere il ruolo della dimensione delle cache e della dimensione delle linee
La dimensione delle cache è ininfluente, perché il programma opera su una sola linea per volta. La dimensione delle linee di cache influenza chiaramente il numero di miss L1: ad esempio, con linee da 128 byte tale numero si dimezzerebbe. Adottare invece linee di cache di dimensione più grande per la cache L2 farebbe ridurre il numero di miss L2 (e crescere il numero di hit L2): con una linea L2 k volte più grande di una linea L1, avremmo infatti un miss L2 ogni k miss L1.
Esercizio 2 - Variante
Dato il seguente frammento di programma C disponibile in due versioni:
double scalare1(double* A, double* B, int n) {
double sum = 0.0; int i;
for (i=0; i<n; i++)
sum += A[i]*B[i];
return sum;
}
typedef struct {
double x, y;
} coppia;
double scalare2(coppia* AB, int n) {
double sum = 0.0; int i;
for (i=0; i<n; i++)
sum += AB[i].x * AB[i].y;
return sum;
}
Si assuma un sistema di calcolo con una cache con spazio per almeno 2 linee da 64 byte. Inoltre, si assuma che le variabili siano mantenute nei registri della CPU, che gli indirizzi di A, B ed AB siano allineati a 64 byte, e che n=1000000. Infine, si consideri che la cache non ha vincoli di associatività, ossia la politica di rimpiazzamento non è soggetta a vincoli particolari quando si deve caricare un blocco in cache a spese di un altro già presente.
1) Determinare numero di accessi a memoria effettuati
Nella prima versione per ciascuna iterazione del ciclo vengono effettuati due accessi a memoria, uno all'array A e uno all'array B, leggendo un double da entrambi. Nella seconda versione per ciascuna iterazione abbiamo analogamente due accessi a memoria, leggendo due double dalla
struct coppia AB[i].
Conteggiamo quindi per entrambe le versioni 2000000 (=2x1000000) di accessi a memoria.
2) Determinare numero di hit e miss per la cache
Nella prima versione possiamo associare una linea di cache ad A ed una a B, con 8 elementi double per linea. In questo modo osserveremo 2 miss (1 per A e 1 per B) seguiti da 14 hit ogni 8 iterazioni del ciclo. Conteggiamo quindi 2*(1000000/8)=250000 miss e 14*(1000000/8)=175000 hit.
Nella seconda versione operiamo con una sola linea, in grado di contenere 4 elementi
coppia. Osserveremo pertanto 1 miss seguito da
7 hit ogni 4 iterazioni del ciclo. Bisogna infatti conteggiare separatamente gli accessi ai due elementi double contenuti all'interno della struct: il cache miss si verificherà quando accederemo al double
x in corrispondenza dell'inizio della linea di cache, mentre per il double
y nella stessa
struct coppia osserveremo un cache hit, seguito da 6 hit per gli elementi delle successive tre
struct coppia. In totale osserviamo quindi 1000000/4=250000 miss e 7*(1000000/4)=1750000 hit.
Le due versioni realizzano lo stesso numero di hit e di miss. Nei calcoli si è tenuto conto che grazie all'allineamento a 64 byte degli indirizzi degli array, ciascun array è perfettamente allineato con l'inizio di una linea di cache e non "inizia" nel mezzo di una di esse.
4) Discutere cosa accade avendo a disposizione 1 sola linea di cache
Per la seconda versione il numero di hit e miss è invariato, dato che essa lavora utilizzando una sola linea. Per la prima versione, invece, avremmo 2*1000000 miss, poiché ogni volta il prossimo dato da leggere si trova in una linea di cache diversa da quella caricata per l'ultima lettura eseguita. Si può pertanto concludere che la seconda versione esibisce una località spaziale migliore.
Esercizio 3 (Memoria virtuale)
1) Offset e numero di pagina
Sia dato uno spazio logico da 4 GB con pagine da 4 KB. Quanti bit servono per rappresentare l'offset all'interno di una pagina? Quanti bit occupa il numero di pagina in un indirizzo logico?
Pagine da 4 KB occupano 4*2^10 bytes = 2^12 bytes: sono quindi necessari 12 bit per indicizzare un singolo byte al suo interno.
Uno spazio logico da 4 GB copre 4*2^30 bytes = 2^32 bytes: esso richiede pertanto indirizzi da log2(2^32)=32 bit.
Il numero di bit occupato dal numero di pagina in un indirizzo logico è pari a 32 - numero bit offset = 32 - 12 = 20.
2) Tabella pagine e grandezza spazio virtuale
Sia data una tabella delle pagine grande 64 MB con celle a 32 bit, e siano in uso al sistema pagine da 8 KB. Quanto è grande lo spazio virtuale?
La tabella delle pagine è grande 64 MB = 64 * 2^20 bytes = 2^6 * 2^20 bytes = 2^26 bytes. Ciascuna cella da 32 bit (4 bytes) viene usata per indicizzare una pagina, per cui il numero di pagine è pari al rapporto tra la grandezza della tabella e la grandezza di una singola cella, ovvero 2^26 bytes / 4 bytes = 2^26 bytes / 2^2 bytes = 2^24.
La grandezza dello spazio virtuale è data dal prodotto tra il numero di pagine nella tabella e la grandezza di ciascuna pagina, ovvero 2^24 bytes * 8 KB = 2^24 * 2^3 * 2^10 bytes = 2^37 bytes = 128 * 2^30 bytes = 128 GB.
3) Layout di memoria di un programma
Dato il seguente programma C, quante pagine di memoria occupano le sezioni DATA, HEAP e STACK subito prima dell'istruzione return? Si assuma un sistema di calcolo con CPU a 32 bit e gestione della memoria virtuale con pagine da 4 KB.
short x[1024];
int main() {
int y[4096];
double* z = malloc(1000000);
return 0;
}
La sezione DATA ospiterà l'array di short x, che occupa 1024*sizeof(short) bytes = 2048 bytes. Essa occuperà una pagina di memoria virtuale, riempiendola per metà.
La sezione HEAP ospiterà un buffer di 1000000 bytes, che richiede 1000000 bytes/ 4 KB = 1000000/4096 = 245 pagine di memoria virtuale.
La sezione STACK ospiterà l'array di int y, che richiede 4096*sizeof(int) bytes = 16 KB, memorizzabili in esattamente 4 pagine di memoria virtuale. Se la variabile puntatore z non è memorizzata in un registro di CPU, sarà necessaria una ulteriore, quinta pagina di memoria virtuale per STACK.
Esercizio 4 (Ottimizzazione località)
Si ottimizzi la località del seguente codice C, in modo da sfruttare in modo più efficiente le cache di memoria:
int idx(int i, int j, int n) {
return i+j*n;
}
int sum(unsigned char* v, int n) {
int s = 0, i, j;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
s += v[idx(i,j,n)];
return s;
}
Soluzione: Analizzando gli accessi a memoria per un indice
i fissato, ci accorgiamo che vengono acceduti e sommati in sequenza elementi nell'array a distanza (stride)
n l'uno dall'altro. Se l'array
v rappresenta una matrice in forma linearizzata, stiamo sommando tutti i suoi elementi secondo un ordine column-major.
Per ottimizzare la località di questo codice, possiamo scambiare il ciclo interno con quello esterno, facendo così in modo che gli elementi dell'array vengano acceduti uno di seguito all'altro, ovvero con stride 1:
int sum(unsigned char* v, int n) {
int s = 0, i, j;
for (j=0; j<n; j++)
for (i=0; i<n; i++)
s += v[idx(i,j,n)];
return s;
}
Un ulteriore raffinamento del codice, che però non influenza la località degli accessi a memoria, è il seguente:
int sum(unsigned char* v, int n) {
int s = 0, i;
for (i=0; i<n*n; i++)
s += v[i];
return s;
}
Esercizio 4 - Variante
Si ottimizzi la località del seguente codice C, in modo da sfruttare in modo più efficiente le cache di memoria:
static int sum_stride(const int* in, int from, int to,
int* out, int stride) {
int i, sum = 0;
for (i=from; i<to; i+=stride) sum += in[i];
return sum;
}
void stat(const int* in, int n, int* out, int stride) {
int i;
for (i=0; i<stride; i++)
out[i] = sum_stride(in, i, n, out, stride);
}
Soluzione: Per ottimizzare il programma, studiamo il pattern di accessi a memoria realizzati per l'assegnamento di
out[i] nel metodo
stat, che avviene tramite invocazione di
sum_stride. In particolare, fissando il valore di
i per ciacuno dei valori compresi in {0, 1, 2, ..., stride-1} otteniamo:
out[0] = in[0] + in[stride] + in[