Lace: non-blocking split deque for work-stealing

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

14 Citations (Scopus)
228 Downloads (Pure)

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.
Original languageUndefined
Title of host publicationProceedings of the 7th International Euro-Par Workshop on Multi-/Many-core Computing Systems, MuCoCoS 2014
Place of PublicationSwitzerland
PublisherSpringer
Pages206-217
Number of pages12
ISBN (Print)978-3-319-14312-5
DOIs
Publication statusPublished - Aug 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer International Publishing
Volume8806
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

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

Cite this

van Dijk, T., & van de Pol, J. C. (2014). Lace: non-blocking split deque for work-stealing. In Proceedings of the 7th International Euro-Par Workshop on Multi-/Many-core Computing Systems, MuCoCoS 2014 (pp. 206-217). (Lecture Notes in Computer Science; Vol. 8806). Switzerland: Springer. https://doi.org/10.1007/978-3-319-14313-2_18
van Dijk, Tom ; van de Pol, Jan Cornelis. / Lace: non-blocking split deque for work-stealing. Proceedings of the 7th International Euro-Par Workshop on Multi-/Many-core Computing Systems, MuCoCoS 2014. Switzerland : Springer, 2014. pp. 206-217 (Lecture Notes in Computer Science).
@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",
year = "2014",
month = "8",
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",

}

van Dijk, T & van de Pol, JC 2014, Lace: non-blocking split deque for work-stealing. in Proceedings of the 7th International Euro-Par Workshop on Multi-/Many-core Computing Systems, MuCoCoS 2014. Lecture Notes in Computer Science, vol. 8806, Springer, Switzerland, pp. 206-217. https://doi.org/10.1007/978-3-319-14313-2_18

Lace: non-blocking split deque for work-stealing. / van Dijk, Tom; van de Pol, Jan Cornelis.

Proceedings of the 7th International Euro-Par Workshop on Multi-/Many-core Computing Systems, MuCoCoS 2014. Switzerland : Springer, 2014. p. 206-217 (Lecture Notes in Computer Science; Vol. 8806).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Lace: non-blocking split deque for work-stealing

AU - van Dijk, Tom

AU - van de Pol, Jan Cornelis

N1 - 10.1007/978-3-319-14313-2_18

PY - 2014/8

Y1 - 2014/8

N2 - 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.

AB - 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.

KW - EWI-25278

KW - CR-D.1.3

KW - CR-E.1

KW - non-blocking deque

KW - IR-93342

KW - lock-free algorithm

KW - Dynamic load-balancing

KW - Work-stealing

KW - METIS-309646

KW - task-based parallelism

U2 - 10.1007/978-3-319-14313-2_18

DO - 10.1007/978-3-319-14313-2_18

M3 - Conference contribution

SN - 978-3-319-14312-5

T3 - Lecture Notes in Computer Science

SP - 206

EP - 217

BT - Proceedings of the 7th International Euro-Par Workshop on Multi-/Many-core Computing Systems, MuCoCoS 2014

PB - Springer

CY - Switzerland

ER -

van Dijk T, van de Pol JC. Lace: non-blocking split deque for work-stealing. In Proceedings of the 7th International Euro-Par Workshop on Multi-/Many-core Computing Systems, MuCoCoS 2014. Switzerland: Springer. 2014. p. 206-217. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-14313-2_18