Using Padding to Optimize Locality in Scientific Applications

Abstract

Program locality exploitation is a key issue to reduce the execution time of scientific applications, so as many techniques have been designed for locality optimization. This paper presents new compiler algorithms based on array padding that optimize program locality either locally (at loop level) or globally (the whole program). We first introduce a formal cache model that is used to analyze how all cache levels are filled up when arrays inside nested loops are referenced. We further study the relation between the model parameters and the data memory layout of the arrays, and define how to pad those arrays in order to optimize cache occupation at all levels. Experimental evaluation on some numerical benchmarks shows the benefits of our approach.