Abstract
There are two major challenges for large-scale graph analytic processing, computational intensiveness caused by complex graph primitives and distributed data management caused by data of massive scales. Existing works on graph data management with CPU-based distributed systems or GPU-based single-node systems only partially solve the problem. Hence, it is desired to have a general graph processing system for both scaling out and scaling up. In this paper, we demonstrate GPUGraphX, a GPU-aided distributed graph processing system which utilizes computation capacities of GPUs for efficiency while taking the advantages of distributed systems for scalability. Results on representative graph algorithms on real datasets evaluate our proposals.
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
Notes
- 1.
Code Repository: https://github.com/Kamosphere/spark-GPUGraphX.
- 2.
The four parts correspond to the four stages of a GraphX iteration during the execution, aggregateMessageswithActiveSet@GraphImpl.scala, shipVertexAttributes@VertexRDDImpl.scala, shipVertexIds@VertexRDDImpl.scala, and count@VertexRDDImpl.scala.
References
Batarfi, O., El Shawi, R., et al.: Large scale graph processing systems: survey and an experimental evaluation. Clust. Comput. 18(3), 1189–1213 (2015)
Bauer, M., Treichler, S., et al.: Legion: expressing locality and independence with logical regions. In: SC, p. 66 (2012)
Gill, G., Dathathri, R., et al.: Abelian: a compiler for graph analytics on distributed, heterogeneous platforms. In: Euro-Par, pp. 249–264 (2018)
Gonzalez, J.E., Xin, R.S., et al.: Graphx: graph processing in a distributed dataflow framework. In: OSDI, pp. 599–613 (2014)
Gonzalez, J.E., Low, Y., et al.: Powergraph: distributed graph-parallel computation on natural graphs. In: OSDI, pp. 17–30 (2012)
Gregor, D., Lumsdaine, A.: The parallel BGL: a generic library for distributed graph computations. In: POOSC (2005)
Han, M., Daudjee, K., et al.: An experimental comparison of pregel-like graph processing systems. PVLDB 7(12), 1047–1058 (2014)
Jia, Z., Kwon, Y., et al.: A distributed multi-GPU system for fast graph processing. VLDB 11(3), 297–310 (2017)
Leskovec, J., Krevl, A.: SNAP datasets: Stanford large network dataset collection (2014). http://snap.stanford.edu/data
Liu, Y., Xie, X.: Xy-sketch: on sketching data streams at web scale. In: WWW, pp. 1169–1180 (2021)
Lu, Y., Cheng, J., et al.: Large-scale distributed graph computing systems: an experimental evaluation. PVLDB 8(3), 281–292 (2014)
Luo, J., Cao, X., Xie, X., Qu, Q., Xu, Z., Jensen, C.S.: Efficient attribute-constrained co-located community search. In: ICDE, pp. 1201–1212 (2020)
Malewicz, G., Austern, M.H., et al.: Pregel: a system for large-scale graph processing. In: SIGMOD, pp. 135–146 (2010)
Mislove, A., Marcon, M., et al.: Measurement and analysis of online social networks. In: IMC (2007)
Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: AAAI (2015). http://networkrepository.com
Saleem, M.A., Kumar, R., Calders, T., Xie, X., Pedersen, T.B.: Location influence in location-based social networks. In: WSDM, pp. 621–630 (2017)
Shun, J., Blelloch, G.E.: Ligra: a lightweight graph processing framework for shared memory. In: PPoPP, pp. 135–146 (2013)
Wang, Y., Davidson, A.A., et al.: Gunrock: a high-performance graph processing library on the GPU. In: PPoPP, pp. 11:1–11:12 (2016)
Watkins, N.: Programmable storage. Ph.D. thesis, University of California, Santa Cruz, USA (2018)
Wu, F., Xie, X., Shi, J.: Top-k closest pair queries over spatial knowledge graph. In: DASFAA, pp. 625–640 (2021)
Xie, X., Mei, B., Chen, J., Du, X., Jensen, C.S.: Elite: an elastic infrastructure for big spatiotemporal trajectories. VLDB J. 25(4), 473–493 (2016)
Xie, X., Yiu, M.L., Cheng, R., Lu, H.: Scalable evaluation of trajectory queries over imprecise location data. TKDE 26(8), 2029–2044 (2014)
Zhong, J., He, B.: Medusa: a parallel graph processing system on graphics processors. SIGMOD Rec. 43(2), 35–40 (2014)
Acknowledgments
This work is partially supported by NSFC (No. 61772492, 62072428) and the CAS Pioneer Hundred Talents Program. The numerical calculations in this paper have been done on the supercomputing system in the Supercomputing Center of University of Science and Technology of China.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Li, Q., Zou, K., Kong, D., Guan, H., Xie, X. (2021). GPUGraphX: A GPU-Aided Distributed Graph Processing System. In: Zhang, W., Zou, L., Maamar, Z., Chen, L. (eds) Web Information Systems Engineering – WISE 2021. WISE 2021. Lecture Notes in Computer Science(), vol 13081. Springer, Cham. https://doi.org/10.1007/978-3-030-91560-5_38
Download citation
DOI: https://doi.org/10.1007/978-3-030-91560-5_38
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-91559-9
Online ISBN: 978-3-030-91560-5
eBook Packages: Computer ScienceComputer Science (R0)