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

Fingerprint

Complex networks
Processing
Resource allocation
Synchronization
Throughput
Data storage equipment

ASJC Scopus subject areas

  • Computer Science(all)

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

Edge v. Node Parallelism for Graph Centrality Metrics. / Jia, Yuntao; Lu, Victor; Hoberock, Jared; Garland, Michael; Hart, John C.

GPU Computing Gems Jade Edition. Elsevier Inc., 2012. p. 15-28.

Research output: Chapter in Book/Report/Conference proceedingChapter

Jia, Y, Lu, V, Hoberock, J, Garland, M & Hart, JC 2012, Edge v. Node Parallelism for Graph Centrality Metrics. in GPU Computing Gems Jade Edition. Elsevier Inc., pp. 15-28. https://doi.org/10.1016/B978-0-12-385963-1.00002-2
Jia Y, Lu V, Hoberock J, Garland M, Hart JC. Edge v. Node Parallelism for Graph Centrality Metrics. In GPU Computing Gems Jade Edition. Elsevier Inc. 2012. p. 15-28 https://doi.org/10.1016/B978-0-12-385963-1.00002-2
Jia, Yuntao ; Lu, Victor ; Hoberock, Jared ; Garland, Michael ; Hart, John C. / Edge v. Node Parallelism for Graph Centrality Metrics. GPU Computing Gems Jade Edition. Elsevier Inc., 2012. pp. 15-28
@inbook{a5f239f80a24499f89d9e3aee351f8a2,
title = "Edge v. Node Parallelism for Graph Centrality Metrics",
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.",
author = "Yuntao Jia and Victor Lu and Jared Hoberock and Michael Garland and Hart, {John C}",
year = "2012",
month = "12",
day = "1",
doi = "10.1016/B978-0-12-385963-1.00002-2",
language = "English (US)",
isbn = "9780123859631",
pages = "15--28",
booktitle = "GPU Computing Gems Jade Edition",
publisher = "Elsevier Inc.",

}

TY - CHAP

T1 - Edge v. Node Parallelism for Graph Centrality Metrics

AU - Jia, Yuntao

AU - Lu, Victor

AU - Hoberock, Jared

AU - Garland, Michael

AU - Hart, John C

PY - 2012/12/1

Y1 - 2012/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84882551380&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84882551380&partnerID=8YFLogxK

U2 - 10.1016/B978-0-12-385963-1.00002-2

DO - 10.1016/B978-0-12-385963-1.00002-2

M3 - Chapter

AN - SCOPUS:84882551380

SN - 9780123859631

SP - 15

EP - 28

BT - GPU Computing Gems Jade Edition

PB - Elsevier Inc.

ER -