A dynamic locality optimization algorithm for linear algebra codes

Compiler-directed optimization techniques are effectiv e in reducing the number of cycles spent in off-c hip memory accesses. Recently, methods have been developed that transform memory layouts of data structures at compile-time to improve spatial locality of nested loops beyond current con trol-cen trie (loop nest-based) optimizations. Most of these data-cen trictransformations use a single static (program-wide) memory layout for each array. A disadv antageof these static layout-based localiy. enhancement strategies is that they might fail to optimize codes that manipulate arrays whic hdemand different layouts (from a data locality perspectiv e) in differed parts of the code. In this paper, we presen t a new approafc which extends current static lay out optimization techniques to select dynamically changing memory layouts to further improve the locality of data accesses. We show that the possibilit y of dynamically changing memory layouts during the course of execution adds a new dimension to the data locality optimization problem. Our strategy employs a static layout optimizer module as a building block and by repeatedly invoking it for different parts of the code, it checks whether runtime layout modifications bring additional benefits beyond static optimizer.