A compiler algorithm for optimizing locality in loop nests
Mahmut Kandemir, Jagannathan Ramanujam, Alok Choudhary · 1997
This paper describes an algorithm to optimize cache locality in scientic codes on uniprocessor and multiprocessor ma-chines. A distinctive characteristic of our algorithm is that it considers loop and data layout transformations in a uni-ed framework. We illustrate through examples that our approach is very eective at reducing cache misses and tile-size sensitivity of blocked loop nests; and can optimize nests for which optimization techniques based on loop transfor-mations alone are not successful. An important special case is the one in which data layouts of some arrays are xed and cannot be changed. We show how our algorithm can handle this case, and demonstrate how it can be used to optimize multiple loop nests. 1