Homework - A.A. 2011-2012
Lo scopo degli homework è quello di familiarizzare con la realizzazione di algoritmi e strutture dati in linguaggio C e approfondire aspetti prestazionali legati all'ottimizzazione del codice e al modo in cui i compilatori generano codice macchina per la piattaforma utilizzata. Per quest'anno accademico è previsto un homework, facoltativo per l'esame e scelto liberamente fra uno dei due seguenti. Il voto in trentesimi assegnato all'homework farà media con il voto di esame in ragione 1/4 per l'homework e 3/4 per il voto dello scritto. L'homework potrà essere consegnato al massimo entro l'appello successivo a quello in cui si svolge lo scritto.
Modalità di realizzazione e consegna
L'homework può essere realizzato in gruppi di al più due persone e prevede la realizzazione di software ed esperimenti prestazionali che devono essere discussi in una breve relazione. La relazione deve includere:
- nome, cognome e matricola degli autori degli homework
- specifiche e obiettivi del progetto
- discussione del codice scritto:
- scelte realizzative
- descrizione delle strutture dati e delle funzioni realizzate
- discussione degli esperimenti
- obiettivi sperimentali
- dettagli sulla piattaforma utilizzata: CPU, memoria, sistema operativo, compilatore, ecc.
- discussione dei risultati ottenuti, eventualmente riportati mediante grafici o tabelle
- sintesi delle conclusioni che sono state tratte dagli esperimenti
La relazione deve essere consegnata e discussa entro l'appello successivo a quello in cui si supera lo scritto dell'esame. La consegna e la discussione degli homework avviene in sede di verbalizzazione. Per prenotarsi per la discussione, inviare al docente per email all'indirizzo
demetres@dis.uniroma1.it un file compresso contenente:
- il codice realizzato
- la relazione
La prenotazione deve avvenire almeno quattro giorni prima della data di discussione.
Homework 1
Parte 1
Proporre tre diverse realizzazioni alternative in C del tipo di dato astratto pila, scrivendo:
- una header stack.h contenente la dichiarazione dei tipi e delle funzioni per manipolare pile di interi.
- un modulo stack-list.c contenente la definizione dei tipi completi e delle funzioni che implementano le operazioni del tipo di dato, usando una lista collegata semplice per rappresentare la pila.
- un modulo stack-array.c contenente la definizione dei tipi completi e delle funzioni che implementano le operazioni del tipo di dato, usando un array per rappresentare la pila. L'array deve essere dimensionato inizialmente per contenere al massimo 1000 interi e deve essere ridimensionato del 50% ogni volta che si riempie.
- un modulo stack-unrolled-list.c contenente la definizione dei tipi completi e delle funzioni che implementano le operazioni del tipo di dato, usando una lista collegata unrolled per rappresentare la pila. Assumere che ogni nodo della lista contenga spazio per 1000 interi.
La realizzazione deve fornire un tipo
stack che rappresenta oggetti pila e le seguenti funzioni per manipolarli:
- stack* stack_new(): crea un nuovo oggetto pila di interi e ne restituisce l'indirizzo;
- void stack_delete(stack* s): dealloca un oggetto pila precedentemente creato;
- void stack_push(stack* s, int item): aggiunge un elemento in cima alla pila;
- int stack_pop(stack* s): se la pila non è vuota, ne rimuove il primo elemento e lo restituisce, altrimenti restituisce -1.
- int stack_top(stack* s): se la pila non è vuota, ne restituisce il primo elemento (senza toglierlo dalla pila), altrimenti restituisce -1.
- int stack_is_empty(stack* s): restituisce 1 se la pila è vuota, e 0 altrimenti.
Assumere che le chiamate a
malloc,
calloc o
realloc restituiscano sempre un valore diverso da
NULL.
Si consideri il seguente programma di test per verificare la correttezza del codice scritto:
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
int main
(int argc,
char** argv
) {
stack* s;
/* create empty stack */
s = stack_new
();
/* add items to stack */
stack_push
(s,
10);
stack_push
(s,
20);
stack_push
(s,
30);
/* print first item (should print 30) */
printf("%d\n", stack_top
(s
));
/* remove items from stack (should print 30 20 10) */
while (!stack_is_empty
(s
)) {
int item = stack_pop
(s
);
printf("%d\n", item
);
}
/* deallocate stack */
stack_delete
(s
);
return 0;
}
Usare il tool
memcheck di Valgrind per testare il funzionamento del codice scritto.
Parte 2
Si calcoli il numero di byte richiesti al sistema operativo da ciascuna delle tre strutture dati proposte per memorizzare una pila contenente n elementi. Assumere di lavorare su una piattaforma a 64 bit e che l'allocatore di memoria del C usi header di 4 byte e blocchi allineati a indirizzi multipli di 8 byte. Quale soluzione richiede meno byte per n grande?
Parte 3
Si consideri il seguente programma di test:
#include <stdio.h>
#include <stdlib.h>
#include "stack.h"
int main
(int argc,
char** argv
) {
unsigned i, n;
stack* q;
/* check command line parameters */
if (argc <
2) exit
((printf("usage: %s num-items seed\n", argv
[0]),
1));
/* get command line parameter */
n = atoi
(argv
[1]);
/* set random generator seed */
srand
(atoi
(argv
[2]));
/* create empty stack */
q = stack_new
();
/* add n items to stack */
for (i=
0; i<n; i++
) stack_push
(q, i
);
/* perform random sequence of 3n push/pop operations on stack */
for (i=
0; i<
3*n; i++
)
if (rand
() %
2)
stack_push
(q, i
);
else stack_pop
(q
);
/* deallocate stack */
stack_delete
(q
);
return 0;
}
Il programma prende da riga di comando un parametro
n e un seme
seed per il generatore di numeri pseudo-casuali ed effettua la seguente sequenza di operazioni:
- creazione di una pila vuota
- inserimento di n interi nella pila
- inserimento/rimozione casuale di 3n elementi dalla pila
- cancellazione della pila con rimozione di tutti i suoi elementi
Ad esempio, i seguenti comandi compilano il programma ed eseguono un test su una pila di dieci milioni di elementi soggetta a operazioni casuali con seme 971, riportando il tempo richiesto dall'esecuzione:
> gcc stack-perf.c stack-list.c -o stack-list-perf-O0
> time ./stack-list-perf-O0 10000000 971
real 0m4.258s
user 0m3.972s
sys 0m0.182s
Scrivere un
makefile che fornisce regole per i seguenti comandi:
- make: compila il programma di test in diverse versioni. In particolare, produce due eseguibili distinti per ciascuna delle tre realizzazioni, compilando con -O0 e con -O3;
- make test: esegue ciascun programma di test su pile di diversi milioni di elementi generati a partire dallo stesso seme (scegliere il più alto numeo possibile di elementi per la propria macchina in modo da non incorrere in fenomeni di swapping della memoria su disco).
Riportare e discutere i risultati ottenuti dall'esecuzione delle diverse versioni del programma di test, rispondendo in particolare alle seguenti domande:
- qual è la realizzazione che scegliereste in pratica e perché?
- dove sono i colli di bottiglia nelle realizzazioni più lente?
- di quanto migliorano le prestazioni passando da -O0 a -O3?
Homework 2
Parte 1
Progettare un algoritmo che, data una matrice quadrata
n x
n memorizzata in ordine row-major (per righe) in un file, modifica il file trasponendo la matrice. L'algoritmo non deve usare file temporanei di appoggio e deve effettuare un numero di I/O pari a
IO(n,b,m)=O(n2/b), dove
n è il lato della matrice,
b è la dimensione di blocco ed
m è la dimensione della memoria interna. Si assuma che
m=Ω(b2).
Parte 2
Implementare in C l'algoritmo della Parte 1 scrivendo una funzione:
void mat_transp(FILE* f, long n, long b)
che, dato un puntatore
f a un file contenente una matrice
n x
n di
unsigned in row-major order e un parametro
b che definisce la size di blocco come numero di item da trasferire negli accessi a disco, modifica il file trasponendo la matrice. Si assuma che
n sia sempre un multiplo di
b. Gestire eventuali errori interni alla funzione terminando il programma con un messaggio di errore.
Per gli accessi a disco, usare le funzioni:
- fseeko∞ per posizionarsi in un punto del file da cui leggere/scrivere;
- fread∞ per leggere b item di dimensione sizeof(unsigned) byte dal file;
- fwrite∞ per scrivere b item di dimensione sizeof(unsigned) byte sul file.
Parte 3
Testare il funzionamento e le prestazioni del codice scritto usando il pacchetto sperimentale
mat-transp∞, che contiene:
- mat-transp.h: header che dichiara il prototipo della funzione mat_transp.
- mat-transp-AUTHOR.c: file contenente la realizzazione della funzione sviluppata nella Parte 2, dove AUTHOR va rimpiazzato con il cognome del primo sviluppatore del team in ordine alfabetico.
- make-matrix-file.c: file contenente un programma per generare file contenenti matrici quadrate memorizzate per righe (row-major). Il programma genera una matrice A tale che A[i][j]=i*n+j, per ogni 0<=i,j<n.
- mat-transp-perf.c: file contenente un programma di test delle prestazioni per la trasposizione di matrici.
- check-mat-transp.c: file contenente un programma per verificare se una matrice creata con make-matrix-file e successivamente trasposta con mat-transp-perf è corretta.
- makefile: script per compilare ed effettuare i test di correttezza e prestazioni. Lo script va modificato definendo opportunamente la macro TEAM impostandolo con il cognome del primo sviluppatore del team in ordine alfabetico.
Compilare il codice con
make e testare la correttezza del codice scritto con
make check.
Il
makefile fornisce regole per eseguire test prestazionali su matrici di dimensione diverse:
- make test20000: misurazioni tempi trasposizione matrice 20000x20000 (file di 1.5 GB) per dimensioni di blocco b=2500, 5000, 10000, 20000;
- make test30000: misurazioni tempi trasposizione matrice 30000x30000 (file di 3.4 GB) per dimensioni di blocco b=2500, 5000, 10000, 15000;
- make test40000: misurazioni tempi trasposizione matrice 40000x40000 (file di 6.0 GB) per dimensioni di blocco b=2500, 5000, 10000, 20000;
- make test60000: misurazioni tempi trasposizione matrice 60000x60000 (file di 13.4 GB) per dimensioni di blocco b=2500, 5000, 10000, 20000;
- make test80000: misurazioni tempi trasposizione matrice 80000x80000 (file di 23.8 GB) per dimensioni di blocco b=2500, 5000, 10000, 20000.
Eseguire i test più appropriati per la propria macchina, modificando eventualmente il
makefile, in modo che:
- la dimensione del file sia maggiore, o solo di poco inferiore, a quella della memoria fisica della propria macchina. Infatti, i sistemi operativi caricano tipicamente ampie porzioni di file in una disk cache in RAM, per cui se la dimensione del file è di molto inferiore a quella della memoria RAM, la maggior parte delle letture/scritture di file effettuate dal programma potrebbero in realtà accedere a memoria interna, fornendo risultati prestazionali non significativi;
- i valori di b usati nel test non siano tali da richiedere un uso di memoria eccessivo al programma di trasposizione. Infatti, se la dimensione di blocco b data in input al programma di trasposizione è troppo grande, il programma stesso potrebbe incorrere in problemi di swap su disco di pagine di memoria centrale, degradando artificialmente le prestazioni. Se necessario, modificare le size di blocco usate per i test, con il solo vincolo che n sia un multiplo di b.
Riportare il tempo richiesto per la creazione del file e riportare i seguenti valori per ciascuna esecuzione del programma di
mat-transp-perf, mediante una tabella o dei grafici in funzione di
b, considerando la media dei valori misurati su almeno tre esecuzioni indipendenti dello stesso test:
- size di blocco b
- tempi real, user e system
- memoria interna usata
- percentuale del tempo di CPU
- throughput del trasferimento di dati tra memoria interna e disco, in MB/sec (cumulativo sia di letture che di scritture)
Discutere e motivare i risultati ottenuti al crescere del parametro
b.