User: Andsol (Andrea Soldà)

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