NDLI: SLAW: A scalable locality-aware adaptive work-stealing scheduler

Content Provider	IEEE Xplore Digital Library
Author	Yi Guo Jisheng Zhao Cave, V. Sarkar, V.
Copyright Year	2010
Description	Author affiliation: Department of Computer Science, Rice University, Houston, Texas 77005 (Yi Guo; Jisheng Zhao; Cave, V.; Sarkar, V.)
Abstract	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.
Starting Page	1
Ending Page	12
File Size	725249
Page Count	12
File Format	PDF
ISBN	9781424464425
ISSN	15302075
e-ISBN	9781424464432
DOI	10.1109/IPDPS.2010.5470425
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-04-19
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Adaptive scheduling Processor scheduling Dynamic scheduling Parallel processing Concurrent computing Programming profession Computer science Runtime library Scheduling algorithm Java Locality-aware Scheduling Task Parallelism Work-stealing Adaptive Scheduling
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

SLAW: A scalable localityaware adaptive work-stealing scheduler (2010)

SLAW: a scalable locality-aware adaptive work-stealing scheduler for multi-core systems

Work-first and help-first scheduling policies for async-finish task parallelism

On-line Scheduling of MPI-2 Programs with Hierarchical Work Stealing

A scalable locality-aware adaptive work-stealing scheduler for multi-core task parallelism

Executing task graphs using work-stealing

Automatic resource management using an adaptive parallelism environment

A new model for static mapping of parallel applications with task and data parallelism

Task scheduling in distributed systems by work stealing and mugging - a simulation study

SLAW: A scalable locality-aware adaptive work-stealing scheduler

Similar Documents

SLAW: A scalable localityaware adaptive work-stealing scheduler (2010)

SLAW: a scalable locality-aware adaptive work-stealing scheduler for multi-core systems

Work-first and help-first scheduling policies for async-finish task parallelism

On-line Scheduling of MPI-2 Programs with Hierarchical Work Stealing

A scalable locality-aware adaptive work-stealing scheduler for multi-core task parallelism

Executing task graphs using work-stealing

Automatic resource management using an adaptive parallelism environment

A new model for static mapping of parallel applications with task and data parallelism

Task scheduling in distributed systems by work stealing and mugging - a simulation study

SLAW: A scalable locality-aware adaptive work-stealing scheduler