Scheduling Parallel Functional Programs

Parallelism abounds! To continue to improve performance, programmers
must use parallel algorithms to take advantage of multi-core and other
parallel architectures. Functional languages allow programmers to
express many parallel algorithms concisely. With a deterministic
semantics, a functional language also allows programmers to reason about
the correctness of parallel programs independently of the language
implementation. Despite this, the performance of these programs still
depends heavily on the language implementation and especially on the
choice of scheduling policy. In some applications, this choice has
asymptotic effects on space use.

In this talk, I will present some of my recent work on a parallel
functional programming language. At the core of this work is a cost
semantics that allows programmers to reason about the performance of
parallel programs and in particular about their use of space. This cost
semantics is the basis for a suite of prototype profiling tools. These
tools enable programmers to simulate and visualize program execution
under different scheduling policies.

This cost semantics also provides a specification for an implementation
of the language. I will describe my implementation, a parallel
extension of MLton, and relate some initial results. These results show
good parallel speedups for several applications and that program
performance reflects the predictions made by my profiler.