Systematic development of an SPMD implementation schema for mutually recursive divide-and-conquer specifications
Sergei Petrovich Gorlatch, Christian Lengauer · 2002
An SPMD parallel implementation schema for divide-and-conquer specifications is proposed and derived b y formal refinement (transformation) of the specifica-tion. The specification is in the form of a mutually recursive functional definition. In a first phase, a par-allel functional program schema is constructed which consists of a communication tree and a functional pro-gram that is shared by all nodes of the tree. The fact that this phase proceeds b y semantics-preserving trans-formations in the Bird-Meertens formalism of higher-order junctions guarantees the correctness of the re-sulting functional implementation. A second phase yields an imperative distributed SPMD implementa-tion of this schema. The derivation process is illus-trated with an example: a two-dimensional numerical integration algorithm. 1