@device(postscript)
@libraryfile(Mathematics10)
@libraryfile(Accents)
@style(fontfamily=timesroman,fontscale=11)
@pagefooting(immediate, left "@c<Technical Report 1996>",
center "@c<Computer Science>",
right "@c<Carnegie Mellon>")
@heading(A Framework for Space and Time Efficient Scheduling of Parallelism)
@heading(CMU-CS-96-197)
@center(@b(Girija J. Narlikar, Guy E. Blelloch))
@center(December 1996)
@center(FTP: CMU-CS-96-197.ps)
@blankspace(1)
@begin(text)

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 @math<S@-[1]> units
of memory for  a computation of depth @math<D> and work @math<W>, our
algorithm results in an execution  on @math<p> processors that requires
@math<S@-[1]#@Add#O(pD#log#p)> units of memory, and 
@math<O(W#@Div#p#@Add#D#log#p)> time, including scheduling overheads.
Finally, we demonstrate that our schedulin
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.

@blankspace(2line)
@begin(transparent,size=10)
@b(Keywords:@ )@c<Space efficiency, dynamic scheduling, nested parallelism, 
parallel language implementation>
@end(transparent)
@blankspace(1line)
@end(text)
@flushright(@b[(34 pages)])