A Hyperplane Based Approach for Optimizing Spatial Locality in Loop Nests
M. Kandemir, A. Choudhary, N. Shenoy, P. Banerjee, and J. Ramanujam
Abstract
This paper presents a data layout optimization technique based on
hyperplane theory from linear algebra. Given a program, our
framework automatically determines the optimal layouts that can be
expressed by hyperplanes for each array that is referenced. We discuss
the cases where data transformations are preferable to loop
transformations and show that under certain conditions a loop
nest can be optimized for perfect spatial locality by using data
transformations. We argue that data transformations can also optimize
spatial locality for some arrays without distorting
temporal/spatial locality exhibited by others. We divide the problem
of optimizing data layout into two independent subproblems: (1)
determining optimal layouts, and (2) determining data transformation
matrices to implement optimal layouts. By postponing the determination
of the transformation matrix to the last stage, our method can be
adapted to compilers with different default layouts. We also give
sketch of an algorithm which considers optimizing parallelism and
spatial locality simultaneously. Our
results on eight programs on the Convex Exemplar and SGI Origin 2000 show
that the layout optimizations can be effective in optimizing spatial
locality.