Improving the Locality of Program Instances by Local Search

In memory hierarchies, programs can be speeded up by increasing their degree of locality. This paper proposes an algorithm that optimizes the locality of program instances. Input is a set of statement instances, where each statement instance is characterized by the sequence of data it accesses. The algorithm orders the statement instances, thereby respecting data dependencies, and groups the data into blocks of memory. It is a local search heuristic with an objective function that quantitatively formalizes the intuitive notion of degree of locality. The algorithm is embedded in a semi-automatic locality optimization method for programs. Experimental results show that the algorithm can improve on current compiler optimizations. 1 Introduction Due to the large and growing gap between processor speeds and memory speeds, the running time of programs critically depends on their ability to use the memory hierarchy efficiently. Data locality is a gradual property of programs that reflects th..