A Generalized Theory of Linear Loop Transformations

In this paper we present a new theory of linear loop transformations called Computation Decomposition and Alignment (CDA). A CDA transformation has two components: Computation Decomposition first decomposes the computations in the loop into computations of finer granularity, from iterations to instances of subexpressions. Computation Alignment subsequently, linearly transforms each of these sets of computations, possibly by using a different transformation for each set. This framework subsumes all existing linear transformation frameworks in that it reduces to a conventional linear loop transformation when the smallest granularity is an iteration, and it reduces to some of the more recently extended frameworks when the smallest granularity is a statement instance. The possibility of being able to align computations at arbitrary granularities addsa new dimensions to performance optimization on high performance computing platforms. We describe ComputationDecompositionandAlignment and pro..