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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione