Abstract: Many of today's high level parallel languages support dynamic, fine-grained parallelism. These languages allow the user to expose all the parallelism in the program, which is typically of a much higher degree than the number of processors. Hence an efficient scheduling algorithm is required to assign computations to processors at runtime. Besides having low overheads and good load balancing, it is important for the scheduling algorithm to minimize the space usage of the parallel program. In this paper, we first present a general framework to model non-preemptive parallel computations based on task graphs, in which schedules of the graphs represent executions of the computations. We then prove bounds on the space and time requirements of certain classes of schedules that can be generated by an offline scheduler. Next, we present an online scheduling algorithm that is provably space-efficient and time-efficient for multithreaded computations with nested parallelism. If a serial execution requires S_1 units of memory for a computation of depth D and work W, our algorithm results in an execution on p processors that requires S_1+O(p D log p) units of memory, and O(W/p+D log p) time, including scheduling overheads. Finally, we demonstrate that our scheduling algorithm is efficient in practice. We have implemented a runtime system that uses our algorithm to schedule parallel threads. The results of executing parallel programs on this system show that our scheduling algorithm significantly reduces memory usage compared to previous techniques, without compromising performance.
@techreport{NB96,
author = "Girija J. Narlikar and Guy E. Blelloch",
title = "A framework for Space and Time Efficient Scheduling
of Parallelism",
institution = "Computer Science Department, Carnegie Mellon University",
number = "CMU-CS-96-197",
year = 1996,
month = "December"
}