A (Somewhat Dated) Comparative Study of Betweenness Centrality Algorithms on GPU
Department of Computer Science and Engineering, University of Connecticut, Storrs, CT-06226
arXiv:1409.7764 [cs.SI], (27 Sep 2014)
@article{2014arXiv1409.7764Q,
author={Quader}, S.},
title={"{A (Somewhat Dated) Comparative Study of Betweenness Centrality Algorithms on GPU}"},
journal={ArXiv e-prints},
archivePrefix={"arXiv"},
eprint={1409.7764},
keywords={Computer Science – Social and Information Networks, Computer Science – Distributed, Parallel, and Cluster Computing, Computer Science – Data Structures and Algorithms},
year={2014},
month={sep},
adsurl={http://adsabs.harvard.edu/abs/2014arXiv1409.7764Q},
adsnote={Provided by the SAO/NASA Astrophysics Data System}
}
The problem of computing the Betweenness Centrality (BC) is important in analyzing graphs in many practical applications like social networks, biological networks, transportation networks, electrical circuits, etc. Since this problem is computation intensive, researchers have been developing algorithms using high performance computing resources like supercomputers, clusters, and Graphics Processing Units (GPUs). Current GPU algorithms for computing BC employ Brandes’ sequential algorithm with different trade-offs for thread scheduling, data structures, and atomic operations. In this paper, we study three GPU algorithms for computing BC of unweighted, directed, scale-free networks. We discuss and measure the trade-offs of their design choices about balanced thread scheduling, atomic operations, synchronizations and latency hiding. Our program is written in NVIDIA CUDA C and was tested on an NVIDIA Tesla M2050 GPU.
September 30, 2014 by hgpu
