Accelerating GPU Betweenness Centrality.
Graphs that model social networks, numerical simulations, and the structure of the Internet are enormous and cannot be manually inspected. A popular metric used to analyze these networks is Betweenness Centrality (BC), which has applications in community detection, power grid contingency analysis, a...
| Published in: | Communications of the ACM Vol. 61; no. 8; pp. 85 - 93 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Published: |
Association for Computing Machinery
Aug2018
|
| Subjects: | |
| Online Access: | View this record in EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=131002275&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 131002275 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Aug2018 vid: 61 iid: 8 pid: 68 pub: Association for Computing Machinery artinfo: ui: 131002275 10.1145/3230485 ppf: 85 ppct: 8 formats: tig: atl: Accelerating GPU Betweenness Centrality. aug: au: McLaughlina, Adam Bader, David A. affil: School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA, USA School of Computational Science and Engineering, Georgia Institute of Technology, Atlanta, GA, USA su: Betweenness relations (Mathematics) Graphics processing units Big data Data structures Social networks sug: subj: Betweenness relations (Mathematics) Graphics processing units Big data Data structures Social networks ab: Graphs that model social networks, numerical simulations, and the structure of the Internet are enormous and cannot be manually inspected. A popular metric used to analyze these networks is Betweenness Centrality (BC), which has applications in community detection, power grid contingency analysis, and the study of the human brain. However, these analyses come with a high computational cost that prevents the examination of large graphs of interest. Recently, the use of Graphics Processing Units (GPUs) has been promising for efficient processing of unstructured data sets. Prior GPU implementations of BC suffer from large local data structures and inefficient graph traversals that limit scalability and performance. Here we present a hybrid GPU implementation that provides good performance on graphs of arbitrary structure rather than just scale-free graphs as was done previously. Our methods achieve up to 13x speedup on high-diameter graphs and an average of 2.71x speedup overall compared to the best existing GPU algorithm. We also observe near linear speedup when running BC on 192 GPUs. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2018 holdings: @attributes: islocal: N |
|---|