Improving data layout through coloring-directed array merging

Scientific computing and image processing applications access
large
amounts of data in regular patterns. In order to relieve the
memory
bottleneck, caching tries to keep recently referenced data
available
in fast storage. This is increasingly important as the gap
between
processor and memory hierarchy speed has widened in recent
years.

There are two main difficulties that cannot be dealt with by
hardware
alone. Firstly, a cache line usually holds several values; often
only
one of them is actually used. Secondly, conflicting accesses to
one
cache line cause data to be evicted which is still required.
In the extreme case, data is replaced on every access, a
situation we
denote as cache thrashing. To overcome these problems, the
temporal/spatial structure of accesses has to be changed.

Compile-time cache optimizations exploit regular access
patterns.
Loop transformations as e.g. tiling are well-established.
For caches with limited associativity, it is often crucial to
additionally adjust the placement of data in memory.
We show that compiler techniques for register allocation, namely
graph coloring, support a systematic data placement.
... mehr

For innermost loops, conflicts and temporal reuse can be modeled
together in a cyclic interval graph. If reuse stretches over
several
loop iterations, live ranges may overlap themselves, prohibiting
usual
cyclic coloring.
By applying the meeting graph method, the compiler can determine
an
unrolling factor and determine the maximal number of colors,
i.e. of
cache lines required.

Values of the same color are mapped to memory together. Since
these
values may stem from different data structures, our technique
offers
a natural way of dealing with conflicts between different
arrays.

We implement this scheme through modifying the standard memory
mapping. At run time, the new compile time mapping function is
used
as index function.
The tradeoff between the additional cost for more complex
indexing
and reduced miss penalty is reflected by a cost function.

For typical example codes from the above areas, reuse and
conflict
behavior are considerably improved, yielding moderate run time
reductions. In addition, on a more coarse level, paging activity
is
often significantly postponed.