Paper Description: MIP-9315

BibTeX entry:

@incollection{MIP-9315,

author="S. Gorlatch, C. Lengauer",

title="Parallelization of Divide-and-Conquer in the Bird-Meertens Formalism",

institution="Fakult{\"a}t f{\"u}r Mathematik und Informatik, Universit{\"a}t Passau",

year=1993,

number={MIP-9315}

}

Abstract:

An SPMD parallel implementation schema for divide-and-conquer specifications is proposed and derived by formal refinement (transformation) of the specification. The specification is in the form of a mutually recursive functional definition. In a first phase, a parallel functional program schema is constructed which consists of a communication tree and a functional program that is shared by all nodes of the tree. The fact that this phase procceeds by semantics-prereserving transformations in the Bird-Meertens formalism of higher-order functions guarantees the correctness of the resulting functional implementation. A second phase yields an imperative distributed SPMD implementation of this schema. The derivation process is illustrated with an example: a two-dimensional numerical integration algorithm. .

Paper itself:

compressed file (for previewing or ftp)

Cross links:

Ulrike Peiker, Martin Griebl