Re: [Bug 15643] 'No' Progress within isl

[Johannes Doerfert]

Hi Tobias,

your right about the detected part of the kernel and the immense amount
of parameters involved (and their ranges).
Unfortunately, your proposed first solution [second 1)] is not working,
as this is exactly what I did when I encountered the delay in the first
place.
To be more precise, I specialized this kernel, thus instantiated nx and
ny with constants. That is also the reason I did not thought of the
problems [first 1) and 2)] before.

The other solutions you proposed are quite ambitious but especially the
first would (in my opinion) improve Polly significantly.
As a general emergency cord, and partial fix for this bug, I support the
idea of a bail out mechanism even if I'm not sure how to implement it.

Best regards,
Johannes

On 04/10/2013 01:24 PM, bugzill...@llvm.org wrote:
> http://llvm.org/bugs/show_bug.cgi?id=15643
>
> Tobias Grosser <gro...@fim.uni-passau.de> changed:
>
> What |Removed |Added
> ----------------------------------------------------------------------------
> CC| |gro...@fim.uni-passau.de
>
> --- Comment #2 from Tobias Grosser <gro...@fim.uni-passau.de> ---
> The kernel looks as follows (the 5x5 is similar)
>
> void apply_kernel_3x3(double* u, double* dx, double* dy, long nx, long ny) {
> long i,j;
> for (i = 1; i < nx - 1; i++) {
> for (j = 1; j < ny - 1; j++) {
>
> dx[i*ny+j] = u[(i-1)*ny+j-1] + 2 * u[(i-1)*ny+j] + u[(i-1)*ny+j+1];
> dx[i*ny+j] += - u[(i+1)*ny+j-1] - 2 * u[(i+1)*ny+j] - u[(i+1)*ny+j+1];
>
> dy[i*ny+j] = - u[(i-1)*ny+j-1] - 2 * u[(i)*ny+j-1] - u[(i+1)*ny+j-1];
> dy[i*ny+j] += u[(i-1)*ny+j+1] + 2 * u[(i)*ny+j+1] + u[(i+1)*ny+j+1];
>
> }
> }
> }
>
> Due to the linearized variable sized arrays we get expressions such as i * ny.
> Those expressions can not be expressed in the polyhedral model.
> As a result we only detect the j-loop as a SCoP and hide the i * ny style
> expressions in scop invariant parameters. This has two problems:
>
> 1) We do not detect the full kernel
>
> If we would understand the multi-dimensionality of the array references, we
> could detect the full kernel and could analyze it in detail
>
> 2) Large number of parameters causes slow downs
>
> Without delinearization we get a large number of independent parameters. With
> increasing dimensionality the number of parameters grows fast, such that even
> at 3D the dependence analysis becomes slow.
>
>
> There are several solutions:
>
> 1) Use fixed size arrays
>
> This makes the problem go away and allows us to fully optimize the kernel
>
> 2) Make Polly understand the multi-dimensionality of the arrays
>
> This needs some work in Polly, but it would be the optimal solution
> as we should both be fast and precise after detecting the multi-dimensionality.
>
> 3) Fix the slow analysis
>
> We should find a way to either do our analysis fast or just bail out when we
> realize we can not do anything useful here.
>
> Cheers,
> Tobias
>

[Tobias Grosser]

On 04/10/2013 04:54 PM, Johannes Doerfert wrote:
> Hi Tobias,
>
> your right about the detected part of the kernel and the immense amount
> of parameters involved (and their ranges).
> Unfortunately, your proposed first solution [second 1)] is not working,
> as this is exactly what I did when I encountered the delay in the first
> place.
> To be more precise, I specialized this kernel, thus instantiated nx and
> ny with constants. That is also the reason I did not thought of the
> problems [first 1) and 2)] before.
>
> The other solutions you proposed are quite ambitious but especially the
> first would (in my opinion) improve Polly significantly.
> As a general emergency cord, and partial fix for this bug, I support the
> idea of a bail out mechanism even if I'm not sure how to implement it.

I have now the feeling the best way to handle this immediately is to
handle scevs of the form {<expr>, +, <param>}_<loop> as if they have
been written <expr> + {0, +, <param>}. This should significantly reduce
the number of parameters involved.

Tobias