Betweenness Centrality (BC) is steadily growing in popularity as a metrics of the inuence of a vertex in a graph. The exact BC computation for a large scale graph is an extraordinary challenging and requires high performance computing techniques to provide results in a reasonable amount of time. Here, we present the techniques we developed to speed-up the computation of the BC on Multi-GPU systems. Our approach combines the bi-dimensional (2-D) decomposition of the graph and multi-level parallelism. Experimental results show that the proposed techniques are well suited to compute BC scores in graphs which are too large to fit in single GPU memory. In particular, the computation time of a 234 million edges graph is reduced to less than 2 hours.

Betweenness centrality on multi-GPU systems / Bernaschi, M.; Carbone, G.; Vella, F.. - ELETTRONICO. - (2015), pp. 1-4. (Intervento presentato al convegno 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015 tenutosi a Austin, TX, USA nel 15th November 2015) [10.1145/2833179.2833192].

Betweenness centrality on multi-GPU systems

Vella F.
2015-01-01

Abstract

Betweenness Centrality (BC) is steadily growing in popularity as a metrics of the inuence of a vertex in a graph. The exact BC computation for a large scale graph is an extraordinary challenging and requires high performance computing techniques to provide results in a reasonable amount of time. Here, we present the techniques we developed to speed-up the computation of the BC on Multi-GPU systems. Our approach combines the bi-dimensional (2-D) decomposition of the graph and multi-level parallelism. Experimental results show that the proposed techniques are well suited to compute BC scores in graphs which are too large to fit in single GPU memory. In particular, the computation time of a 234 million edges graph is reduced to less than 2 hours.
2015
Proceedings of the 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015
New York, USA
Association for Computing Machinery, Inc
9781450340014
Bernaschi, M.; Carbone, G.; Vella, F.
Betweenness centrality on multi-GPU systems / Bernaschi, M.; Carbone, G.; Vella, F.. - ELETTRONICO. - (2015), pp. 1-4. (Intervento presentato al convegno 5th Workshop on Irregular Applications: Architectures and Algorithms, IA3 2015 tenutosi a Austin, TX, USA nel 15th November 2015) [10.1145/2833179.2833192].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/332804
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 15
social impact