Brushing the Locks out of the Fur: A Lock-Free Work Stealing Library Based on Wool
2009 (English)Conference paper (Refereed)
We present a lock-free version of the light-weight userlevel task management library called Wool, in an aim to show that even extremely well tuned, in terms of synchronization,applications can benefit from lock-free programming.Explicit multi-threading is an efficient way to exploit the offered parallelism of multi-core and multi-processor based systems. However, it can sometimes be hard to expressthe inherited parallelism in programs using a limited number of long lived threads. Often it can be more straightforwardto dynamically create a large number of small tasks that in turn automatically execute on the available threads.Wool is a promising and efficient library and framework that allows the programmer to create user tasks in C with a very low overhead. The library automatically executestasks and balances the load evenly on a given number of threads by utilizing work stealing techniques. However, thesynchronization for stealing tasks is based on mutual exclusion which is known to limit parallelism and efficiency. We have designed and implemented a new lock-free algorithmfor synchronization of stealing tasks in Wool. Experiments show similar or significantly improved performance on a setof benchmarks executed on a multi-core platform.
Place, publisher, year, edition, pages
Computer and Information Science Computer and Information Science
Research subject Library and Information Science
IdentifiersURN: urn:nbn:se:hb:diva-6308Local ID: 2320/5912OAI: oai:DiVA.org:hb-6308DiVA: diva2:886995
The Second Swedish Workshop on Multi-Core Computing MCC09, 2009, Uppsala, Sweden