Scalable betweenness centrality on multi GPU systems
Betweenness Centrality (BC) is steadily growing in popularity as a metrics of the influence of a vertex in a graph. The BC score of a vertex is proportional to the number of all pairs shortest paths passing through it. However, complete and exact BC computation for a large scale graph is an extraordinary challenge that requires high performance computing techniques to provide results in a reasonable amount of time. Our approach combines bi dimensional (2 D) decomposition of the graph and multi level parallelism together with a suitable data thread mapping that overcomes most of the difficulties caused by the irregularity of the computation on GPUs. In order to reduce time and space requirements of BC computation, a heuristics based on 1 degree reduction technique is developed as well. Experimental results on synthetic and real world graphs show that the proposed techniques are well suited to compute BC scores in graphs which are too large to fit in the memory of a single computational node.
Conf. Computing Frontiers