© 1997 by British Computer Society
A Parametrized Loop Fusion Algorithm for Improving Parallelism and Cache Locality
Systems for Advanced Architectures, Department of Computer Science, University of Massachusetts, Amherst, MA 01003, USA Email: singhai{at}cs.umass.edu
Loop fusion is a reordering transformation that merges multiple loops into a single loop. It can increase data locality and the granularity of parallel loops, thus improving program performance. Previous approaches to this problem have looked at these two benefits in isolation. In this work, we propose a new model which considers data locality, parallelism and register pressure together. We build a weighted directed acyclic graph in which the nodes represent program loops along with their register pressure, and the edges represent the amount of locality and parallelism present. The direction of an edge represents an execution order constraint. We then partition the graph into components such that the sum of the weights on the edges cut is minimized, subject to the constraint that the nodes in the same partition can be safely fused together, and the register pressure of the combined loop does not exceed the number of available registers. Previous work demonstrates that the general problem of finding optimal partitions is NP-hard. In restricted cases, we show that it is possible to arrive at the optimal solution. We give an algorithm for the restricted case and a heuristic for the general case. We demonstrate the effectiveness of fusion and our approach with experimental results.
Received October 1996. revised July 1997.