CRPC-TR99789						December 1999

Title: Fast Greedy Weighted Fusion

Author: Ken Kennedy

Submitted December 1999

Abstract:

Loop fusion is important to optimizing compilers because it is an
important tool in managing the memory hierarchy.  By fusing loops that use
the same data elements, we can of the ensure that uses after the first can
take data from cache or registers rather than memory, avoiding costly
cache misses.  Unfortunately the problem of optimal loop fusion for reuse
has been shown to be NP-hard, so compilers must resort to heuristics to
avoid unreasonably long compile times.  Greedy strategies are often
excellent heuristics, and can be used to produce high-quality solutions in
reasonable running times.  We present an algorithm for greedy weighted
fusion, in which the heaviest edge (the one with the most reuse) is
selected for possible fusion on each step.  The algorithm is shown to be
fast in the sense that it takes O(VE + V^2) time, which is arguably
optimal for this problem.

------------------------------------------------------------------------------

ken@rice.edu
Center for High Performance Software
Rice University