Revisiting Edge and Node Parallelism for Dynamic GPU Graph Analytics

Adam McLaughlin, David A. Bader
School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0250
8th Workshop on Multithreaded Architectures and Applications (MTAAP), 2014


   title={Revisiting Edge and Node Parallelism for Dynamic GPU Graph Analytics},

   author={McLaughlin, Adam and Bader, David A},

   booktitle={Eighth Workshop on Multithreaded Architectures and Applications (MTAAP)},

   location={Phoenix, Arizona, USA},



Download Download (PDF)   View View   Source Source   



Betweenness Centrality is a widely used graph analytic that has applications such as finding influential people in social networks, analyzing power grids, and studying protein interactions. However, its complexity makes its exact computation infeasible for large graphs of interest. Furthermore, networks tend to change over time, invalidating previously calculated results and encouraging new analyses regarding how centrality metrics vary with time. While GPUs have dominated regular, structured application domains, their high memory throughput and massive parallelism has made them a suitable target architecture for irregular, unstructured applications as well. In this paper we compare and contrast two GPU implementations of an algorithm for dynamic betweenness centrality. We show that typical network updates affect the centrality scores of a surprisingly small subset of the total number of vertices in the graph. By efficiently mapping threads to units of work we achieve up to a 110x speedup over a CPU implementation of the algorithm and can update the analytic 45x faster on average than a static recomputation on the GPU.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: