Computer Science Masters Thesis Presentation

Friday, December 6, 2019 - 3:00pm


Blelloch-Skees Conference Room 8115 Gates Hillman Centers


YUE YAO, Masters Student

Work Efficient Schedulers

The scheduling of multithreaded computations has attracted extensive research over past decades. Most of the research focused on design schedulers that are efficient in terms of runtime and space consumption, very often at the cost of performing more work than the computation itself required.

This work considers a new class of schedulers, called work-efficient schedulers. Work-efficient schedulers aim to minimize extra work, measured by the total number of instructions executed by all processors due to scheduling, including idle (referred to as spinning time in this work) time. Specifically, the total amount of work performed during the scheduling of a computation must be within a small constant factor of the total work of the computation. This work first presents an offline work-efficient scheduler that achieves the goal by dynamically scaling up or down the amount of processors it utilizes in response to the instantaneous parallelism. We prove a runtime and total work bound for our work-efficient scheduler and show that it achieves linear speedup with respect to the number of processors available, while maintaining work efficiency.

This work further presents an online work-efficient work-stealing algorithm, called the parsimonious scheduler, that aims at approximating the offline work-efficient scheduler. The parsimonious scheduler augments the traditional work-stealing algorithm with a "lifeline forest" data structure that allows processors to respond swiftly to varying instantaneous parallelism in a distributed manner. We implemented the parsimonious scheduler and evaluated its performance and work efficiency by comparing it with existing implementations of traditional work-stealing schedulers. Results show that 1) for highly parallel computations, our parsimonious scheduler is comparable to classic work-stealing in its speedup; 2) for computations where parallelism is more limited, our parsimonious scheduler performs considerably less work.

Thesis Committee:
Umut A. Acar (Chair)
Randal E. Bryant

Additional Thesis Information

For More Information, Contact:


Master's Thesis Presentation