Parallelization of divide-and-conquer in the Bird-Meertens formalism |
| |
Authors: | Sergei Gorlatch Christian Lengauer |
| |
Affiliation: | (1) Fakultät für Mathematik und Informatik, Universität Passau, D-94030 Passau, Germany |
| |
Abstract: | An SPMD parallel implementation schema for divide-and-conquer specifications is proposed and derived by formal refinement (transformation) of the specification schema. 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 proceeds by semantics-preserving 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 message-passing implementation of this schema. The derivation process is illustrated with an example: a two-dimensional numerical integration algorithm.Parts of this paper were presented at the International Parallel Processing Symposium, Mexico, 1994 [GoL94] and at the World Transputer Congress, Italy, 1994 [Gor94] |
| |
Keywords: | Bird-Meertens formalism Divide-and-conquer Functional programming Parallel programming Transformations |
本文献已被 SpringerLink 等数据库收录! |