Informazioni personali
Nome: Andrea Soldà
E-mail: a.solda@studenti.unisa.it o a.solda92@gmail.com
Laurea triennale
Introduzione
Il mio lavoro di tesi prevede un confronto tra algoritmi per il partizionamento di grafi massivi. Lo scopo di questi algoritmi è di distribuire efficientemente il campo network di dMASON.
Obiettivi
Trovare il modo migliore per partizionare un grafo massivo durante una simulazione in ambito distribuito.
Eventualmente proporre un nuovo approccio al problema ed una soluzione competitiva.
Diario
Prima settimana
Per prima cosa ho preso familiarità con JgraphT, una libreria Java utilizzata già in altri lavori svolti in laboratorio da altri tesisti. Ho modificato delle classi realizzate da Francesco Milone per creare un parser che mi permettesse di importare grafi da file in formato gml o GraphML all'interno del mio codice.
Ho poi svolto delle ricerche per trovare alternative alle soluzioni proposte da Ada Mancuso nel suo lavoro di tesi, imbattendomi nel software METIS, sul quale sto lavorando ora.
Seconda settimana
Nel corso di questa settimana ho continuato a lavorare su METIS e sono riuscito a farlo funzionare sotto Ubuntu. Ho tuttavia riscontrato numerosi problemi nel comprendere la strutturazione dei file che il software accetta in input. Dopo uno studio del codice ed alcuni tentativi pratici sono riuscito a completare un parser in Java che converte file dal formato GML al formato graph.
Al momento mi appresto a cominciare la fase di testing degli algoritmi di METIS, che finora sembrano promettere bene.
Terza settimana
Durante questa settimana ho continuato a fare test su METIS. Ho introdotto una mia modifica nell'algoritmo per diminuire l'indice di comunicazione nel supergrafo risultante sbilanciando leggermente la taglia delle community risultanti.
Quarta settimana
I test su METIS sono quasi completi. Ora che ho a disposizione tutti i dati necessari inizio la fase di confronto con gli altri algoritmi a disposizione. Finora, basandomi su alcuni test effettuati rapidamente, METIS sembra competitivo.
Quinta settimana
In questa settimana ho completato tutti i test ed ho preparato il mio primo seminario, che si terrà venerdì 4 Aprile alle ore 10.
Sesta settimana
Dopo le considerazioni fatte durante il seminario ho effettuato alcuni test modificando dei parametri nell'UKWayPart, che però non hanno influito né sulle prestazioni né sulla qualità del partizionamento
Settima settimana
Sto lavorando per implementare METIS in DMASON, creando un tool esterno che permetta di partizionare il grafo della simulazione. Presto inizieranno i test sulle simulazioni complete utilizzando il cluster Oxygen
Ottava/nona/decima settimana
Il tool per l'implementazione di METIS in DMASON è stato completato, consente di partizionare il grafo della simulazione con un algoritmo a scelta, ma anche di ottenere parti del grafo caratterizzate da un id di community ed un parametro aoi, utile per riempire le strutture utilizzate in DMASON.
Seminari
Seminario venerdì 4 Aprile 2014
Titolo: Unbalanced KWayPart Algorithm: un algoritmo veloce ed affidabile per partizionare grafi massivi
Abstract: n questo seminario verrà presentato l'UKWayPart, un algoritmo progettato partendo dall'algoritmo METIS KWayPart per il partizionamento di grafi massivi. Verrà posta una particolare enfasi sull'applicazione dell'algoritmo nell'ambito di dMASON per il partizionamento del campo Network. Verranno inoltre esposti i risultati dei test effettuati sui vari dataset scelti e verranno fatte considerazioni sull'eventuale implementazione in dMASON