A Singular Loop Transformation Framework Based on Non-singular Matrices

Abstract

In this paper, we discuss a loop transformation framework that is based on integer non-singular matrices. The transformations included in this framework are called A-transformations and include permutation, skewing and reversal, as well as transformation called loop scaling. This framework i s more general than existing ones; however, it is also more difficult to generate code in our frame- work. This paper shows how integer lattice theory can be used to generate efficient code. An added advantage of our framework over existing ones is that there is a simple completion algorithm which, given a partial transformation matrix, produces a full transformation matrix that satisfies all dependencies. This completion procedure has applications in parallelization and in the generation of code for NUMA machines.