CDA Loop Transformations

In this paper we present a new loop transformation technique called Computation Decomposition and Alignment (CDA). Computation Decomposition first decomposes the iteration space into finer computation spaces. Computation Alignment subsequently, linearly transforms each computation space independently. CDA is a general framework in that linear transformations and its recent extensions are just special cases of CDA. CDA's fine grained loop restructuring can incur considerable computational effort, but can exploit optimization opportunities that earlier frameworks cannot. We present four optimization contexts in which CDA can be useful. Our initial experiments demonstrate that CDA adds a new dimension to performance optimization. 1 INTRODUCTION The introduction of linear transformations in 1990 as an algebraic framework for loop optimization [5, 22] was a major contribution for three reasons: First, the framework provides a unified approach to loop restructuring since most existing loop ..