{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:48:59Z","timestamp":1774986539304,"version":"3.50.1"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"Ministry of Education AcRF Tier 2 grant","award":["MOE-T2EP20121-0016"],"award-info":[{"award-number":["MOE-T2EP20121-0016"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>Efficient graph processing is critical in various modern applications, such as social network analysis, recommendation systems, and large-scale data mining. Traditional single-FPGA systems struggle to handle the increasing size and complexity of real-world graphs due to limitations in memory and computational resources. Existing multi-FPGA solutions face significant challenges, including high communication overhead caused by irregular data transfer patterns and workload imbalances stemming from skewed graph distributions. These inefficiencies hinder scalability and performance, highlighting a critical research gap. To address these issues, we introduce Clementi, an efficient multi-FPGA graph processing framework that features customized fine-grained pipelines for computation and cross-FPGA communication. Clementi uniquely integrates an accurate performance model for execution time prediction, enabling a novel scheduling method that balances workload distribution and minimizes communication overhead by overlapping communication and computation stages. Experimental results demonstrate that Clementi achieves speedups of up to 8.75\u00d7 compared to state-of-the-art multi-FPGA designs, indicating significant improvements in processing efficiency as the number of FPGAs increases. This near-linear scalability underscores the framework' s potential to enhance graph processing capabilities in practical applications. Clementi is open-sourced at https:\/\/github.com\/Xtra-Computing\/Clementi.<\/jats:p>","DOI":"10.1145\/3725275","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-27","source":"Crossref","is-referenced-by-count":1,"title":["Clementi: Efficient Load Balancing and Communication Overlap for Multi-FPGA Graph Processing"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-2207-8465","authenticated-orcid":false,"given":"Feng","family":"Yu","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3243-6875","authenticated-orcid":false,"given":"Hongshi","family":"Tan","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1951-5015","authenticated-orcid":false,"given":"Xinyu","family":"Chen","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5798-2282","authenticated-orcid":false,"given":"Yao","family":"Chen","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8618-4581","authenticated-orcid":false,"given":"Bingsheng","family":"He","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4281-2053","authenticated-orcid":false,"given":"Weng-Fai","family":"Wong","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2016.60"},{"key":"e_1_2_2_2_1","unstructured":"AMD Xilinx 2024. Heterogeneous Accelerated Compute Cluster (HACC) at NUS. https:\/\/xacchead.d2.comp.nus.edu.sg\/."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA52012.2021.00054"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_2_6_1","volume-title":"Karen Dragon Devine, and Sivasankaran Rajamanickam","author":"Boman Erik G","year":"2014","unstructured":"Erik G Boman, Karen Dragon Devine, and Sivasankaran Rajamanickam. 2014. 2D Partitioning for Scalable Matrix Computations on Scale-Free Graphs. Technical Report. Sandia National Lab.(SNL-NM), Albuquerque, NM (United States)."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2016.7783710"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2015.88"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2019.00020"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO56248.2022.00092"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3431920.3439290"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2847263.2847339"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3020078.3021739"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357596"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2621934.2621936"},{"key":"e_1_2_2_16_1","volume-title":"Scott Sallinen, and Matei Ripeanu.","author":"Gharaibeh Abdullah","year":"2013","unstructured":"Abdullah Gharaibeh, Tahsin Reza, Elizeu Santos-Neto, Lauro Beltrao Costa, Scott Sallinen, and Matei Ripeanu. 2013. Efficient large-scale graph processing on hybrid CPU and GPU systems. arXiv preprint arXiv:1312.3018 (2013)."},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation","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 (Hollywood, CA, USA) (OSDI'12). USENIX Association, USA, 17--30."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-019--1914-z"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD51958.2021.9643582"},{"key":"e_1_2_2_20_1","unstructured":"Intel. 2024. Intel turbostat. https:\/\/www.linux.org\/docs\/man8\/turbostat.html."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157799"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/305219.305248"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600212.2600227"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_2_25_1","article-title":"Kronecker graphs: an approach to modeling networks","volume":"11","author":"Leskovec Jure","year":"2010","unstructured":"Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. 2010. Kronecker graphs: an approach to modeling networks. Journal of Machine Learning Research 11, 2 (2010).","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_2_26_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford large network dataset collection."},{"key":"e_1_2_2_27_1","volume-title":"Ullman","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec, Anand Rajaraman, and Jeffrey D. Ullman. 2014. Mining of massive datasets. Cambridge University Press."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807594"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_2_31_1","volume-title":"January","author":"Azure Microsoft","year":"2025","unstructured":"Microsoft Azure. Accessed: January 2025. Microsoft Azure Pricing Calculator. https:\/\/azure.microsoft.com\/en-us\/pricing\/calculator\/."},{"key":"e_1_2_2_32_1","volume-title":"January","author":"Azure Microsoft","year":"2025","unstructured":"Microsoft Azure. Accessed: January 2025. Microsoft Azure Virtual Machines Documentation. https:\/\/learn.microsoft.com\/zh-cn\/azure\/virtual-machines\/."},{"key":"e_1_2_2_33_1","unstructured":"NVIDIA [n. d.]. Nvidia system management interface. https:\/\/developer.nvidia.com\/nvidia-system-management-interface."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2847263.2847337"},{"key":"e_1_2_2_35_1","unstructured":"Open MPI [n. d.]. Open MPI: Open Source High Performance Computing. https:\/\/www.open-mpi.org\/."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2015.42"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815408"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40537-023-00756-x"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610518"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2.4.320"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289602.3293900"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2745562"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583155"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3016078.2851145"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","unstructured":"Jagath Weerasinghe Francois Abel Christoph Hagleitner and Andreas Herkersdorf. 2015. Enabling FPGAs in Hyperscale Data Centers. In 2015 IEEE 12th Intl Conf on Ubiquitous Intelligence and Computing and 2015 IEEE 12th Intl Conf on Autonomic and Trusted Computing and 2015 IEEE 15th Intl Conf on Scalable Computing and Communications and Its Associated Workshops (UIC-ATC-ScalCom). 1078--1086. doi:10.1109\/UIC-ATC-ScalCom-CBDCom-IoP.2015.199","DOI":"10.1109\/UIC-ATC-ScalCom-CBDCom-IoP.2015.199"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915220"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-021--1242-y"},{"key":"e_1_2_2_49_1","unstructured":"Xilinx [n. d.]. Vitis HLS. https:\/\/www.xilinx.com\/products\/design-tools\/vitis\/vitis-hls.html."},{"key":"e_1_2_2_50_1","unstructured":"Xilinx. 2021. U250 Data Center Accelerator Card. https:\/\/www.xilinx.com\/products\/boards-and-kits\/alveo\/u250.html."},{"key":"e_1_2_2_51_1","unstructured":"Xilinx 2021. Vitis Xbutil. https:\/\/xilinx.github.io\/XRT\/master\/html\/xbutil.html."},{"key":"e_1_2_2_52_1","unstructured":"Xilinx. 2022. xup_vitis_network_example. https:\/\/github.com\/Xilinx\/xup_vitis_network_example."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2020.3035090"},{"key":"e_1_2_2_54_1","volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies","author":"Zheng Da","unstructured":"Da Zheng, Disa Mhembere, Randal Burns, Joshua Vogelstein, Carey E. Priebe, and Alexander S. Szalay. 2015. FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs. In Proceedings of the 13th USENIX Conference on File and Storage Technologies (Santa Clara, CA) (FAST'15). USENIX Association, USA, 45--58."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2694413.2694421"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2910068"},{"key":"e_1_2_2_57_1","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 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 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). 301--316."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725275","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:54:37Z","timestamp":1774983277000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725275"],"URL":"https:\/\/doi.org\/10.1145\/3725275","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}