Title/Author/Abstract
- Title:
A Case for Array Merging in Memory Hierarchies
- Author:
Daniela Genius and Sylvain Lelait
- Full Paper(.pdf version)
- Abstract:
Many data layout techniques for cache optimization reduce miss rates
ssignificantly, while only marginally improving on run time. One
reason is that some data layouts inflate the array size, thus causing
more misses in higher levels of the memory hierarchy. Misses in the
Translation Look-aside Buffers (TLBs) have emerged as a major source
of performance degradation. We suggest the first systematic approach
to array merging for stencil codes, which are not viable to standard
data layout techniques because of interference between different arrays
in several directions. The heuristic presented here is borrowed from
the register allocation context, and uses coloring to avoid
conflicts. Cyclic coloring is used to determine a merging of different
arrays which are accessed together in a loop. Gaps may occur in the
data layout, but these are on average far smaller than with standard
techniques. The new layout reduces conflicts while keeping the run
time overhead fairly small. In particular, TLB miss reduction is
encouraging.
Please contact our
webadmin with any comments or changes.
Unless explicitly stated otherwise, all material is
copyright © The University of Edinburgh.