A simple program transformation for parallelism
Saumya Debray, Mudita Jain · 1994
Most of the research, to date, on optimizing program transformations for declarative languages has focused on sequential execution strategies. In this paper, we consider a class of commonly encountered computations whose "natural" specification is essentially sequential, and show how algebraic properties of the operators involved can be used to transform them into divide-and-conquer programs that are considerably more efficient, both in theory and in practice, on parallel machines. 1 Introduction Among the advantages claimed for declarative programming languages are that (i) programs written in such languages are relatively easy to reason about, which makes it possible to automatically transform simple declarative specifications into efficiently executable code; and (ii) it is easy to exploit parallelism in programs written in such languages. Nevertheless, most of the research on transformation of programs in high level languages has focused, to date, on execution strategies that are...