Friendly barriers: Efficient work-stealing with return barriers

Vivek Kumar, Stephen M. Blackburn, David Grove

    Research output: Contribution to conferencePaperpeer-review

    4 Citations (Scopus)

    Abstract

    This paper addresses the problem of efficiently supporting parallelism within a managed runtime. A popular approach for exploiting software parallelism on parallel hardware is task parallelism, where the programmer explicitly identifies potential parallelism and the runtime then schedules the work. Work-stealing is a promising scheduling strategy that a runtime may use to keep otherwise idle hardware busy while relieving overloaded hardware of its burden. However, work-stealing comes with substantial overheads. Recent work identified sequential overheads of work-stealing, those that occur even when no stealing takes place, as a significant source of overhead. That work was able to reduce sequential overheads to just 15% [21]. In this work, we turn to dynamic overheads, those that occur each time a steal takes place. We show that the dynamic overhead is dominated by introspection of the victim's stack when a steal takes place. We exploit the idea of a low overhead return barrier to reduce the dynamic overhead by approximately half, resulting in total performance improvements of as much as 20%. Because, unlike prior work, we attack the overheads directly due to stealing and therefore attack the overheads that grow as parallelism grows, we improve the scalability of work-stealing applications. This result is complementary to recent work addressing the sequential overheads of work-stealing. This work therefore substantially relieves work-stealing of the increasing pressure due to increasing intra-node hardware parallelism.

    Original languageEnglish
    Pages165-176
    Number of pages12
    DOIs
    Publication statusPublished - 2014
    Event10th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, VEE 2014 - Salt Lake City, UT, United States
    Duration: 1 Mar 20142 Mar 2014

    Conference

    Conference10th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, VEE 2014
    Country/TerritoryUnited States
    CitySalt Lake City, UT
    Period1/03/142/03/14

    Fingerprint

    Dive into the research topics of 'Friendly barriers: Efficient work-stealing with return barriers'. Together they form a unique fingerprint.

    Cite this