This paper introduces SLAW, a Scalable Locality-aware Adaptive Work-stealing scheduler. The SLAW scheduler is designed to address two common limitations in current work-stealing schedulers: use of a fixed task scheduling policy and locality-obliviousness due to randomized stealing. Past work has demonstrated the pros and cons of using fixed scheduling policies, such as work-first and help-first, in different cases without a clear win for one policy over the other. The SLAW scheduler addresses this limitation by supporting both work-first and help-first policies simultaneously. It does so by using an adaptive approach that selects a scheduling policy on a per-task basis at runtime. The SLAW scheduler also establishes bounds on the stack and heap space needed to store tasks. The experimental results for the benchmarks studied in this paper show that SLAW's adaptive scheduler achieves 0.98× to 9.2× speedup over the help-first scheduler and 0.97× to 4.5× speedup over the work-first scheduler for 64-thread executions, thereby establishing the robustness of using an adaptive approach instead of a fixed policy. In contrast, the help-first policy is 9.2× slower than work-first in the worst case for a fixed help-first policy, and the work-first policy is 3.7× slower than help-first in the worst case for a fixed work-first policy. Further, for large irregular recursive parallel computations, the adaptive scheduler runs with bounded stack usage and achieves performance (and supports data sizes) that cannot be delivered by the use of any single fixed policy. It is also known that work-stealing schedulers can be cache-unfriendly for some applications due to randomized stealing. The SLAW scheduler is designed for programming models where locality hints are provided to the runtime by the programmer or compiler, and achieves locality-awareness by grouping workers into places. Locality awareness can lead to improved performance by increasing temporal data reuse within a worker and among workers in the same place. Our experimental results show that locality-aware scheduling can achieve up to 2.6× speedup over locality-oblivious scheduling, for the benchmarks studied in this paper.
SLAW: A scalable locality-aware adaptive work-stealing scheduler
Yi Guo,Jisheng Zhao,V. Cavé,Vivek Sarkar
Published 2010 in IEEE International Parallel and Distributed Processing Symposium
ABSTRACT
PUBLICATION RECORD
- Publication year
2010
- Venue
IEEE International Parallel and Distributed Processing Symposium
- Publication date
2010-01-09
- Fields of study
Computer Science
- Identifiers
- External record
- Source metadata
Semantic Scholar
CITATION MAP
EXTRACTION MAP
CLAIMS
CONCEPTS
- adaptive scheduling
A scheduling approach that chooses among policies at runtime on a per-task basis.
Aliases: adaptive scheduler
- bounded stack and heap space
A task-storage property in which the scheduler places limits on the stack and heap memory required to manage tasks.
Aliases: bounded stack usage, bounded heap usage
- help-first policy
A work-stealing scheduling policy that prioritizes helping complete available tasks before continuing the current continuation.
Aliases: help-first scheduler
- locality-aware scheduling
A scheduling approach that tries to keep related computation on nearby workers to improve data reuse.
Aliases: locality-aware scheduler
- locality hints
Information supplied by the programmer or compiler that guides the runtime's placement decisions.
- places
Groups of workers used to organize execution so that locality can be managed within and across worker groups.
- slaw scheduler
A scalable locality-aware adaptive work-stealing scheduler that serves as the paper's proposed runtime system.
Aliases: SLAW
- work-first policy
A work-stealing scheduling policy that prioritizes executing the spawned work on the current worker.
Aliases: work-first scheduler
REFERENCES
Showing 1-24 of 24 references · Page 1 of 1