{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T15:43:48Z","timestamp":1783784628904,"version":"3.55.0"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:p>Modern analytics and recommendation systems are increasingly based on graph data that capture the relations between entities being analyzed. Practical graphs come in huge sizes, offer massive parallelism, and are stored in sparse-matrix formats such as compressed sparse row (CSR). To exploit the massive parallelism, developers are increasingly interested in using GPUs for graph traversal. However, due to their sizes, graphs often do not fit into the GPU memory. Prior works have either used input data pre-processing\/partitioning or unified virtual memory (UVM) to migrate chunks of data from the host memory to the GPU memory. However, the large, multi-dimensional, and sparse nature of graph data presents a major challenge to these schemes and results in significant amplification of data movement and reduced effective data throughput. In this work, we propose EMOGI, an alternative approach to traverse graphs that do not fit in GPU memory using direct cache-line-sized access to data stored in host memory.<\/jats:p>\n          <jats:p>This paper addresses the open question of whether a sufficiently large number of overlapping cache-line-sized accesses can be sustained to 1) tolerate the long latency to host memory, 2) fully utilize the available bandwidth, and 3) achieve favorable execution performance. We analyze the data access patterns of several graph traversal applications in GPU over PCIe using an FPGA to understand the cause of poor external bandwidth utilization. By carefully coalescing and aligning external memory requests, we show that we can minimize the number of PCIe transactions and nearly fully utilize the PCIe bandwidth with direct cache-line accesses to the host memory. EMOGI achieves 2.60X speedup on average compared to the optimized UVM implementations in various graph traversal applications. We also show that EMOGI scales better than a UVM-based solution when the system uses higher bandwidth interconnects such as PCIe 4.0.<\/jats:p>","DOI":"10.14778\/3425879.3425883","type":"journal-article","created":{"date-parts":[[2020,11,25]],"date-time":"2020-11-25T02:45:23Z","timestamp":1606272323000},"page":"114-127","source":"Crossref","is-referenced-by-count":50,"title":["EMOGI"],"prefix":"10.14778","volume":"14","author":[{"given":"Seung Won","family":"Min","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vikram Sharma","family":"Mailthody","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zaid","family":"Qureshi","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jinjun","family":"Xiong","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center Yorktown Heights"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eiman","family":"Ebrahimi","sequence":"additional","affiliation":[{"name":"NVIDIA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wen-mei","family":"Hwu","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,11,16]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. nvGRAPH. https:\/\/developer.nvidia.com\/nvgraph.  [n.d.]. nvGRAPH. https:\/\/developer.nvidia.com\/nvgraph."},{"key":"e_1_2_1_2_1","unstructured":"2016. NVIDIA Tesla P100 Architecture Whitepaper. https:\/\/www.nvidia.com\/object\/pascal-architecture-whitepaper.html.  2016. NVIDIA Tesla P100 Architecture Whitepaper. https:\/\/www.nvidia.com\/object\/pascal-architecture-whitepaper.html."},{"key":"e_1_2_1_3_1","unstructured":"2017. NVIDIA Tesla V100 GPU Architecture Whitepaper. https:\/\/images.nvidia.com\/content\/volta-architecture\/pdf\/volta-architecture-whitepaper.pdf.  2017. NVIDIA Tesla V100 GPU Architecture Whitepaper. https:\/\/images.nvidia.com\/content\/volta-architecture\/pdf\/volta-architecture-whitepaper.pdf."},{"key":"e_1_2_1_4_1","unstructured":"2020. CUDA C++ Best Practices Guide. https:\/\/docs.nvidia.com\/cuda\/cuda-c-best-practices-guide\/index.html.  2020. CUDA C++ Best Practices Guide. https:\/\/docs.nvidia.com\/cuda\/cuda-c-best-practices-guide\/index.html."},{"key":"e_1_2_1_5_1","unstructured":"2020. Intel\u00ae VTune\u2122 Profiler. https:\/\/software.intel.com\/content\/www\/us\/en\/develop\/tools\/vtune-profiler.html.  2020. Intel\u00ae VTune \u2122 Profiler. https:\/\/software.intel.com\/content\/www\/us\/en\/develop\/tools\/vtune-profiler.html."},{"key":"e_1_2_1_6_1","unstructured":"2020. NVIDIA A100 GPU Architecture Whitepaper. https:\/\/www.nvidia.com\/content\/dam\/en-zz\/Solutions\/Data-Center\/nvidia-ampere-architecture-whitepaper.pdf.  2020. NVIDIA A100 GPU Architecture Whitepaper. https:\/\/www.nvidia.com\/content\/dam\/en-zz\/Solutions\/Data-Center\/nvidia-ampere-architecture-whitepaper.pdf."},{"key":"e_1_2_1_7_1","unstructured":"2020. NVIDIA DGX A100 Datasheet. https:\/\/www.nvidia.com\/content\/dam\/en-zz\/Solutions\/Data-Center\/nvidia-dgx-a100-datasheet.pdf.  2020. NVIDIA DGX A100 Datasheet. https:\/\/www.nvidia.com\/content\/dam\/en-zz\/Solutions\/Data-Center\/nvidia-dgx-a100-datasheet.pdf."},{"key":"e_1_2_1_8_1","unstructured":"2020. PCIe 3.0 Specification. https:\/\/members.pcisig.com\/wg\/PCI-SIG\/document\/download\/8257.  2020. PCIe 3.0 Specification. https:\/\/members.pcisig.com\/wg\/PCI-SIG\/document\/download\/8257."},{"key":"e_1_2_1_9_1","volume-title":"2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 458--466","author":"Aasawat T. K.","unstructured":"T. K. Aasawat , T. Reza , and M. Ripeanu . 2018. How Well do CPU, GPU and Hybrid Graph Processing Frameworks Perform? . In 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 458--466 . T. K. Aasawat, T. Reza, and M. Ripeanu. 2018. How Well do CPU, GPU and Hybrid Graph Processing Frameworks Perform?. In 2018 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). 458--466."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786763.2694381"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3123939.3123975"},{"key":"e_1_2_1_12_1","volume-title":"Patterson","author":"Beamer Scott","year":"2015","unstructured":"Scott Beamer , Krste Asanovic , and David A . Patterson . 2015 . The GAP Benchmark Suite. CoRR abs\/1508.03619 (2015). arXiv:1508.03619 http:\/\/arxiv.org\/abs\/1508.03619 Scott Beamer, Krste Asanovic, and David A. Patterson. 2015. The GAP Benchmark Suite. CoRR abs\/1508.03619 (2015). arXiv:1508.03619 http:\/\/arxiv.org\/abs\/1508.03619"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.587"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.587"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2014.7040962"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2014.07.003"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3307681.3326606"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3307650.3322224"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Thirty-forth International Conference on Parallel and Distributed Processing (IPDPS).","author":"Ganguly Debashis","year":"2020","unstructured":"Debashis Ganguly , Z Zhang , J Yang , and Rami Melhem . 2020 . Adaptive Page Migration for Irregular Data-intensive Applications under GPU Memory Over-subscription . In Proceedings of the Thirty-forth International Conference on Parallel and Distributed Processing (IPDPS). Debashis Ganguly, Z Zhang, J Yang, and Rami Melhem. 2020. Adaptive Page Migration for Irregular Data-intensive Applications under GPU Memory Over-subscription. In Proceedings of the Thirty-forth International Conference on Parallel and Distributed Processing (IPDPS)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384358"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370816.2370866"},{"key":"e_1_2_1_25_1","volume-title":"2017 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). 43--54","author":"G\u00f3mez-Luna J.","unstructured":"J. G\u00f3mez-Luna , I. E. Hajj , L. Chang , V. Garc\u00eda-Floreszx , S. G. de Gonzalo , T. B. Jablin , A. J. Pe\u00f1a , and W. Hwu . 2017. Chai: Collaborative heterogeneous applications for integrated-architectures . In 2017 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). 43--54 . J. G\u00f3mez-Luna, I. E. Hajj, L. Chang, V. Garc\u00eda-Floreszx, S. G. de Gonzalo, T. B. Jablin, A. J. Pe\u00f1a, and W. Hwu. 2017. Chai: Collaborative heterogeneous applications for integrated-architectures. In 2017 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). 43--54."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/3195638.3195707"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of 26th International Conference on Parallel Architectures and Compilation Techniques (PACT). 233--245","author":"Han W.","unstructured":"W. Han , D. Mawhirter , B. Wu , and M. Buland . 2017. Graphie: Large-Scale Asynchronous Graph Traversals on Just a GPU . In Proceedings of 26th International Conference on Parallel Architectures and Compilation Techniques (PACT). 233--245 . W. Han, D. Mawhirter, B. Wu, and M. Buland. 2017. Graphie: Large-Scale Asynchronous Graph Traversals on Just a GPU. In Proceedings of 26th International Conference on Parallel Architectures and Compilation Techniques (PACT). 233--245."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1782174.1782200"},{"key":"e_1_2_1_29_1","unstructured":"Mark Harris. 2017. Unified Memory for CUDA Beginners. https:\/\/devblogs.nvidia.com\/unified-memory-cuda-beginners\/.  Mark Harris. 2017. Unified Memory for CUDA Beginners. https:\/\/devblogs.nvidia.com\/unified-memory-cuda-beginners\/."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2010.07.002"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038037.1941590"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038037.1941590"},{"key":"e_1_2_1_33_1","volume-title":"New Trends in Database","author":"Kaczmarski Krzysztof","unstructured":"Krzysztof Kaczmarski , Piotr Przymus , and Pawe\u0142 Rz\u0105\u017cewski . 2015. Improving high-performance GPU graph traversal with compression . In New Trends in Database and Information Systems II. Springer , 201--214. Krzysztof Kaczmarski, Piotr Przymus, and Pawe\u0142 Rz\u0105\u017cewski. 2015. Improving high-performance GPU graph traversal with compression. In New Trends in Database and Information Systems II. Springer, 201--214."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2817817.2731192"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2015.15"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600212.2600227"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373376.3378529"},{"key":"e_1_2_1_38_1","volume-title":"ReCALL: Reordered Cache Aware Locality Based Graph Processing. In 2017 IEEE 24th International Conference on High Performance Computing (HiPC). 273--282","author":"Lakhotia K.","unstructured":"K. Lakhotia , S. Singapura , R. Kannan , and V. Prasanna . 2017 . ReCALL: Reordered Cache Aware Locality Based Graph Processing. In 2017 IEEE 24th International Conference on High Performance Computing (HiPC). 273--282 . K. Lakhotia, S. Singapura, R. Kannan, and V. Prasanna. 2017. ReCALL: Reordered Cache Aware Locality Based Graph Processing. In 2017 IEEE 24th International Conference on High Performance Computing (HiPC). 273--282."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304044"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/3154690.3154709"},{"key":"e_1_2_1_41_1","volume-title":"2018 IEEE High Performance extreme Computing Conference (HPEC'18).","author":"Mailthody Vikram S","unstructured":"Vikram S Mailthody , Ketan Date , Zaid Qureshi , Carl Pearson , Rakesh Nagi , Jinjun Xiong , and Wen-mei Hwu. 2018. Collaborative (CPU+ GPU) algorithms for triangle counting and truss decomposition. In 2018 IEEE High Performance extreme Computing Conference (HPEC'18). Boston, USA. Vikram S Mailthody, Ketan Date, Zaid Qureshi, Carl Pearson, Rakesh Nagi, Jinjun Xiong, and Wen-mei Hwu. 2018. Collaborative (CPU+ GPU) algorithms for triangle counting and truss decomposition. In 2018 IEEE High Performance extreme Computing Conference (HPEC'18). Boston, USA."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2717511"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807626"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3296957.3173180"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3022671.2984015"},{"key":"e_1_2_1_48_1","volume-title":"Multi-GPU Graph Analytics. In 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 479--490","author":"Pan Y.","unstructured":"Y. Pan , Y. Wang , Y. Wu , C. Yang , and J. D. Owens . 2017 . Multi-GPU Graph Analytics. In 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 479--490 . Y. Pan, Y. Wang, Y. Wu, C. Yang, and J. D. Owens. 2017. Multi-GPU Graph Analytics. In 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 479--490."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.34"},{"key":"e_1_2_1_50_1","volume-title":"Update on Triangle Counting on GPU. In 2019 IEEE High Performance extreme Computing Conference (HPEC'19)","author":"Pearson Carl","unstructured":"Carl Pearson , Mohammad Almasri , Omer Anjum , Vikram S Mailthody , Zaid Qureshi , Rakesh Nagi , Jinjun Xiong , and Wen-mei Hwu. 2019. Update on Triangle Counting on GPU. In 2019 IEEE High Performance extreme Computing Conference (HPEC'19) . Boston, USA. Carl Pearson, Mohammad Almasri, Omer Anjum, Vikram S Mailthody, Zaid Qureshi, Rakesh Nagi, Jinjun Xiong, and Wen-mei Hwu. 2019. Update on Triangle Counting on GPU. In 2019 IEEE High Performance extreme Computing Conference (HPEC'19). Boston, USA."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/2888116.2888372"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387537"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41060-016-0027-9"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807655"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151113.3151122"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319871"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517327.2442530"},{"key":"e_1_2_1_59_1","volume-title":"Euro-Par 2014 Parallel Processing, Fernando Silva, In\u00eas Dutra, and V\u00edtor Santos Costa (Eds.)","author":"Simmhan Yogesh","unstructured":"Yogesh Simmhan , Alok Kumbhare , Charith Wickramaarachchi , Soonil Nagarkar , Santosh Ravi , Cauligi Raghavendra , and Viktor Prasanna . 2014. GoFFish: A Sub-graph Centric Framework for Large-Scale Graph Analytics . In Euro-Par 2014 Parallel Processing, Fernando Silva, In\u00eas Dutra, and V\u00edtor Santos Costa (Eds.) . Springer International Publishing , Cham , 451--462. Yogesh Simmhan, Alok Kumbhare, Charith Wickramaarachchi, Soonil Nagarkar, Santosh Ravi, Cauligi Raghavendra, and Viktor Prasanna. 2014. GoFFish: A Sub-graph Centric Framework for Large-Scale Graph Analytics. In Euro-Par 2014 Parallel Processing, Fernando Silva, In\u00eas Dutra, and V\u00edtor Santos Costa (Eds.). Springer International Publishing, Cham, 451--462."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809983"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098057"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3016078.2851145"},{"key":"e_1_2_1_64_1","volume-title":"GARDENIA: A Domain-specific Benchmark Suite for Next-generation Accelerators. CoRR abs\/1708.04567","author":"Xu Zhen","year":"2017","unstructured":"Zhen Xu , Xuhao Chen , Jie Shen , Yang Zhang , Cheng Chen , and Canqun Yang . 2017 . GARDENIA: A Domain-specific Benchmark Suite for Next-generation Accelerators. CoRR abs\/1708.04567 (2017). arXiv:1708.04567 http:\/\/arxiv.org\/abs\/1708.04567 Zhen Xu, Xuhao Chen, Jie Shen, Yang Zhang, Cheng Chen, and Canqun Yang. 2017. GARDENIA: A Domain-specific Benchmark Suite for Next-generation Accelerators. CoRR abs\/1708.04567 (2017). arXiv:1708.04567 http:\/\/arxiv.org\/abs\/1708.04567"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.138"},{"key":"e_1_2_1_66_1","volume-title":"2017 IEEE International Conference on Big Data (Big Data). 293--302","author":"Zhang Y.","unstructured":"Y. Zhang , V. Kiriansky , C. Mendis , S. Amarasinghe , and M. Zaharia . 2017. Making caches work for graph analytics . In 2017 IEEE International Conference on Big Data (Big Data). 293--302 . Y. Zhang, V. Kiriansky, C. Mendis, S. Amarasinghe, and M. Zaharia. 2017. Making caches work for graph analytics. In 2017 IEEE International Conference on Big Data (Big Data). 293--302."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304029"},{"key":"e_1_2_1_68_1","volume-title":"2016 IEEE International Symposium on High Performance Computer Architecture (HPCA). 345--357","author":"Zheng T.","unstructured":"T. Zheng , D. Nellans , A. Zulfiqar , M. Stephenson , and S. W. Keckler . 2016. Towards high performance paged memory for GPUs . In 2016 IEEE International Symposium on High Performance Computer Architecture (HPCA). 345--357 . T. Zheng, D. Nellans, A. Zulfiqar, M. Stephenson, and S. W. Keckler. 2016. Towards high performance paged memory for GPUs. In 2016 IEEE International Symposium on High Performance Computer Architecture (HPCA). 345--357."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.111"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3425879.3425883","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:05:27Z","timestamp":1672225527000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3425879.3425883"}},"subtitle":["efficient memory-access for out-of-memory graph-traversal in GPUs"],"short-title":[],"issued":{"date-parts":[[2020,10]]},"references-count":68,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["10.14778\/3425879.3425883"],"URL":"https:\/\/doi.org\/10.14778\/3425879.3425883","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,10]]}}}