# Paper Description: GorSCP

### BibTeX entry:

@Article{GorSCP,
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