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