Sun Apr 18 10:27:31 EDT 2010

Loop Fusion: Parametrization of Equivalence Classes

What is the big idea?  You want to separate:

   1. declaration of functional dependencies

   2. iteration strategy

The formula 

          map f (Indexed 1 ixf) = Indexed 1 (f . ixf)

can be interpreted in two ways.  As a rewrite rule (from left to
right) which picks a particular iteration strategy, or as an equiation
that creates an ``equi-semantical'' subspace of terms.

Is it somehow possible to construct representation of this
eqiu-semantical space that is explicitly parameterized, or at least
can be navigated locally.

In the end, this is really about symmetry.  It should be possible to
somehow relate this to discrete groups.

Once that group is explicit, optimizing the representation could be
done according to some well-defined measure, by defining a function
that maps the group to a (set of) benchmarks.

I.e. for the formula

         map f (map g v) = map (f . g) v

Essentially these are rotations of binary trees.

Maybe it's time to understand contemporary directed systems
(optimizers) first[1], and then move on to manual structure space

Before that, let's try to understand why one would ever want to move
in the other direction.  Fusion eliminates intermediate data storage.

When can (some) intermediate storage be good? 

Suppose that by using fusion, we can replace buffer memory access with
register memory access.  This works well as long as we have enough
registers.  Once we need to start spilling registers to memory we
might loose inner loop speed.  Let's call this "spill pressure" and
find a concrete example of it actually occurring.

Anyways..  This subject is quite complicated as there are so many
specific rewrite rules based on heuristics.  The more I see this, the
more I want to put "knobs" on it.  Make a user interface to program
transformation.  Navigate the equi-semantic manifold.

[1] http://www.cse.unsw.edu.au/~dons/papers/CLS07.html