Edge v. Node Parallelism for Graph Centrality Metrics

Yuntao Jia, Victor Lu, Jared Hoberock, Michael Garland, John C. Hart

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

This chapter proposes an improved edge-parallel approach for computing centrality metrics that can also accelerate breadth-first search and all-pairs shortest path. For some graph algorithms such as computing centrality, breadth-first search, and even all-pairs shortest path, an edge-parallel approach improves graphical processing unit (GPU) throughput with better load balancing and less thread divergence on scale-free networks. The edge-parallel approach is less appropriate for grids, meshes, and other graphs with low-degree variance, and it performs less well on dense graphs with many edges. The edge-parallel approach requires more GPU memory than node-parallel, which could limit its application to larger graphs than the considered, for which one could investigate efficient inter-block synchronization techniques. It has been believed the edge-parallel approach would benefit most scale-free network applications and should be investigated on further graph algorithms such as max flow.

Original languageEnglish (US)
Title of host publicationGPU Computing Gems Jade Edition
PublisherElsevier Inc.
Pages15-28
Number of pages14
ISBN (Print)9780123859631
DOIs
StatePublished - Dec 1 2012

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Edge v. Node Parallelism for Graph Centrality Metrics'. Together they form a unique fingerprint.

  • Cite this

    Jia, Y., Lu, V., Hoberock, J., Garland, M., & Hart, J. C. (2012). Edge v. Node Parallelism for Graph Centrality Metrics. In GPU Computing Gems Jade Edition (pp. 15-28). Elsevier Inc.. https://doi.org/10.1016/B978-0-12-385963-1.00002-2