@inproceedings{bdece849dc44432ab039fd9661f6621a,
title = "Lace: non-blocking split deque for work-stealing",
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.",
keywords = "EWI-25278, CR-D.1.3, CR-E.1, non-blocking deque, IR-93342, lock-free algorithm, Dynamic load-balancing, Work-stealing, METIS-309646, task-based parallelism",
author = "{van Dijk}, Tom and {van de Pol}, {Jan Cornelis}",
note = "10.1007/978-3-319-14313-2_18 ; null ; Conference date: 26-08-2014 Through 26-08-2014",
year = "2014",
month = aug,
doi = "10.1007/978-3-319-14313-2_18",
language = "Undefined",
isbn = "978-3-319-14312-5",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "206--217",
booktitle = "Proceedings of the 7th International Euro-Par Workshop on Multi-/Many-core Computing Systems, MuCoCoS 2014",
}