UNIVERSITÁ DEGLI STUDI DI PERUGIA

Facoltá di Scienze Matematiche, Fisiche e Naturali

Corso di laurea specialistica in INFORMATICA

Progetto di applicazione e calcolo in rete:corso avanzato

DatabaseData Aggregator

Relatori: Professore:Andrea Manfucci Antonio LaganáDavide Ciambelli

Anno Accademico 2008/2009

Indice

1 Presentazione del problema 21.1 Da sqlite3 a MySQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 I contesti di comunicazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Grana fine o grana grossa? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Struttura del database 5

3 Ambiente di sviluppo e testing 7

4 Algoritmo sequenziale 8

5 Algoritmo parallelo 10

6 Analisi di complessità e scalabilità 14

7 Valutazione e misurazione delle prestazioni 15

1

Capitolo 1

Presentazione del problema

Il presente lavoro ha portato alla realizzazione di un database data aggregator. In parti-colare è stato implementato un programma parallelo che ha permesso la raccolta e l’aggre-gazione in un’unica base di dati (che per comodità chiameremo db_master) di informazionidisperse in vari database (che per comodità chiameremo aggregators). Il problema è statoaffrontato seguendo una strategia bottom up per cui l’implementazione finale è il risultato dimiglioramenti incrementali del codice che hanno permesso il raggiungimento dell’obiettivo.

Tutti i database utilizzati sono stati definiti con la stessa struttura ma con nomi diversi.Le tabelle che compongono le varie basi di dati sono del tipo:

principale(id_operazione, protocollo, id_citta, id_stato)

secondaria(cod_controllo, part_iva, quantita)

Per comodità i campi delle tabelle sono stati definiti con tipi di dato numerici per sfruttarealgoritmi che generassero numeri progressivi che hanno permesso di caricare ciascuna basedi dati fino ad un massimo di 18000 occorrenze.

I dati, diversi per ogni database aggregators, sono recuperati dai singoli processi slave me-diante operazioni di select per essere poi inseriti nel db_master. Gli unici vincoli del problemasono le eventuali duplicazioni dei dati già presenti nel db_master che quindi vanno evitatee l’accesso da parte dei processi dispari a porzioni di dati diverse da quelle a cui hanno ac-cesso i processi pari e viceversa. I programmi sono stati realizzati facendo uso di deriveddatatypes, due diversi contesti di comunicazione ed accesso remoto alla memoria.

Per capire meglio il problema analizziamolo in dettaglio.

1.1 Da sqlite3 a MySQL

Innanzi tutto è stato scelto il database da utilizzare. I requisiti fondamentali dovevano esseresemplicità di gestione e facilità di utilizzo. La preferenza è quindi ricaduta sul DBMS SQ-LITE. SQlite è una libreria software scritta in linguaggio C che implementa un DBMS SQLincorporabile all’interno di applicazioni. Il suo creatore è D. Richard Hipp, che lo ha rilasciatocome software Open Source di pubblico dominio, privo di qualsiasi licenza. Permette di otte-nere una base di dati (comprese tabelle, query, form, report) incorporate in un unico file, comeil modulo Access di Microsoft Office o il modulo Base di OpenOffice.org.

2

1.2 I contesti di comunicazione

Essendo una libreria, non è un processo standalone utilizzabile di per sè, ma può esserelinkato all’interno di un altro programma. È utilizzabile con linguaggio C/C++ ed esiste ancheper altri linguaggi. Il pacchetto ha molte interessanti caratteristiche ma presenta anche deisvantaggi che inizialmente non erano stati presi in considerazione come la gestione dellaconcorrenza (le applicazioni che lo utilizzano, se necessario, devono implementarla) e l’assenzadi una cache per le query (non esistendo un processo server centrale). Queste imperfezioninon permettevano l’esecuzione di query parallele che causavano il bloccaggio del database(SQLITE_BUSY) ogni volta che venivano effettuate operazioni di lettura e scrittura concorrente(eseguite da più processi contemporaneamente). Queste limitazioni hanno reso necessariol’utilizzo del DBMS MySQL.

MySQL è un database management system relazionale, composto da un client con inter-faccia a caratteri e un server, entrambi disponibili sia per sistemi Unix come GNU/Linux cheper Windows. Dal 1996 supporta la maggior parte della sintassi SQL e si prevede in futuro ilpieno rispetto dello standard ANSI. Il codice di MySQL è di proprietà dell’omonima società,viene però distribuito con la licenza GNU GPL oltre che con una licenza commerciale. Finoalla versione 4.0, una buona parte del codice del client era licenziato con la GNU LGPL epoteva dunque essere utilizzato per applicazioni commerciali. Dalla versione 4.1 in poi, ancheil codice dei client è distribuito sotto GNU GPL. Esiste peraltro una clausola estensiva checonsente l’utilizzo di MySQL con una vasta gamma di licenze libere. In MySQL una tabellapuò essere di diversi tipi (o storage engine).

Ogni tipo di tabella presenta proprietà e caratteristiche differenti (transazionale o meno,migliori prestazioni, diverse strategie di locking, funzioni particolari, ecc). Esiste poi un’APIche si può utilizzare per creare in modo relativamente facile un nuovo tipo di tabella, chepoi si può installare senza dover ricompilare o riavviare il server. Il tipo di tabella utiliz-zata nel programma parallelo è lo storage engine InnoDB (di tipo transazionale, sviluppatoda InnoBase Oy, società ora comprata da Oracle). InnoDB è un motore per il salvataggio didati per MySQL, fornito in tutte le sue distribuzioni. La sua caratteristica principale è quel-la di supportare le transazioni di tipo ACID. ACID deriva dall’acronimo inglese Atomicity,Consistency, Isolation, e Durability (Atomicità, Coerenza, Isolamento e Durabilità). Perché letransazioni parallele operino in modo corretto sui dati è necessario che i meccanismi che leimplementano soddisfino le quattro proprietà citate sopra. In particolare deve essere garanti-to l’isolamento in quanto ogni transazione deve essere eseguita in modo isolato e indipendentedalle altre transazioni e l’eventuale fallimento di una transazione non deve interferire con lealtre transazioni in esecuzione simultaneamente.

1.2 I contesti di comunicazione

Inizialmente è stata valutata la possibilità di utilizzare due contesti di comunicazione. L’ideaera quella di formare due gruppi di processi suddivisi in base al rango pari e dispari. Avan-zando nella progettazione però è stato ritenuto inutile suddividere i processi in due gruppidistinti in quanto le comunicazioni che avvenivano erano essenzialmente point-to-point. In-fatti i processi slave devono comunicare solamente con il processo master e non hanno bisognodi scambiarsi informazioni tra di loro; inoltre non c’era la necessità di inviare collettive daparte del master verso i due gruppi di processi (broadcast messagges). Compiere una sud-divisione tra i processi slave avrebbe solo aumentato la complessità del programma senzaportare sostanziali miglioramenti. Alla fine quindi è stato deciso di utilizzare un solo contestodi comunicazione.

3

1.3 Grana fine o grana grossa?

1.3 Grana fine o grana grossa?

La scelta della grana è stata vincolata dall’utilizzo dei database. Le basi di dati sono strut-ture statiche quindi poco compatibili con un programma parallelo. Rendono molto difficoltosoil mantenimento della scalabilità del programma riducendo di parecchio la dinamicità. Inprincipio è stata valutata la possibilità di effettuare più query in parallelo permettendo a piùprocessi di lavorare sulla stessa base di dati simultaneamente. L’idea in pratica era quelladi limitare (SELECT * FROM TABELLA LIMIT n,k;) il numero di occorrenze di ogni query sullamedesima tabella in modo da garantire un buon load balancing. In SQL è possibile eseguirequery parallele ma dopo aver testato la velocità di esecuzione di una singola query contro lavelocità di esecuzione di un insieme di query sulla medesima tabella, è emerso quanto segue:

• il costo dell’esecuzione seriale della query non è sufficientemente elevato da suggerirel’adozione di un piano alternativo di esecuzione parallela;

• un piano di esecuzione seriale è considerato più veloce di ogni possibile piano di esecu-zione parallela per la query in esame.

Prendendo atto di quanto detto sopra è stata preferita una diversa implementazione che con-siste nell’assegnare ad ogni processo slave un database. In questo modo si hanno tre possibilicasi:

1. due processi slave che lavorano su sei database aggregators;

2. quattro processi slave che lavorano su sei database aggregators;

3. sei processi slave che lavorano su sei database aggregator.

Il tempo di esecuzione di ciascuna query è stato drasticamente diminuito e nel primo e terzocaso il bilanciamento del carico viene mantenuto. Gli unici difetti di questa implementazionesono la limitata scalabilità e il caso 2 che provoca una distribuzione del carico sbilanciata inquanto, su quattro processi slave, due lavorano il doppio. Il programma quindi gira con unminimo di tre fino ad un massimo di sette processi con il vincolo che il numero di processislave deve essere pari.

4

Capitolo 2

Struttura del database

Come già anticipato nel capitolo precedente, la struttura di ciascuna base di dati consiste didue tabelle definite in questo modo:

Figura 2.1: Struttura della tabella PRINCIPALE

Nella Figura 2.1 si può notare che il campo id_operazione è chiave primaria di tipo float. Irestanti campi invece sono di tipo int. Tutti i campi devono essere NOT NULL.

Figura 2.2: Struttura della tabella SECONDARIA

Nella Figura 2.2 si può notare che il campo cod_controllo è chiave primaria di tipo float. Irestanti campi invece sono di tipo int. Tutti i campi devono essere NOT NULL.

Le tabelle non presentano nessun vincolo di integrità referenziale come si può vedere dallistato 2.1.

Listing 2.1: Creazione della base di dati1 CREATE TABLE princ ipale (2 id_operazione float PRIMARY KEY,

5

3 pro to co l l o int NOT NULL,4 i d _ c i t t a int NOT NULL,5 id_stato int NOT NULL6 )7 TYPE = InnoDB ;8

9 CREATE TABLE secondaria (10 cod_contro l lo float PRIMARY KEY,11 part_iva int NOT NULL,12 quantita int NOT NULL13 )14 TYPE = InnoDB ;

6

Capitolo 3

Ambiente di sviluppo e testing

La parte di sviluppo del codice è stata eseguita su un cluster di workstation formato da 1front-end e 5 nodi. Le caratteristiche tecniche del front-end sono riportate di seguito:

• CPU AMD Athlon XP 1,8 Ghz;

• Hard Disk da 40m GB;

• SO Debian GNU/Linux 4.0 Etch;

• Rete Fast Ethernet;

• Switch 10/100 Mbps.

Queste invece sono le caratteristiche tecniche di ciascun nodo:

• CPU Pentium II 300 Mhz;

• Hard Disk da 40 GB;

• SO Debian GNU/Linux 4.0 Etch;

• Rete Fast Ethernet;

• Switch 10/100 Mbps.

L’algoritmo è stato implementato usando la Message Passing Interface: in particolare l’imple-mentazione di MPI usata è stata la MPICH-2. Ogni test è stato ripetuto 5 volte ed è stato presoil valore medio dei singoli tempi come tempo di esecuzione.

7

Capitolo 4

Algoritmo sequenziale

L’algoritmo sequenziale consiste in un ciclo che scorre tutti i database aggregator e per ognunoeffettua due query di selezione: la prima seleziona tutto il contenuto dalla tabella principalementre la seconda seleziona tutto da secondaria. Ad ogni ciclo vengono anche effettuate lescritture nel db_master.

Listing 4.1: Esempio di interrogazione di un aggregator e scrittura nel buffer1 i f ( i == num_database ) {2 conn = mysql_init (NULL) ;3 i f ( ! mysql_real_connect ( conn , server , user , password , db2 , 0 , NULL, 0) ) {4 f p r i n t f ( stderr , "%s\n" , mysql_error ( conn ) ) ;5 ex i t ( 1 ) ;6 }7 i f ( mysql_query ( conn , " s e l e c t ∗ from princ ipale " ) ) {8 f p r i n t f ( stderr , "%s\n" , mysql_error ( conn ) ) ;9 ex i t ( 1 ) ;

10 }11 res = mysql_use_result ( conn ) ;12 contatore = 0;13 while ( ( row = mysql_fetch_row ( res ) ) != NULL) {14 buffer [ contatore ] . id_operazione = ato f ( row [ 0 ] ) ;15 buffer [ contatore ] . p ro to co l l o = ato i ( row [ 1 ] ) ;16 buffer [ contatore ] . i d _ c i t t a = ato i ( row [ 2 ] ) ;17 buffer [ contatore ] . id_stato = ato i ( row [ 3 ] ) ;18 contatore ++;19 }20 mysql_free_result ( res ) ;21 i f ( mysql_query ( conn , " s e l e c t ∗ from secondaria " ) ) {22 f p r i n t f ( stderr , "%s\n" , mysql_error ( conn ) ) ;23 ex i t ( 1 ) ;24 }25 res = mysql_use_result ( conn ) ;26 contatore = 0;27 while ( ( row = mysql_fetch_row ( res ) ) != NULL) {28 buffer [ contatore ] . cod_contro l lo = ato f ( row [ 0 ] ) ;29 buffer [ contatore ] . part_iva = ato i ( row [ 1 ] ) ;30 buffer [ contatore ] . quantita = ato i ( row [ 2 ] ) ;31 contatore ++;32 }33 mysql_free_result ( res ) ;34 mysql_close ( conn ) ;

8

35 }

Listing 4.2: Esempio di scrittura nel database db_master1 for ( j = 0 ; j < NELEM; j ++) {2 spr int f ( scr i t tura_pr inc ipa le ,3 " insert into pr inc ipale values (%3.2 f , %d , %d ,

%d ) " , buf fer [ j ] . id_operazione , buf fer [ j ] . protoco l lo , buf fer [ j ] . id_c i t ta ,buf fer [ j ] . id_stato ) ;

4 mysql_query ( conn_master1 , s c r i t tura_pr inc ipa le ) ;5 }6 for ( j = 0 ; j < NELEM; j ++) {7 spr int f ( scrittura_secondaria ,8 " insert into secondaria values (%3.2 f , %d ,

%d ) " , buf fer [ j ] . cod_control lo , buf fer [ j ] . part_iva , buf fer [ j ] . quantita ) ;9 mysql_query ( conn_master1 , scr i t tura_secondaria ) ;

10 }

9

Capitolo 5

Algoritmo parallelo

L’algoritmo parallelo si divide principalmente in due sezioni: quella del master e quella delloslave. All’inizio il master conosce il numero degli slave e, utilizzando una MPI_Send, in-via a ciascuno di essi le informazioni necessarie per effettuare l’accesso in lettura a ciascunaggregator.

Per comodità è stato creato un vettore database che contiene i nomi degli aggregators cheancora devono essere assegnati. Tale vettore viene tenuto in continuo aggiornamento dal ma-ster che ha il compito di eliminare i nomi dei database ogni volta che questi vengono assegnatiai processi slave.

Gli slave, che fino a quel momento erano in “ascolto” con l’ausilio della primitiva MPI_Probe,rispondono alla richiesta con una MPI_Recv ed iniziano il proprio lavoro. In questo modo ogniprocesso slave opera nel corrispettivo database, effettua le query, e scrive nel buffer.

A questo punto avviene il processo di sincronizzazione. Il master crea la memory win-dow (MPI_Win_create) a cui gli slave da remoto fanno riferimento per inviare, tramite laprimitiva MPI_Put, i buffer che precedentemente erano stati riempiti.

Il master ora è in possesso di tutti i risultati delle query effettuate fino a quel momentodai processi slave e quindi può effettuare la prima scrittura nel db_master. Adesso il masterdeve controllare il vettore database. Se questo è vuoto significa che il contenuto di tutti gliaggregators è stato scritto nel db_master e in tal caso il programma termina con l’invio atutti gli slave di una MPI_Send con un tag di fine lavoro. In caso contrario, il master devecontrollare quali sono i processi slave liberi in quel momento trasmettendo loro le informazionirimanenti.

Naturalmente il tutto avviene discriminando i processi dispari da quelli pari per cui ad unaggregator di indice dispari avrà accesso esclusivamente un processo dispari e viceversa.

Listing 5.1: Funzione master: prima assegnazione dei lavori agli slave1 for ( i = 1 ; i <= numworker ; i ++) {2 invio = i ;3 MPI_Send(&invio , 1 , MPI_INT, i , CICLO1, MPI_COMM_WORLD) ;4 database [ i ] = 1 ;5 }6 MPI_Win_create(&buffer , NELEM ∗ sizeof ( query ) , sizeof ( query ) , MPI_INFO_NULL,

MPI_COMM_WORLD, &f ines tra ) ;7 MPI_Win_fence (0 , f ines t ra ) ;8 //

10

9 //10 MPI_Win_fence (0 , f ines t ra ) ;11 MPI_Win_free(& f ines t ra ) ;

Listing 5.2: Funzione master: assegnazione dei lavori successivi agli slave1 MPI_Recv (NULL, 0 , MPI_INT, MPI_ANY_SOURCE, CICLO2, MPI_COMM_WORLD, &status ) ;2 terminato = status .MPI_SOURCE;3 vettore [ terminato ] = 1 ;4 i f ( ( terminato % 2) == 1) {5 k = 1;6 for (k = 1; k <= DATABASE; k++) {7 i f ( database [k ] == 0 && (k % 2) == 1) {8 invio = k ;9 MPI_Send(&invio , 1 , MPI_INT, terminato , CICLO1, MPI_COMM_WORLD) ;

10 database [k ] = 1 ;11 break ;12 }13 }14 }15 i f ( ( terminato % 2) == 0) {16 k = 1;17 for (k = 1; k <= DATABASE; k++) {18 i f ( database [k ] == 0 && (k % 2) == 0) {19 invio = k ;20 MPI_Send(&invio , 1 , MPI_INT, terminato , CICLO1, MPI_COMM_WORLD) ;21 database [k ] = 1 ;22 break ;23 }24 }25 }

Listing 5.3: La funzione slave1 for ( ; ; ) {2 disp = ( rank−1)∗NELEM;3 MPI_Probe (0 ,MPI_ANY_TAG,MPI_COMM_WORLD,& status ) ;4 i f ( status .MPI_TAG==CICLO1) {5 MPI_Recv(&invio ,1 ,MPI_INT, source ,CICLO1,MPI_COMM_WORLD,& status ) ;6 spr int f ( pippo , " db_slave_%d" , invio ) ;7 char ∗db=pippo ;8

9 //******** Lavoro database *********//10

11 conn=mysql_init (NULL) ;12

13 /* Connect to database */14

15 i f ( ! mysql_real_connect ( conn , server , user , password , db ,0 ,NULL, 0 ) ) {16 f p r i n t f ( stderr , "%s\n" , mysql_error ( conn ) ) ;17 ex i t ( 1 ) ;18 }19

20 /* send SQL query */21

22 i f ( mysql_query ( conn , " s e l e c t ∗ from princ ipale " ) ) {

11

23 f p r i n t f ( stderr , "%s\n" , mysql_error ( conn ) ) ;24 ex i t ( 1 ) ;25 }26 res = mysql_use_result ( conn ) ;27 k = 0;28 while ( ( row = mysql_fetch_row ( res ) ) != NULL) {29 buffer [k ] . id_operazione = ato f ( row [ 0 ] ) ;30 buffer [k ] . p ro to co l l o = ato i ( row [ 1 ] ) ;31 buffer [k ] . i d _ c i t t a = ato i ( row [ 2 ] ) ;32 buffer [k ] . id_stato = ato i ( row [ 3 ] ) ;33 k++;34 }35 mysql_free_result ( res ) ;36

37 /* send SQL query */38

39 i f ( mysql_query ( conn , " s e l e c t ∗ from secondaria " ) ) {40 f p r i n t f ( stderr , "%s\n" , mysql_error ( conn ) ) ;41 ex i t ( 1 ) ;42 }43 res = mysql_use_result ( conn ) ;44 k = 0;45 while ( ( row = mysql_fetch_row ( res ) ) != NULL) {46 buffer [k ] . cod_contro l lo = ato f ( row [ 0 ] ) ;47 buffer [k ] . part_iva = ato i ( row [ 1 ] ) ;48 buffer [k ] . quantita = ato i ( row [ 2 ] ) ;49 k++;50 }51

52 /* close connection */53

54 mysql_free_result ( res ) ;55 mysql_close ( conn ) ;56 MPI_Type_struct (2 , blockcounts , o f f se t , oldtypes ,&MY_PART) ;57 MPI_Type_commit(&MY_PART) ;58 MPI_Win_create (MPI_BOTTOM,0 ,1 ,MPI_INFO_NULL,MPI_COMM_WORLD,& f ines tra ) ;59 MPI_Win_fence (0 , f ines t ra ) ;60 MPI_Put(&buffer ,NELEM,MY_PART,0 , disp ,NELEM,MY_PART, f ines t ra ) ;61 MPI_Win_fence (0 , f ines t ra ) ;62 MPI_Win_free(& f ines t ra ) ;63 MPI_Type_free(&MY_PART) ;64 MPI_Send(NULL,0 ,MPI_INT,0 ,CICLO2,MPI_COMM_WORLD) ;65 }66 else i f ( status .MPI_TAG == CICLO3) {67 MPI_Recv (NULL,0 ,MPI_INT, source ,CICLO3,MPI_COMM_WORLD,& status ) ;68 MPI_Win_create (MPI_BOTTOM,0 ,1 ,MPI_INFO_NULL,MPI_COMM_WORLD,& f ines tra ) ;69 MPI_Win_fence (0 , f ines t ra ) ;70 MPI_Win_fence (0 , f ines t ra ) ;71 MPI_Win_free(& f ines t ra ) ;72 }73 else i f ( status .MPI_TAG == FINITO) {74 pr int f ( "FINE\n" ) ;75 break ;76 }77 }

La struttura che abbiamo utilizzato per il buffer prevede sette campi che coincidono con quelli

12

delle due tabelle del database.

Listing 5.4: Struct query e derived datatype1 //-----Define struct-----//2

3 typedef struct {4 float id_operazione ;5 float cod_contro l lo ;6 int pro to co l l o ;7 int i d _ c i t t a ;8 int id_stato ;9 int part_iva ;

10 int quantita ;11 } query ;12

13 //-----Derived datatype-----//14

15 MPI_Datatype oldtypes [ 2 ] = { MPI_FLOAT, MPI_INT } ;16 int blockcounts [ 2 ] = { 2 , 5 } ;17 MPI_Aint o f f s e t [ 2 ] = { 0 , 2 ∗ sizeof ( float ) } ;18 MPI_Datatype MY_PART;

13

Capitolo 6

Analisi di complessità e scalabilità

La complessità temporale dell’algoritmo varia in relazione alla dimensione dell’input. Infattiall’aumentare delle occorrenze nelle tabelle dei vari aggregators aumenta il tempo di esecu-zione delle varie query. Come è già stato detto in precedenza si è scelto di effettuare unaquery per ogni aggregator invece di effettuare query parallele per non incorrere in una dila-tazione ancora maggiore dei tempi. Le prove e gli studi effettuati sul tempo di esecuzione divarie query hanno permesso di stabilire che la complessità temporale dell’algoritmo dipendefortemente dal tempo effettivo di esecuzione di una query SQL.

Il tempo delle query è lineare ed aumenta in base al numero di occorrenze. È naturalequindi che il tempo di esecuzione del programma deriva dal tempo totale per leggere tutte leoccorrenze dei vari aggregators sommato al tempo che occorre al master per scrivere i risultatinel db_master. Questo è riconducibile al problema di cercare un elemento all’interno di unalista non ordinata. Tale problema ha una complessità pari ad O (n).

Per quanto riguarda la scalabilità il programma è da considerarsi “parzialmente” scalabile(scalabilità di carico) in quanto l’implementazione è vincolata dal numero di database. Infattile basi di dati sono strutture statiche e devono essere già presenti nel cluster al momentodel lancio del programma. Tali strutture non possono essere costruite a run-time e perciòlimitano la scalabilità e modificano le strategie di implementazione del codice.

14

Capitolo 7

Valutazione e misurazione delleprestazioni

Sono stati eseguiti diversi test con valori variabili di carico dei database in modo da osservarel’impatto delle dimensioni sulle performance; i test sono stati ripetuti per tre dimensioni dicarico: 36000 occorrenze (6000 per ogni aggregator), 72000 occorrenze (12000 per ogni aggre-gator) e 108000 occorrenze (18000 per ogni aggregator). La tabella 7.1 riporta i valori osservatiper le tre dimensioni:

Tabella 7.1: Valori osservati nelle diverse proveOccorrenze Processori Tp Sp Ep

36000 seriale 80,2 1 136000 3 58,4 1,37 0,4636000 5 57,6 1,39 0,2836000 7 56,6 1,42 0,18

72000 seriale 156,4 1 172000 3 113,2 1,38 0,4672000 5 112 1,4 0,2872000 6 108,8 1,44 0,21

108000 seriale 234,6 1 1108000 3 167,6 1,4 0,47108000 5 164,8 1,42 0,28108000 7 161,2 1,46 0,21

Le figure 7.1, 7.2 e 7.3 invece mostrano i grafici relativi ai dati osservati per le diversedimensioni del problema testate. Dal grafico 7.2 si evince che più sono piccole le dimensioni deldatabase e maggiore sarà l’overhead. Non avendo a disposizione un algoritmo sequenziale èstato calcolato lo speedup relativo eseguendo il programma parallelo con un solo processore.

15

Figura 7.1: Grafico del tempo relativo alle tre prove

Figura 7.2: Grafico dello speedup relativo alle tre prove

16

Figura 7.3: Grafico dell’efficienza relativo alle tre prove

17

Bibliografia

[1] http://it.wikipedia.org/.

[2] www-it.mysql.com/.

[3] L. Pacifici, Dispense del corso di Applicazione e Calcolo in Rete - Corso Avanzato.Corso di laurea specialistica in Informatica, Università degli studi di Perugia, Italia.

18