Loop optimization for aggregate array computations
Abstract:
An aggregate array computation is a loop that computes accumulated
quantities over array elements. Such computations are common in
programs that use arrays, and the array elements involved in such
computations often overlap, especially across iterations of loops,
resulting in significant redundancy in the overall computation. This
paper presents a method and algorithms that eliminate such overlapping
aggregate array redundancies and shows both analytical and experimental
performance improvements. The method is based on incrementalization,
i.e., updating the values of aggregate array computations from iteration
to iteration rather than computing them from scratch in each iteration.
This involves maintaining additional information not maintained in the
original program and performing additionally enabled optimizations. We
reduce various analysis problems to solving inequality constraints on
loop variables and array subscripts, and we apply results from work on
array data dependence analysis. Incrementalizing aggregate array
computations produces drastic program speedup compared to previous
optimizations. Previous methods for loop optimizations of arrays do not
perform incrementalization, and previous techniques for loop
incrementalization do not handle arrays.
Scott Stoller's Home Page