Large-scale Network Analysis on Distributed Architectures

Paolino, Carmine (2011) Large-scale Network Analysis on Distributed Architectures. [Laurea], Università di Bologna, Corso di Studio in Informatica [L-DM509]
Documenti full-text disponibili:
[img]
Anteprima
Documento PDF
Download (725kB) | Anteprima

Abstract

Questa dissertazione esamina le sfide e i limiti che gli algoritmi di analisi di grafi incontrano in architetture distribuite costituite da personal computer. In particolare, analizza il comportamento dell'algoritmo del PageRank così come implementato in una popolare libreria C++ di analisi di grafi distribuiti, la Parallel Boost Graph Library (Parallel BGL). I risultati qui presentati mostrano che il modello di programmazione parallela Bulk Synchronous Parallel è inadatto all'implementazione efficiente del PageRank su cluster costituiti da personal computer. L'implementazione analizzata ha infatti evidenziato una scalabilità negativa, il tempo di esecuzione dell'algoritmo aumenta linearmente in funzione del numero di processori. Questi risultati sono stati ottenuti lanciando l'algoritmo del PageRank della Parallel BGL su un cluster di 43 PC dual-core con 2GB di RAM l'uno, usando diversi grafi scelti in modo da facilitare l'identificazione delle variabili che influenzano la scalabilità. Grafi rappresentanti modelli diversi hanno dato risultati differenti, mostrando che c'è una relazione tra il coefficiente di clustering e l'inclinazione della retta che rappresenta il tempo in funzione del numero di processori. Ad esempio, i grafi Erdős–Rényi, aventi un basso coefficiente di clustering, hanno rappresentato il caso peggiore nei test del PageRank, mentre i grafi Small-World, aventi un alto coefficiente di clustering, hanno rappresentato il caso migliore. Anche le dimensioni del grafo hanno mostrato un'influenza sul tempo di esecuzione particolarmente interessante. Infatti, si è mostrato che la relazione tra il numero di nodi e il numero di archi determina il tempo totale.

Abstract
Tipologia del documento
Tesi di laurea (Laurea)
Autore della tesi
Paolino, Carmine
Relatore della tesi
Correlatore della tesi
Scuola
Corso di studio
Ordinamento Cds
DM509
Parole chiave
PageRank, Parallel, Distributed, Network, Analysis, C++, BGL, PBGL, Boost, Graph, Library, Scalability, Grafi, Calcolo, Parallelo, Analisi, Scalabilità, Reti
Data di discussione della Tesi
23 Marzo 2011
URI

Altri metadati

Statistica sui download

Gestione del documento: Visualizza il documento

^