Parallel Programming, List Homomorphisms and the Maximum Segment Sum Problem.

Abstract

We review the use of the Bird-Meertens Formalism as a vehicle for the construction of programs with massive implicit parallelism. We show that a simple result from the theory, concerning the expression of list homomorphisms, can help us in our search for parallel algorithms and demonstrate its application to some simple problems including the maximum segment sum problem. Our main purpose is to show that an understanding of the homomorphism lemma can be helpful in producing programs for problems which are "not quite" list homomorphisms themselves. A more general goal is to illustrate the benefits which can arise from taking a little theory with a pinch of pragmatic salt. 1 Introduction The use of bulk operations on aggregate data sets as a means of generating programs with a high degree of implicit parallelism has a long history (e.g. see [4] for a recent presentation). Although traditionally associated with an imperative programming style and SIMD machines, the approach lends itself e...