Loading...
Please wait, while we are loading the content...
Similar Documents
Betweenness Centrality in an HSA-enabled System
| Content Provider | ACM Digital Library |
|---|---|
| Author | Gallmeier, Jonathan Orr, Marc Che, Shuai Rodgers, Gregory |
| Abstract | This paper studies different approaches to implementing betweenness centrality in a heterogeneous system. Betweenness centrality is an important algorithm in graph processing. It presents multiple levels of parallelism when processing a graph, and is an interesting problem to exploit various optimizations. We implement different versions of betweenness centrality on an AMD accelerated processing unit (APU). These include GPU-only implementations with two edge distribution methods, GPU-side load balancing, CPU-GPU load balancing in a master-worker model with queue monitoring and in a work stealing model. We take advantage of the latest development of heterogeneous system architecture (HSA), such as the features of unified virtual address space and diverse atomics. We also use different memory scope and ordering options for different synchronization scenarios. We compare multiple implementations of betweenness centrality, analyze their performance, and discuss important future research directions. |
| Starting Page | 35 |
| Ending Page | 38 |
| Page Count | 4 |
| File Format | |
| ISBN | 9781450343503 |
| DOI | 10.1145/2915516.2915526 |
| Language | English |
| Publisher | Association for Computing Machinery (ACM) |
| Publisher Date | 2016-05-31 |
| Publisher Place | New York |
| Access Restriction | Subscribed |
| Subject Keyword | Work stealing Betweenness centrality Heterogeneous computing |
| Content Type | Text |
| Resource Type | Article |
