Graphite: Collapsing of loop nests ?

Graphite: Collapsing of loop nests ?

[Toon Moene]

I wonder if Graphite can do this one (or is planned to be able to):

Another loop optimization that suggests itself
is the following, trying to eliminate unnecessary
loop constructs:
\begin{verbatim}
       SUBROUTINE SUB(A, B, C, N, M)
       REAL A(N, M), B(N, M), C(N, M)
       DO J = 1, M
          DO I = 1, N
             C(I, J) = A(I, J) + B(I, J)
          ENDDO
       ENDDO
       END
\end{verbatim}
If we could generate code that looks like what is
written below, we would have nothing but
{\em one} loop.
\begin{verbatim}
       DO K = 1, M*N
          C(K, 1) = A(K, 1) + B(K, 1)
       ENDDO
\end{verbatim}
In this case, this transformation can be done
because the tuple $(i,j)$ forms an induction
variable $i+n*(j-1)$ in its own right
(replaced by $k$ in the {\em collapsed} loop).

This is the latex from a set of slides I used in my LinuxExpo '99 talk 
(22nd of May 1999).

These loop nests result quite naturally from whole array expressions in 
Fortran.

Cheers,

-- 
Toon Moene - e-mail: toon@moene.org - phone: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
At home: http://moene.org/~toon/
Progress of GNU Fortran: http://gcc.gnu.org/gcc-4.5/changes.html

Re: Graphite: Collapsing of loop nests ?

[Sebastian Pop]

On Fri, Dec 4, 2009 at 09:41, Toon Moene <toon@moene.org> wrote:
> I wonder if Graphite can do this one (or is planned to be able to):
>
> Another loop optimization that suggests itself
> is the following, trying to eliminate unnecessary
> loop constructs:
> \begin{verbatim}
>      SUBROUTINE SUB(A, B, C, N, M)
>      REAL A(N, M), B(N, M), C(N, M)
>      DO J = 1, M
>         DO I = 1, N
>            C(I, J) = A(I, J) + B(I, J)
>         ENDDO
>      ENDDO
>      END
> \end{verbatim}
> If we could generate code that looks like what is
> written below, we would have nothing but
> {\em one} loop.
> \begin{verbatim}
>      DO K = 1, M*N
>         C(K, 1) = A(K, 1) + B(K, 1)
>      ENDDO
> \end{verbatim}
> In this case, this transformation can be done
> because the tuple $(i,j)$ forms an induction
> variable $i+n*(j-1)$ in its own right
> (replaced by $k$ in the {\em collapsed} loop).

For the moment Graphite wouldn't do this kind of transform.  But I think
that this could be done: CLooG should generate the following code if we
ask it to collapse the two loops:

DO K = 1, M*N
 I = K mod N
 J = K / N
 C(I, J) = A(I, J) + B(I, J)
ENDDO

And then one would have to cleanup the scalar arithmetic to have
linearized array accesses, and that should already be done by GCC in
the lowering of memory accesses.

Now a question for Cedric: how would you ask CLooG to generate this
collapsed loop?

Thanks,
Sebastian

Re: Graphite: Collapsing of loop nests ?

[Tobias Grosser]

On Fri, 2009-12-04 at 10:29 -0600, Sebastian Pop wrote:
> On Fri, Dec 4, 2009 at 09:41, Toon Moene <toon@moene.org> wrote:
> > I wonder if Graphite can do this one (or is planned to be able to):
> >
> > Another loop optimization that suggests itself
> > is the following, trying to eliminate unnecessary
> > loop constructs:
> > \begin{verbatim}
> >      SUBROUTINE SUB(A, B, C, N, M)
> >      REAL A(N, M), B(N, M), C(N, M)
> >      DO J = 1, M
> >         DO I = 1, N
> >            C(I, J) = A(I, J) + B(I, J)
> >         ENDDO
> >      ENDDO
> >      END
> > \end{verbatim}
> > If we could generate code that looks like what is
> > written below, we would have nothing but
> > {\em one} loop.
> > \begin{verbatim}
> >      DO K = 1, M*N
> >         C(K, 1) = A(K, 1) + B(K, 1)
> >      ENDDO
> > \end{verbatim}
> > In this case, this transformation can be done
> > because the tuple $(i,j)$ forms an induction
> > variable $i+n*(j-1)$ in its own right
> > (replaced by $k$ in the {\em collapsed} loop).
> 
> For the moment Graphite wouldn't do this kind of transform.  But I think
> that this could be done: CLooG should generate the following code if we
> ask it to collapse the two loops:
> 
> DO K = 1, M*N
>  I = K mod N
>  J = K / N
>  C(I, J) = A(I, J) + B(I, J)
> ENDDO
> 
> And then one would have to cleanup the scalar arithmetic to have
> linearized array accesses, and that should already be done by GCC in
> the lowering of memory accesses.
> 
> Now a question for Cedric: how would you ask CLooG to generate this
> collapsed loop?

I do not believe this is already possible for arbitrary N.

You would have to write a scattering function like this

s0 = i+n*(j-1)

What is

s= i + n*j - n
       ^^^  Here is a product that is not affine linear.

There are extensions to the polytop model to make this possible, but
they are not close to be production ready. Just recently I Armin
Groesslinger gave a nice talk about this topic. If you want I can look
for his work describing solutions.

Tobi

Re: Graphite: Collapsing of loop nests ?

[Cédric Bastoul]

I see no way to do this with affine scattering. We would need
polynomial functions like Armin Grosslinger is doing, see
http://www.infosun.fim.uni-passau.de/cl/publications/docs/MIP-0803.pdf
but I think that's too slow at the moment...

On Fri, Dec 4, 2009 at 11:29 AM, Sebastian Pop <sebpop@gmail.com> wrote:
> On Fri, Dec 4, 2009 at 09:41, Toon Moene <toon@moene.org> wrote:
>> I wonder if Graphite can do this one (or is planned to be able to):
>>
>> Another loop optimization that suggests itself
>> is the following, trying to eliminate unnecessary
>> loop constructs:
>> \begin{verbatim}
>>      SUBROUTINE SUB(A, B, C, N, M)
>>      REAL A(N, M), B(N, M), C(N, M)
>>      DO J = 1, M
>>         DO I = 1, N
>>            C(I, J) = A(I, J) + B(I, J)
>>         ENDDO
>>      ENDDO
>>      END
>> \end{verbatim}
>> If we could generate code that looks like what is
>> written below, we would have nothing but
>> {\em one} loop.
>> \begin{verbatim}
>>      DO K = 1, M*N
>>         C(K, 1) = A(K, 1) + B(K, 1)
>>      ENDDO
>> \end{verbatim}
>> In this case, this transformation can be done
>> because the tuple $(i,j)$ forms an induction
>> variable $i+n*(j-1)$ in its own right
>> (replaced by $k$ in the {\em collapsed} loop).
>
> For the moment Graphite wouldn't do this kind of transform.  But I think
> that this could be done: CLooG should generate the following code if we
> ask it to collapse the two loops:
>
> DO K = 1, M*N
>  I = K mod N
>  J = K / N
>  C(I, J) = A(I, J) + B(I, J)
> ENDDO
>
> And then one would have to cleanup the scalar arithmetic to have
> linearized array accesses, and that should already be done by GCC in
> the lowering of memory accesses.
>
> Now a question for Cedric: how would you ask CLooG to generate this
> collapsed loop?
>
> Thanks,
> Sebastian
>

Re: Graphite: Collapsing of loop nests ?

[Sebastian Pop]

On Fri, Dec 4, 2009 at 10:39, Tobias Grosser <grosser@fim.uni-passau.de> wrote:
> I do not believe this is already possible for arbitrary N.
>
> You would have to write a scattering function like this
>
> s0 = i+n*(j-1)
>
> What is
>
> s= i + n*j - n
>       ^^^  Here is a product that is not affine linear.

Yes this is affine linear, but not representable in the current way we
deal with parameters in the polyhedral model...  Note that constant
times IV would be allowed, and yes parameters are named constants.

> There are extensions to the polytop model to make this possible, but
> they are not close to be production ready.

I think that we should revisit this independently of general solutions.

> Just recently I Armin Groesslinger gave a nice talk about this
> topic. If you want I can look for his work describing solutions.

I also have discussed with Armin when I was visiting INRIA earlier
this year, and I know what he's working on.

Sebastian

Re: Graphite: Collapsing of loop nests ?

[Sebastian Pop]

On Fri, Dec 4, 2009 at 10:44, Cédric Bastoul <cedric.bastoul@inria.fr> wrote:
> I see no way to do this with affine scattering. We would need
> polynomial functions like Armin Grosslinger is doing, see
> http://www.infosun.fim.uni-passau.de/cl/publications/docs/MIP-0803.pdf
> but I think that's too slow at the moment...

I think that this is only needed to address expressions of the form IV times IV,
and not for parameter times IV.

Sebastian

Re: Graphite: Collapsing of loop nests ?

[Cédric Bastoul]

On Fri, Dec 4, 2009 at 11:50 AM, Sebastian Pop <sebpop@gmail.com> wrote:
> On Fri, Dec 4, 2009 at 10:39, Tobias Grosser <grosser@fim.uni-passau.de> wrote:
>> I do not believe this is already possible for arbitrary N.
>>
>> You would have to write a scattering function like this
>>
>> s0 = i+n*(j-1)
>>
>> What is
>>
>> s= i + n*j - n
>>       ^^^  Here is a product that is not affine linear.
>
> Yes this is affine linear, but not representable in the current way we
> deal with parameters in the polyhedral model...  Note that constant
> times IV would be allowed, and yes parameters are named constants.

We usually call this case (parameter times IV) "fully parametric".
Armin Grosslinger looked at it before finding a more general solution,
it's not easy and typically it leads to a massive versioning :-/...

>> There are extensions to the polytop model to make this possible, but
>> they are not close to be production ready.
>
> I think that we should revisit this independently of general solutions.
>
>> Just recently I Armin Groesslinger gave a nice talk about this
>> topic. If you want I can look for his work describing solutions.
>
> I also have discussed with Armin when I was visiting INRIA earlier
> this year, and I know what he's working on.
>
> Sebastian
>

Re: Graphite: Collapsing of loop nests ?

[Tobias Grosser]

On Fri, 2009-12-04 at 10:50 -0600, Sebastian Pop wrote:
> On Fri, Dec 4, 2009 at 10:39, Tobias Grosser <grosser@fim.uni-passau.de> wrote:
> > I do not believe this is already possible for arbitrary N.
> >
> > You would have to write a scattering function like this
> >
> > s0 = i+n*(j-1)
> >
> > What is
> >
> > s= i + n*j - n
> >       ^^^  Here is a product that is not affine linear.
> 
> Yes this is affine linear, but not representable in the current way we
> deal with parameters in the polyhedral model...  Note that constant
> times IV would be allowed, and yes parameters are named constants.

However at the moment we represent parameters as variables that tend to
be constant. So as you said that will not work. Probably there is some
way to regenerate the loops from scratch based on analysing the memory
dependencies, as in this case such a complicated scattering is probably
not required. But this case is definitely not that easy to solve.

> > There are extensions to the polytop model to make this possible, but
> > they are not close to be production ready.
> 
> I think that we should revisit this independently of general solutions.
> 
> > Just recently I Armin Groesslinger gave a nice talk about this
> > topic. If you want I can look for his work describing solutions.
> 
> I also have discussed with Armin when I was visiting INRIA earlier
> this year, and I know what he's working on.
> 
> Sebastian

Re: Graphite: Collapsing of loop nests ?

[Sebastian Pop]

On Fri, Dec 4, 2009 at 11:08, Cédric Bastoul <cedric.bastoul@inria.fr> wrote:
> We usually call this case (parameter times IV) "fully parametric".
> Armin Grosslinger looked at it before finding a more general solution,

I don't want the more general solution: IV * IV doesn't commonly
happen, but parameter * IV does, and ought to be handled separately.

> it's not easy and typically it leads to a massive versioning :-/...

In which cases do you see versioning?  Do you have a paper that
describes the problems you are speaking about?

Sebastian

Re: Graphite: Collapsing of loop nests ?

[Cédric Bastoul]

On Fri, Dec 4, 2009 at 1:20 PM, Sebastian Pop <sebpop@gmail.com> wrote:
> On Fri, Dec 4, 2009 at 11:08, Cédric Bastoul <cedric.bastoul@inria.fr> wrote:
>> We usually call this case (parameter times IV) "fully parametric".
>> Armin Grosslinger looked at it before finding a more general solution,
>
> I don't want the more general solution: IV * IV doesn't commonly
> happen, but parameter * IV does, and ought to be handled separately.
>
>> it's not easy and typically it leads to a massive versioning :-/...
>
> In which cases do you see versioning?  Do you have a paper that
> describes the problems you are speaking about?

No, it's based on my old knowledge of the first implementation by
Armin. AFAIR the trick was to rely on a fully parametric
Fourier-Motzkin elimination that could explode but worked in practice.
I think the best way is to let Armin enter the loop and let him
explain how we could handle the fully parametric case. He's clearly
the specialist of the question. Armin, did you write any report on
supporting the fully parametric case for code generation ? Here is one
specific case we would like to support :

[Anyway, extending CLooG to support this would *not* be trivial :-/]

On Fri, Dec 4, 2009 at 11:29 AM, Sebastian Pop <sebpop@gmail.com> wrote:
> On Fri, Dec 4, 2009 at 09:41, Toon Moene <toon@moene.org> wrote:
>> I wonder if Graphite can do this one (or is planned to be able to):
>>
>> Another loop optimization that suggests itself
>> is the following, trying to eliminate unnecessary
>> loop constructs:
>> \begin{verbatim}
>>      SUBROUTINE SUB(A, B, C, N, M)
>>      REAL A(N, M), B(N, M), C(N, M)
>>      DO J = 1, M
>>         DO I = 1, N
>>            C(I, J) = A(I, J) + B(I, J)
>>         ENDDO
>>      ENDDO
>>      END
>> \end{verbatim}
>> If we could generate code that looks like what is
>> written below, we would have nothing but
>> {\em one} loop.
>> \begin{verbatim}
>>      DO K = 1, M*N
>>         C(K, 1) = A(K, 1) + B(K, 1)
>>      ENDDO
>> \end{verbatim}
>> In this case, this transformation can be done
>> because the tuple $(i,j)$ forms an induction
>> variable $i+n*(j-1)$ in its own right
>> (replaced by $k$ in the {\em collapsed} loop).
>
> For the moment Graphite wouldn't do this kind of transform.  But I think
> that this could be done: CLooG should generate the following code if we
> ask it to collapse the two loops:
>
> DO K = 1, M*N
>  I = K mod N
>  J = K / N
>  C(I, J) = A(I, J) + B(I, J)
> ENDDO
>
> And then one would have to cleanup the scalar arithmetic to have
> linearized array accesses, and that should already be done by GCC in
> the lowering of memory accesses.
>
> Now a question for Cedric: how would you ask CLooG to generate this
> collapsed loop?
>
> Thanks,
> Sebastian
>

Re: Graphite: Collapsing of loop nests ?

[Armin Größlinger]

Hi,

I tried the "m*n example" with my prototype code generator for fully
parametric domains (which is not publicly available, yet) - sorry for
the delayed reply.

To be precise, the input is the iteration domain
  0 <= j <= m-1
  0 <= i <= n-1
for iterators j,i and scattering
  k = j + m*i

(I based the domains at 0 (instead of 1) for easier analysis of the output.)

As has been said in the discussion, the desired code for this input is

      for (k=0; k<=n*m-1; k++) {
        j = k%m;
        i = k/m;
        S1(j,i);
      }

but we are not getting this code (yet?). Here are my observations. My
prototype code generator for fully parametric input generates the
following code (for the general case, I'm omitting the case distinctions
and code for special cases like m=1 etc.):

      for (k=0; k<=n*m-1; k++) {
        for (j=max(0,k+(-n+1)*m); j<=min(k,m-1); j++) {
          for (i=ceild(k-j,m); i<=floord(k-j,m); i++) {
            S1(j,i);
          }
        }
      }

This is obviously sub-optimal as the loop on j tries every value for j
between 0 and m-1 and then the loop on i checks whether k-j is a
multiple of m. To get a more reasonable code, we would have to infer
from the condition in the loop on i (that m must divide k-j) that the
loop on j should be executed with a stride of m (starting at a suitable
value for j). From there, using the bounds of the loop on j, we could
infer that the loop on j has only one iteration, leading to  j = k%m,
i = (k-j)/m. Finally (by using the bounds on j again), we could infer
that  i=k/m.

This required reasoning relies on the properties of integers and is, of
course, more difficult in the parametric case. I tried to run the
example with m=9 through cloog-isl and what I got is

      for (k=0;k<=9*n-1;k++) {
        for (j=max(0,k-9*n+9);j<=min(8,k);j++) {
          if ((k+8*j)%9 == 0) {
            S1(j,(k-j)/9);
          }
        }
      }

so cloog-isl does not seem to perform the required reasoning, either.
(Or did I miss a switch to turn this on?)

With cloog-isl, the situation is much better if the loop on j becomes
the innermost loop (i.e., j and i are exchanged):

      for (k=0;k<=9*n-1;k++) {
        i = floord(k,9);
        S1(i,k-9*i);
      }

My prototype for the fully parametric case does not fully profit from
the exchange of the inner loops and generates

      for (k=0; k<=n*m-1; k++) {
        for (i=max(0,ceild(k-m+1,m)); i<=min(floord(k,m),n-1); i++) {
          for (j=max(k-m*i,0); j<=min(k-m*i,m-1); j++) {
            S1(i,j);
          }
        }
      }

which shows the "integer" problem that it does optimize the loop bounds
sufficiently. For example, it does not recognize that in the upper bound
of i, floord(k,m) is always less than or equal to n-1 (it fails because
it only checks k/m vs. n-1 but in the rationals k/m can be greater than
n-1). Therefore, it misses the chance to detect that i = floord(k,m) etc.

So, there are obviously some "integer" challenges to generating the good
code desired in this example. At the moment, I'm thinking about which
tests/heuristics to implement in my prototype to take advantage/care of
integrality.

Thanks for this "food for thought"!

Regards,
Armin