A Direct Approach for Finding Loop Transformation Matrices

Loop transformations,such as loop interchange,reversal and skewing,have been unified under linear matrix transformations.A legal transformation matrix is usually generated based upon distance vectors or direction vectors.Unfortunately,for some nested loops,distance vectors may not be computable and direction vectors, Unfortunately,for some nested loops,distance vectors may not be computable and direction vectors,on the other hand,may not contain useful information.We propose the use of linear equations or inequalities of distance vectors to approximate data dependence.This approach is advantageous since(1) many loops having no constant distance vectors have very simple equations of distance vectors;(2) these equations contain more information than direction vectors do,thus the chance of exploiting potential parallelism is improved.In general,the equations or inequalities that approximate the data dependence of a given nested loop is not unique,hence classification is discussed for the purpose of loop transformationEfficient algorithms are developed to generate all kinds of linear equations of distance vectors for a given nested loop.The issue of how to obtain a desired transformation matrix from those equations is also addressed.

A direct approach for finding loop transformation matrices

Loop transformations, such as loop interchange, reversal and skewing, have been unified under linear matrix transformations. A legal transformation matrix is usually generated based upon distance vectors or direction vectors. Unfortunately, for some nested loops, distance vectors may not be computable and direction vectors, on the other hand, may not contain useful information. We propose the use of linear equations or inequalities of distance vectors to approximate data dependence. This approach is advantageous since (1) many loops having no constant distance vectors have very simple equations of distance vectors; (2) these equations contain more information than derection vectors do, thus the chance of exploiting potential parallesism is improved. In general, the equations or inequalities that approximate the data dependence of a given nested loop is not unique, hence classification is discussed for the purpose of loop transformation. Efficient algorithms are developed to generate all kinds of linear equations of distance vectors for a given nested loop. The issue of how to obtain a desired transformation matrix from those equations is also addressed.