SUMMARY: Loop transformations with unimodular matrices

Here comes a summary of answers concerning the description of loop
transformations with unimodular matrices. Thanks to all who have
responded.


------------------------------------------------------------------------------
From: pugh@cs.umd.edu (Bill Pugh)


Actually, it was M. E. Wolf, not M. Wolfe (confusing, isn't it?). Here
are a couple of references on the subject.


U. Banerjee.
  Unimodular transformations of double loops.
  In {\em Proc. of the 3rd Workshop on Programming Languages and
    Compilers for Parallel Computing}, Irvine, CA, August 1990.


Paul Feautrier.
  Some efficient solutions to the affine scheduling problem, part i,
    one-dimensional time.
  Technical Report 92.28, IBP/MASI, April 1992.


Paul Feautrier.
  Some efficient solutions to the affine scheduling problem, part ii,
    multi-dimensional time.
  Technical Report 92.78, IBP/MASI, Oct 1992.


Wayne Kelly and William Pugh,
  Generating Schedules and Code within a
Unified Reordering Transformation Framework,
    Technical Report CS-TR-2995,
    Dept. of Computer Science, University of Maryland, College Park,
    November, 1992




K. G. Kumar, D. Kulkarni, and A. Basu.
  Deriving good transformations for mapping nested loops on hieracical
    parallel machines in polynomial time.
  In {\em Proc. of the 1992 International Conference on
    Supercomputing}, July 1992.


Wei Li and Keshav Pingali.
  A singular loop transformation framework based on non-singular
    matrices.
  In {\em 5th Workshop on Languages and Compilers for Parallel
    Computing}, Yale University, August 1992.


Lee-Chung Lu.
  A unified framework for systematic loop transformations.
  In {\em Proceedings of Third ACM SIGPLAN Symp. on the Principles \&
    Practice of Parallel Programming}, April 1991.


William Pugh.
  Uniform techniques for loop optimization.
  In {\em 1991 International Conference on Supercomputing}, pages
    341--352, Cologne, Germany, June 1991.


J. Ramanujam.
  Non-unimodular transformations of nested loops.
  In {\em Supercomputing `92}, November 1992.


Vivek Sarkar and Radhika Thekkath.
  A general framework for iteration-reordering loop transformations.
  In {\em ACM SIGPLAN'92 Conference on Programming Language Design and
    Implementation}, San Francisco, California, Jun 1992.


Michael E. Wolf and Monica S. Lam.
  A data locality optimizing algorithm.
  In {\em ACM SIGPLAN'91 Conference on Programming Language Design and
    Implementation}, 1991.


Michael E. Wolf and Monica S. Lam.
  A loop transformation theory and an algorithm to maximize
    parallelism.
  In {\em IEEE Transactions on Parallel and Distributed Systems}, July
    1991.


------------------------------------------------------------------------------


From: wak@cs.UMD.EDU (Wayne Kelly)


@inproceedings{Ban90,
                author = "U. Banerjee",
                title = "Unimodular Transformations of Double Loops",
                booktitle = "Proc. of the 3rd Workshop on Programming Languages and
                                Compilers for Parallel Computing",
                month = aug,
                year = 1990,
                address = "Irvine, CA" }


@INPROCEEDINGS{WL91,
author = {Michael E. Wolf and Monica S. Lam},
title = {A Data Locality Optimizing Algorithm},
booktitle = {ACM SIGPLAN'91 Conference on Programming Language
Design and Implementation},
year = 1991
}


@INPROCEEDINGS{WL91b,
author = {Michael E. Wolf and Monica S. Lam},
title = {A loop transformation theory and an algorithm to maximize
parallelism},
booktitle = {IEEE Transactions on Parallel and Distributed Systems},
month = {July},
year = 1991
}


Unimodular transformations is a unified framework that is able to describe
any transformation that can be obtained by compositions of loop
interchange, loop skewing, and loop reversal. Unfortunately, unimodular
transformations are limited by two facts: they can only be applied to
perfectly nested loops, and all statements in the loop nest are
transformed in the same way. They can therefore not represent some
important transformations such as loop fusion, loop distribution and
statement reordering.


We have developed a framework that generalizes unimodular transformations.
Our framework can represent a much broader set of reordering
transformations, including any transformation that can be obtained from
some combination of: loop interchange, loop reversal, loop skewing,
statement reordering, loop distribution, loop fusion, loop scaling, loop
alignment, index set splitting, loop blocking, loop interleaving, loop
coalescing. I would be happy to send you a copy of our paper if you are
interested.




---------------------------------------------------------------------------
From: wei@cs.cornell.EDU (Wei Li)


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
---------------------------------------------------------------------------
From: mehrotra@csrd.uiuc.edu (Sharad Mehrotra)


Those are excellent pointers, but unimodular transformations are only one
aspect of the larger problem of automatic program parallelization. If you
are just getting started in the area, you might find the following CSRD
report (also to appear soon in the Proceedings of the IEEE) useful:


Banerjee, U., Eigenman, R., Nicolau, A., and Padua, D.,
"Automatic Program Parallelization", CSRD TR 1250, November 1992.


The report contains a timely survey of the field and a bibliography with
161 citations.


Many CSRD Tech Reports are available for anonymous ftp from host
sp2.csrd.uiuc.edu (128.174.153.4) in directory CSRD_Info/reports. We'll
try and arrange to put the PostScript for this report there soon. If it's
not available in a few days, email reinhart@csrd.uiuc.edu, and ask for a
paper copy by snail mail.


---------------------------------------------------------------------------
From: dsehr@gomez.intel.com (David Sehr)


A colleague here at Intel has been working on exactly that problem for
several years. His name is Utpal Banerjee, and he has recently published
a book describing the approach you mention (using unimodular matrices for
dependence testing and transformation). The full info:
Loop Transformations for Restructuring Compilers: the Foundations
Utpal Banerjee
Kluwer Academic Publishers
ISBN: 0-7923-9318-X


Other possibilities to pursue are the recent papers of William Pugh of the
University of Maryland (pugh@cs.umd.edu), and Paul Feautrier of the
University of P. et M. Curie (feautrier@masi.ibp.fr).


David C. Sehr, Intel Corporation
2200 Mission College Blvd., M/S RN6-18
Santa Clara, CA 95052-8119
---------------------------------------------------------------------------
From: paik@mlo.dec.com (Samuel S. Paik)


Access Normalization: Loop Restructuring for NUMA Compilers. Wei Li,
Keshav Pingali. Proceedings of the Fifth International Conference on
Architectural Support for Programming Languages and Operating Systems,
SIGPLAN Notices, Vol. 27, No. 9, Sept 1992, pp. 285-295. ACM.


    Generalizes Banerjee's work on unimodular matrices for modeling
    loop transformations to invertable matrices, and applies this to
    restructuring loops for NUMA multiprocessors. Also available as a
    Cornell University CS technical report.


---------------------------------------------------------------------------
From: Francois IRIGOIN <irigoin@cri.ensmp.fr>


Some loop transformations are equivalent to a change of basis. To preserve
the number of iterations, the change of basis matrix has to be unimodular.
This idea has been around implictly for at least 6 years. Utpal Banerjee
has a paper on the subject. He's also written a book. Perhaps, you should
get in touch with him: <banerjee@csrd.uiuc.edu>.


Non-unimodular matrices are useful for tiling transformations.


Some loop transformations cannot be put in this framework: loop
distribution and loop alignment are good examples.


I'd like to know why you are interested in this subject. We've been
active in this field for many years but did not really manage to get in
touch with people in Germany, except the SUPERB team, Hans Zima/Michael
Gerndt.


Also, there is a Workshop in June in Germany (Dagsthul) about scheduling.
Simple schedules lead to matrix transformations, complex ones cover the
other loop transformation.


Francois Irigoin tel. +33 1 64 69 48 48
Centre de Recherche en Informatique fax. +33 1 64 69 47 09
Ecole des Mines de Paris e-mail: irigoin@cri.ensmp.fr
35 rue Saint Honore irigoin@fremp11.bitnet
77300 FONTAINEBLEAU
FRANCE
------------------------------------------------------------------------------
From: jrbd@craycos.com (James Davies)


I have a paper here for ASPLOS V (1992), published by ACM, which seems
related; it's called "Access Normalization: Loop restructuring for NUMA
Compilers", by Wei Li and Keshav Pingali of Cornell University, and
discusses using invertible matrices to model loop transformations. They
refer to a paper by Utpal Banerjee in Proceedings of the Workshop on
Advances in Languages and Compilers for Parallel Processing, August 1990,
called "Unimodular Transformations of Double Loops", which is supposed to
have also used matrices to model loop transforms. (I don't know who
published this workshop, all I have is the reference in the Li-Pingali
paper.)


------------------------------------------------------------------------------
From: vadik@cs.UMD.EDU (Vadim Maslov)


Ask Dr. Pugh (pugh@cs.umd.edu) and/or Mr. Kelly (wak@cs.umd.edu) from
University of Maryland. They have a theory that goes beyond unimodular
transformations. There are a couple of papers on it which are
electronically available.


------------------------------------------------------------------------------
From: Joe Hummel <jhummel@esp.ICS.UCI.EDU>


Actually, I think it was Utpal Banerjee with his work on unimodular
transformations. His new book, which is just being published, should have
lots of info on this. Utpal also has a paper, I think it appeared in the
last year or two in the IEEE Trans on Parallel and Distributed Computing.


------------------------------------------------------------------------------
From: Lode Nachtergaele <nachterg@imec.be>


M.E. Wolfe, M. Lam, "A loop transformation theory and an algorithm to
maximize parallelism", IEEE transactions on parallel and distributed
systems, Vol.2, October 1991


Look also to the work going on at the university of Maryland. The papers
and reports can be ftp'ed from : ftp.cs.umd.edu


Lode Nachtergaele
IMEC V.Z.W.
Kapeldreef 75
3001 Heverlee
Belgium
Phone : +32 (0)16 28.15.12
E-mail: nachterg@imec.be


------------------------------------------------------------------------------
Yep. I found it in ACM SIGPLAN'91 Conference: p.30-45,
authors Michael E. Wolf (not Wolfe) and Monica S. Lam (Stanford Uni.)
--
Jan Jongejan email: jjan@cs.rug.nl
Dept. Comp.Sci.,
Univ. of Groningen,
Netherlands.
--
Uwe Assmann
GMD Forschungsstelle an der Universitaet Karlsruhe
Vincenz-Priessnitz-Str. 1
7500 Karlsruhe GERMANY
Email: assmann@karlsruhe.gmd.de Tel: 0721/662255 Fax: 0721/6622968
--

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