{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T00:18:12Z","timestamp":1782519492029,"version":"3.54.5"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"AI Singapore Programme","award":["AISG2-TC-2021-002"],"award-info":[{"award-number":["AISG2-TC-2021-002"]}]},{"name":"Google South \\& Southeast Asia Research Award 2022"},{"name":"AMD Heterogeneous Accelerated Compute Clusters (HACC) program"},{"name":"Ministry of Education AcRF Tier 2 grant","award":["MOE-000242-00 \/ MOE-000242-01"],"award-info":[{"award-number":["MOE-000242-00 \/ MOE-000242-01"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Graph dynamic random walks (GDRWs) have recently emerged as a powerful paradigm for graph analytics and learning applications, including graph embedding and graph neural networks. Despite the fact that many existing studies optimize the performance of GDRWs on multi-core CPUs, massive random memory accesses and costly synchronizations cause severe resource underutilization, and the processing of GDRWs is usually the key performance bottleneck in many graph applications. This paper studies an alternative architecture, FPGA, to address these issues in GDRWs, as FPGA has the ability of hardware customization so that we are able to explore fine-grained pipeline execution and specialized memory access optimizations. Specifically, we propose LightRW, a novel FPGA-based accelerator for GDRWs. LightRW embraces a series of optimizations to enable fine-grained pipeline execution on the chip and to exploit the massive parallelism of FPGA while significantly reducing memory accesses. As current commonly used sampling methods in GDRWs do not efficiently support fine-grained pipeline execution, we develop a parallelized reservoir sampling method to sample multiple vertices per cycle for efficient pipeline execution. To address the random memory access issues, we propose a degree-aware configurable caching method that buffers hot vertices on-chip to alleviate random memory accesses and a dynamic burst access engine that efficiently retrieves neighbors. Experimental results show that our optimization techniques are able to improve the performance of GDRWs on FPGA significantly. Moreover, LightRW delivers up to 9.55x and 9.10x speedup over the state-of-the-art CPU-based MetaPath and Node2vec random walks, respectively. This work is open-sourced on GitHub at https:\/\/github.com\/Xtra-Computing\/LightRW.<\/jats:p>","DOI":"10.1145\/3588944","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-27","source":"Crossref","is-referenced-by-count":11,"title":["LightRW: FPGA Accelerated Graph Dynamic Random Walks"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3243-6875","authenticated-orcid":false,"given":"Hongshi","family":"Tan","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1951-5015","authenticated-orcid":false,"given":"Xinyu","family":"Chen","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"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":[{"vocabulary":"crossref","role":"author"}]},{"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":[{"vocabulary":"crossref","role":"author"}]},{"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":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"AMD. 2023. Heterogeneous Accelerated Compute Clusters (HACC) Program. https:\/\/www.amd-haccs.io\/index.html."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2019.2899330"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.110"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2019.00049"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2018.01.002"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3307681.3326609"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304019"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2019.00051"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2019.00020"},{"key":"e_1_2_2_12_1","volume-title":"ThunderGP: Resource-Efficient Graph Processing Framework on FPGAs with HLS. ACM Transactions on Reconfigurable Technology and Systems (TRETS)","author":"Chen Xinyu","year":"2022","unstructured":"Xinyu Chen, Feng Cheng, Hongshi Tan, Yao Chen, Bingsheng He, Weng-Fai Wong, and Deming Chen. 2022. ThunderGP: Resource-Efficient Graph Processing Framework on FPGAs with HLS. ACM Transactions on Reconfigurable Technology and Systems (TRETS) (2022)."},{"key":"e_1_2_2_13_1","volume-title":"Skew-Oblivious Data Routing for Data Intensive Applications on FPGAs with HLS. In 2021 58th ACM\/IEEE Design Automation Conference (DAC). IEEE, 937--942","author":"Chen Xinyu","year":"2021","unstructured":"Xinyu Chen, Hongshi Tan, Yao Chen, Bingsheng He, Weng-Fai Wong, and Deming Chen. 2021a. Skew-Oblivious Data Routing for Data Intensive Applications on FPGAs with HLS. In 2021 58th ACM\/IEEE Design Automation Conference (DAC). IEEE, 937--942."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3431920.3439290"},{"key":"e_1_2_2_15_1","volume-title":"Markov Chains","author":"Ching Wai-Ki","unstructured":"Wai-Ki Ching, Ximin Huang, Michael K Ng, and Tak-Kuen Siu. 2013. Higher-order markov chains. In Markov Chains. Springer, 141--176."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3431920.3439301"},{"key":"e_1_2_2_17_1","unstructured":"Intel Corporation. 2022. Intel VTune Profiler. https:\/\/www.intel.com\/content\/www\/us\/en\/developer\/tools\/oneapi\/vtune-profiler.html"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013164120801"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098036"},{"key":"e_1_2_2_20_1","volume-title":"Weighted random sampling with a reservoir. Information processing letters","author":"Efraimidis Pavlos S","year":"2006","unstructured":"Pavlos S Efraimidis and Paul G Spirakis. 2006. Weighted random sampling with a reservoir. Information processing letters, Vol. 97, 5 (2006), 181--185."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492517.2492620"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM48280.2020.00015"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/WI.2006.149"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387641"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3358061"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD51958.2021.9643582"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASSET.1999.756775"},{"key":"e_1_2_2_29_1","volume-title":"Parallel Weighted Random Sampling. In 27th Annual European Symposium on Algorithms (ESA","author":"H\u00fcbschle-Schneider Lorenz","year":"2019","unstructured":"Lorenz H\u00fcbschle-Schneider and Peter Sanders. 2019. Parallel Weighted Random Sampling. In 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319696"},{"key":"e_1_2_2_31_1","volume-title":"14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)","author":"Korolija Dario","year":"2020","unstructured":"Dario Korolija, Timothy Roscoe, and Gustavo Alonso. 2020. Do $$OS$$ abstractions make sense on $$FPGAs$$?. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 991--1010."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3364180"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1268776.1268777"},{"key":"e_1_2_2_34_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, Vol. 11, 2 (2010).","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_2_35_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898361"},{"key":"e_1_2_2_37_1","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1109\/TVLSI.2013.2262103","article-title":"Software\/Hardware Parallel Long-Period Random Number Generation Framework Based on the WELL Method","volume":"22","author":"Li Yuan","year":"2013","unstructured":"Yuan Li, Paul Chow, Jiang Jiang, Minxuan Zhang, and Shaojun Wei. 2013. Software\/Hardware Parallel Long-Period Random Number Generation Framework Based on the WELL Method. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol. 22, 5 (2013), 1054--1059.","journal-title":"IEEE Transactions on Very Large Scale Integration (VLSI) Systems"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308560.3316585"},{"key":"e_1_2_2_39_1","volume-title":"Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications","author":"L\u00fc Linyuan","year":"2011","unstructured":"Linyuan L\u00fc and Tao Zhou. 2011. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications, Vol. 390, 6 (2011), 1150--1170."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/272991.272995"},{"key":"e_1_2_2_41_1","unstructured":"SoSy Lab LMU Munich. 2021. CPU Energy Meter. https:\/\/github.com\/sosy-lab\/cpu-energy-meter."},{"key":"e_1_2_2_42_1","first-page":"16211","article-title":"Random walk graph neural networks","volume":"33","author":"Nikolentzos Giannis","year":"2020","unstructured":"Giannis Nikolentzos and Michalis Vazirgiannis. 2020. Random walk graph neural networks. Advances in Neural Information Processing Systems, Vol. 33 (2020), 16211--16222.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC41405.2020.00060"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.5108534"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIE.2007.898279"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/2888116.2888372"},{"key":"e_1_2_2_48_1","volume-title":"Simulation and the Monte Carlo method","author":"Rubinstein Reuven Y","unstructured":"Reuven Y Rubinstein and Dirk P Kroese. 2016. Simulation and the Monte Carlo method. Vol. 10. John Wiley & Sons."},{"key":"e_1_2_2_49_1","unstructured":"Ilya Safro Paul D Hovland Jaewook Shin and Michelle Mills Strout. 2009. Improving Random Walk Performance.. In CSC. 108--112."},{"key":"e_1_2_2_50_1","volume-title":"Monte Carlo and Quasi-Monte Carlo Methods","author":"Saito Mutsuo","year":"2006","unstructured":"Mutsuo Saito and Makoto Matsumoto. 2008. SIMD-oriented fast Mersenne Twister: a 128-bit pseudorandom number generator. In Monte Carlo and Quasi-Monte Carlo Methods 2006. Springer, 607--622."},{"key":"e_1_2_2_51_1","volume-title":"Principles of random walk \/ Frank Spitzer 2d ed. ed.)","author":"Spitzer Frank Ludvig","unstructured":"Frank Ludvig Spitzer. 1976. Principles of random walk \/ Frank Spitzer 2d ed. ed.). Springer-Verlag New York. xiii, 408 p. ; pages."},{"key":"e_1_2_2_52_1","volume-title":"Open Problems in Mathematics and Computational Science","author":"Kaya Kocc Mario Stipvc","unstructured":"Mario Stipvc evi\u0107 and cC etin Kaya Kocc. 2014. True random number generators. In Open Problems in Mathematics and Computational Science. Springer, 275--315."},{"key":"e_1_2_2_53_1","volume-title":"Graph Sampling with Fast Random Walker on HBM-enabled FPGA Accelerators. In 2021 31st International Conference on Field-Programmable Logic and Applications (FPL). IEEE, 211--218","author":"Su Chunyou","year":"2021","unstructured":"Chunyou Su, Hao Liang, Wei Zhang, Kun Zhao, Baole Ai, Wenting Shen, and Zeke Wang. 2021. Graph Sampling with Fast Random Walker on HBM-enabled FPGA Accelerators. In 2021 31st International Conference on Field-Programmable Logic and Applications (FPL). IEEE, 211--218."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476257"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2481244.2481248"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447818.3461664"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3079628.3079685"},{"key":"e_1_2_2_58_1","unstructured":"Fatemeh Vahedian Robin D Burke and Bamshad Mobasher. 2016. Weighted Random Walks for Meta-Path Expansion in Heterogeneous Networks.. In RecSys Posters."},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.6073"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2020.0543"},{"key":"e_1_2_2_61_1","volume-title":"The Free Encyclopedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Inverse_transform_sampling&oldid=1115190568 [Online","author":"Wikipedia","year":"2022","unstructured":"Wikipedia contributors. 2022a. Inverse transform sampling -- Wikipedia, The Free Encyclopedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Inverse_transform_sampling&oldid=1115190568 [Online; accessed 16-October-2022]."},{"key":"e_1_2_2_62_1","volume-title":"The Free Encyclopedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Link_prediction&oldid=1100501520 [Online","author":"Wikipedia","year":"2022","unstructured":"Wikipedia contributors. 2022b. Link prediction -- Wikipedia, The Free Encyclopedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Link_prediction&oldid=1100501520 [Online; accessed 14-October-2022]."},{"key":"e_1_2_2_63_1","volume-title":"Vitis Unified Software Development Platform","year":"2020","unstructured":"Xilinx. 2020a. Vitis Unified Software Development Platform 2020.2 Documentation. https:\/\/www.xilinx.com\/html_docs\/xilinx2020_2\/vitis_doc\/index.html."},{"key":"e_1_2_2_64_1","unstructured":"Xilinx. 2020b. Xilinx OpenNIC Shell. https:\/\/github.com\/Xilinx\/open-nic-shell"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359634"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556259"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3458817.3480854"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2910068"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588944","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588944","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:37Z","timestamp":1750178857000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588944"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":68,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588944"],"URL":"https:\/\/doi.org\/10.1145\/3588944","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}