Cited By
View all- Bao ZChen CZhang W(2018)Task Scheduling of Data-Parallel Applications on HSA PlatformData Science10.1007/978-981-13-2203-7_35(452-461)Online publication date: 9-Sep-2018
Betweenness Centrality in an HSA-enabled System
Pages 35 - 38
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.
References
[1]
The 10th DIMACS Implementation Challenge Graph Partitioning and Graph Clustering. Web resource. http://www.cc.gatech.edu/dimacs10/.
[2]
U. Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25:163--177, 2001.
[3]
S. Che, G. Rodgers, B. Beckmann, and S. Reinhardt. Graph coloring on the GPU and some techniques to improve load imbalance. In Proceedings of the Fifth International Workshop on Accelerators and Hybrid Exascale Systems, May 2015.
[4]
CL Offline Compiler and SNACK. Web resource. https://github.com/HSAFoundation/CLOC.
[5]
Graph input for interacting proteins. Web resource. http://www.sommer.jp/graphs/.
[6]
Heterogeneous System Architecture: A Technical Review. Web resource. http://developer.amd.com/wordpress/media/2012/10/hsa10.pdf.
[7]
Heterogeneous System Architecture (HSA). Web resource. http://hsafoundation.com/.
[8]
Y. Jia, V. Lu, J. Hoberock, M. Garland, and J. C. Hart. Edge v. node parallelism for graph centrality metrics. GPU Computing Gems, 2:15--30, 2011.
[9]
D. Kaeli, P. Mistry, D. Schaa, and D. P. Zhang. Heterogeneous Computing with OpenCL 2.0. Morgan Kaufmann, 2015.
[10]
A. McLaughlin and D. Bader. Scalable and high performance betweenness centrality on the GPU. In Proceedings of Supercomputing Conference, Nov 2014.
[11]
GTGraph: A Suite of Synthetic Random Graph Generators. Web resource. http://www.cse.psu.edu/ madduri/software/GTgraph/index.html.
[12]
OpenCL. Web resource. http://www.khronos.org/opencl/.
[13]
A. E. Sariyuce, K. Kaya, E. Saule, and U. V. Catalyurek. Betweenness centrality on GPUs and heterogeneous architectures. In Proceedings of the 6th Workshop on General Purpose Processor Using Graphics Processing Units, Mar 2013.
[14]
Z. Shi and B. Zhang. Fast network centrality analysis using GPUs. BMC Bioinformatics, 12(149), 2011.
[15]
The University of Florida Sparse Matrix Collection. Web resource. http://www.cise.ufl.edu/research/sparse/matrices/.
[16]
P. Tsigas and D. Cedermann. GPU Computing Gems Jade Edition, chapter Dynamic Load Balancing Using Work-Stealing. Morgan Kaufmann, 2011.
[17]
Y. Wang, A. Davidson, Y. Pan, Y. Wu, A. Riffel, and J. D. Owens. Gunrock: A high-performance graph processing library on the GPU. In Proceedings of the 21st Symposium on Principles and Practice of Parallel Programming, Mar 2016.
Index Terms
- Betweenness Centrality in an HSA-enabled System
Recommendations
Betweenness centrality on GPUs and heterogeneous architectures
GPGPU-6: Proceedings of the 6th Workshop on General Purpose Processor Using Graphics Processing UnitsThe betweenness centrality metric has always been intriguing for graph analyses and used in various applications. Yet, it is one of the most computationally expensive kernels in graph mining. In this work, we investigate a set of techniques to make the ...
Regularizing graph centrality computations
Centrality metrics such as betweenness and closeness have been used to identify important nodes in a network. However, it takes days to months on a high-end workstation to compute the centrality of today's networks. The main reasons are the size and the ...
Preliminary Experiments with XKaapi on Intel Xeon Phi Coprocessor
SBAC-PAD '13: Proceedings of the 2013 25th International Symposium on Computer Architecture and High Performance ComputingThis paper presents preliminary performance comparisons of parallel applications developed natively for the Intel Xeon Phi accelerator using three different parallel programming environments and their associated runtime systems. We compare Intel OpenMP, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2016
60 pages
ISBN:9781450343503
DOI:10.1145/2915516
- General Chairs:
- Toyotaro Suzumura,
- Dario Garcia-Gasulla,
- Program Chair:
- Miyuru Dayarathna
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
- University of Arizona: University of Arizona
- SIGARCH: ACM Special Interest Group on Computer Architecture
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 31 May 2016
Check for updates
Author Tags
Qualifiers
- Short-paper
Conference
HPDC'16
Sponsor:
- University of Arizona
- SIGARCH
HPDC'16: The 25th International Symposium on High-Performance Parallel and Distributed Computing
May 31, 2016
Kyoto, Japan
Acceptance Rates
HPGP '16 Paper Acceptance Rate 5 of 6 submissions, 83%;
Overall Acceptance Rate 5 of 6 submissions, 83%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 152Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 17 Feb 2025
Other Metrics
Citations
Cited By
View all- Bao ZChen CZhang W(2018)Task Scheduling of Data-Parallel Applications on HSA PlatformData Science10.1007/978-981-13-2203-7_35(452-461)Online publication date: 9-Sep-2018
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in