{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T01:18:02Z","timestamp":1789435082142,"version":"build-2803163510"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:p>\n                    The growing scale of graph data across various applications demands efficient distributed graph processing systems. Despite the widespread use of the\n                    <jats:italic toggle=\"yes\">Scatter-Gather<\/jats:italic>\n                    model for large-scale graph processing across distributed machines, the performance still can be significantly improved as the computation ability of each machine is not fully utilized and the communication costs during graph processing are expensive in the distributed environment. In this work, we propose a novel and efficient distributed graph processing system Nezha on heterogeneous hardware, where each machine is equipped with both CPU and GPU processors and all these machines in the distributed cluster are interconnected via Remote Direct Memory Access (RDMA).To reduce the communication costs, we devise an effective communication mode with a graph-friendly communication protocol in the graph-based RDMA communication adapter of Nezha. To improve the computation efficiency, we propose a multi-device cooperative execution mechanism in Nezha, which fully utilizes the CPU and GPU processors of each machine in the distributed cluster. We also alleviate the workload imbalance issue at inter-machine and intra-machine levels via the proposed workload balancer in Nezha. We conduct extensive experiments by running 4 widely-used graph algorithms on 5 graph datasets to demonstrate the superiority of Nezha over existing systems.\n                  <\/jats:p>","DOI":"10.1145\/3709707","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-27","source":"Crossref","is-referenced-by-count":3,"title":["Nezha: An Efficient Distributed Graph Processing System on Heterogeneous Hardware"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-3753-490X","authenticated-orcid":false,"given":"Pengjie","family":"Cui","sequence":"first","affiliation":[{"name":"Northeastern University, Shenyang, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8784-8711","authenticated-orcid":false,"given":"Haotian","family":"Liu","sequence":"additional","affiliation":[{"name":"Southern University of Science and Technology, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-0511-0272","authenticated-orcid":false,"given":"Dong","family":"Jiang","sequence":"additional","affiliation":[{"name":"Northeastern University, Shenyang, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8424-0092","authenticated-orcid":false,"given":"Bo","family":"Tang","sequence":"additional","affiliation":[{"name":"Southern University of Science and Technology, Shenzhen, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0247-9866","authenticated-orcid":false,"given":"Ye","family":"Yuan","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Andreea Anghel German Rodriguez Bogdan Prisacari Cyriel Minkenberg and Gero Dittmann. 2015. Quantifying communication in graph analytics. In HPC. 472--487.","DOI":"10.1007\/978-3-319-20119-1_33"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Claude Barthels Simon Loesing Gustavo Alonso and Donald Kossmann. 2015. Rack-scale in-memory join processing using RDMA. In SIGMOD. 1463--1475.","DOI":"10.1145\/2723372.2750547"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3155284.3018756"},{"key":"e_1_2_1_4_1","volume-title":"PRISM: Rethinking the RDMA interface for distributed systems. In SOSP. 228--242.","author":"Burke Matthew","year":"2021","unstructured":"Matthew Burke, Sowmya Dharanipragada, Shannon Joyner, Adriana Szekeres, Jacob Nelson, Irene Zhang, and Dan RK Ports. 2021. PRISM: Rethinking the RDMA interface for distributed systems. In SOSP. 228--242."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3298989"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3648160.3648179"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536222.2536239"},{"key":"e_1_2_1_9_1","unstructured":"Aleksandar Dragojevi\u0107 Dushyanth Narayanan Miguel Castro and Orion Hodson. 2014. FaRM: Fast remote memory. In NSDI 14. 401--414."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3282488"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2009.32"},{"key":"e_1_2_1_12_1","volume-title":"Elizeu Santos-Neto, and Matei Ripeanu.","author":"Gharaibeh Abdullah","year":"2012","unstructured":"Abdullah Gharaibeh, Lauro Beltr ao 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_13_1","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_14_1","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_15_1","volume-title":"Elvis Liu, Georgios Theodoropoulos, and Wentong Cai.","author":"Hanai Masatoshi","year":"2019","unstructured":"Masatoshi Hanai, Toyotaro Suzumura, Wen Jun Tan, Elvis Liu, Georgios Theodoropoulos, and Wentong Cai. 2019. Distributed edge partitioning for trillion-edge graphs. arXiv preprint arXiv:1908.05855 (2019)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796821000277"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157799"},{"key":"e_1_2_1_18_1","volume-title":"Workshop on HPI-DC; In conjunction with HPDC-14","author":"Jin Hyun-Wook","year":"2005","unstructured":"Hyun-Wook Jin, Sundeep Narravula, Gregory Brown, Karthikeyan Vaidyanathan, Pavan Balaji, and Dhabaleswar K Panda. 2005. Performance evaluation of rdma over ip: A case study with the ammasso gigabit ethernet nic. In Workshop on HPI-DC; In conjunction with HPDC-14."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2762294"},{"key":"e_1_2_1_20_1","unstructured":"Anuj Kalia Michael Kaminsky and David G Andersen. 2016. Design guidelines for high performance RDMA systems. In ATC. 437--450."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Zuhair Khayyat Karim Awara Amani Alonazi Hani Jamjoom Dan Williams and Panos Kalnis. 2013. Mizan: a system for dynamic load balancing in large-scale graph processing. In EuroSys. 169--182.","DOI":"10.1145\/2465351.2465369"},{"key":"e_1_2_1_22_1","volume-title":"Parmat: A parallel generator for large r-mat graphs. In PACT.","author":"Khorasani Farzad","year":"2015","unstructured":"Farzad Khorasani, Keval Vora, and Rajiv Gupta. 2015. Parmat: A parallel generator for large r-mat graphs. In PACT."},{"key":"e_1_2_1_23_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_24_1","unstructured":"Aapo Kyrola Guy Blelloch and Carlos Guestrin. 2012. GraphChi:Large-Scale graph computation on just a PC. In OSDI. 31--46."},{"key":"e_1_2_1_25_1","volume-title":"Improving spark performance with zero-copy buffer management and RDMA","author":"Li Hu","unstructured":"Hu Li, Tianjia Chen, and Wei Xu. 2016. Improving spark performance with zero-copy buffer management and RDMA. In INFOCOM WKSHPS. IEEE, 33--38."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-018-00623-w"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360900"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/782814.782855"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735517"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Teng Ma Tao Ma Zhuo Song Jingxuan Li Huaixin Chang Kang Chen Hai Jiang and Yongwei Wu. 2019. X-RDMA: Effective RDMA middleware in large-scale production environments. In CLUSTER. 1--12.","DOI":"10.1109\/CLUSTER.2019.8891004"},{"key":"e_1_2_1_31_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_32_1","volume-title":"Heiko Geppert, Larissa Laich, Lukas Rieger, and Kurt Rothermel.","author":"Mayer Christian","year":"2018","unstructured":"Christian Mayer, Ruben Mayer, Muhammad Adnan Tariq, Heiko Geppert, Larissa Laich, Lukas Rieger, and Kurt Rothermel. 2018. Adwise: Adaptive window-based streaming edge partitioning for high-speed graph processing. In ICDCS. 685--695."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Ruben Mayer Kamil Orujzade and Hans-Arno Jacobsen. 2022. Out-of-core edge partitioning at linear run-time. In ICDE. 2629--2642.","DOI":"10.1109\/ICDE53745.2022.00242"},{"key":"e_1_2_1_34_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_35_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342011434065"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Anil Pacaci and M Tamer \u00d6zsu. 2019. Experimental analysis of streaming algorithms for graph partitioning. In SIGMOD. 1375--1392.","DOI":"10.1145\/3299869.3300076"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Yuechao Pan Yangzihao Wang Yuduo Wu Carl Yang and John D Owens. 2017. Multi-GPU graph analytics. In IPDPS. 479--490.","DOI":"10.1109\/IPDPS.2017.117"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806424"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Louise Quick Paul Wilkinson and David Hardcastle. 2012. Using pregel-like large scale graph processing frameworks for social network analysis. In ASONAM. 457--463.","DOI":"10.1109\/ASONAM.2012.254"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_1_42_1","volume-title":"Gps: A graph processing system. In SSDBM. 1--12.","author":"Salihoglu Semih","year":"2013","unstructured":"Semih Salihoglu and Jennifer Widom. 2013. Gps: A graph processing system. In SSDBM. 1--12."},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Semih Salihoglu and Jennifer Widom. 2014. Optimizing graph algorithms on pregel-like systems. (2014).","DOI":"10.14778\/2732286.2732294"},{"key":"e_1_2_1_44_1","volume-title":"Jiwon Seo, Jongsoo Park, M Amber Hassaan, Shubho Sengupta, Zhaoming Yin, and Pradeep Dubey.","author":"Satish Nadathur","year":"2014","unstructured":"Nadathur Satish, Narayanan Sundaram, Md Mostofa Ali Patwary, Jiwon Seo, Jongsoo Park, M Amber Hassaan, Shubho Sengupta, Zhaoming Yin, and Pradeep Dubey. 2014. Navigating the maze of graph analytics frameworks using massive graph datasets. In SIGMOD. 979--990."},{"key":"e_1_2_1_45_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_46_1","doi-asserted-by":"crossref","unstructured":"Julian Shun and Guy E Blelloch. 2013a. Ligra: a lightweight graph processing framework for shared memory. In PPoPP. 135--146.","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Julian Shun and Guy E Blelloch. 2013b. Ligra: a lightweight graph processing framework for shared memory. In PPoPP. 135--146.","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_1_48_1","volume-title":"Goffish: A sub-graph centric framework for large-scale graph analytics. In Euro-Par 2014 Parallel Processing. 451--462.","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. 451--462."},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Isabelle Stanton and Gabriel Kliot. 2012. Streaming graph partitioning for large distributed graphs. In SIGKDD. 1222--1230.","DOI":"10.1145\/2339530.2339722"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Philip Stutz Abraham Bernstein and William Cohen. 2010. Signal\/collect: graph algorithms for the (semantic) web. In The Semantic Web--ISWC. 764--780.","DOI":"10.1007\/978-3-642-17746-0_48"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064189"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Adrian Tate Amir Kamil Anshu Dubey Armin Groblinger Brad Chamberlain Brice Goglin Harold C Edwards Chris J Newburn David Padua Didem Unat et al. 2014. Programming abstractions for data locality. Technical Report. OSTI.","DOI":"10.2172\/1172915"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Shin-Yeh Tsai and Yiying Zhang. 2017. LITE kernel RDMA support for datacenter applications. In SOSP. 306--324.","DOI":"10.1145\/3132747.3132762"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556213"},{"key":"e_1_2_1_56_1","volume-title":"Scaleg: A distributed disk-based system for vertex-centric graph processing. In ICDE. 1511--1512.","author":"Wang Xubo","year":"2022","unstructured":"Xubo Wang, Dong Wen, Lu Qin, Lijun Chang, and Wenjie Zhang. 2022. Scaleg: A distributed disk-based system for vertex-centric graph processing. In ICDE. 1511--1512."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851145"},{"key":"e_1_2_1_58_1","volume-title":"Gram: Scaling graph computation to the trillions. In SoCC. 408--421.","author":"Wu Ming","year":"2015","unstructured":"Ming Wu, Fan Yang, Jilong Xue, Wencong Xiao, Youshan Miao, Lan Wei, Haoxiang Lin, Yafei Dai, and Lidong Zhou. 2015. Gram: Scaling graph computation to the trillions. In SoCC. 408--421."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2019.00025"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858788.2688508"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733103"},{"key":"e_1_2_1_62_1","first-page":"1619","article-title":"Wukong G: Fast and concurrent RDF query processing using RDMA-assisted GPU graph exploration","volume":"33","author":"Yao Zihang","year":"2021","unstructured":"Zihang Yao, Rong Chen, Binyu Zang, and Haibo Chen. 2021. Wukong G: Fast and concurrent RDF query processing using RDMA-assisted GPU graph exploration. TPDS, Vol. 33, 7 (2021), 1619--1635.","journal-title":"TPDS"},{"key":"e_1_2_1_63_1","doi-asserted-by":"crossref","unstructured":"Andy Yoo Edmond Chow Keith Henderson William McLendon Bruce Hendrickson and Umit Catalyurek. 2005. A scalable distributed parallel breadth-first search algorithm on BlueGene\/L. In SC. 25--25.","DOI":"10.1109\/SC.2005.4"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.222"},{"key":"e_1_2_1_65_1","unstructured":"Matei Zaharia Mosharaf Chowdhury Tathagata Das Ankur Dave Justin Ma Murphy McCauly Michael J Franklin Scott Shenker and Ion Stoica. 2012. Resilient distributed datasets: A Fault-Tolerant abstraction for In-Memory cluster computing. In NSDI 12. 15--28."},{"key":"e_1_2_1_66_1","volume-title":"The end of a myth: Distributed transactions can scale. arXiv preprint arXiv:1607.00655","author":"Zamanian Erfan","year":"2016","unstructured":"Erfan Zamanian, Carsten Binnig, Tim Kraska, and Tim Harris. 2016. The end of a myth: Distributed transactions can scale. arXiv preprint arXiv:1607.00655 (2016)."},{"key":"e_1_2_1_67_1","doi-asserted-by":"crossref","unstructured":"Kaiyuan Zhang Rong Chen and Haibo Chen. 2015. NUMA-aware graph-structured analytics. In PPoPP. 183--193.","DOI":"10.1145\/2688500.2688507"},{"key":"e_1_2_1_68_1","first-page":"463","article-title":"DRONE","volume":"34","author":"Zhang Shuai","year":"2022","unstructured":"Shuai Zhang, Zite Jiang, Xingzhong Hou, Mingyu Li, Mengting Yuan, and Haihang You. 2022. DRONE: An Efficient Distributed Subgraph-Centric Framework for Processing Large-Scale Power-law Graphs. TPDS, Vol. 34, 2 (2022), 463--474.","journal-title":"TPDS"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477603"},{"key":"e_1_2_1_70_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, Vol. 25, 6 (2013), 1543--1552.","journal-title":"TPDS"},{"key":"e_1_2_1_71_1","volume-title":"Gemini: A Computation-Centric distributed graph processing system. In OSDI. 301--316.","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. 301--316."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13222-020-00355-7"},{"key":"e_1_2_1_73_1","volume-title":"Carsten Binnig, Rodrigo Fonseca, and Tim Kraska.","author":"Ziegler Tobias","year":"2019","unstructured":"Tobias Ziegler, Sumukha Tumkur Vani, Carsten Binnig, Rodrigo Fonseca, and Tim Kraska. 2019. Designing distributed tree-based index structures for fast rdma-capable networks. In SIGMOD. 741--758."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709707","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709707","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:19:55Z","timestamp":1774981195000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709707"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":73,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3709707"],"URL":"https:\/\/doi.org\/10.1145\/3709707","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}