{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T23:56:48Z","timestamp":1772927808015,"version":"3.50.1"},"reference-count":23,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2026,3,1]]},"DOI":"10.1587\/transfun.2025vlp0009","type":"journal-article","created":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T22:09:27Z","timestamp":1757455767000},"page":"563-570","source":"Crossref","is-referenced-by-count":0,"title":["Nested-Pipeline Delta-Stepping Scalable FPGA Accelerator for Parallel Single-Source Shortest Path with High-Level Synthesis"],"prefix":"10.1587","volume":"E109.A","author":[{"given":"Haopeng","family":"MENG","sequence":"first","affiliation":[{"name":"The University of Tokyo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazutoshi","family":"WAKABAYASHI","sequence":"additional","affiliation":[{"name":"The University of Tokyo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Makoto","family":"IKEDA","sequence":"additional","affiliation":[{"name":"The University of Tokyo"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] M. Abeydeera and D. Sanchez, \u201cChronos: Efficient speculative parallelism for accelerators,\u201d ASPLOS\u201920, pp.1247-1262, March 2020. 10.1145\/3373376.3378454","DOI":"10.1145\/3373376.3378454"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] Y. Hu, Y. Du, E. Ustun, and Z. Zhang, \u201cGraphLily: Accelerating graph linear algebra on HBM-equipped FPGAs,\u201d 2021 IEEE\/ACM International Conference On Computer Aided Design (ICCAD), 2021. 10.1109\/iccad51958.2021.9643582","DOI":"10.1109\/ICCAD51958.2021.9643582"},{"key":"3","doi-asserted-by":"crossref","unstructured":"[3] S. Zhou, R. Kannan, V.K. Prasanna, G. Seetharaman, and Q. Wu, \u201cHitGraph: High-throughput graph processing framework on FPGA,\u201d IEEE Trans. Parallel and Distrib. Syst., vol.30, no.10, pp.2249-2264, Oct. 2019. 10.1109\/tpds.2019.2910068","DOI":"10.1109\/TPDS.2019.2910068"},{"key":"4","doi-asserted-by":"publisher","unstructured":"[4] G. Lei, Y. Dou, R. Li, and F. Xia, \u201cAn FPGA implementation for solving the large single-source-shortest-path problem,\u201d IEEE Trans. Circuits Syst. II, Exp. Briefs, vol.63, no.5, pp.473-477, May 2016. 10.1109\/tcsii.2015.2505998","DOI":"10.1109\/TCSII.2015.2505998"},{"key":"5","unstructured":"[5] Y. Takei, M. Hariyama, and M. Kameyama, \u201cEvaluation of an FPGA-based shortest-path-search accelerator,\u201d Conference: International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), 2015."},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] X. Chen, F. Cheng, H. Tan, Y. Chen, B. He, W.-F. Wong, and D. Wang, \u201cThunderGP: HLS-based graph processing framework on FPGAs,\u201d ACM Trans. Reconfigurable Technol. Syst., vol.15, no.4, Article no.: 44, pp.1-31, Dec. 2022. 10.1145\/3517141","DOI":"10.1145\/3517141"},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] Y. Chi, L. Guo, and J. Cong, \u201cAccelerating SSSP for power-law graphs,\u201d Proc. 2022 ACM\/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA\u201922), pp.190-200, Feb. 2022. 10.1145\/3490422.3502358","DOI":"10.1145\/3490422.3502358"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. Paul, \u201cOptimistic parallelism requires abstractions,\u201d PLDI\u201907, pp.211-222, June 2007. 10.1145\/1250734.1250759","DOI":"10.1145\/1250734.1250759"},{"key":"9","unstructured":"[9] R. Bhagwan and B. Lin, \u201cFast and scalable priority queue architecture for high-speed network switches,\u201d Proc. IEEE INFOCOM 2000, March 2002. 10.1109\/infcom.2000.832227"},{"key":"10","doi-asserted-by":"publisher","unstructured":"[10] U. Meyer and P. Sanders, \u201cDelta-stepping: A parallelizable shortest path algorithm,\u201d J. Algorithms, vol.49, no.1, pp.114-152, Oct. 2003. 10.1016\/s0196-6774(03)00076-2","DOI":"10.1016\/S0196-6774(03)00076-2"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] A. Shimbel, \u201cStructural parameters of communication networks,\u201d The Bulletin of Mathematical Biophysics, vol.15, pp.501-507, 1953. 10.1007\/bf02476438","DOI":"10.1007\/BF02476438"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] R.A. Rossi and N.K. Ahmed, \u201cThe network data repository with interactive graph analytics and visualization,\u201d https:\/\/networkrepository.com, 2015.","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"13","unstructured":"[13] J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani, \u201cKronecker graphs: An approach to modeling networks,\u201d arXiv:0812.4905, Dec. 2008. 10.48550\/arXiv.0812.4905"},{"key":"14","doi-asserted-by":"crossref","unstructured":"[14] H. Park and M.-S. Kim, \u201cLineageBA: A fast, exact and scalable graph generation for the Barab\u00e1si-Albert model,\u201d 2021 IEEE 37th International Conference on Data Engineering (ICDE), 2021. 10.1109\/icde51399.2021.00053","DOI":"10.1109\/ICDE51399.2021.00053"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] Y. Chi and J. Cong, \u201cExploiting computation reuse for stencil accelerators,\u201d 2020 57th ACM\/IEEE Design Automation Conference (DAC), Oct. 2020. 10.1109\/dac18072.2020.9218680","DOI":"10.1109\/DAC18072.2020.9218680"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] Y. Chi, J. Cong, P. Wei, and P. Zhou, \u201cSODA: Stencil with optimized dataflow architecture,\u201d The International Conference, 2018. 10.1145\/3240765.3240850","DOI":"10.1145\/3240765.3240850"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] J. de Fine Licht, A. Kuster, T. De Matteis, T. Ben-Nun, D. Hofer, and T. Hoefler, \u201cStencilFlow: Mapping large stencil programs to distributed spatial computing systems,\u201d IET 2021 IEEE\/ACM International Symposium on Code Generation and Optimization (CGO), 2021. 10.1109\/cgo51591.2021.9370315","DOI":"10.1109\/CGO51591.2021.9370315"},{"key":"18","doi-asserted-by":"crossref","unstructured":"[18] J. Li, Y. Chi, and J. Cong, \u201cHeteroHalide: From image processing DSL to efficient FPGA acceleration,\u201d FPGA\u201920, pp.51-57, Feb. 2020. 10.1145\/3373087.3375320","DOI":"10.1145\/3373087.3375320"},{"key":"19","doi-asserted-by":"crossref","unstructured":"[19] K. Wang, D. Fussell, and C. Lin, \u201cA fast work-efficient SSSP algorithm for GPUs,\u201d PPoPP\u201921, pp.133-146, Feb. 2021. 10.1145\/3437801.3441605","DOI":"10.1145\/3437801.3441605"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] A. Davidson, S. Baxter, M. Garland, and J.D. Owens, \u201cWork-efficient parallel GPU methods for single-source shortest paths,\u201d 2014 IEEE 28th International Parallel and Distributed Processing Symposium, 2014. 10.1109\/ipdps.2014.45","DOI":"10.1109\/IPDPS.2014.45"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[21] G. Dai, Y. Chi, Y. Wang, and H. Yang, \u201cFPGP: Graph processing framework on FPGA a case study of breadth-first search,\u201d Proc. 2016 ACM\/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA\u201916), pp.105-110, Feb. 2016. 10.1145\/2847263.2847339","DOI":"10.1145\/2847263.2847339"},{"key":"22","doi-asserted-by":"crossref","unstructured":"[22] G. Dai, T. Huang, Y. Chi, N. Xu, Y. Wang, and H. Yang, \u201cForeGraph: Exploring large-scale graph processing on multi-FPGA architecture,\u201d IET FPGA\u201917, pp.217-226, Feb. 2017. 10.1145\/3020078.3021739","DOI":"10.1145\/3020078.3021739"},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] Z. Shao, R. Li, D. Hu, X. Liao, and H. Jin, \u201cImproving performance of graph processing on FPGA-DRAM platform by two-level vertex caching,\u201d FPGA\u201919, pp.320-329, Feb. 2019. 10.1145\/3289602.3293900","DOI":"10.1145\/3289602.3293900"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E109.A\/3\/E109.A_2025VLP0009\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T04:11:46Z","timestamp":1772856706000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E109.A\/3\/E109.A_2025VLP0009\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,1]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2025vlp0009","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,1]]},"article-number":"2025VLP0009"}}