Paper Description: GorEuro

BibTeX entry:

author ="S. Gorlatch",
title = "Systematic Efficient Parallelization of Scan and Other List Homomorphisms",
editor = "L.~Bouge and P.~Fraigniaud and A.~Mignotte and Y.~Robert",
pages = "401--408",
booktitle = "Euro-Par'96. Parallel Processing",
series = "Lecture Notes in Computer Science 1124",
year = "1996",
publisher = "Springer-Verlag",
abstract =
"Homomorphisms are functions which can be parallelized by the divide-and-conquer paradigm. A class of Distributable Homomorphisms (DH) is introduced and an efficient parallel implementation schema for all functions of the class is derived by transformations in the Bird-Meertens formalism. The schema can be directly mapped on the hypercube with an unlimited or an arbitrary fixed number of processors, providing provable correctness and predictable performance. The popular Scan function (parallel prefix) illustrates the presentation: the systematically derived implementation for Scan coincides with the practically used ``folklore'' algorithm for distributed-memory machines."

Paper itself:

Cross links:

Martin Griebl