Files in this item

FilesDescriptionFormat

application/pdf

application/pdfLIFFLANDER-DISSERTATION-2016.pdf (7MB)
(no description provided)PDF

Description

Title:Optimizing work stealing algorithms with scheduling constraints
Author(s):Lifflander, Jonathan Josiah
Director of Research:Kale, Laxmikant V.
Doctoral Committee Chair(s):Kale, Laxmikant V.
Doctoral Committee Member(s):Krishnamoorthy, Sriram; Padua, David; Sarkar, Vivek; Snir, Marc
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:Ph.D.
Genre:Dissertation
Subject(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.
Issue Date:2016-04-11
Type:Thesis
URI:http://hdl.handle.net/2142/90511
Rights Information:Copyright 2016 Jonathan Josiah Lifflander
Date Available in IDEALS:2016-07-07
Date Deposited:2016-05


This item appears in the following Collection(s)

Item Statistics