Lace: Non-blocking Split Deque for Work-Stealing



Published in: MuCoCoS pp 206–217

DOI: 10.1007/978-3-319-14313-2_18



Work-stealing is an efficient method to implement load balancing in fine-grained task parallelism. Typically, concurrent deques are used for this purpose. A disadvantage of many concurrent deques is that they require expensive memory fences for local deque operations.

In this paper, we propose a new non-blocking work-stealing deque based on the split task queue. Our design uses a dynamic split point between the shared and the private portions of the deque, and only requires memory fences when shrinking the shared portion.

We present Lace, an implementation of work-stealing based on this deque, with an interface similar to the work-stealing library Wool, and an evaluation of Lace based on several common benchmarks. We also implement a recent approach using private deques in Lace. We show that the split deque and the private deque in Lace have similar low overhead and high scalability as Wool.

BibTeX entry:

 author = {Tom van Dijk and Jaco van de Pol},
 booktitle = {MuCoCoS},
 doi = {10.1007/978-3-319-14313-2_18},
 pages = {206--217},
 publisher = {Springer},
 series = {LNCS},
 talk = {2014lace_talk.pdf},
 title = {{Lace: Non-blocking Split Deque for Work-Stealing}},
 volume = {8806},
 year = {2014}