Withdraw
Loading…
Optimizing work stealing algorithms with scheduling constraints
Lifflander, Jonathan Josiah
Loading…
Permalink
https://hdl.handle.net/2142/90511
Description
- Title
- Optimizing work stealing algorithms with scheduling constraints
- Author(s)
- Lifflander, Jonathan Josiah
- Issue Date
- 2016-04-11
- Director of Research (if dissertation) or Advisor (if thesis)
- Kalé, Laxmikant V
- Doctoral Committee Chair(s)
- Kalé, Laxmikant V
- Committee Member(s)
- Krishnamoorthy, Sriram
- Padua, David
- Sarkar, Vivek
- Snir, Marc
- Department of Study
- Computer Science
- Discipline
- Computer Science
- Degree Granting Institution
- University of Illinois at Urbana-Champaign
- Degree Name
- Ph.D.
- Degree Level
- Dissertation
- Keyword(s)
- concurrency
- work-stealing
- fork-join
- scheduling
- locality
- Abstract
- The fork-join paradigm of concurrent expression has gained popularity in conjunction with work-stealing schedulers. Random work-stealing schedulers have been shown to effectively perform dynamic load balancing, yielding provably-efficient schedules and space bounds on shared-memory architectures with uniform memory models. However, the advent of hierarchical, non-uniform multicore systems and large-scale distributed-memory architectures has reduced the efficacy of these scheduling policies. Furthermore, random work stealing schedulers do not exploit persistence within iterative, scientific applications. In this thesis, we prove several properties of work-stealing schedulers that enable online tracing of the tasks with very low overhead. We then describe new scheduling policies that use online schedule introspection to understand scheduler placement and thus improve the performance on NUMA and distributed-memory architectures. Finally, by incorporating an inclusive data effect system into fork--join programs with schedule placement knowledge, we show how we can transform a fork-join program to significantly improve locality.
- Graduation Semester
- 2016-05
- Type of Resource
- text
- Permalink
- http://hdl.handle.net/2142/90511
- Copyright and License Information
- Copyright 2016 Jonathan Josiah Lifflander
Owning Collections
Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at IllinoisManage Files
Loading…
Edit Collection Membership
Loading…
Edit Metadata
Loading…
Edit Properties
Loading…
Embargoes
Loading…