Additions:
**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.
Deletions:
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.
Additions:
**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:
Deletions:
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:
Additions:
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[2*stride] + ...
out[1] = in[1] + in[stride+1] + in[2*stride+1] + ...
out[2] = in[2] + in[stride+2] + in[2*stride+2] + ...
...
out[stride-1] = in[stride-1] + in[stride+(stride-1)] + in[2*stride+(stride-1)] + ...
Le somme avvengono sommando di volta in volta uno spiazzamento pari a ##stride## all'indice iniziale determinato da #i#, per cui possiamo rappresentarle in modo compatto facendo ricorso all'operatore modulo ##%##. Ottimizziamo pertanto il loop in ##stat## come segue, senza invocare più ##sum_stride##:
for (i=0; i
out[i%stride] += in[i];
Deletions:
Si faccia riferimento alle [[SolEserc06AA1617 soluzioni]] pubblicate per l'esercitazione di fine corso.
Additions:
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.
Deletions:
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)=25000 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=25000 miss e 7*(1000000/4)=175000 hit.
Additions:
""|----|======|--|==|======|
Deletions:
""|----|======|--|==|===|
Additions:
16 byte
Deletions:
16 bytes
Additions:
80 byte
Deletions:
80 bytes
No differences.
Additions:
==Esercizio 4 (Ottimizzazione località)==
==Esercizio 4 - Variante==
Deletions:
==Esercizio 3 (Ottimizzazione località)==
==Esercizio 3 - Variante==
Additions:
==Esercizio 3 (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 (j=0; j
s += v[idx(i,j,n)];
return s;
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
for (i=0; 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
s += v[i];
return s;
==Esercizio 3 - 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
void stat(const int* in, int n, int* out, int stride) {
int i;
for (i=0; i
out[i] = sum_stride(in, i, n, out, stride);
Si faccia riferimento alle [[SolEserc06AA1617 soluzioni]] pubblicate per l'esercitazione di fine corso.
No differences.
Additions:
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.
Deletions:
La sezione STACK ospiterà l'array di int y, che richiede 4096*sizeof(int) bytes = 16 KB, che possono essere memorizzati 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.
Additions:
**4) Discutere cosa accade avendo a disposizione 1 sola linea di cache**
==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, che possono essere memorizzati 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.
Deletions:
**4) Discutere cosa accadrebbe avendo a disposizione 1 sola linea di cache**
Additions:
Dato il seguente frammento di programma C disponibile in due versioni:
Deletions:
Dato il seguente frammento di programma C in due versioni:
Additions:
**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**
**3) Determinare numero di hit e miss per la cache L2**
**4) Discutere il ruolo della dimensione delle cache e della dimensione delle linee**
==Esercizio 2 - Variante==
Dato il seguente frammento di programma C in due versioni:
double scalare1(double* A, double* B, int n) {
double sum = 0.0; int i;
sum += A[i]*B[i];
typedef struct {
double x, y;
} coppia;
double scalare2(coppia* AB, int n) {
double sum = 0.0; int i;
sum += AB[i].x * AB[i].y;
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)=25000 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=25000 miss e 7*(1000000/4)=175000 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 accadrebbe 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.
Deletions:
**1) Determinare numero di hit e miss per la cache L1**
In primis determiniamo il 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 L2**
**3) Discutere il ruolo della dimensione delle cache e della dimensione delle linee**
Additions:
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.
Deletions:
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 permetterebbe di ridurre il numero di miss L2: con una linea L2 k volte più grande di una linea L1, avremmo infatti un miss L2 ogni k miss L1.
Additions:
In primis determiniamo il 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//.
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.
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.
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 permetterebbe di ridurre il numero di miss L2: con una linea L2 k volte più grande di una linea L1, avremmo infatti un miss L2 ogni k miss L1.
Deletions:
In primis determiniamo il 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 seguendo il pattern ##i*n+j## accedono all'array con un ordinamento //sequenziale//.
Essendo A composto da elementi di tipo short, abbiamo 32 elementi per linea di cache, ed osserveremo un cache miss ogni qual volta si accede al primo elemento di una linea. Ovvero, trattandosi di un accesso sequenziale ordinati, avremo un miss ogni 32 elementi. Il numero complessivo 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: 1000000-31250=968750.
Il numero di miss L2 è pari al numero di miss L1, perché ogni linea di cache viene caricata 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 manipolata in precedenza.
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 L2 permetterebbe di ridurre il numero di miss L2: con una linea L2 k volte più grande di una linea L1, avremmo infatti un miss L2 ogni k miss L1.
Additions:
==Esercizio 2 (Calcolo cache hit e miss)==
int somma(short* A, int n) {
int sum = 0, i, j;
for (i=0; i
for (j=0; 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 hit e miss per la cache L1**
In primis determiniamo il 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 seguendo il pattern ##i*n+j## accedono all'array con un ordinamento //sequenziale//.
Essendo A composto da elementi di tipo short, abbiamo 32 elementi per linea di cache, ed osserveremo un cache miss ogni qual volta si accede al primo elemento di una linea. Ovvero, trattandosi di un accesso sequenziale ordinati, avremo un miss ogni 32 elementi. Il numero complessivo 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: 1000000-31250=968750.
**2) 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 viene caricata 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 manipolata in precedenza.
**3) 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 L2 permetterebbe di ridurre il numero di miss L2: con una linea L2 k volte più grande di una linea L1, avremmo infatti un miss L2 ogni k miss L1.