{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T18:43:49Z","timestamp":1790275429647,"version":"4.1.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T00:00:00Z","timestamp":1718928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Strategic Priority Research Program of Chinese Academy of Sciences","award":["XDB44000000"],"award-info":[{"award-number":["XDB44000000"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2024,7,31]]},"abstract":"<jats:p>Graph processing is widely used for many modern applications, such as social networks, recommendation systems, and knowledge graphs. However, processing large-scale graphs on traditional Von Neumann architectures is challenging due to the irregular graph data and memory-bound graph algorithms. Processing-in-memory (PIM) architecture has emerged as a promising approach for accelerating graph processing by enabling computation to be performed directly on memory. Despite having many processing units and high local memory bandwidth, PIM often suffers from insufficient global communication bandwidth and high synchronization overhead due to load imbalance.<\/jats:p>\n          <jats:p>This article proposes GraphB, a novel PIM-based graph processing system, to address all these issues. From the algorithm perspective, we propose a degree-aware graph partitioning algorithm that can generate balanced partitioning at a low cost. From the architecture perspective, we introduce tile buffers incorporated with an on-chip 2D-Mesh, which provides high bandwidth for inter-node data transfer. Dataflow in GraphB is designed to enable computation\u2013communication overlap and dynamic load balancing. In a PyMTL3-based cycle-accurate simulator with five real-world graphs and three common algorithms, GraphB achieves an average 2.2\u00d7 and maximum 2.8\u00d7 speedup compared to the SOTA PIM-based graph processing system GraphQ.<\/jats:p>","DOI":"10.1145\/3659951","type":"journal-article","created":{"date-parts":[[2024,4,18]],"date-time":"2024-04-18T08:21:27Z","timestamp":1713428487000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Load Balanced PIM-Based Graph Processing"],"prefix":"10.1145","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-7378-6860","authenticated-orcid":false,"given":"Xiang","family":"Zhao","sequence":"first","affiliation":[{"name":"School of Microelectronics, University of Science and Technology of China, Hefei, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0341-3428","authenticated-orcid":false,"given":"Song","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Microelectronics, University of Science and Technology of China, Hefei, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5487-6855","authenticated-orcid":false,"given":"Yi","family":"Kang","sequence":"additional","affiliation":[{"name":"School of Microelectronics, University of Science and Technology of China, Hefei, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,21]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2749469.2750386"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/bbl022"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2015.12"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3514354"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3564290"},{"key":"e_1_3_1_8_2","article-title":"Hybrid Memory Cube Specification 2.1","author":"Consortium Hybrid Memory Cube","year":"2014","unstructured":"Hybrid Memory Cube Consortium et\u00a0al. 2014. Hybrid Memory Cube Specification 2.1. Technical Report.","journal-title":"Technical Report"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2821565"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.46"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/IEDM13553.2020.9372039"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2022.102755"},{"key":"e_1_3_1_13_2","first-page":"17","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912)","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 Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912). USENIX Association, 17\u201330."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.49"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(98)00093-3"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.14"},{"key":"e_1_3_1_17_2","volume-title":"Hbm2e","author":"Hynix S.","year":"2021","unstructured":"S. Hynix. 2021. Hbm2e. https:\/\/product.skhynix.com\/products\/dram\/hbm\/hbm2e.go"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2020.2997638"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/LSSC.2022.3171862"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_3_1_22_2","first-page":"31","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912)","author":"Kyrola Aapo","year":"2012","unstructured":"Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. 2012. GraphChi: Large-scale graph computation on just a PC. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912). USENIX Association, 31\u201346."},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3380942"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/1232722.1232727"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/WI.2006.202"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.5555\/2999134.2999195"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/LCA.2020.3039498"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806424"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISSCC42615.2023.10067477"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339722"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809983"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_16"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556213"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3576196"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCSW.2011.34"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3016078.2851145"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48096-0_34"},{"key":"e_1_3_1_42_2","first-page":"1673","volume-title":"Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 1 (NIPS\u201914)","author":"Xie Cong","year":"2014","unstructured":"Cong Xie, Ling Yan, Wu-Jun Li, and Zhihua Zhang. 2014. Distributed power-law graph computing: Theoretical and empirical analysis. In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 1 (NIPS\u201914). MIT Press, Cambridge, MA, USA, 1673\u20131681."},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2023.3288755"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358318"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA53966.2022.00023"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2018.00053"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.23919\/DATE51398.2021.9473227"},{"key":"e_1_3_1_48_2","first-page":"301","volume-title":"Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201916)","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 Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201916). USENIX Association, 301\u2013316."},{"key":"e_1_3_1_49_2","first-page":"375","volume-title":"2015 USENIX Annual Technical Conference (USENIX ATC\u201915)","author":"Zhu Xiaowei","year":"2015","unstructured":"Xiaowei Zhu, Wentao Han, and Wenguang Chen. 2015. GridGraph: Large-scale graph processing on a single machine using 2-level hierarchical partitioning. In 2015 USENIX Annual Technical Conference (USENIX ATC\u201915). 375\u2013386."},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3352460.3358256"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3659951","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3659951","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:30Z","timestamp":1750294710000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3659951"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,21]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,7,31]]}},"alternative-id":["10.1145\/3659951"],"URL":"https:\/\/doi.org\/10.1145\/3659951","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,21]]},"assertion":[{"value":"2023-10-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-08","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}