Lace: Non-blocking Split Deque for Work-Stealing

2014/01/01

Authors:

Published in: MuCoCoS pp 206–217

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

Paper

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},
 title = {{Lace: Non-blocking Split Deque for Work-Stealing}},
 volume = {8806},
 year = {2014}
}