Functional Array Fusion

Manuel M. T. Chakravarty and Gabriele Keller

To appear at International Conference on Functional Programming (ICFP01), Firenze, Italy, 3-5 September 2001


This paper introduces a new approach to compiling array algorithms in functional languages. We are specifically aiming at an efficient implementation of irregular array algorithms that are hard to implement in conventional array languages such as Fortran. We optimise the storage layout of arrays containing complex data structures and reduce the runtime of functions operating on these arrays by means of equational program transformations. In particular, this paper discusses a novel form of combinator loop fusion, which by removing intermediate structures optimises the use of the memory hierarchy. We identify a combinator named loopP that provides a general scheme for iterating over an array and that in conjunction with an array constructor replicateP is sufficient to express a wide range of array algorithms. On this basis, we define equational transformation rules that combine traversals of loopP and replicateP as well as sequences of applications of loopP into a single loopP traversal. Our approach naturally generalises to a parallel implementation and includes facilities for optimising load balancing and communication. A prototype implementation based on the rewrite rule pragma of the Glasgow Haskell Compiler is significantly faster than standard Haskell arrays and approaches the speed of hand coded C for simple examples.

Server START Conference Manager
Update Time 11 May 2001 at 15:31:50
Start Conference Manager
Conference Systems