12869

A (Somewhat Dated) Comparative Study of Betweenness Centrality Algorithms on GPU

Saad Quader
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}

}

Download Download (PDF)   View View   Source Source   

770

views

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.
No votes yet.
Please wait...

* * *

* * *

Featured events

2018
November
27-30
Hida Takayama, Japan

The Third International Workshop on GPU Computing and AI (GCA), 2018

2018
September
19-21
Nagoya University, Japan

The 5th International Conference on Power and Energy Systems Engineering (CPESE), 2018

2018
September
22-24
MediaCityUK, Salford Quays, Greater Manchester, England

The 10th International Conference on Information Management and Engineering (ICIME), 2018

2018
August
21-23
No. 1037, Luoyu Road, Hongshan District, Wuhan, China

The 4th International Conference on Control Science and Systems Engineering (ICCSSE), 2018

2018
October
29-31
Nanyang Executive Centre in Nanyang Technological University, Singapore

The 2018 International Conference on Cloud Computing and Internet of Things (CCIOT’18), 2018

HGPU group © 2010-2018 hgpu.org

All rights belong to the respective authors

Contact us: