Abstract
High compute power provided by the many-threaded SIMT model of Graphics Processing Units (GPUs) accompanied with the recent advancements in their programmability has allowed expression of massively parallel computations. Graph processing is one of the applications that expose such parallelism, and hence, candidates GPUs as attractive execution platforms. However, irregularities in large real-world graphs makes effective and scalable utilization of symmetric GPU architecture a challenging task. While degree distribution in graphs extracted from real-world origins is usually power law, GPUs demand homogeneous computation patterns on consecutive data elements. This article summarizes recent research advancements to overcome this challenge. We first overview the main concepts in the field of graph processing on GPUs . Then, we introduce novel graph representations that, unlike conventional storage formats, are a better match for GPUs . We then present a GPU-friendly decomposition scheme that provides balanced thread to task assignment and enhances the scalability and the execution performance. Finally, we discuss a set of techniques that allow scaling the computation over multiple GPUs efficiently.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
F. Khorasani, K. Vora, R. Gupta, L.N. Bhuyan, 2014. CuSha: vertex-centric graph processing on GPUs, in Proceedings of the 23rd International Symposium on High-Performance Parallel and Distributed Computing (HPDC ’14) (ACM, New York, NY, USA), pp. 239–252. https://doi.org/10.1145/2600212.2600227
S. Hong, S.K Kim, T. Oguntebi, K. Olukotun, Accelerating CUDA graph algorithms at maximum warp, in Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP ’11) (ACM, New York, NY, USA, 2011), pp. 267–276. https://doi.org/10.1145/1941553.1941590
A. Gharaibeh, L.B. Costa, E. Santos-Neto, M. Ripeanu, A yoke of oxen and a thousand chickens for heavy lifting graph processing, in 2012 21st International Conference on Parallel Architectures and Compilation Techniques (PACT) (Minneapolis, MN, 2012), pp. 345–354
F. Khorasani, R. Gupta, L.N. Bhuyan, Scalable SIMD-efficient graph processing on GPUs, in 2015 International Conference on Parallel Architecture and Compilation (PACT) (San Francisco, CA, 2015), pp. 39–50. https://doi.org/10.1109/PACT.2015.15
A. Kyrola, G.E. Blelloch, C. Guestrin, textitGraphchi: Large-scale graph computation on just a pc (USENIX, 2012)
P. Harish, P.J. Narayanan, Accelerating large graph algorithms on the GPU using CUDA. HiPC 7, 197–208 (2007)
F. Khorasani, High Performance Vertex-Centric Graph Analytics on GPUs (University of California, Riverside, PhD diss., 2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this chapter
Cite this chapter
Khorasani, F. (2018). High Performance and Scalable Graph Computation on GPUs. In: Amini, M., Boroojeni, K., Iyengar, S., Pardalos, P., Blaabjerg, F., Madni, A. (eds) Sustainable Interdependent Networks. Studies in Systems, Decision and Control, vol 145. Springer, Cham. https://doi.org/10.1007/978-3-319-74412-4_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-74412-4_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-74411-7
Online ISBN: 978-3-319-74412-4
eBook Packages: EngineeringEngineering (R0)