Show simple item record

dc.contributor.advisor Sarkar, Vivek
dc.creatorGuo, Yi
dc.date.accessioned 2012-07-03T22:49:56Z
dc.date.available 2012-07-03T22:49:56Z
dc.date.created 2010-08
dc.date.issued 2011
dc.identifier.citation Guo, Yi. "A Scalable Locality-aware Adaptive Work-stealing Scheduler for Multi-core Task Parallelism." (2011) Diss., Rice University. https://hdl.handle.net/1911/64446.
dc.identifier.urihttps://hdl.handle.net/1911/64446
dc.description.abstract Recent trend has made it clear that the processor makers are committed to the multicore chip designs. The number of cores per chip is increasing, while there is little or no increase in the clock speed. This parallelism trend poses a significant and urgent challenge on computer software because programs have to be written or transformed into a multi-threaded form to take full advantage of future hardware advances. Task parallelism has been identified as one of the prerequisites for software productivity. In task parallelism, programmers focus on decomposing the problem into subcomputations that can run in parallel and leave the compiler and runtime to handle the scheduling details. This separation of concerns between task decomposition and scheduling provides productivity to the programmer but poses challenges to the runtime scheduler. Our thesis is that work-stealing schedulers with adaptive scheduling policies and locality-awareness can provide a scalable and robust runtime foundation for multicore task parallelism. We evaluate our thesis using the new Scalable Locality-aware Adaptive Work-stealing (SLAW) runtime scheduler developed for the Habanero-Java programming language, a task-parallel variant of Java. SLAW's adaptive task scheduling is motivated by the study of two common scheduling policies in a work-stealing scheduler, specifically, the work-first and the help-first policy. Both policies exhibit limitations in performance and resource usage in different situations. The variances make it hard to determine the best policy a priori. SLAW addresses these limitations by supporting both policies simultaneously and selecting policies adaptively on a per-task basis at runtime. Our results show that SLAW achieves O.98x to 9.2x speedup over the help-first scheduler and O.97x to 4.5x speedup over the work-first scheduler. Further, for large irregular parallel computations, SLAW supports data sizes and achieves performance that cannot be delivered by the use of any single fixed policy. SLAW's locality-aware scheduling framework aims to overcome the cache unfriendliness of work-stealing 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. Our results show that locality-aware scheduling can improve performance by increasing temporal data reuse for iterative data-parallel applications.
dc.format.extent 143 pp
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectComputer science
dc.title A Scalable Locality-aware Adaptive Work-stealing Scheduler for Multi-core Task Parallelism
dc.identifier.digital GuoY
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Computer Science
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record