Scalable and High Performance Betweenness Centrality on the GPU
School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0250
26th ACM/IEEE International Conference on High Performance Computing, Networking, Storage, and Analysis (SC), 2014
@article{mclaughlin2014scalable,
title={Scalable and High Performance Betweenness Centrality on the GPU},
author={McLaughlin, Adam and Bader, David A},
year={2014}
}
Graphs that model social networks, numerical simulations, and the structure of the Internet are enormous and cannot be manually inspected. A popular metric used to analyze these networks is betweenness centrality, which has applications in community detection, power grid contingency analysis, and the study of the human brain. However, these analyses come with a high computational cost that prevents the examination of large graphs of interest. Prior GPU implementations suffer from large local data structures and inefficient graph traversals that limit scalability and performance. Here we present several hybrid GPU implementations, providing good performance on graphs of arbitrary structure rather than just scale-free graphs as was done previously. We achieve up to 13x speedup on high-diameter graphs and an average of 2.71x speedup overall over the best existing GPU algorithm. We observe near linear speedup and performance exceeding tens of GTEPS when running betweenness centrality on 192 GPUs.
August 1, 2014 by hgpu
