Integer linear programming approach for optimizing cache locality

M. Kandemir*, P. Banerjee, A. Choudhary, J. Ramanujam, E. Ayguade

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

10 Scopus citations


The actual performance of programs on modern processors that employ deep memory hierarchies is closely related to the performance of the memory subsystem. Compiler optimizations aimed at improving cache locality are critical in realizing the performance potential 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 characteristics of loop nests. This paper presents a technique based on integer linear programming (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 sequence 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 presented here obviates the need for such heuristics. Experimental results on a MIPS R10000 based system demonstrate the benefits of this approach, and show that the use of the ILP formulation does not increase the compilation time significantly.

Original languageEnglish (US)
Number of pages10
StatePublished - 1999
EventProceedings of the 1999 13th ACM International Conference on Supercomputing, ICS'99 - Rhodes, Greece
Duration: Jun 20 1999Jun 25 1999


ConferenceProceedings of the 1999 13th ACM International Conference on Supercomputing, ICS'99
CityRhodes, Greece

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Integer linear programming approach for optimizing cache locality'. Together they form a unique fingerprint.

Cite this