{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T06:19:38Z","timestamp":1767853178183,"version":"3.49.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,3]],"date-time":"2020-06-03T00:00:00Z","timestamp":1591142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Key Research and Development Program of China","award":["2018YFB1003500"],"award-info":[{"award-number":["2018YFB1003500"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61972444, 61825202, 61832006 and 61732010"],"award-info":[{"award-number":["61972444, 61825202, 61832006 and 61732010"]}],"id":[{"id":"10.13039\/501100001809","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":[[2020,9,30]]},"abstract":"<jats:p>Graph processing is one of the important research topics in the big-data era. To build a general framework for graph processing by using a DRAM-based FPGA board with deep memory hierarchy, one of the reasonable methods is to partition a given big graph into multiple small subgraphs, represent the graph with a two-dimensional grid, and then process the subgraphs one after another to divide and conquer the whole problem. Such a method (grid-graph processing) stores the graph data in the off-chip memory devices (e.g., on-board or host DRAM) that have large storage capacities but relatively small bandwidths, and processes individual small subgraphs one after another by using the on-chip memory devices (e.g., FFs, BRAM, and URAM) that have small storage capacities but superior random access performances. However, directly exchanging graph (vertex and edge) data between the processing units in FPGA chip with slow off-chip DRAMs during grid-graph processing leads to limited performances and excessive data transmission amounts between the FPGA chip and off-chip memory devices.<\/jats:p>\n          <jats:p>\n            In this article, we show that it is effective in improving the performance of grid-graph processing on DRAM-based FPGA hardware accelerators by leveraging the flexibility and programmability of FPGAs to build application-specific caching mechanisms, which bridge the performance gaps between on-chip and off-chip memory devices, and reduce the data transmission amounts by exploiting the localities on data accessing. We design two application-specific caching mechanisms (i.e.,\n            <jats:italic>vertex caching<\/jats:italic>\n            and\n            <jats:italic>edge caching<\/jats:italic>\n            ) to exploit two types of localities (i.e.,\n            <jats:italic>vertex locality<\/jats:italic>\n            and\n            <jats:italic>subgraph locality<\/jats:italic>\n            ) that exist in grid-graph processing, respectively. Experimental results show that with the vertex caching mechanism, our system (named as FabGraph) achieves up to 3.1\u00d7 and 2.5\u00d7 speedups for BFS and PageRank, respectively, over ForeGraph when processing medium graphs stored in the on-board DRAM. With the edge caching mechanism, the extension of FabGraph (named as FabGraph+) achieves up to 9.96\u00d7 speedups for BFS over FPGP when processing large graphs stored in the host DRAM.\n          <\/jats:p>","DOI":"10.1145\/3391920","type":"journal-article","created":{"date-parts":[[2020,6,3]],"date-time":"2020-06-03T16:06:02Z","timestamp":1591200362000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Processing Grid-format Real-world Graphs on DRAM-based FPGA Accelerators with Application-specific Caching Mechanisms"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2139-6465","authenticated-orcid":false,"given":"Zhiyuan","family":"Shao","sequence":"first","affiliation":[{"name":"National Engineering Research Center for Big Data Technology and System, Services Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenhao","family":"Liu","sequence":"additional","affiliation":[{"name":"National Engineering Research Center for Big Data Technology and System, Services Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruoshi","family":"Li","sequence":"additional","affiliation":[{"name":"National Engineering Research Center for Big Data Technology and System, Services Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaofei","family":"Liao","sequence":"additional","affiliation":[{"name":"National Engineering Research Center for Big Data Technology and System, Services Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hai","family":"Jin","sequence":"additional","affiliation":[{"name":"National Engineering Research Center for Big Data Technology and System, Services Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77615"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2018.2858250"},{"key":"e_1_2_1_3_1","unstructured":"ARM. 2019. AMBA AXI and ACE Protocol Specification. Retrieved from https:\/\/static.docs.arm.com\/ihi0022\/g\/IHI0022G_amba_axi_protocol_spec.pdf.  ARM. 2019. AMBA AXI and ACE Protocol Specification. Retrieved from https:\/\/static.docs.arm.com\/ihi0022\/g\/IHI0022G_amba_axi_protocol_spec.pdf."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the IEEE International Parallel Distributed Processing Symposium Workshops (IPDPSW\u201914)","author":"Attia O. G."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the IEEE International Symposium on Workload Characterization (IISWC\u201915)","author":"Beamer S."},{"key":"e_1_2_1_6_1","first-page":"3","article-title":"Community detection in social networks","volume":"6","author":"Bedi P.","year":"2016","journal-title":"WIREs Data Min. Knowl. Discov."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP\u201912)","author":"Betkaoui B."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"C. E. Bichot and P. Siarry. 2013. Graph Partitioning. John Wiley 8 Sons Ltd.  C. E. Bichot and P. Siarry. 2013. Graph Partitioning. John Wiley 8 Sons Ltd.","DOI":"10.1002\/9781118601181"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480506.1480511"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE\u201916)","author":"Chi Y."},{"key":"e_1_2_1_12_1","unstructured":"Graph 500 Committees. 2017. Graph 500. Retrieved from http:\/\/graph500.org\/.  Graph 500 Committees. 2017. Graph 500. Retrieved from http:\/\/graph500.org\/."},{"key":"e_1_2_1_13_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2001. Introduction to Algorithms (2 ed.). MIT Press and McGraw-Hill. 531\u2013539 pages.  T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2001. Introduction to Algorithms (2 ed.). MIT Press and McGraw-Hill. 531\u2013539 pages."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the ACM\/SIGDA International Conference on Field-Programmable Gate Arrays (FPGA\u201916)","author":"Dai G."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the ACM\/SIGDA International Conference on Field-Programmable Gate Arrays (FPGA\u201917)","author":"Dai G."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM\u201906)","author":"deLorimier M."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/316194.316229"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912)","author":"Gonzalez J. E."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the IEEE\/ACM International Symposium on Microarchitecture (MICRO\u201916)","author":"Ham T. J."},{"key":"e_1_2_1_20_1","volume-title":"Computer Architecture: A Quantitative ApproachComputer Architecture: A Quantitative Approach","author":"Hennessy J. L.","year":"2011","edition":"5"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01199431"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the IEEE International Memory Workshop (IMW\u201917)","author":"Jun H."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASAP.2015.7245698"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the ACM International Conference on World Wide Web (WWW\u201910)","author":"Kwak H."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSII.2015.2505998"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the VLDB Endowment (VLDB\u201912)","author":"Low Y."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD\u201910)","author":"Malewicz G."},{"key":"e_1_2_1_28_1","unstructured":"Micron. 2015. DDR4 SDRAM for Automotive. Retrieved from https:\/\/www.micron.com\/products\/dram\/ddr4-sdram\/.  Micron. 2015. DDR4 SDRAM for Automotive. Retrieved from https:\/\/www.micron.com\/products\/dram\/ddr4-sdram\/."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM\u201914)","author":"Nurvitadhi E."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the ACM\/SIGDA International Conference on Field-Programmable Gate Arrays (FPGA\u201916)","author":"Oguntebi T."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/L-CA.2011.4"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the ACM Symposium on Operating Systems Principles (SOSP\u201913)","author":"Roy A."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the ACM\/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA\u201919)","author":"Shao Z."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517327.2442530"},{"key":"e_1_2_1_35_1","unstructured":"Stanford. 2018. SNAP large network dataset collection. Retrieved from http:\/\/snap.stanford.edu\/data\/index.html.  Stanford. 2018. SNAP large network dataset collection. Retrieved from http:\/\/snap.stanford.edu\/data\/index.html."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the VLDB Endowment (VLDB\u201913)","author":"Tian Y."},{"key":"e_1_2_1_37_1","unstructured":"J. Ugander B. Karrer L. Backstrom and C. Marlow. 2011. The anatomy of the facebook social graph. Retrieved from http:\/\/arxiv.org\/abs\/1111.4503.  J. Ugander B. Karrer L. Backstrom and C. Marlow. 2011. The anatomy of the facebook social graph. Retrieved from http:\/\/arxiv.org\/abs\/1111.4503."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3108140"},{"key":"e_1_2_1_39_1","unstructured":"Wikipedia. 2010. PCI Express. Retrieved from https:\/\/en.wikipedia.org\/wiki\/PCI_Express.  Wikipedia. 2010. PCI Express. Retrieved from https:\/\/en.wikipedia.org\/wiki\/PCI_Express."},{"key":"e_1_2_1_40_1","unstructured":"Xilinx. 2017. Block Memory Generator v8.4. Retrieved from https:\/\/www.xilinx.com\/support\/documentation\/ip_documentation\/blk_mem_gen\/v8_4\/.  Xilinx. 2017. Block Memory Generator v8.4. Retrieved from https:\/\/www.xilinx.com\/support\/documentation\/ip_documentation\/blk_mem_gen\/v8_4\/."},{"key":"e_1_2_1_41_1","unstructured":"Xilinx. 2018. UltraScale Architecture Memory Resources-User Guide. Retrieved from https:\/\/www.xilinx.com\/support\/documentation\/user_guides\/.  Xilinx. 2018. UltraScale Architecture Memory Resources-User Guide. Retrieved from https:\/\/www.xilinx.com\/support\/documentation\/user_guides\/."},{"key":"e_1_2_1_42_1","unstructured":"Xilinx. 2018. Xilinx Boards and Kits. Retrieved from https:\/\/www.xilinx.com\/products\/boards-and-kits.html.  Xilinx. 2018. Xilinx Boards and Kits. Retrieved from https:\/\/www.xilinx.com\/products\/boards-and-kits.html."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the ACM\/SIGDA International Conference on Field-Programmable Gate Arrays (FPGA\u201917)","author":"Zhang J."},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the ACM\/SIGDA International Conference on Field-Programmable Gate Arrays (FPGA\u201918)","author":"Zhang J."},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP\u201915)","author":"Zhang K."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2694413.2694421"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium Workshop (IPDPSW\u201915)","author":"Zhou S."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the IEEE International Conference on ReConFigurable Computing and FPGAs (ReConFig\u201915)","author":"Zhou S."},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM\u201916)","author":"Zhou S."},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the USENIX Conference on Usenix Annual Technical Conference (ATC\u201915)","author":"Zhu X."},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the IEEE International Conference on Field-Programmable Technology (FPT\u201918)","author":"Zou Y."},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI\u201918)","author":"Zou Y."}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3391920","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3391920","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:48Z","timestamp":1750199928000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3391920"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,3]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9,30]]}},"alternative-id":["10.1145\/3391920"],"URL":"https:\/\/doi.org\/10.1145\/3391920","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"value":"1936-7406","type":"print"},{"value":"1936-7414","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,3]]},"assertion":[{"value":"2019-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}