# Paper Description: GorPLILP

### BibTeX entry:

@InCollection{GorPLILP,
author ="S. Gorlatch",
title = "**Systematic Extraction and Implementation of
Divide-and-Conquer Parallelism**",
editor = "H.~Kuchen and D.~Swierstra",
booktitle = "Programming languages: Implementation, Logics and
Programs. PLILP'96",
series = {Lecture Notes in Computer Science 1140},
publisher = {Springer-Verlag},
year = "1996",
pages = "274--288",
abstract =
"Homomorphisms are functions that match the divide-and-conquer paradigm
and thus can be
computed in parallel.
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.
A systematic approach to parallelism extraction proceeds
by generalization of two sequential
representations based on traditional cons-lists and dual snoc-lists.
For some non-homomorphic functions,
e.g., the maximum segment sum problem, our method
provides an embedding
into a homomorphism.
The implementation
is addressed by introducing a subclass of distributable homomorphisms
and deriving for them a parallel program schema,
which is time optimal on the hypercube architecture.
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 function
Scan (parallel prefix), for which the combination of
our two systematic methods
yields the ``folklore'' hypercube algorithm, usually presented
ad hoc in the literature."

}

### Paper itself:

### Cross links:

Martin Griebl