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


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.
Number of pages14
ISBN (Print)9780123859631
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