Paper Info
Title
Functional array fusion
Abstract
This paper introduces a new approach to optimizing 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 optimize the storage layout of arrays containing complex data structures and reduce the running time 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 optimizes the use of the memory hierarchy. We identify a combinator named loop P that provides a general scheme for iterating over an array and that in conjunction with an array constructor replicate P is sufficient to express a wide range of array algorithms. On this basis, we define equational transformation rules that combine traversals of loop P and replicate P as well as sequences of applications of loop P into a single loop P traversal. Our approach naturally generalizes to a parallel implementation and includes facilities for optimizing 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.
Year
DOI
Venue
2001
10.1145/507669.507661
Special Interest Group on Programming Languages
Keywords
Field
DocType
functional language,views,tournament,complex data,loop fusion,load balance
Loop fusion,Data structure,Tree traversal,Programming language,Functional programming,Computer science,Combinatory logic,Parallel computing,Compiler,Loop interchange,Haskell
Conference
Volume
Issue
ISSN
36
10
0362-1340
ISBN
Citations 
PageRank 
1-58113-415-0
13
1.01
References 
Authors
27
2
Name
Order
Citations
PageRank
Manuel M. T. Chakravarty166641.89
Gabriele Keller265736.02