Re: Theory on loop transformations

assmann@karlsruhe.gmd.de (Uwe Assmann) writes:
|> In general, I am interested in a general theory on loop transformations.


  We have a matrix-oriented approach to loop transformations that uses
non-singular matrices to represent loop transformations. Non-singular
matrices generalize the unimodular approach (unimodular matrices are a
special case of non-singular matrices in which the determinant is 1 or
-1). Some important transformations such as loop tiling can only be
modeled by non-singular matrices. Furthermore, we provide a completion
algorithm that makes the theory easier to use in practice. In
transformations for parallelism and data locality, it is very useful to
have such completion algorithm. Our work was presented at the 5th
Compiler Workshop at Yale last year. A journal version is to appear soon
in IJPP.


We have used the non-singular matrix framework to develop optimizations
for data locality in our compiler for NUMA parallel machines. You can
find how the transformation matrix is constructed automatically. The
algorithms are in the paper that appeared in ASPLOS V (ACM SIGPLAN
Notices, Vol 27, Number 9, Sep. 1992).


The papers can also be found via ftp from Cornell (ftp.cs.cornell.edu,
pub/TyphoonCompiler/papers-ps/).


---------------------------------------------------------------------------
file: framework.ps


                "A Singular Loop Transformation Framework
                  Based on Non-singular Matrices"
                      by Wei Li and Keshav Pingali
---------------------------------------------------------------------------
file: asplos92.ps


                "Access Normalization: Loop Restructuring for NUMA Compilers"
                      by Wei Li and Keshav Pingali
---------------------------------------------------------------------------
file: pnuma.ps


                "Loop Transformations for NUMA Machines"
                      by Wei Li and Keshav Pingali
                      SIGPLAN Notices, January 1993


-- Wei Li
Department of Computer Science
Cornell University
Ithaca, NY 14853
--

Return to the comp.compilers page.
Search the comp.compilers archives again.