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 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 elastic scheduler that achieves the goal by dynamically scaling up or down the processors it utilizes in response to the instantaneous parallelism. We prove a runtime and total work bound for our offline elastic scheduler and show that it achieves linear speedup with respect to the number of processors, while maintaining work efficiency.

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

73 pages

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

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu