Skip navigation
Skip navigation

Friendly Barriers: Efficient Work-Stealing With Return Barriers

Kumar, Vivek; Blackburn, Stephen; Grove, David

Description

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...[Show more]

dc.contributor.authorKumar, Vivek
dc.contributor.authorBlackburn, Stephen
dc.contributor.authorGrove, David
dc.coverage.spatialSalt Lake City USA
dc.date.accessioned2015-12-10T23:22:54Z
dc.date.createdMarch 1-2 2014
dc.identifier.urihttp://hdl.handle.net/1885/66719
dc.description.abstractThis 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.
dc.publisherAssociation for Computing Machinery (ACM)
dc.relation.ispartofseries10th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments VEE 2014
dc.sourceFriendly Barriers: Efficient Work-Stealing With Return Barriers
dc.titleFriendly Barriers: Efficient Work-Stealing With Return Barriers
dc.typeConference paper
local.description.notesImported from ARIES
local.description.refereedYes
dc.date.issued2014
local.identifier.absfor080308 - Programming Languages
local.identifier.ariespublicationu4334215xPUB1331
local.type.statusPublished Version
local.contributor.affiliationKumar, Vivek, College of Engineering and Computer Science, ANU
local.contributor.affiliationBlackburn, Stephen, College of Engineering and Computer Science, ANU
local.contributor.affiliationGrove, David, Thomas J Watson Research Centre
local.description.embargo2037-12-31
local.bibliographicCitation.startpage165
local.bibliographicCitation.lastpage176
local.identifier.doi10.1145/2576195.2576207
local.identifier.absseo970108 - Expanding Knowledge in the Information and Computing Sciences
dc.date.updated2015-12-10T10:35:25Z
local.identifier.scopusID2-s2.0-84897546886
local.identifier.thomsonID000344456400017
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Kumar_Friendly_Barriers:_Efficient_2014.pdf714.96 kBAdobe PDFThumbnail


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator