Dynamic memory management is critical for efficiently porting modern data processing pipelines to GPUs. However, building a general-purpose dynamic memory manager on GPUs is challenging due to the massive parallelism and weak memory coherence. Existing state-of-the-art GPU memory managers, Ouroboros and Reg-Eff, employ traditional data structures such as arrays and linked lists to manage memory objects. They build specialized pipelines to achieve perfor- mance for a fixed set of allocation sizes and fall back to the CUDA allocator for allocating large sizes. In the process, they lose general-purpose usability and fail to support critical applications such as streaming graph processing.

In this paper, we introduce Gallatin, a general-purpose and high-performance GPU memory manager. Gallatin uses the van Emde Boas (vEB) tree to manage memory objects effi- ciently and supports allocations of any size. We develop a wait-free GPU implementation of the vEB tree to exploit mas- sive parallelism on GPUs. It supports constant time insertions, deletions, and successor operations for a given memory size.

In our evaluation, we compare Gallatin with state-of-the- art specialized allocator variants. It is up to 568× faster on single-sized allocations and up to 374× faster on mixed-size allocations than the next-best allocator. Gallatin also scales well as the number of threads increases and is up to 146× faster for single-sized allocations. For the graph benchmarks, Gallatin is faster than the state-of-the-art for range operations and is the fastest allocator for all graph expansion tests.