A LOOP TRANSFORMATION THEORY AND AN ALGORITHM TO MAXIMIZE PARALLELISM

This paper proposes a new approach to transformations for general loop nests. In this approach, we unify all combinations of loop interchange, skewing and reversal as unimodular transformations. The use of matrices to model transformations has previously been applied only to those loop nests whose dependences can be summarized by distance vectors. Our technique is applicable to general loop nests where the dependences include both distances and directions. This theory provides the foundation for solving an open question in compilation for parallel machines: which loop transformations, and in what order, should be applied to achieve a particular goal, such as maximizing parallelism or data locality. This paper presents an efficient loop transformation algorithm based on this theory to maximize the degree of parallelism in a loop nest.