A long version of this article is available back to publications page
back to publications page

Abstract

We show that cyclic graph coloring techniques from register allocation are successfully applicable to caches. The presence of values in the cache can be modeled in analogy to register live ranges. By applying the meeting graph method, the compiler can determine an unrolling factor and guarantee the maximal number of colors, i.e.~of cache lines required. Values of one color belong together, even if they stem from different data structures. For a class of scientific codes, the new data layout improves reuse and conflict behavior by a systematic merging.