Automatic Derivation of Parallel and Systolic Programs

We present a simple method for developing parallel and systolic programs from data dependence. We derive sequences of parallel computations and communications based on data dependence and communication delays, and minimize the communication delays and processor idle time. The potential applications for this method include supercompiling, automatic development of parallel programs, and systolic array design. 1 Introduction Given a sequential program consisting of a loop, or a set of equations that recursively define an array, we want to develop a parallel program for a shared or distributed memory parallel computer. There are two problems here. First we have to reveal the parallelism and find the sequences of parallel computations. Second, for distributed memory parallel computers, we want to schedule the computations and communications at compile time so that all data needed arrive before a computation is scheduled to start, and minimize processor idle time and overall communications...