A linear algebra framework for automatic determination of optimal data layouts

This paper presents a data layout optimization technique for sequential and parallel programs based on the theory of hyperplanes from linear algebra. Given a program, our framework automatically determines suitable memory lay outs that can be expressed by hyperplanes for each array that is referenced . We discuss the cases where data transformations are preferable to loop tr ansformations and show that under certain conditions a loop nest can be opt imized for perfect spatial locality by using data transformations. We argue that data transformations can also optimize spatial locality for some arra ys without distorting temporal/spatial locality exhibited by others. We div ide the problem of optimizing data layout into two independent subproblems: 1) determining optimal static data layouts, and 2) determining data transf ormation matrices to implement the optimal layouts. By postponing the deter mination of the transformation matrix to the last stage, our method can be adapted to compilers with different default layouts. We then present an alg orithm that considers optimizing parallelism and spatial locality simultane ously. Our results on eight programs on two distributed shared-memory multi processors, the Convex Exemplar SPP-2000 and the SGI Origin 2000, show that the layout optimizations are effective in optimizing spatial locality and parallelism.