{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,3]],"date-time":"2026-09-03T16:55:01Z","timestamp":1788454501986,"version":"build-2803163510"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,2,26]],"date-time":"2018-02-26T00:00:00Z","timestamp":1519603200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61672116"],"award-info":[{"award-number":["61672116"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Chongqing High-Tech Research Program","award":["cstc2016jcyjA0332"],"award-info":[{"award-number":["cstc2016jcyjA0332"]}]},{"name":"Research Grants Council of the Hong Kong Special Administrative Region, China","award":["GRF 15222315\/15E, GRF 152736\/16E and GRF 152066\/17E"],"award-info":[{"award-number":["GRF 15222315\/15E, GRF 152736\/16E and GRF 152066\/17E"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2018,2,28]]},"abstract":"<jats:p>Graph algorithms such as graph traversal have been gaining ever-increasing importance in the era of big data. However, graph processing on traditional architectures issues many random and irregular memory accesses, leading to a huge number of data movements and the consumption of very large amounts of energy. To minimize the waste of memory bandwidth, we investigate utilizing processing-in-memory (PIM), combined with non-volatile metal-oxide resistive random access memory (ReRAM), to improve both computation and I\/O performance.<\/jats:p>\n          <jats:p>We propose a new ReRAM-based processing-in-memory architecture called RPBFS, in which graph data can be persistently stored and processed in place. We study the problem of graph traversal, and we design an efficient graph traversal algorithm in RPBFS. Benefiting from low data movement overhead and high bank-level parallel computation, RPBFS shows a significant performance improvement compared with both the CPU-based and the GPU-based BFS implementations. On a suite of real-world graphs, our architecture yields a speedup in graph traversal performance of up to 33.8\u00d7, and achieves a reduction in energy over conventional systems of up to 142.8\u00d7.<\/jats:p>","DOI":"10.1145\/3177916","type":"journal-article","created":{"date-parts":[[2018,2,26]],"date-time":"2018-02-26T18:25:15Z","timestamp":1519669515000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["A Novel ReRAM-Based Processing-in-Memory Architecture for Graph Traversal"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1081-9178","authenticated-orcid":false,"given":"Lei","family":"Han","sequence":"first","affiliation":[{"name":"Hong Kong Polytechnic University, Hong Kong SAR, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhaoyan","family":"Shen","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University, Hong Kong SAR, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Duo","family":"Liu","sequence":"additional","affiliation":[{"name":"Chongqing University, Chongqing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zili","family":"Shao","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University, Hong Kong SAR, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"H. Howie","family":"Huang","sequence":"additional","affiliation":[{"name":"George Washington University, Washington, DC"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao","family":"Li","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,2,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2749469.2750386"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2749469.2750385"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2749469.2750397"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1088\/0957-4484\/23\/7\/075201"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2014.55"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1155\/2013\/702694"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2015.12"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741970"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2016.13"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Workshop on Economics of Peer-to-Peer Systems","volume":"6","author":"Cohen Bram","year":"2003"},{"key":"e_1_2_1_11_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/99.660313"},{"key":"e_1_2_1_13_1","volume-title":"Emerging Memory Technologies","author":"Dong Xiangyu"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/NVMSA.2017.8064464"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.14"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_17_1","unstructured":"Jure Leskovec and Andrej Krevl. 2015. {SNAP Datasets}:{Stanford} Large Network Dataset Collection.  Jure Leskovec and Andrej Krevl. 2015. {SNAP Datasets}:{Stanford} Large Network Dataset Collection."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/IMW.2011.5873227"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2014.2341922"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807594"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882959"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2744769.2744900"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2464996.2465013"},{"key":"e_1_2_1_24_1","volume-title":"Intel power gadget","author":"Dimitrov Martin","year":"2016"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370036.2145832"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 5th Workshop on Architectures and Systems for Big Data (ASBD\u201915)","author":"Mirzadeh Nooshin","year":"2015"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2561828.2561832"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2650280.2650336"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2016.24"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPASS.2014.6844483"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2024724.2024730"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484843"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2540708.2540725"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2016.12"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/605459.605464"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2017.55"},{"key":"e_1_2_1_40_1","first-page":"06248","article-title":"GraphR: Accelerating graph processing using ReRAM","volume":"1708","author":"Song Linghao","year":"2017","journal-title":"Arxiv"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/NVMSA.2017.8064463"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851145"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMSCS.2016.2516015"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2012.2190369"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/2691365.2691376"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE). IEEE, 1--6.","author":"Xu Cong","year":"2011"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2015.7056056"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463209.2488867"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600212.2600213"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2971808.2971982"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3020078.3021737"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.111"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/3DIC.2013.6702348"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2013.6670336"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3177916","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3177916","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:02:55Z","timestamp":1750215775000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3177916"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,26]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2,28]]}},"alternative-id":["10.1145\/3177916"],"URL":"https:\/\/doi.org\/10.1145\/3177916","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,26]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}