Revisiting edge and node parallelism for dynamic GPU graph analytics

Adam McLaughlin, David A. Bader

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014
PublisherIEEE Computer Society
Pages1396-1406
Number of pages11
ISBN (Electronic)9780769552088
DOIs
StatePublished - Nov 27 2014
Externally publishedYes
Event28th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014 - Phoenix, United States
Duration: May 19 2014May 23 2014

Publication series

NameProceedings - IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014

Conference

Conference28th IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2014
Country/TerritoryUnited States
CityPhoenix
Period5/19/145/23/14

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Hardware and Architecture
  • Software

Keywords

  • Betweenness Centrality
  • GPUs
  • Graph Analytics

Fingerprint

Dive into the research topics of 'Revisiting edge and node parallelism for dynamic GPU graph analytics'. Together they form a unique fingerprint.

Cite this