{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T05:21:05Z","timestamp":1755926465762},"reference-count":109,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:p>Non-volatile main memory (NVRAM) technologies provide an attractive set of features for large-scale graph analytics, including byte-addressability, low idle power, and improved memory-density. NVRAM systems today have an order of magnitude more NVRAM than traditional memory (DRAM). NVRAM systems could therefore potentially allow very large graph problems to be solved on a single machine, at a modest cost. However, a significant challenge in achieving high performance is in accounting for the fact that NVRAM writes can be much more expensive than NVRAM reads.<\/jats:p>\n          <jats:p>\n            In this paper, we propose an approach to parallel graph analytics using the\n            <jats:italic>Parallel Semi-Asymmetric Model (PSAM)<\/jats:italic>\n            , in which the graph is stored as a read-only data structure (in NVRAM), and the amount of mutable memory is kept proportional to the number of vertices. Similar to the popular semi-external and semi-streaming models for graph analytics, the PSAM approach assumes that the vertices of the graph fit in a fast read-write memory (DRAM), but the edges do not. In NVRAM systems, our approach eliminates writes to the NVRAM, among other benefits.\n          <\/jats:p>\n          <jats:p>\n            To experimentally study this new setting, we develop\n            <jats:italic>Sage<\/jats:italic>\n            , a parallel semi-asymmetric graph engine with which we implement provably-efficient (and often work-optimal) PSAM algorithms for over a dozen fundamental graph problems. We experimentally study Sage using a 48--core machine on the largest publicly-available real-world graph (the Hyperlink Web graph with over 3.5 billion vertices and 128 billion edges) equipped with Optane DC Persistent Memory, and show that Sage outperforms the fastest prior systems designed for NVRAM. Importantly, we also show that Sage nearly matches the fastest prior systems running solely in DRAM, by effectively hiding the costs of repeatedly accessing NVRAM versus DRAM.\n          <\/jats:p>","DOI":"10.14778\/3397230.3397251","type":"journal-article","created":{"date-parts":[[2020,6,29]],"date-time":"2020-06-29T11:46:24Z","timestamp":1593431184000},"page":"1598-1613","source":"Crossref","is-referenced-by-count":15,"title":["Sage"],"prefix":"10.14778","volume":"13","author":[{"given":"Laxman","family":"Dhulipala","sequence":"first","affiliation":[{"name":"CMU"}]},{"given":"Charles","family":"McGuffey","sequence":"additional","affiliation":[{"name":"CMU"}]},{"given":"Hongbo","family":"Kang","sequence":"additional","affiliation":[{"name":"Tsinghua"}]},{"given":"Yan","family":"Gu","sequence":"additional","affiliation":[{"name":"U.C. Riverside"}]},{"given":"Guy E.","family":"Blelloch","sequence":"additional","affiliation":[{"name":"CMU"}]},{"given":"Phillip B.","family":"Gibbons","sequence":"additional","affiliation":[{"name":"CMU"}]},{"given":"Julian","family":"Shun","sequence":"additional","affiliation":[{"name":"MIT CSAIL"}]}],"member":"320","published-online":{"date-parts":[[2020,6,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0088-5"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal and J. S. Vitter. The Input\/Output complexity of sorting and related problems. Commun. ACM 31(9) 1988.  A. Aggarwal and J. S. Vitter. The Input\/Output complexity of sorting and related problems. Commun. ACM 31(9) 1988.","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"M. Alshboul H. Elnawawy R. Elkhouly K. Kimura J. Tuck and Y. Solihin. Efficient checkpointing with recompute scheme for non-volatile main memory. ACM Transactions on Architecture and Code Optimization (TACO) 16(2):18 2019.  M. Alshboul H. Elnawawy R. Elkhouly K. Kimura J. Tuck and Y. Solihin. Efficient checkpointing with recompute scheme for non-volatile main memory. ACM Transactions on Architecture and Code Optimization (TACO) 16(2):18 2019.","DOI":"10.1145\/3323091"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231764"},{"issue":"5","key":"e_1_2_1_5_1","first-page":"553","article-title":"BzTree: A high-performance latch-free range index for non-volatile memory","volume":"11","author":"Arulraj J.","year":"2018","journal-title":"PVLDB"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3054780"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"H. Attiya O. Ben-Baruch P. Fatourou D. Hendler and E. Kosmas. Tracking in order to recover: Recoverable lock-free data structures. CoRR abs\/1905.13600 2019.  H. Attiya O. Ben-Baruch P. Fatourou D. Hendler and E. Kosmas. Tracking in order to recover: Recoverable lock-free data structures. CoRR abs\/1905.13600 2019.","DOI":"10.1145\/3350755.3400257"},{"key":"e_1_2_1_8_1","volume-title":"SC","author":"Beamer S.","year":"2012"},{"key":"e_1_2_1_9_1","unstructured":"S. Beamer K. Asanovic and D. A. Patterson. The GAP benchmark suite. CoRR abs\/1508.03619 2015.  S. Beamer K. Asanovic and D. A. Patterson. The GAP benchmark suite. CoRR abs\/1508.03619 2015."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935767"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00081"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323187"},{"key":"e_1_2_1_13_1","unstructured":"G. E. Blelloch and L. Dhulipala. Introduction to parallel algorithms 15-853: Algorithms in the real world. 2018.  G. E. Blelloch and L. Dhulipala. Introduction to parallel algorithms 15-853: Algorithms in the real world. 2018."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935768"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755604"},{"key":"e_1_2_1_16_1","volume-title":"European Symposium on Algorithms (ESA)","author":"Blelloch G. E.","year":"2016"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3350755.3400227"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976021.8"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210380"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/209936.209958"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324962"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.3390\/mi10050346"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.114"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10586-019-02925-1"},{"key":"e_1_2_1_29_1","volume-title":"Conference on Innovative Data Systems Research (CIDR)","author":"Chen S.","year":"2011"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752947"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210400"},{"key":"e_1_2_1_32_1","volume-title":"MIT Press","author":"Cormen T. H.","year":"2009"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210392"},{"key":"e_1_2_1_34_1","volume-title":"FAST","author":"Da Zheng D. M.","year":"2015"},{"issue":"1","key":"e_1_2_1_35_1","volume":"38","author":"Davis T. A.","year":"2011","journal-title":"The University of Florida Sparse Matrix Collection. ACM Trans. Math. Softw."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087580"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210414"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"L. Dhulipala C. McGuffey H. Kang Y. Gu G. E. Blelloch P. B. Gibbons and J. Shun. Sage: Parallel semi-asymmetric graph algorithms for NVRAMs. arXiv preprint arXiv:1910.12310 2020.  L. Dhulipala C. McGuffey H. Kang Y. Gu G. E. Blelloch P. B. Gibbons and J. Shun. Sage: Parallel semi-asymmetric graph algorithms for NVRAMs. arXiv preprint arXiv:1910.12310 2020.","DOI":"10.14778\/3397230.3397251"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732289"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056115"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"J. Feigenbaum S. Kannan A. McGregor S. Suri and J. Zhang. On graph problems in a semi-streaming model. Theoretical Computer Science 348(2--3):207--216 2005.  J. Feigenbaum S. Kannan A. McGregor S. Suri and J. Zhang. On graph problems in a semi-streaming model. Theoretical Computer Science 348(2--3):207--216 2005.","DOI":"10.1016\/j.tcs.2005.09.013"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389145"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178506"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755597"},{"key":"e_1_2_1_45_1","volume-title":"European Symposium on Algorithms (ESA)","author":"Gu Y.","year":"2018"},{"key":"e_1_2_1_46_1","first-page":"337","volume-title":"ACM SIGMOD","author":"Han W.-S.","year":"2013"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2150976.2151013"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_49_1","unstructured":"J. Izraelevitz J. Yang L. Zhang J. Kim X. Liu A. Memaripour Y. J. Soh Z. Wang Y. Xu S. R. Dulloor etal Basic performance measurements of the Intel Optane DC persistent memory module. arXiv preprint arXiv:1903.05714 2019.  J. Izraelevitz J. Yang L. Zhang J. Kim X. Liu A. Memaripour Y. J. Soh Z. Wang Y. Xu S. R. Dulloor et al. Basic performance measurements of the Intel Optane DC persistent memory module. arXiv preprint arXiv:1903.05714 2019."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087583"},{"key":"e_1_2_1_51_1","volume-title":"Addison-Wesley Professional","author":"Jaja J.","year":"1992"},{"key":"e_1_2_1_52_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1007\/978-3-319-49487-6_11","volume-title":"Algorithm Engineering - Selected Results and Surveys","author":"Kliemann L.","year":"2016"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_54_1","volume-title":"USENIX Conference on File and Storage Technologies (FAST)","author":"Lee S. K.","year":"2017"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3329785.3329931"},{"key":"e_1_2_1_56_1","unstructured":"J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014.  J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014."},{"key":"e_1_2_1_57_1","article-title":"Efficient core maintenance in large dynamic graphs","author":"Li R.-H.","year":"2013","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2019.00009"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2018.00029"},{"key":"e_1_2_1_60_1","unstructured":"X. Liu Y. Hua X. Li and Q. Liu. Write-optimized and consistent RDMA-based NVM systems. arXiv preprint arXiv:1906.08173 2019.  X. Liu Y. Hua X. Li and Q. Liu. Write-optimized and consistent RDMA-based NVM systems. arXiv preprint arXiv:1906.08173 2019."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064191"},{"key":"e_1_2_1_62_1","doi-asserted-by":"crossref","unstructured":"R. R. McCune T. Weninger and G. Madey. Thinking like a vertex: A survey of vertex-centric frameworks for large-scale distributed graph processing. ACM Comput. Surv. 48(2) Oct. 2015.  R. R. McCune T. Weninger and G. Madey. Thinking like a vertex: A survey of vertex-centric frameworks for large-scale distributed graph processing. ACM Comput. Surv. 48(2) Oct. 2015.","DOI":"10.1145\/2818185"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_2_1_64_1","volume-title":"Workshop on Hot Topics in Operating Systems (HotOS)","author":"McSherry F.","year":"2015"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740673"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2567948.2576928"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1561\/106.00000003"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755574"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486180"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2019.00058"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137629"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2019.00100"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.34"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/P14-1131"},{"issue":"4","key":"e_1_2_1_77_1","first-page":"420","article-title":"The ubiquity of large graphs and surprising challenges of graph processing","volume":"11","author":"Sahu S.","year":"2017","journal-title":"PVLDB"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275536.3275540"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741640"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68783-4_31"},{"key":"e_1_2_1_81_1","doi-asserted-by":"crossref","unstructured":"J. Shi L. Dhulipala and J. Shun. Parallel clique counting and peeling algorithms. arXiv preprint arXiv:2002.10047 2020.  J. Shi L. Dhulipala and J. Shun. Parallel clique counting and peeling algorithms. arXiv preprint arXiv:2002.10047 2020.","DOI":"10.1137\/1.9781611976830.13"},{"key":"e_1_2_1_82_1","doi-asserted-by":"crossref","unstructured":"X. Shi Z. Zheng Y. Zhou H. Jin L. He B. Liu and Q.-S. Hua. Graph processing on GPUs: A survey. ACM Comput. Surv. 50(6) Jan. 2018.  X. Shi Z. Zheng Y. Zhou H. Jin L. He B. Liu and Q.-S. Hua. Graph processing on GPUs: A survey. ACM Comput. Surv. 50(6) Jan. 2018.","DOI":"10.1145\/3128571"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314608"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612692"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2015.8"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994522"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/3079079.3079097"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPADS.2017.00045"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364334"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178509"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196897"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/3329785.3329930"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33074-2_30"},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732269.2732277"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1145\/3316482.3326358"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_99_1","first-page":"763","volume-title":"USENIX Symposium on Operating Systems Design and Implementation (OSDI)","author":"Wang K.","year":"2018"},{"key":"e_1_2_1_100_1","volume-title":"ACM SIGMOD","author":"Wang Y.","year":"2020"},{"key":"e_1_2_1_101_1","first-page":"7","article-title":"Big graph analytics platforms","author":"Yan D.","year":"2017","journal-title":"Foundations and Trends in Databases"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688500.2688507"},{"key":"e_1_2_1_104_1","volume-title":"USENIX Annual Technical Conference (USENIX ATC)","author":"Zhang L.","year":"2019"},{"key":"e_1_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276491"},{"key":"e_1_2_1_106_1","volume-title":"USENIX Conference on File and Storage Technologies (FAST)","author":"Zheng D.","year":"2015"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2618791"},{"key":"e_1_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323176"},{"key":"e_1_2_1_109_1","first-page":"301","volume-title":"USENIX Symposium on Operating Systems Design and Implementation (OSDI)","author":"Zhu X.","year":"2016"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3397230.3397251","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:25:47Z","timestamp":1672223147000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3397230.3397251"}},"subtitle":["parallel semi-asymmetric graph algorithms for NVRAMs"],"short-title":[],"issued":{"date-parts":[[2020,5]]},"references-count":109,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["10.14778\/3397230.3397251"],"URL":"https:\/\/doi.org\/10.14778\/3397230.3397251","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,5]]}}}