Extracting and implementing list homomorphisms in parallel program development

摘要

Homomorphisms are functions that match the divide-and-conquer pattem and are widely used in parallel programming. Two problems are studied for homomorphisms on lists: (l) parallelism extraction: finding a homomorphic representation of a given function; (2) parallelism implemen- tation deriving an efficient parallel program that computes the function. The proposed approach to parallelism extraction starts by whting 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 prob- lem, 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 correcturess 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 algorithin, usually presented ad hoc in the literature.