Parallel Algorithms and Sequential Languages
Guy Blelloch

Over the years many researchers have argued that an important aspect
of functional languages is their inherent parallelism.  Furthermore
researchers have presented many implementation techniques to take
advantage of this parallelism, including data-flow, parallel graph
reduction, and various compiler techniques.  Such work has suggested
that it might not be necessary to add explicit parallel constructs to
functional languages to get adequate parallelism.  There has been
little study, however, of how much parallelism can be achieved for
various problems, or how the inherent parallelism in functional
languages relates to more standard models used for analyzing parallel
algorithms, such as the PRAM.  For example, what are asymptotic bounds
for sorting using a parallel implementation of a functional language
such as ML?  What kind of sort would we use?  How would the bounds
compare with parallel sorting algorithms designed for various machine
models?  Does it matter whether the language is strict or lazy?  This
talk will address these issues.

This is joint work with John Greiner.