# EMOGI: Efficient Memory-access for Out-of-memory Graph-traversal In GPUs

arXiv: https://arxiv.org/abs/2006.06890 · HTML: https://mlsanity.com/paper/2006.06890/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2020.

## Built on by (most cited first, 10 of 10)

- [IGB: Addressing The Gaps In Labeling, Features, Heterogeneity, and Size of Public Graph Datasets for Deep Learning Research](https://mlsanity.com/paper/2302.13522/) (2023)
- [RecShard: Statistical Feature-Based Memory Optimization for Industry-Scale Neural Recommendation](https://mlsanity.com/paper/2201.10095/) (2022)
- [Strata: Hierarchical Context Caching for Long Context Language Model Serving](https://mlsanity.com/paper/2508.18572/) (2025)
- [Large Graph Convolutional Network Training with GPU-Oriented Data Communication Architecture](https://mlsanity.com/paper/2103.03330/) (2021)
- [PyTorch-Direct: Enabling GPU Centric Data Access for Very Large Graph Neural Network Training with Irregular Accesses](https://mlsanity.com/paper/2101.07956/) (2021)
- [StitchCUDA: An Automated Multi-Agents End-to-End GPU Programing Framework with Rubric-based Agentic Reinforcement Learning](https://mlsanity.com/paper/2603.02637/) (2026)
- [TOD: GPU-accelerated Outlier Detection via Tensor Operations](https://mlsanity.com/paper/2110.14007/) (2021)
- [MultiEM: Efficient and Effective Unsupervised Multi-Table Entity Matching](https://mlsanity.com/paper/2308.01927/) (2023)
- [DR-CircuitGNN: Training Acceleration of Heterogeneous Circuit Graph Neural Network on GPUs](https://mlsanity.com/paper/2508.16769/) (2025)
- [Reducing the GPU Memory Bottleneck with Lossless Compression for ML -- Extended](https://mlsanity.com/paper/2605.30728/) (2026)

## Abstract (arXiv)

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 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 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 cacheline-sized access to data stored in host memory. This paper addresses the open question of whether a sufficiently large number of overlapping cacheline-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 even with direct cache-line accesses to the host memory. EMOGI achieves 2.92× 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.