CMU-CS-96-197, December 1996

**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" }