User:aleant

 

Balanced Graph Partitioning per simulazioni agent-based distribuite

Il Problema

k-way partitioning 

D-MASON permette di parallelizzare simulazioni basate su agenti adottando un approccio di space partitioning, che consente di bilanciare il carico di lavoro tra le risorse coinvolte nella computazione, limitando i costi della comunicazione. Ogni macchina eseguirà, quindi, la simulazione degli agenti che si trovano nello spazio assegnato ad essa. Comprensibilmente, questi possono migrare da una risorsa all’altra e quando ciò avviene le macchine hanno bisogno di comunicare informazioni circa gli agenti migrati o gli agenti che potrebbero migrare nel prossimo passo di simulazione.

Il problema, dunque, riguarda come partizionare in modo dinamico il campo Network di D-MASON, in modo tale che:

1. le componenti abbiano approssimativamente la stessa dimensione

2. il numero di connessioni e il volume di comunicazione tra vertici appartenenti a componenti differenti sia minimizzato.

Ciò è ben noto in letteratura come graph partitioning problem.

Il problema di computare una partizione ottimale di un supergrafo è NP-hard; ciò significa che soluzioni esatte sono ricavate in tempo ragionevole solo per grafi di piccole dimensioni. Tuttavia, le applicazioni di questo problema richiedono di partizionare grafi di dimensioni molto  maggiori e per questo motivo sono state sviluppate diverse soluzioni euristiche, basate su differenti approcci.

Gli algoritmi

Approccio multi-livello

METIS

Questo algoritmo computa le partizioni in tre fasi. Nella prima i vertici vengono collassati in modo da far diminuire la taglia del grafo di partenza; questa azione viene eseguita fino ad arrivare ad un grafo semplificato sul quale viene eseguito il partizionamento. Nell’ultima fase, il grafo viene riportato alla forma originaria, rifinendo ad ogni passo la qualità delle partizioni computate.

KaFFPa

KaFFPa, come METIS, usa un approccio multi-livello per il partizionamento; questi due algoritmi si differenziano, però, nell’ultima fase dove usano diverse tecniche di rifinizione delle partizioni generate.

Approccio distribuito

Ja-Be-Ja

A differenza degli algoritmi precedenti, Ja-be-ja nasce come algoritmo distribuito, senza richiedere nessuna conoscenza globale della topologia del grafo. Ogni nodo del grafo è un’unità di elaborazione e conserva informazioni riguardanti i suoi vicini e alcuni nodi selezionati a caso. Inizialmente, ad ogni nodo viene assegnata una partizione, facendo in modo che queste siano bilanciate. Ad ogni iterazione, i nodi scambiano le loro partizioni di appartenenza al fine di aumentare il numero di vicini che si trovano nella stessa partizione.

 Baseline

Random

Questo algoritmo assegna ogni vertice ad un componente casuale, fornendo sempre un ottimo bilanciamento. E’ usato come baseline nelle comparazioni effettuate.

Obiettivo

Studio e benchmark di algoritmi per il partizionamento bilanciato di grafi per simulazioni agent-based distribuite.

I test

Criteri di analisi

In modo da valutare quali siano l’euristiche che producano il partizionamento migliore per la risoluzione del problema sopra citato, sono state considerate le seguenti metriche:

– dimensione del taglio: numero totale di archi incidenti su vertici appartenenti a diversi componenti;

– numero di canali di comunicazione: indica il numero di archi nel supergrafo ottenuto considerando i nodi in ogni componente come un singolo vertice.

– sbilanciamento:  coefficiente di sbilanciamento della dimensione dei componenti della partizione.

Risultati

Analizzando i risultati ottenuti dall’esecuzione dei diversi algoritmi, si evince che le performance delle soluzioni multi-livello sono comparabili sia in termini di dimensione del taglio, sia per numero di canali di comunicazione generati. Tuttavia, le prestazioni di Ja-Be-Ja sono peggiori di quelle dei suoi avversari; ciò può essere dovuto al basso numero di iterazioni effettuate.

In generale, tutti gli algoritmi producono partizioni abbastanza bilanciate. Su questo campo, quindi, nessuna strategia prevale sulle altre.

I risultati ottenuti nell’ambiente reale di simulazione sono consistenti con quelli analitici, sia in termini di dimensione del taglio sia nel numero di canali di comunicazione. In particolare, le performance delle simulazioni distribuite sono influenzate dalle metriche analitiche. Esiste, quindi, una correlazioni tra il tempo totale di simulazione e le prestazioni degli algoritmi (misurate in termini di dimensione del taglio, numero di canali di comunicazione e sbilanciamento), soprattutto per quanto riguarda la dimensione del taglio.

Dall’analisi è, inoltre, emerso che la qualità dello sbilanciamento tra le componenti non è legata direttamente alle performance reali: questo valore potrà, quindi, essere alterato in modo da comportare le diminuzione di altri parametri, quali dimensione del taglio e numero di canali di comunicazione, aventi diretto influsso sulle prestazioni.

Riferimenti

  1. Fatemeh Rahimian, Amir H. Payberah, Sarunas Girdzijauskas, Mark Jelasity, Seif Haridi, Ja-be-Ja: A Distributed Algorithm for Balanced Graph PartitioningOttobre 2012.
  2. George Karypis and Vipin Kumar, Multilevel k-way Hypergraph Partitioning1999.
  3. David Easley and Jon Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World – Overviewcap. 1, 2010.
  4. David Easley and Jon Kleinberg, Networks, Crowds, and Markets: Reasoning About a Highly Connected World – Graphscap. 2, 2010.
  5. Jim Demmel, Lectures 20 and 21, Graph Partitioning, Part 1, 1996.
  6. Jim Demmel, Lectures 23, Graph Partitioning, Part 2, 1996.
  7. B. Cosenza, G. Cordasco, R. De Chiara, V. Scarano. Distributed Load Balancing for Parallel Agent-based Simulations, 2011.
  8. Peter Sanders and Christian Schulz, Engineering Multilevel Graph Partitioning Algorithms, 2011.
  9. Implementazione dell’algoritmo Ja-be-ja.
  10. Graph Partitioning Archive.
  11. D. A. Bader, H. Meyerhenke, P. Sanders, and D. Wagner, editors. Graph Partitioning and Graph Clustering.
  12. B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs.
  13. C. M. Fiduccia and R. M. Mattheyses. A Linear-Time Heuristic for Improving Network Partitions.
                                                                                                                                 «Per aspera sic itur ad astra.» – Seneca, Hercules Furens.                                                                                                                                 email: aless.antelmi@gmail.com

User:marpel

Informazioni personali

Nome: Maria Angela Pellegrino Contatti: m.pellegrino27@studenti.unisa.it mariaangela.pellegrino@virgilio.it

Diario di bordo

Per inquadrare il contesto in cui è stato sviluppato aCME ho letto l’articolo scritto da Delfina Malandrino, Ilaria Manno, Giuseppina Palmieri, Vittorio Scarano, Luca Tateo, Daniele Casola, Ivan Ferrante, Francesco Foresta in cui sono stati delineati gli scopi di aCME, i requisiti funzionali e trasversali e le sfide pedagogiche affrontate per l’integrazione di teorie dell’insegnamento e attività di insegnamento mobile. Articolo: 06937153-Journal-TLT-2014 Per approfondire lo studio della piattaforma aCME ho letto le tesi dei tre ragazzi che la hanno implementata: Ivan Ferrante ha spiegato l’architettura di aCME e le scelte che hanno valutato prima di giungere alle tecnologie usate in fase di sviluppo (Tesi Ivan Ferrante: https://mega.co.nz/#!9FwxgRCZ!I-w5iU-C75zK4v35LgWeaeflxN2W5REjUHmhz8k3-QQ); Francesco Foresta si è dedicato alla spiegazione di Vaadin e le valutazioni fatte prima di scegliere questo framework confrontandolo con RAP e ha presentato i tre web-bundle usati per gestire Administrator, Controller e Discusser (Tesi Francesco Foresta: https://mega.co.nz/#!hBZyRDgR!AzvejtRdkjoOteSbpcjEcnOiL7QT-OyiNJw2qT9HKCw); Daniele Casola ha spiegato il concetto di acmeTool, ha elencato i passi principali da seguire per creare un nuovo acmeTool e presentato il Wizard che hanno realizzato per aiutare i nuovi sviluppatori di aCME a implementare un nuovo acmeTool (Tesi Daniele Casola: https://mega.co.nz/#!1QxECTAQ!GMkoLWtQPzWDwTxLTWNUSnSCFuqKvEIIRNkwSCGgCoE). Per imparare il framework Vaadin sto leggendo il libro ufficiale: https://vaadin.com/book/-/page/preface.html.

Seminario 1

Nel primo seminario ho – descritto brevemente la piattaforma aCME Groupware, – introdotto gli aCME Tool che sono gli strumenti di lavoro, – implementato un esempio di Tool (HelloTool) per mostrare come il Wizard realizzato dagli sviluppatori di aCME Groupware semplifica il lavoro di sviluppo di un nuovo tool e ho mostrato come farne il deploy e integrarlo all’interno del sistema, – presentato l’oggetto di tesi: – gestione dei gruppi – memory tool in gruppo. Non ho mostrato dettagli implementativi, ma il mio obiettivo è stato quello di decidere e valutare politiche di implementazione. Per vedere il seminario fare click qui.

Seminario 2

Nel secondo seminario, che è anche stato quello conclusivo, ho – riepilogato velocemente il sistema aCME Groupware, – elencato le operazioni che permettono la gestione dei gruppi, – presentato alcune parti dell’implementazione di tali operazioni mostrando anche come si può usufruire di tale funzionalità a partire dall’interfaccia, – presentato il MemoryTool partendo dall’idea fino alla sua implementazione, – descritto alcune modifiche apportate all’interfaccia sia lato controller che lato discusser e al QuizTool per migliorarne l’usabilità. Per vedere il seminario fare click qui.