Paper Description: GorSCP

BibTeX entry:

author ="S. Gorlatch",
title = "Extracting and Implementing List Homomorphisms in Parallel Program Development",
journal = "Science of Computer Programming",
year = "1999",
volume = "33",
number = "1",
pages = "1--27",
abstract =
"Homomorphisms are functions that match the divide-and-conquer pattern and are widely used in parallel programming. Two problems are studied for homomorphisms on lists: (1) parallelism extraction: finding a homomorphic representation of a given function; (2) parallelism implementation: deriving an efficient parallel program that computes the function. The proposed approach to parallelism extraction starts by writing two sequential programs for the function, on traditional cons lists and on dual snoc lists; the parallel program is obtained by generalizing sequential programs as terms. For almost-homomorphic functions, e.g., the maximum segment sum problem, our method provides a systematic embedding into a homomorphism. The implementation problem is addressed by introducing the class of distributable homomorphisms and deriving for them a common parallel program schema. The derivation is based on equational reasoning in the Bird-Meertens formalism, which guarantees the correctness of the parallel target program. The approach is illustrated with the function scan (parallel prefix), for which the combination of our two systematic methods yields the optimal hypercube algorithm, usually presented ad hoc in the literature."

Paper itself:

Because of copyright restrictions we can only supply a previous version, whichg does not reflect the comments of the reviewers. You can obtain the journal paper from the Web site of the journal or by asking the author for a reprint.

Cross links:

Sergei Gorlatch