ScatterAlloc: Massively Parallel Dynamic Memory Allocation for the GPU
đź“ś Abstract
In this paper, we analyze the special requirements of a dynamic memory allocator that is designed for massively parallel architectures such as Graphics Processing Units (GPUs). We show that traditional strategies, which work well on CPUs, are not well suited for the use on GPUs and present the thorough design of ScatterAlloc, which can efficiently deal with hundreds of requests in parallel. Our allocator greatly reduces collisions and congestion by scattering memory requests based on hashing. We analyze ScatterAlloc in terms of allocation speed, data access time and fragmentation, and compare it to current state-of-the-art allocators, including the one provided with the NVIDIA CUDA toolkit. Our results show, that ScatterAlloc clearly outperforms these other approaches, yielding speed-ups between 10 to 100.
✨ Summary
Paper summary
The paper addresses dynamic memory allocation under GPU execution models, where hundreds or thousands of threads may issue requests concurrently and where synchronization, global-memory latency, SIMD execution, and cache behavior make conventional CPU-oriented allocators ineffective. It establishes correctness, allocation/deallocation speed, memory-access efficiency, scalability, low divergence, coalesced access, and limited memory consumption as key design objectives.
ScatterAlloc uses fixed-size pages grouped into super blocks. Each page is divided into equally sized chunks, with page-usage metadata consisting of a chunk size, an allocation counter, and bit fields identifying occupied chunks. A second bit-field hierarchy supports pages containing up to 1,024 chunks. Allocation requests are distributed with a hash function based on requested size and multiprocessor identity. This reduces contention on individual pages while encouraging cache-friendly placement for threads executing on the same multiprocessor and adjacent placement for threads within a warp. Atomic operations are used for page acquisition, counters, and bit masks, but the design attempts to distribute these operations rather than concentrating them on a global list or queue.
The allocator trades some external fragmentation for substantially better parallel scalability. It supports reuse of freed pages, metadata for avoiding nearly full regions, and a separate strategy for requests larger than one page. In the reported experiments on an NVIDIA Quadro 6000, ScatterAlloc’s allocation performance remained nearly independent of the number of concurrent threads. At full GPU utilization, it was reported as approximately 100 times faster than the CUDA toolkit allocator and up to 10 times faster than XMalloc with SIMD optimization. Its internal fragmentation was comparable to list-based allocators, while its memory placement produced slightly faster data access in some tested configurations.
Subsequent research and implementation impact
Later GPU-allocation research continued to cite ScatterAlloc as an early design based on scattering allocation activity to reduce contention. The 2015 Register Efficient Dynamic Memory Allocator for GPUs cites it among prior GPU allocator designs, while NVIDIA Research’s 2019 Throughput-Oriented GPU Memory Allocation explicitly describes using a similar collision-avoidance idea and identifies ScatterAlloc’s bitmap-based tracking and hashing of atomic updates as related techniques. (onlinelibrary.wiley.com)
The algorithm was also preserved and extended in open-source implementations. The mallocMC project states that it supports the ScatterAlloc algorithm and evolved from a fork of the original project; related repositories document continued CUDA use and further development of the allocator. (github.com) More recent GPU-memory-management literature continues to list ScatterAlloc as a reference point when discussing highly parallel runtime allocation, although the available evidence supports citation and technical reuse rather than a claim that it became a standard industry allocator. (pmc.ncbi.nlm.nih.gov)