Paper Info
Title
Near Optimal Work-Stealing Tree Scheduler for Highly Irregular Data-Parallel Workloads.
Abstract
We present a work-stealing algorithm for runtime scheduling of data-parallel operations in the context of shared-memory architectures on data sets with highly-irregular workloads that are not known a priori to the scheduler. This scheduler can parallelize loops and operations expressible with a parallel reduce or a parallel scan. The scheduler is based on the work-stealing tree data structure, which allows workers to decide on the work division in a lock-free, workload-driven manner and attempts to minimize the amount of communication between them. A significant effort is given to showing that the algorithm has the least possible amount of overhead. We provide an extensive experimental evaluation, comparing the advantages and shortcomings of different data-parallel schedulers in order to combine their strengths. We show specific workload distribution patterns appearing in practice for which different schedulers yield suboptimal speedup, explaining their drawbacks and demonstrating how the work-stealing tree scheduler overcomes them. We thus justify our design decisions experimentally, but also provide a theoretical background for our claims.
Year
DOI
Venue
2013
10.1007/978-3-319-09967-5_4
Lecture Notes in Computer Science
Field
DocType
Volume
Data set,CPU cache,Computer science,Scheduling (computing),A priori and a posteriori,Parallel computing,Tree (data structure),Work stealing,Distributed computing
Conference
8664
ISSN
Citations 
PageRank 
0302-9743
5
0.48
References 
Authors
12
2
Name
Order
Citations
PageRank
Aleksandar Prokopec116313.56
Martin Odersky22261170.39