Optimizing work stealing algorithms with scheduling constraints

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2016

Author dc:creator

• Lifflander, Jonathan Josiah

Contributors dc:contributor

• Kalé, Laxmikant V
• Krishnamoorthy, Sriram
• Padua, David
• Sarkar, Vivek
• Snir, Marc

• concurrency
• work-stealing
• fork-join
• scheduling
• locality

Statement dc:rights

• Copyright 2016 Jonathan Josiah Lifflander

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/90511

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/90511