Authors:
- Tom van Dijk
- Jaco van de Pol
Published in: MuCoCoS pp 206–217
DOI: 10.1007/978-3-319-14313-2_18
Abstract:
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:
@inproceedings{DijkP14,
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}
}