Abstract Parallel Machines: Organizing Higher Order Functions for Parallel Program Derivation

John O'Donnell and Gudula Ruenger

We need to take a flexible approach in designing a family of higher order functions to support parallel program derivation. For example, it isn't enough just to define scan and give it a log time cost model, because there are actually many different implementations with different costs, suitable in different circumstances. To help a programmer decide what to do next in a derivation, the parallel operations need to be defined at several levels of abstraction and to have a suitable operational semantics at each level.

We propose Abstract Parallel Machines to address these problems, and we apply them to two case study derivations: a parallel heat equation program and a parallel addition algorithm.

An abstract parallel machine defines a set of parallel operations, and it expresses these definitions using a set of computational sites (`abstract processors') and coordination functions (`abstract network'). This makes a suitable model of implementation available at each level. The framework can describe higher order parallel operations at high levels (SPMD), intermediate levels (scan) and low levels (digital circuits). We have found that this approach helps guide the derivation process by clarifying the relationships between alternative realizations of a function, and we plan to experiment with it on more complex case studies.