Abstract An Integer Linear Programming Approach for Optirnizing Cache Locality

The actual performance of programs on modern processors that em-ploy deep memory hierarchies is closely related to the performance of the memory subsystem. Compiler optimizations aimed at im-proving cache locality are critical in realizing the performance po-tential of powerful processors. For scientific applications, several loop transformations have been shown to be useful in improving both temporal and spatial locality. Recently, there has been some work in the area of data layout optimizations, i.e., changing the memory layouts of multi-dimensional arrays from the language-defined default such as column-major storage in Fortran. These memory layout optimizations affect the spatial locality characteris-tics of loop nests. This paper presents a technique based on integer linear pro-gramming (ILP) that attempts to derive the best combination of loop and data layout transformations. Prior attempts to unify loop and data layout transformations for programs consisting of a se-quence of loop nests have been based on heuristics not only for transformations for a single loop nest but also for the sequence in which loop nests will be considered. The ILP formulation pre-sented here obviates the need for such heuristics. Experimental results on a MIPS RlOOOO based system demonstrate the benefits of this approach, and show that the use of the ILP formulation does not increase the compilation time significantly.