Re: [PATCH] Matrix Flattening and Transposing optimizations

[Razya Ladelsky <RAZYA at il dot ibm dot com>]

Toon Moene <toon@moene.indiv.nluug.nl> wrote on 28/04/2007 20:45:17:

> Diego Novillo wrote:
> 
> > [ Jan, you are CC'd because there are a couple of questions for you
> > regarding cgraph and ipa ]
> > 
> > Razya Ladelsky wrote on 03/25/07 07:21:
> > 
> >>   Matrix flattening optimization tries to replace a N-dimernsional
> >>   matrix with its equivalent M-dimensional matrix, where M < N.
> > 
> > Thanks, looks interesting.  Any idea on how often this transformation
> > is useful (besides the obvious benchmarks)?  Should we enable this at
> > some -Ox?
> 
> What the Fortran community is most interested in is the following:
> 
>    Matrix Transposing
>    ==================
>    The idea of Matrix Transposing is organizing the matrix in a 
different
>    layout such that the dimensions are reordered.
>    This could produce better cache behaviour in some cases.
> 
>    For example, lets look at the matrix accesses in the following loop:
> 
>     for (i=0; i<N; i++)
>      for (j=0; j<M; j++)
>       access to a[i][j]
> 
>    This loop can produce good cache behavior because the elements of
>    the inner dimension are accessed sequentially.
> 
>    However, if the accesses of the matrix were of the following form:
> 
>    for (i=0; i<N; i++)
>     for (j=0; j<M; j++)
>       access to a[j][i]
> 
>    In this loop we iterate the columns and not the rows.
>    Therefore, replacing the rows and columns
>    would have had an organization with better (cache) locality.
>    Replacing the dimensions of the matrix is called matrix transposing.
> 
> Razya, does your patch does the right thing to reorder:
> 
>        SUBROUTINE SUB(A, B, N, M)
>        DIMENSION A(N, M), B(N, M)
>        DO I = 1, N
>           DO J = 1, M
>              A(I, J) = B(I, J)
>           ENDDO
>        ENDDO
>        END
> 
> Currently, it doesn't vectorize because the loops are not in the right 
> order.  Note that you don't have to "reorganize the matrix [layout]" to 
> get this right - just reorder the loops.
> 
> Thanks,
> 

Matrix transposing could be complementary to loop interchange, in a sense 
that it is not constrained by data dependencies, it can be applied to 
imperfectly nested loops and while loop transformations affect all the 
matrices 
referenced in the loop nest, matrix transformations do not.

However, currently transposing refers only to (dynamic) matrices,
multi dimensional at tree-ssa level, where fortran matrices are already 
one dimensional after front end phase. 
So Fortran matrices are not handled so far.

Razya

> -- 
> Toon Moene - e-mail: toon@moene.indiv.nluug.nl - phone: +31 346 214290
> Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
> At home: http://moene.indiv.nluug.nl/~toon/
> Who's working on GNU Fortran: 
> http://gcc.gnu.org/ml/gcc/2007-01/msg00059.html