Lace: non-blocking split deque for work-stealing

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

    18 Citations (Scopus)
    554 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
    Event7th International Euro-Par Workshop on Multi-/Many-core Computing Systems, MuCoCoS 2014 - Porto, Portugal
    Duration: 26 Aug 201426 Aug 2014

    Publication series

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

    Workshop

    Workshop7th International Euro-Par Workshop on Multi-/Many-core Computing Systems, MuCoCoS 2014
    Period26/08/1426/08/14
    Other26 August 2014

    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