Mark-Sharing: A Parallel Garbage Collection Algorithm for Low Synchronization Overhead

Hyunkyu Park, Changmin Lee, Seung-Hun Kim, Won Woo Ro, Jean-Luc Gaudiot

Abstract

Two main problems prevent a parallel garbage collection (GC) scheme with lock-based synchronization from providing a high level of scalability: the load imbalance and the runtime overhead of thread synchronization operations. These problems become even more serious as the number of available threads increases. We propose the Mark-Sharing algorithm to improve the performance of parallel GC using transactional memory (TM) systems. The Mark-Sharing algorithm guarantees that all threads access the shared resource by using both the task-stealing and task-releasing mechanisms appropriately. In addition, we introduce a selection manager that minimizes the contention and idle time of garbage collectors by maintaining task information. The proposed algorithm outperforms the prior pool-sharing algorithm of GC in the HTM, providing more than 90% performance improvement on average.
BibTeX
@inproceedings{park2013mark,
  author = {Hyunkyu Park and Changmin Lee and Seung-Hun Kim and Won Woo Ro and Jean-Luc Gaudiot},
  title = {{Mark-Sharing: A Parallel Garbage Collection Algorithm for Low Synchronization Overhead}},
  booktitle = {ICPADS},
  year = {2013},
  doi = {10.1109/icpads.2013.16},
}

Loading related content...

Figure