Esercitazione 6 - 16 dicembre 2016 (120 min)
Esercizio 1 - ottimizzazione località
Si ottimizzi la località del seguente codice, in modo da sfruttare in modo più efficiente le cache di memoria:
// calcola le somme degli elementi di "in" a distanza "stride"
// fra loro a partire da "from" fino a "to"
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;
}
// calcola in "out[i]" le somme degli elementi di "in" a distanza
// "stride" fra loro a partire da "i", per ogni i in [0,stride-1]
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);
}
Si raccomanda di realizzare la versione ottimizzata all'interno di un file
stat-opt.c e di confrontare le prestazioni delle due versioni (base e ottimizzata) compilandole insieme con il seguente main di prova:
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#define N 100000000
#define S 100
void stat
(const int* in,
int n,
int* out,
int stride
);
void init
(int* v,
int n,
int s
) {
int i;
for (i=
0; i<n; i++
) v
[i
] = i % s;
}
void print_array
(int* v,
int n
) {
int i;
for (i=
0; i<n; i++
) {
printf("%10d ", v
[i
]);
if ((i
+1)%
10 ==
0) printf("\n");
}
}
int main
() {
int *in = malloc
(N*
sizeof(int));
int *out = malloc
(S*
sizeof(int));
assert
(in !=
NULL && out !=
NULL);
init
(in, N, S
);
stat
(in, N, out, S
);
printf("Risultato: \n");
print_array
(out, S
);
free
(in
);
free
(out
);
return 0;
}
Esercizio 2 - unrolled linked list
Lo scopo dell'esercizio è implementare una struttura dati chiamata
unrolled linked list. Questa struttura dati è una via di mezzo tra un array ed una lista collegata.
Si ricorda che in un array:
- tutti gli elementi sono memorizzati consecutivamente in un unico blocco di memoria;
- l'accesso al k-esimo elemento è un operazione immediata e richiede tempo costante.
Al contrario, in una lista collegata:
- ogni elemento è memorizzato in un blocco di memoria distinto (nodo della lista);
- ogni nodo ha un puntatore al nodo successivo;
- l'accesso al k-esimo elemento richiede l'attraversamento di k puntatori (partendo dal nodo in testa alla lista)
L'unrolled linked list è una variante della linked list in cui i nodi della lista possono mantenere
r>=1 elementi. In particolare, ogni nodo memorizza
- un puntatore al nodo successivo della lista;
- il numero di elementi attualmente memorizzati nel nodo;
- un array grande a sufficienza per memorizzare r elementi
Si noti che
r è un intero positivo costante (ad esempio:
r = 64).
Parte I: definizione tipi + inserimento in coda di un elemento
La prima parte dell'esercizio richiede di:
- definire nel file header
unrolled_linked_list.h (vedere lo scheletro completo proposto più in basso) un tipo C, chiamato
unrolled_list_t
- definire nel file header
unrolled_linked_list.h un tipo C, chiamato
node_t, che definisce la struttura di un nodo. Assumiamo che gli elementi memorizzati nella lista siano di tipo
int
- implementare la funzione:
unrolled_list_t * new_unrolled_list();
che restituisce una nuova lista unrolled (inizialmente senza alcun nodo).
- implementare la funzione:
void append(unrolled_list_t * list, int x);
che inserisce in coda l'elemento
x nella lista
list.
- implementare la funzione:
int list_size(unrolled_list_t * list);
che ritorna il numero di elementi presenti nella lista
list.
L'inserimento in coda (append) di un elemento in una lista unrolled segue la seguente strategia:
- (CASO A) se l'ultimo nodo della lista non è pieno (ospita meno di r elementi):
- si inserisce l'elemento nel nodo;
- si aggiorna il numero elementi memorizzati nel nodo
- (CASO B) se l'ultimo nodo della lista è pieno (ospita esattamente r elementi):
- si alloca un nuovo nodo;
- si collega l'ultimo nodo della lista al nodo appena creato;
- si inizializza il puntatore al nodo successivo nel nodo appena creato.
- si eseguono gli step del CASO A
- (CASO C) se la lista non contiene alcun nodo:
- si alloca un nuovo nodo;
- si collega il nodo alla lista;
- si inizializza il puntatore al nodo successivo nel nodo appena creato;
- si eseguono gli step del CASO A
Il file header
unrolled_linked_list.h deve avere il seguente scheletro:
#ifndef UNROLLED_LINKED_LIST_H
#define UNROLLED_LINKED_LIST_H
#define MAX_N_ELEM_NODE 8 // r = 8 per semplicita'
typedef struct node_t {
// ToDo
} node_t;
typedef struct unrolled_list_t {
// ToDo
} unrolled_list_t;
unrolled_list_t * new_unrolled_list(); // Parte I
void append_elem(unrolled_list_t * list, int x); // Parte I
int list_size(unrolled_list_t * list) // Parte I
int get_elem(unrolled_list_t * list, int k); // Parte III
void remove_elem(unrolled_list_t * list, int k); // Parte IV
void delete_unrolled_list(unrolled_list_t * list); // Parte V
#endif
Si proceda a testare la propria implementazione utilizzando il seguente
main di prova:
#include <stdio.h>
#include "unrolled_linked_list.h"
int main
() {
unrolled_list_t * list = new_unrolled_list
();
int k;
for (k =
0; k <
20; k++
)
append_elem
(list, k
);
printf("Numero di elementi nella lista: %d (corretto: 20)\n", list_size
(list
));
return 0;
}
Parte II: accesso k-esimo elemento
La seconda parte dell'esercizio richiede l'implementazione della funzione:
int get_elem(unrolled_list_t * list, int k);
Tale funzione ritorna il
k-esimo l'elemento contenuto nella lista
list. Se l'indice non è valido, viene terminato il programma stampando un messaggio di errore.
Si proceda a testare la propria implementazione utilizzando il seguente
main di prova:
#include <stdio.h>
#include "unrolled_linked_list.h"
int main
() {
unrolled_list_t * list = new_unrolled_list
();
int k;
for (k =
0; k <
20; k++
)
append_elem
(list, k
);
printf("Numero di elementi nella lista: %d (corretto: 20)\n", list_size
(list
));
for (k =
0; k <
20; k++
)
printf("Elemento [%d]: %d\n", k, get_elem
(list, k
));
return 0;
}
Parte III: benchmarking
Scaricando il seguente
archivio è possibile effettuare un primo confronto prestazionale tra la propra implementazione di lista unrolled e una linked list tradizionale, concentrandosi in particolare sulle due operazioni appena implementate.
Una volta decompresso l'archivio, copiare all'interno della cartella
bench/ il file C ed il file header utilizzati per implementare la lista unrolled. Procedere dunque alla compilazione via
Makefile con il comando
make e confrontare i tempi riportati durante l'esecuzione dei due programmi generati (ovvero
bench-linked e
bench-unrolled). Quali conclusioni preliminari si possono trarre?
Parte IV: rimozione del k-esimo elemento
La quarta parte dell'esercizio richiede l'implementazione della funzione:
void remove_elem(unrolled_list_t * list, int k);
Tale funzione rimuove il
k-esimo elemento contenuto nella lista
list. Se l'indice non è valido, viene terminato il programma stampando un messaggio di errore.
L'eliminazione del k-esimo elemento deve seguire la seguente strategia:
1) trovare il nodo che ospita il k-esimo elemento
2) decrementare il numero di elementi ospitati dal nodo
3) compattare gli elementi presenti nel nodo: tutti gli elementi successivi a quello che si vuole rimuovere devono essere spostati a sinistra di una posizione
4) se il nodo non ha più elementi al suo interno: scollegare il nodo dalla lista e liberare la sua memoria
Si proceda a testare la propria implementazione utilizzando il seguente
main di prova:
#include <stdio.h>
#include "unrolled_linked_list.h"
int main
() {
unrolled_list_t * list = new_unrolled_list
();
int k;
for (k =
0; k <
20; k++
)
append_elem
(list, k
);
printf("Numero di elementi nella lista: %d (corretto: 20)\n", list_size
(list
));
printf("\n");
for (k =
0; k <
20; k++
)
printf("Elemento [%d]: %d (corretto: %d)\n", k, get_elem
(list, k
), k
);
for (k =
0; k <
16; k++
)
remove_elem
(list,
0);
printf("\n");
for (k =
0; k <
4; k++
)
printf("Elemento [%d]: %d (corretto: %d)\n", k, get_elem
(list, k
), k +
16);
printf("Numero di elementi nella lista: %d (corretto: 4)\n", list_size
(list
));
return 0;
}