{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,19]],"date-time":"2026-08-19T18:07:32Z","timestamp":1787162852168,"version":"build-2736575974"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:p>In recent years, many CPU-GPU heterogeneous graph processing systems have been developed in both academic and industrial to facilitate large-scale graph processing in various applications, e.g., social networks and biological networks. However, the performance of existing systems can be significantly improved by addressing two prevailing challenges: GPU memory over-subscription and efficient CPU-GPU cooperative processing.<\/jats:p>\n                  <jats:p>In this work, we propose CGgraph, an ultra-fast CPU-GPU graph processing system to address these challenges. In particular, CGgraph overcomes GPU-memory over-subscription by extracting a subgraph which only needs to be loaded into GPU memory once, but its vertices and edges can be used in multiple iterations during the graph processing procedure. To support efficient CPU-GPU co-processing, we design a CPU-GPU cooperative processing scheme, which balances the workloads between CPU and GPU by on-demand task allocation. To evaluate the efficiency of CG-graph, we conduct extensive experiments, comparing it with 7 state-of-the-art systems using 4 well-known graph algorithms on 6 real-world graphs. Our prototype system CGgraph outperforms all existing systems, delivering up to an order of magnitude improvement. Moreover, CGgraph on a modern commodity machine with a CPU-GPU co-processor yields superior (or at the very least, comparable) performance compared to existing systems on a high-end CPU-GPU server.<\/jats:p>","DOI":"10.14778\/3648160.3648179","type":"journal-article","created":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T17:52:53Z","timestamp":1714758773000},"page":"1405-1417","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["CGgraph: An Ultra-Fast Graph Processing System on Modern Commodity CPU-GPU Co-processor"],"prefix":"10.14778","volume":"17","author":[{"given":"Pengjie","family":"Cui","sequence":"first","affiliation":[{"name":"Northeastern University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haotian","family":"Liu","sequence":"additional","affiliation":[{"name":"Southern University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bo","family":"Tang","sequence":"additional","affiliation":[{"name":"Southern University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ye","family":"Yuan","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2023. CGgraph source code. https:\/\/github.com\/DBGroup-SUSTech\/CGgraph"},{"key":"e_1_2_1_2_1","unstructured":"2023. CGgraph (Technical Report). https:\/\/github.com\/PengBo410\/CGgraphV1\/blob\/master\/src\/TR\/TR.pdf"},{"key":"e_1_2_1_3_1","unstructured":"2023. Galois. https:\/\/github.com\/IntelligentSoftwareSystems\/Galois"},{"key":"e_1_2_1_4_1","unstructured":"2023. Gemini. https:\/\/github.com\/thu-pacman\/GeminiGraph"},{"key":"e_1_2_1_5_1","unstructured":"2023. Groute. https:\/\/github.com\/groute\/groute"},{"key":"e_1_2_1_6_1","unstructured":"2023. Gunrock. https:\/\/github.com\/gunrock\/gunrock"},{"key":"e_1_2_1_7_1","unstructured":"2023. Subway. https:\/\/github.com\/AutomataLab\/Subway"},{"key":"e_1_2_1_8_1","unstructured":"2023. Totem. https:\/\/github.com\/netsyslab\/Totem"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3155284.3018756"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Paolo Boldi Marco Rosa Massimo Santini and Sebastiano Vigna. 2011. Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In WWW. 587--596.","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_2_1_12_1","first-page":"1","article-title":"CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression","volume":"1","author":"Chen Zheng","year":"2023","unstructured":"Zheng Chen, Feng Zhang, JiaWei Guan, Jidong Zhai, Xipeng Shen, Huanchen Zhang, Wentong Shu, and Xiaoyong Du. 2023. CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression. Proceedings of the ACM on Management of Data 1, 1 (2023), 1--31.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536239"},{"key":"e_1_2_1_14_1","volume-title":"ACM National Conference. 157--172","author":"Cuthill Elizabeth","year":"1969","unstructured":"Elizabeth Cuthill and James McKee. 1969. Reducing the bandwidth of sparse symmetric matrices. In ACM National Conference. 157--172."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Laxman Dhulipala Igor Kabiljo Brian Karrer Giuseppe Ottaviano Sergey Pupyrev and Alon Shalita. 2016. Compressing graphs and indexes with recursive graph bisection. In SIGKDD. 1535--1544.","DOI":"10.1145\/2939672.2939862"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"James Dinan D Brian Larkins Ponnuswamy Sadayappan Sriram Krishnamoorthy and Jarek Nieplocha. 2009. Scalable work stealing. In SC. 1--11.","DOI":"10.1145\/1654059.1654113"},{"key":"e_1_2_1_17_1","volume-title":"A closer look at lightweight graph reordering","author":"Faldu Priyank","unstructured":"Priyank Faldu, Jeff Diamond, and Boris Grot. 2019. A closer look at lightweight graph reordering. In IISWC. IEEE, 1--13."},{"key":"e_1_2_1_18_1","volume-title":"Traversing Large Compressed Graphs on GPUs. In 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 25--35","author":"Gera Prasun","year":"2023","unstructured":"Prasun Gera and Hyesoon Kim. 2023. Traversing Large Compressed Graphs on GPUs. In 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 25--35."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384358"},{"key":"e_1_2_1_20_1","volume-title":"Elizeu Santos-Neto, and Matei Ripeanu.","author":"Gharaibeh Abdullah","year":"2012","unstructured":"Abdullah Gharaibeh, Lauro Beltr\u00e3o Costa, Elizeu Santos-Neto, and Matei Ripeanu. 2012. A yoke of oxen and a thousand chickens for heavy lifting graph processing. In PACT. 345--354."},{"key":"e_1_2_1_21_1","volume-title":"Powergraph: Distributed graph-parallel computation on natural graphs. In OSDI. 17--30.","author":"Gonzalez Joseph E","year":"2012","unstructured":"Joseph E Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. Powergraph: Distributed graph-parallel computation on natural graphs. In OSDI. 17--30."},{"key":"e_1_2_1_22_1","volume-title":"Graphx: Graph processing in a distributed dataflow framework. In OSDI. 599--613.","author":"Gonzalez Joseph E","year":"2014","unstructured":"Joseph E Gonzalez, Reynold S Xin, Ankur Dave, Daniel Crankshaw, Michael J Franklin, and Ion Stoica. 2014. Graphx: Graph processing in a distributed dataflow framework. In OSDI. 599--613."},{"key":"e_1_2_1_23_1","volume-title":"Graphie: Large-scale asynchronous graph traversals on just a GPU. In PACT. 233--245.","author":"Han Wei","year":"2017","unstructured":"Wei Han, Daniel Mawhirter, Bo Wu, and Matthew Buland. 2017. Graphie: Large-scale asynchronous graph traversals on just a GPU. In PACT. 233--245."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"e4","DOI":"10.1017\/S0956796821000277","article-title":"Fregel: a functional domain-specific language for vertex-centric large-scale graph processing","volume":"32","author":"Iwasaki Hideya","year":"2022","unstructured":"Hideya Iwasaki, Kento Emoto, Akimasa Morihata, Kiminori Matsuzaki, and Zhenjiang Hu. 2022. Fregel: a functional domain-specific language for vertex-centric large-scale graph processing. Journal of Functional Programming 32 (2022), e4.","journal-title":"Journal of Functional Programming"},{"key":"e_1_2_1_25_1","volume-title":"Distributed Work Stealing in a Task-Based Dataflow Runtime","author":"John Joseph","unstructured":"Joseph John, Josh Milthorpe, and Peter Strazdins. 2022. Distributed Work Stealing in a Task-Based Dataflow Runtime. In PPAM. Springer, 225--236."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Farzad Khorasani Keval Vora Rajiv Gupta and Laxmi N Bhuyan. 2014. CuSha: vertex-centric graph processing on GPUs. In HPDC. 239--252.","DOI":"10.1145\/2600212.2600227"},{"key":"e_1_2_1_27_1","volume-title":"GTS: A fast and scalable graph processing method based on streaming topology to GPUs. In SIGMOD. 447--461.","author":"Kim Min-Soo","year":"2016","unstructured":"Min-Soo Kim, Kyuhyeon An, Himchan Park, Hyunseok Seo, and Jinwook Kim. 2016. GTS: A fast and scalable graph processing method based on streaming topology to GPUs. In SIGMOD. 447--461."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3380942","article-title":"Gpop: A scalable cache-and memory-efficient framework for graph processing over parts","volume":"7","author":"Lakhotia Kartik","year":"2020","unstructured":"Kartik Lakhotia, Rajgopal Kannan, Sourav Pati, and Viktor Prasanna. 2020. Gpop: A scalable cache-and memory-efficient framework for graph processing over parts. TOPC 7, 1 (2020), 1--24.","journal-title":"TOPC"},{"key":"e_1_2_1_29_1","volume-title":"A survey of algorithms for dense subgraph discovery. Managing and mining graph data","author":"Lee Victor E","year":"2010","unstructured":"Victor E Lee, Ning Ruan, Ruoming Jin, and Charu Aggarwal. 2010. A survey of algorithms for dense subgraph discovery. Managing and mining graph data (2010), 303--336."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Chen Li Rachata Ausavarungnirun Christopher J Rossbach Youtao Zhang Onur Mutlu Yang Guo and Jun Yang. 2019. A framework for memory oversubscription management in graphics processing units. In ASPLOS. 49--63.","DOI":"10.1145\/3297858.3304044"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Hang Liu and H Howie Huang. 2015. Enterprise: breadth-first graph traversal on GPUs. In SC. 1--12.","DOI":"10.1145\/2807591.2807594"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Haotian Liu Bo Tang Jiashu Zhang Yangshen Deng Xiao Yan Xinying Zheng Qiaomu Shen Dan Zeng Zunyao Mao Chaozu Zhang et al. 2022. GHive: accelerating analytical query processing in apache hive via CPU-GPU heterogeneous computing. In SoCC. 158--172.","DOI":"10.1145\/3542929.3563503"},{"key":"e_1_2_1_33_1","volume-title":"James C Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski.","author":"Malewicz Grzegorz","year":"2010","unstructured":"Grzegorz Malewicz, Matthew H Austern, Aart JC Bik, James C Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. 2010. Pregel: a system for large-scale graph processing. In SIGMOD. 135--146."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Ke Meng Jiajia Li Guangming Tan and Ninghui Sun. 2019. A pattern based algorithmic autotuner for graph processing on GPUs. In PPoPP. 201--213.","DOI":"10.1145\/3293883.3295716"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370036.2145832"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Donald Nguyen Andrew Lenharth and Keshav Pingali. 2013. A lightweight infrastructure for graph analytics. In SOSP. 456--471.","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0405-2"},{"key":"e_1_2_1_39_1","volume-title":"Subway: Minimizing data transfer during out-of-GPU-memory graph processing. In EuroSys. 1--16.","author":"Nodehi Sabet Amir Hossein","year":"2020","unstructured":"Amir Hossein Nodehi Sabet, Zhijia Zhao, and Rajiv Gupta. 2020. Subway: Minimizing data transfer during out-of-GPU-memory graph processing. In EuroSys. 1--16."},{"key":"e_1_2_1_40_1","volume-title":"Benchmarking for graph clustering and partitioning. ESNAM","author":"Sanders Peter","year":"2014","unstructured":"Peter Sanders, Christian Schulz, and Dorothea Wagner. 2014. Benchmarking for graph clustering and partitioning. ESNAM (2014)."},{"key":"e_1_2_1_41_1","volume-title":"Kapil Agarwal, and Karsten Schwan.","author":"Sengupta Dipanjan","year":"2015","unstructured":"Dipanjan Sengupta, Shuaiwen Leon Song, Kapil Agarwal, and Karsten Schwan. 2015. Graphreduce: processing large-scale graphs on accelerator-based systems. In SC. 1--12."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319871"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2745562"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Julian Shun and Guy E Blelloch. 2013. Ligra: a lightweight graph processing framework for shared memory. In PPoPP. 135--146.","DOI":"10.1145\/2517327.2442530"},{"key":"e_1_2_1_45_1","volume-title":"Euro-Par 2014 Parallel Processing: 20th International Conference, Porto, Portugal, August 25-29, 2014. Proceedings 20","author":"Simmhan Yogesh","year":"2014","unstructured":"Yogesh Simmhan, Alok Kumbhare, Charith Wickramaarachchi, Soonil Nagarkar, Santosh Ravi, Cauligi Raghavendra, and Viktor Prasanna. 2014. Goffish: A sub-graph centric framework for large-scale graph analytics. In Euro-Par 2014 Parallel Processing: 20th International Conference, Porto, Portugal, August 25-29, 2014. Proceedings 20. Springer, 451--462."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_2_1_47_1","volume-title":"Gpu accelerated voxel grid generation for fast mav exploration. arXiv:2112.13169","author":"Toumieh Charbel","year":"2021","unstructured":"Charbel Toumieh and Alain Lambert. 2021. Gpu accelerated voxel grid generation for fast mav exploration. arXiv:2112.13169 (2021)."},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Hao Wang Liang Geng Rubao Lee Kaixi Hou Yanfeng Zhang and Xiaodong Zhang. 2019. SEP-graph: finding shortest execution paths for graph processing under a hybrid framework on GPU. In PPoPP. 38--52.","DOI":"10.1145\/3293883.3295733"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3444844","article-title":"Grus: Toward unified-memory-efficient high-performance graph processing on gpu","volume":"18","author":"Wang Pengyu","year":"2021","unstructured":"Pengyu Wang, Jing Wang, Chao Li, Jianzong Wang, Haojin Zhu, and Minyi Guo. 2021. Grus: Toward unified-memory-efficient high-performance graph processing on gpu. TACO 18, 2 (2021), 1--25.","journal-title":"TACO"},{"key":"e_1_2_1_50_1","volume-title":"HyTGraph: GPU-Accelerated Graph Processing with Hybrid Transfer Management. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 558--571","author":"Wang Qiange","year":"2023","unstructured":"Qiange Wang, Xin Ai, Yanfeng Zhang, Jing Chen, and Ge Yu. 2023. HyTGraph: GPU-Accelerated Graph Processing with Hybrid Transfer Management. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 558--571."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851145"},{"key":"e_1_2_1_52_1","volume-title":"Can Lu, and Xuemin Lin.","author":"Wei Hao","year":"2016","unstructured":"Hao Wei, Jeffrey Xu Yu, Can Lu, and Xuemin Lin. 2016. Speedup graph processing by graph ordering. In SIGMOD. 1813--1828."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.222"},{"key":"e_1_2_1_54_1","volume-title":"Big Data","author":"Zhang Yunming","unstructured":"Yunming Zhang, Vladimir Kiriansky, Charith Mendis, Saman Amarasinghe, and Matei Zaharia. 2017. Making caches work for graph analytics. In Big Data. IEEE, 293--302."},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3477603","article-title":"LargeGraph: An efficient dependency-aware GPU-accelerated large-scale graph processing","volume":"18","author":"Zhang Yu","year":"2021","unstructured":"Yu Zhang, Da Peng, Xiaofei Liao, Hai Jin, Haikun Liu, Lin Gu, and Bingsheng He. 2021. LargeGraph: An efficient dependency-aware GPU-accelerated large-scale graph processing. TACO 18, 4 (2021), 1--24.","journal-title":"TACO"},{"key":"e_1_2_1_56_1","volume-title":"Graphit: A high-performance graph dsl. PACMPL 2, OOPSLA","author":"Zhang Yunming","year":"2018","unstructured":"Yunming Zhang, Mengjiao Yang, Riyadh Baghdadi, Shoaib Kamil, Julian Shun, and Saman Amarasinghe. 2018. Graphit: A high-performance graph dsl. PACMPL 2, OOPSLA (2018), 1--30."},{"key":"e_1_2_1_57_1","first-page":"1543","article-title":"Medusa: Simplified graph processing on GPUs","volume":"25","author":"Zhong Jianlong","year":"2013","unstructured":"Jianlong Zhong and Bingsheng He. 2013. Medusa: Simplified graph processing on GPUs. TPDS 25, 6 (2013), 1543--1552.","journal-title":"TPDS"},{"key":"e_1_2_1_58_1","first-page":"301","article-title":"Gemini: A computation-centric distributed graph processing system","volume":"16","author":"Zhu Xiaowei","year":"2016","unstructured":"Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma. 2016. Gemini: A computation-centric distributed graph processing system.. In OSDI, Vol. 16. 301--316.","journal-title":"OSDI"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3648160.3648179","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,17]],"date-time":"2024-11-17T20:02:07Z","timestamp":1731873727000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3648160.3648179"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2]]},"references-count":58,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["10.14778\/3648160.3648179"],"URL":"https:\/\/doi.org\/10.14778\/3648160.3648179","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,2]]},"assertion":[{"value":"2024-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}