Abstract:
Practical parallel programming demands that the details of distributing data to processors and inter-
processor communication be managed by the compiler. These tasks quickly become too di cult for
a programmer to do by hand for all but the simplest parallel programs. Yet, many parallel languages
still require the programmer to manage much of the the parallelism.
I discuss the synthesis of parallel imperative code from algorithms written in a functional language
called Alpha. Alpha is based on systems of a ne recurrence equations and was designed to specify
algorithms for regular array architectures. Being a functional language, Alpha implicitly supports
the expression of both concurrency and communication. Thus, the programmer is freed from having
to explicitly manage the parallelism.
Using the information derived from static analysis, Alpha can be transformed into a form suitable
for generating imperative parallel code through a series of provably correct program transformations.
The kinds of analysis needed to generate e cient code for array-based functional programs are a
generalization of dependency analysis, usage analysis, and scheduling techniques used in systolic
array synthesis.
