Fast and Robust Memory Reclamation for Concurrent Data Structures
Event details
| Date | 07.06.2016 |
| Hour | 14:00 › 16:00 |
| Speaker | Mihail Igor Zablotchi |
| Location | |
| Category | Conferences - Seminars |
EDIC Candidacy Exam
Exam President: Prof. Willy Zwaenepoel
Thesis Director: Prof. Rachid Guerraoui
Co-examiner: Prof. Christos Kozyrakis
Background papers:
Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects (2004) by M. Michael.
Performance of memory reclamation for lockless synchronization (2007) by T. E. Hart, P. E. McKenney, A. D. Brown and J. Walpole.
Fence-Free Work Stealing on Bounded TSO Processors(2014) by A. Morrison and Y. Afek.
Abstact
Efficiently reusing memory is essential for applications whose data structures grow and shrink dynamically. In a concurrent setting without automatic garbage collection, determining when it is safe to reuse memory is a challenge, especially for lock-free data structures. Existing practical solutions are either robust but slow or fast but vulnerable to thread delays.
In this proposal, we discuss three existing works and how they relate to our research. First, we examine hazard pointers, a well-established wait-free solution to the memory reclamation problem. Second, we consider a comparative performance study showing that practical implementations of hazard pointers are slowed down by seemingly necessary memory barriers and that blocking solutions are faster. Third, we analyze a paper eliminating memory barriers from another type of algorithm, a work stealing queue, by relying on the behavior of hardware store buffers. Finally, we show how these works have inspired us to achieve memory barrier elision for hazard pointers and then combine these barrier-free hazard pointers with a blocking solution in a hybrid technique that is at the same time fast and robust.
Exam President: Prof. Willy Zwaenepoel
Thesis Director: Prof. Rachid Guerraoui
Co-examiner: Prof. Christos Kozyrakis
Background papers:
Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects (2004) by M. Michael.
Performance of memory reclamation for lockless synchronization (2007) by T. E. Hart, P. E. McKenney, A. D. Brown and J. Walpole.
Fence-Free Work Stealing on Bounded TSO Processors(2014) by A. Morrison and Y. Afek.
Abstact
Efficiently reusing memory is essential for applications whose data structures grow and shrink dynamically. In a concurrent setting without automatic garbage collection, determining when it is safe to reuse memory is a challenge, especially for lock-free data structures. Existing practical solutions are either robust but slow or fast but vulnerable to thread delays.
In this proposal, we discuss three existing works and how they relate to our research. First, we examine hazard pointers, a well-established wait-free solution to the memory reclamation problem. Second, we consider a comparative performance study showing that practical implementations of hazard pointers are slowed down by seemingly necessary memory barriers and that blocking solutions are faster. Third, we analyze a paper eliminating memory barriers from another type of algorithm, a work stealing queue, by relying on the behavior of hardware store buffers. Finally, we show how these works have inspired us to achieve memory barrier elision for hazard pointers and then combine these barrier-free hazard pointers with a blocking solution in a hybrid technique that is at the same time fast and robust.
Practical information
- General public
- Free
Contact
- Cecilia Chapuis EDIC