EXTRACTING AND IMPLEMENTING LIST HOMOMORPHISMS IN PARALLEL PROGRAM-DEVELOPMENT

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 homo morphic representation of a given function; (2) parallelism implementa tion: deriving an efficient parallel program that computes the functio n. The proposed approach to parallelism extraction starts by writing t wo 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 embe dding 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 equa tional reasoning in the Bird-Meertens formalism, which guarantees the correctness of the parallel target program. The approach is illustrate d 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. (C) 1999 Elsevier Science B.V. All rights reserved.