Refinement Transformation Using Abstract Parallel Machines

Joy Goodman, John O'Donnell, Gudula Rünger


Abstract Parallel Machines support a design methodology for the refinement of a high level specification into an executable parallel program. Parallel combinators are defined in a normal form which allows a calcluation of the cost as well as the semantics. The user can define several versions of these combinators, corresponding to different levels of abstraction. A specification is compiled (either manually or automatically) into an implementation through a sequence of refinements, where each version of the algorithm uses a suitable set of parallel combinators defined in an Abstract Parallel Machine. We illustrate the method with a simple case study: the refinement transformation of a concise functional program to sum the columns of a triangular matrix into a parallel C+MPI program that uses load balancing to improve performance.

The full paper

Associated software

You can also see the main Haskell programs, the Haskell program using the MPI APM, and the C+MPI program referenced in the paper.
You will need the MPIapm, PST and ParTypes modules to run the second of these programs.
Lastly, here are sketches of the derivations (or proofs of equivalence) between the stages:
Stage 1 -> Stage 2, Stage 2 -> Stage 3, Stage 3 -> Stage 4(the MPI apm stage), Stage 4 -> C version.

These programs and modules are in the form they were in in 1999.

Related links

BibTeX citation

  author =       {Joy Goodman and John O'Donnell and Gudula R\"unger},
  title =        {Refinement transformation using
                  {Abstract Parallel Machines}},
  booktitle =    {Glasgow Workshop on Functional Programming},
  year =         1998,
  organization = {Computing Science Department, University of Glasgow}
Joy Goodman
Back to my research page
Back to my home page