The University of Arizona
banner image

  A Simple Program Transformation for Parallelism

Saumya Debray   Mudita Jain
Department of Computer Science
University of Arizona
Tucson, AZ 85721, U.S.A.
 

Abstract
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.