Systematic Extraction and Implementation of Divide-and-Conquer Parallelism

摘要: Homomorphisms are functions that match the divide-and-conquer paradigm and thus can be computed in parallel. Two problems studied for homomorphisms on lists: (1) parallelism extraction: finding a homomorphic representation of given function; (2) implementation: deriving an efficient parallel program computes function. A systematic approach to extraction proceeds by generalization two sequential representations based traditional cons lists dual snoc lists. For some non-homomorphic functions, e.g., maximum segment sum problem, our method provides embedding into homomorphism. The implementation is addressed introducing subclass distributable them schema, which time optimal hypercube architecture. derivation equational reasoning Bird-Meertens formalism, guarantees correctness target program. illustrated with function scan (parallel prefix), combination methods yields “folklore” algorithm, usually presented ad hoc literature.