Large-Scale Dynamic Graph Processing with Graphic Processing Unit-Accelerated Priority-Driven Differential Scheduling and Operation Reduction
Source abstract
Abstract
Recently, there has been active research on utilizing GPUs for the efficient processing of large-scale dynamic graphs. However, challenges arise due to the repeated transmission and processing of identical data during dynamic graph operations. This paper proposes an efficient processing scheme for large-scale dynamic graphs in GPU environments with limited memory, leveraging dynamic scheduling and operation reduction. The proposed scheme partitions the dynamic graph and schedules each partition based on active and tentative active vertices, optimizing GPU utilization. Additionally, snapshots are employed to capture graph changes, enabling the detection of redundant edge and vertex modifications. This reduces unnecessary computations, thereby minimizing GPU workloads and data transmission costs. The scheme significantly enhances performance by eliminating redundant operations on the same edges or vertices. Performance evaluations demonstrate an average improvement of 280% over existing static graph processing techniques and 108% over existing dynamic graph processing schemes.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Graph Theory and Algorithms · Advanced Graph Neural Networks · Advanced Image and Video Retrieval Techniques
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Information and Communication Engineering, Chungbuk National University Hospital, Chungbuk National University, Chungdae-ro 1, Seowon-gu, Cheongju 28644, Chungcheongbuk-do, Republic of Korea
National Institute of Agricultural Sciences, Nongsaengmyeong-ro 300, Deokjin-gu, Jeonju-si 55365, Jeonbuk-do, Republic of Korea
Department of Computer Engineering, Changwon National University, Changwondaehak-ro 20, Uichang-gu, Changwon-si 51140, Gyeongsangnam-do, Republic of Korea
Department of Artificial Intelligence Convergence, Wonkwang University, Iksandae 460, Iksan 54538, Jeollabuk-do, Republic of Korea
Funding
MSIT (Ministry of Science and ICT) · Rural Development Administration, Republic of Korea
References (40)
Show source-provided references
1. Green, O., and Bader, D.A. (2016, January 13–15). CuSTINGER: Supporting Dynamic Graph Algorithms for GPUs. Proceedings of the IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.10.1109/HPEC.2016.7761622 ↗
2. Busato, F., Green, O., Bombieri, N., and Bader, D.A. (2018, January 25–27). Hornet: An Efficient Data Structure for Dynamic Sparse Graphs and Matrices on GPUs. Proceedings of the 2018 IEEE High Performance extreme Computing Conference (HPEC), Waltham, MA, USA.10.1109/HPEC.2018.8547541 ↗
3. Accelerating Dynamic Graph Analytics on GPUs10.14778/3151113.3151122 ↗
4. An Efficient Data Structure for Dynamic Graph on GPUs10.1109/TKDE.2023.3235941 ↗
5. Winter, M., Zayer, R., and Steinberger, M. (2017, January 12–14). Autonomous, Independent Management of Dynamic Graphs on GPUs. Proceedings of the 2017 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA.10.1109/HPEC.2017.8091058 ↗
6. Winter, M., Mlakar, D., Zayer, R., Seidel, H.-P., and Steinberger, M. (2018, January 11–16). FaimGraph: High Performance Management of Fully-Dynamic Graphs under Tight Memory Constraints on the GPU. Proceedings of the Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis, Dallas, TX, USA.10.1109/SC.2018.00063 ↗
7. EGraph: Efficient Concurrent GPU-Based Dynamic Graph Processing
8. Gao, H., Liao, X., Shao, Z., Li, K., Chen, J., and Jin, H. (2023). A Survey on Dynamic Graph Processing on GPUs: Concepts, Terminologies, and Systems. Front. Comput. Sci., 18.10.1007/s11704-023-2656-1 ↗
9. PMGraph: Accelerating Concurrent Graph Queries Over Streaming Graphs10.1145/3689337 ↗
10. Recent Advances in Fully Dynamic Graph Algorithms—A Quick Reference Guide
11. Pandey, P., Wheatman, B., Xu, H., and Buluc, A. (2021, January 20–25). Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs. Proceedings of the ACM SIGMOD International Conference on Management of Data, Xi’an, Shaanxi, China.10.1145/3448016.3457313 ↗
12. Vaziri, P., and Vora, K. (2021, January 14–16). Controlling Memory Footprint of Stateful Streaming Graph Processing. Proceedings of the 2021 USENIX Annual Technical Conference (USENIX ATC 21), Virtual, Santa Clara, CA, USA. Available online: https://www.usenix.org/conference/atc21/presentation/vaziri.
13. Jiang, Z., Mao, F., Guo, Y., Liu, X., Liu, H., Liao, X., Jin, H., and Zhang, W. (2023, January 9–13). ACGraph: Accelerating Streaming Graph Processing via Dependence Hierarchy. Proceedings of the 60th ACM/IEEE Design Automation Conference (DAC), San Francisco, CA, USA.10.1109/DAC56929.2023.10247904 ↗
14. Sun, G., Zhou, J., Li, B., Gu, X., Wang, W., and He, S. (2024, January 24–27). FTGraph: A Flexible Tree-Based Graph Store on Persistent Memory for Large-Scale Dynamic Graphs. Proceedings of the 2024 IEEE International Conference on Cluster Computing (CLUSTER), Kobe, Japan.10.1109/CLUSTER59578.2024.00011 ↗
15. Zhao, J., Zhang, Y., Cheng, J., Wu, Y., Ye, C., Yu, H., Huang, Z., Jin, H., Liao, X., and Gu, L. (2023, January 9–13). SaGraph: A Similarity-Aware Hardware Accelerator for Temporal Graph Processing. Proceedings of the 2023 60th ACM/IEEE Design Automation Conference (DAC), San Francisco, CA, USA.10.1109/DAC56929.2023.10247966 ↗
16. Meerkat: A Framework for Dynamic Graph Algorithms on GPUs10.1007/s10766-024-00774-z ↗
17. Cheng, R., Hong, J., Kyrola, A., Miao, Y., Weng, X., Wu, M., Yang, F., Zhou, L., Zhao, F., and Chen, E. (2012, January 10–13). Kineograph: Taking the Pulse of a Fast-Changing and Connected World. Proceedings of the 7th ACM European Conference on Computer Systems, Bern, Switzerland.10.1145/2168836.2168846 ↗
18. Han, W., Miao, Y., Li, K., Wu, M., Yang, F., Zhou, L., Prabhakaran, V., Chen, W., and Chen, E. (2014, January 14–16). Chronos: A Graph Engine for Temporal Graph Analysis. Proceedings of the Ninth European Conference on Computer Systems, Amsterdam, The Netherlands.10.1145/2592798.2592799 ↗
19. Shi, X., Cui, B., Shao, Y., and Tong, Y. (July, January 26). Tornado: A System for Real-Time Iterative Analysis over Evolving Data. Proceedings of the 2016 International Conference on Management of Data, San Francisco, CA, USA.10.1145/2882903.2882950 ↗
20. Sheng, F., Cao, Q., Cai, H., Yao, J., and Xie, C. (2018, January 11–13). GraPU: Accelerate Streaming Graph Analysis through Preprocessing Buffered Updates. Proceedings of the ACM Symposium on Cloud Computing, Carlsbad, CA, USA.10.1145/3267809.3267811 ↗
21. Jaiyeoba, W., and Skadron, K. (2019, January 20–24). GraphTinker: A High-Performance Data Structure for Dynamic Graph Processing. Proceedings of the 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), Rio de Janeiro, Brazil.10.1109/IPDPS.2019.00110 ↗
22. Mariappan, M., Che, J., and Vora, K. (2021, January 26–28). DZiG: Sparsity-Aware Incremental Processing of Streaming Graphs. Proceedings of the Sixteenth European Conference on Computer Systems, Virtual, Edinburgh, UK.10.1145/3447786.3456230 ↗
23. Ediger, D., McColl, R., Riedy, J., and Bader, D.A. (2012, January 10–12). STINGER: High Performance Data Structure for Streaming Graphs. Proceedings of the 2012 IEEE Conference on High Performance Extreme Computing, Waltham, MA, USA.10.1109/HPEC.2012.6408680 ↗
24. An Adaptive Packed-Memory Array10.1145/1292609.1292616 ↗
25. Kim, M.-S., An, K., Park, H., Seo, H., and Kim, J. (July, January 26). GTS: A Fast and Scalable Graph Processing Method Based on Streaming Topology to GPUs. Proceedings of the 2016 International Conference on Management of Data, San Francisco, CA, USA.10.1145/2882903.2915204 ↗
26. Khorasani, F., Vora, K., Gupta, R., and Bhuyan, L.N. (2014, January 23–27). CuSha: Vertex-Centric Graph Processing on GPUs. Proceedings of the 23rd International Symposium on High-Performance Parallel and Distributed Computing, Vancouver, BC, Canada.10.1145/2600212.2600227 ↗
27. Wang, Y., Davidson, A., Pan, Y., Wu, Y., Riffel, A., and Owens, J.D. (2016, January 12–16). Gunrock: A High-Performance Graph Processing Library on the GPU. Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Barcelona, Spain.10.1145/2851141.2851145 ↗
28. Gharaibeh, A., Beltrão Costa, L., Santos-Neto, E., and Ripeanu, M. (2012, January 19–23). A Yoke of Oxen and a Thousand Chickens for Heavy Lifting Graph Processing. Proceedings of the 21st International Conference on Parallel Architectures and Compilation Techniques, Minneapolis, MN, USA.10.1145/2370816.2370866 ↗
29. Ma, L., Yang, Z., Chen, H., Xue, J., and Dai, Y. (2017, January 12–14). Garaph: Efficient {GPU-Accelerated} Graph Processing on a Single Machine with Balanced Replication. Proceedings of the 2017 USENIX Annual Technical Conference (USENIX ATC 17), Santa Clara, CA, USA. Available online: https://www.usenix.org/conference/atc17/technical-sessions/presentation/ma.
30. Zheng, L., Li, X., Zheng, Y., Huang, Y., Liao, X., Jin, H., Xue, J., Shao, Z., and Hua, Q.-S. (2020, January 15–17). Scaph: Scalable GPU-Accelerated Graph Processing with Value-Driven Differential Scheduling. Proceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference, Boston, MA, USA.
31. Sabet, A.H.N., Zhao, Z., and Gupta, R. (2020, January 27–30). Subway: Minimizing Data Transfer During Out-of-GPU-Memory Graph Processing. Proceedings of the Fifteenth European Conference on Computer Systems, Heraklion, Greece.10.1145/3342195.3387537 ↗
32. Han, W., Mawhirter, D., Wu, B., and Buland, M. (2017, January 9–13). Graphie: Large-Scale Asynchronous Graph Traversals on Just a GPU. Proceedings of the 26th International Conference on Parallel Architectures and Compilation Techniques (PACT), Portland, OR, USA.10.1109/PACT.2017.41 ↗
33. Wang, Q., Ai, X., Zhang, Y., Chen, J., and Yu, G. (2023, January 3–7). HyTGraph: GPU-Accelerated Graph Processing with Hybrid Transfer Management. Proceedings of the 2023 IEEE 39th International Conference on Data Engineering (ICDE), Anaheim, CA, USA. Available online: https://doi.ieeecomputersociety.org/10.1109/ICDE55515.2023.00049.10.1109/ICDE55515.2023.00049 ↗
34. Graph Processing Scheme Using GPU With Value-Driven Differential Scheduling10.1109/ACCESS.2024.3374513 ↗
35. Low, Y., Gonzalez, J., Kyrola, A., Bickson, D., Guestrin, C., and Hellerstein, J.M. (2012). Distributed GraphLab: A Framework for Machine Learning in the Cloud. arXiv.10.14778/2212351.2212354 ↗
36. Gonzalez, J.E., Low, Y., Gu, H., Bickson, D., and Guestrin, C. (2012, January 8–10). {PowerGraph}: Distributed {Graph-Parallel} Computation on Natural Graphs. Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12), Hollywood, CA, USA. Available online: https://www.usenix.org/conference/osdi12/technical-sessions/presentation/gonzalez.
37. HotGraph: Efficient Asynchronous Processing for Real-World Graphs10.1109/TC.2016.2624289 ↗
38. Wonderland: A Novel Abstraction-Based Out-of-Core Graph Processing System10.1145/3296957.3173208 ↗
39. Malewicz, G., Austern, M.H., Bik, A.J.C., Dehnert, J.C., Horn, I., Leiser, N., and Czajkowski, G. (2010, January 6–10). Pregel: A System for Large-Scale Graph Processing. Proceedings of the ACM SIGMOD International Conference on Management of Data, Indianapolis, IN, USA.10.1145/1582716.1582723 ↗
40. (2025, February 08). Suite Sparse Matric Collection, Formerly the University of Florida Sparse Matric Collection. Available online: https://sparse.tamu.edu.