"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."
Martin Griebl