{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:51:38Z","timestamp":1773481898692,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,11,21]],"date-time":"2019-11-21T00:00:00Z","timestamp":1574294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Research Grants Council of Hong Kong","award":["GRF 17245716"],"award-info":[{"award-number":["GRF 17245716"]}]},{"DOI":"10.13039\/501100001692","name":"Croucher Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001692","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>Due to the irregular nature of connections in most graph datasets, partitioning graph analysis algorithms across multiple computational nodes that do not share a common memory inevitably leads to large amounts of interconnect traffic. Previous research has shown that FPGAs can outcompete software-based graph processing in shared memory contexts, but it remains an open question if this advantage can be maintained in distributed systems.<\/jats:p>\n          <jats:p>In this work, we present GraVF-M, a framework designed to ease the implementation of FPGA-based graph processing accelerators for multi-FPGA platforms with distributed memory. Based on a lightweight description of the algorithm kernel, the framework automatically generates optimized RTL code for the whole multi-FPGA design. We exploit an aspect of the programming model to present a familiar message-passing paradigm to the user, while under the hood implementing a more efficient architecture that can reduce the necessary inter-FPGA network traffic by a factor equal to the average degree of the input graph. A performance model based on a theoretical analysis of the factors influencing performance serves to evaluate the efficiency of our implementation. With a throughput of up to 5.8GTEPS (billions of traversed edges per second) on a 4-FPGA system, the designs generated by GraVF-M compare favorably to state-of-the-art frameworks from the literature and reach 94% of the projected performance limit of the system.<\/jats:p>","DOI":"10.1145\/3357596","type":"journal-article","created":{"date-parts":[[2019,11,21]],"date-time":"2019-11-21T13:35:22Z","timestamp":1574343322000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["GraVF-M"],"prefix":"10.1145","volume":"12","author":[{"given":"Nina","family":"Engelhardt","sequence":"first","affiliation":[{"name":"University of Hong Kong, Pokfulam Road, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hayden K.-H.","family":"So","sequence":"additional","affiliation":[{"name":"University of Hong Kong, Pokfulam Road, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,11,21]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the IEEE International Parallel Distributed Processing Symposium Workshops (IPDPSW\u201914)","author":"Attia O. G.","year":"2014"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the International Conference on ReConFigurable Computing and FPGAs (ReConFig\u201915)","author":"Attia O. G.","year":"2015"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPT.2011.6132667"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 23rd International Conference on Application-Specific Systems, Architectures and Processors (ASAP\u201912)","author":"Betkaoui B.","year":"2012"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"D. Chakrabarti Y. Zhan and C. Faloutsos. 2004. R-MAT: A Recursive Model for Graph Mining. 442--446. DOI:https:\/\/doi.org\/10.1137\/1.9781611972740.43  D. Chakrabarti Y. Zhan and C. Faloutsos. 2004. R-MAT: A Recursive Model for Graph Mining. 442--446. DOI:https:\/\/doi.org\/10.1137\/1.9781611972740.43","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_1_6_1","unstructured":"Convey Computer. 2011. Convey Computer Doubles Graph500 Performance Develops New Graph Personality. Press release. Retrieved from: http:\/\/investors.micron.com\/news-releases\/news-release-details\/convey-computer-doubles-graph500-performance-develops-new-graph.  Convey Computer. 2011. Convey Computer Doubles Graph500 Performance Develops New Graph Personality. Press release. Retrieved from: http:\/\/investors.micron.com\/news-releases\/news-release-details\/convey-computer-doubles-graph500-performance-develops-new-graph."},{"key":"e_1_2_1_7_1","unstructured":"Convey Computer. 2012. New Convey MX\u2122 Demonstrates Leading Power\/Performance on Graph 500 Benchmark. Press release. Retrieved from: https:\/\/www.yahoo.com\/news\/convey-mx-tm-demonstrates-leading-214814156.html.  Convey Computer. 2012. New Convey MX\u2122 Demonstrates Leading Power\/Performance on Graph 500 Benchmark. Press release. Retrieved from: https:\/\/www.yahoo.com\/news\/convey-mx-tm-demonstrates-leading-214814156.html."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2847263.2847339"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the International Symposium on Field-Programmable Gate Arrays (FPGA\u201917)","author":"Dai G.","year":"2007"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2019583.2019584"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 14th IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM\u201906)","author":"deLorimier M.","year":"2006"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 28th International Conference on Field Programmable Logic and Applications (FPL\u201918)","author":"Engelhardt Nina","year":"2018"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2016.7577360"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3120895.3120896"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASAP.2015.7245698"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3174243.3174260"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 21st International Joint Conference on Artifical Intelligence (IJCAI\u201909)","author":"Korf Richard E.","year":"2009"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137776"},{"key":"e_1_2_1_20_1","unstructured":"Guoqing Lei Rongchun Li Song Guo and Fei Xia. 2015. TorusBFS: A novel message-passing parallel breadth-first search architecture on FPGAs. IRACST\u2014Eng. Sci. Technol.: Int. J. 5 5 (Oct. 2015) 313--318.  Guoqing Lei Rongchun Li Song Guo and Fei Xia. 2015. TorusBFS: A novel message-passing parallel breadth-first search architecture on FPGAs. IRACST\u2014Eng. Sci. Technol.: Int. J. 5 5 (Oct. 2015) 313--318."},{"key":"e_1_2_1_21_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from: http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from: http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_22_1","unstructured":"M-Labs. 2012. Migen. Retrieved from: http:\/\/m-labs.hk\/migen.  M-Labs. 2012. Migen. Retrieved from: http:\/\/m-labs.hk\/migen."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3020078.3021743"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM.","author":"Malewicz G."},{"key":"e_1_2_1_25_1","unstructured":"Richard C. Murphy Kyle B. Wheeler Brian W. Barrett and James A. Ang. 2010. Introducing the Graph500. Cray User\u2019s Group (2010). Retrieved from: https:\/\/cug.org\/5-publications\/proceedings_attendee_lists\/CUG10CD\/pages\/1-program\/final_program\/CUG10_Proceedings\/pages\/authors\/11-15Wednesday\/14C-Murphy-paper.pdf.  Richard C. Murphy Kyle B. Wheeler Brian W. Barrett and James A. Ang. 2010. Introducing the Graph500. Cray User\u2019s Group (2010). Retrieved from: https:\/\/cug.org\/5-publications\/proceedings_attendee_lists\/CUG10CD\/pages\/1-program\/final_program\/CUG10_Proceedings\/pages\/authors\/11-15Wednesday\/14C-Murphy-paper.pdf."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 22nd International Symposium on Field-Programmable Custom Computing Machines (FCCM\u201914)","author":"Nurvitadhi E."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2847263.2847337"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the International Conference on Field Programmable Logic and Applications (FPL\u201915)","author":"Umuroglu Y.","year":"2015"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the International Conference on Field-Programmable Technology (FPT\u201910)","author":"Wang Q.","year":"2010"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the International Symposium on Field-Programmable Gate Arrays (FPGA\u201917)","author":"Zhang J.","year":"2007"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3174243.3174245"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 17th IEEE\/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID\u201917)","author":"Zhou J.","year":"2017"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the IEEE 24th International Symposium on Field-Programmable Custom Computing Machines (FCCM\u201916)","author":"Zhou S.","year":"2016"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 15th ACM International Conference on Computing Frontiers (CF\u201918)","author":"Zhou Shijie","year":"2032"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 29th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD\u201917)","author":"Zhou S.","year":"2017"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the USENIX Annual Technical Conference (USENIX ATC\u201915)","author":"Zhu Xiaowei","year":"2015"}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357596","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357596","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:22Z","timestamp":1750202602000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357596"}},"subtitle":["Graph Processing System Generation for Multi-FPGA Platforms"],"short-title":[],"issued":{"date-parts":[[2019,11,21]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3357596"],"URL":"https:\/\/doi.org\/10.1145\/3357596","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"value":"1936-7406","type":"print"},{"value":"1936-7414","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,21]]},"assertion":[{"value":"2019-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}