Parallel Memory Defragmentation on a GPU

Ronald Veldema, Michael Philippsen
University of Erlangen-Nuremberg, Computer Science Department 2, Martensstr. 3, 91058 Erlangen, Germany
2012 ACM SIGPLAN Workshop on Memory Systems Performance and Correctness (MSPC ’12), 2012


   author={Veldema, Ronald and Philippsen, Michael},

   title={Parallel memory defragmentation on a GPU},

   booktitle={Proceedings of the 2012 ACM SIGPLAN Workshop on Memory Systems Performance and Correctness},

   series={MSPC ’12},



   location={Beijing, China},







   address={New York, NY, USA},

   keywords={GPU, garbage collection, mark and sweep, parallel}


Download Download (PDF)   View View   Source Source   



High-throughput memory management techniques such as malloc/free or mark-and-sweep collectors often exhibit memory fragmentation leaving allocated objects interspersed with free memory holes. Memory defragmentation removes such holes by moving objects around in memory so that they become adjacent (compaction) and holes can be merged (coalesced) to form larger holes. However, known defragmentation techniques are slow. This paper presents a parallel solution to best-effort partial defragmentation that makes use of all available cores. The solution not only speeds up defragmentation times significantly, but it also scales for many simple cores. It can therefore even be implemented on a GPU. One problem with compaction is that it requires all references to moved objects to be retargeted to point to their new locations. This paper further improves existing work by a better identification of the parts of the heap that contain references to objects moved by the compactor and only processes these parts to find the references that are then retargeted in parallel. To demonstrate the performance of the new memory defragmentation algorithm on many-core processors, we show its performance on a modern GPU. Parallelization speeds up compaction 40 times and coalescing up to 32 times. After compaction, our algorithm only needs to process 2%–4% of the total heap to retarget references.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2023 hgpu.org

All rights belong to the respective authors

Contact us: