[PPL-devel] integer versus rational solutions

[Albert Cohen]

Tobias Grosser wrote:
> Sure. The same with the polyhedral representation in Graphite. It also
> should allow us to compose and generalize arbitrary transformations on
> the polyhedral data structures.
> 
> However I do not remember that we specified any 2d+1 encoding in our
> data structures. So at the moment we are more general, and as you might
> remember from early discussions it is very important for me to keep this
> until we have a discussion where we agree to trade of generality for
> performance.

Yes, this is a good thing to do. We should keep this generality as much 
as possible. Some part of the API may require stronger assumtions, however.

> Ideally we would have an example, a compile time problem and a
> discussion where we agree that adding a assumption like 2d+1 will
> improve algorithmic complexity and that this improvement is required in
> real world code.
> This information should than be part of graphite-poly.h.

It is probably best to limit the assumption/restriction to a subset of 
the API, and to document it in the header files.

> Sure. The idea I have of Graphite is that we have a set of
> transformations that all analyze GPOLY and try to improve it.
> However improve does not go only in one direction. For example there
> might be passes trading dependencies for memory usage, that improve
> memory usage, but add dependencies or remove dependencies and add memory
> usage.

Yes, like the expansion/contraction tradeoff.

> I would like to have a clever scheduler (or some database) deciding
> which passes should be applied. E.g. first we trade some memory for less
> dependencies, than we try to expose more parallelism, maybe do some
> interchange to enable fusion and fission, and finally parallelize all
> the stuff.
> 
> To allow this free ordering we have to ensure, that every pass is able
> to analyze GPOLY to see if it can apply e.g. interchange. So e.g. after
> strip mining it might still be useful to do some more transformations to
> allow vectorization. If the vectorization pass can not analyze the GPOLY
> after strip mining is applied this will not work.

This is a good argument.

> So what I want is:
> 
> 1. We have one representation GPOLY where we do our optimizations on
> 2. Every optimization pass works only on GPOLY
> 2.1 Every pass has to be able to read GPOLY and to generate GPOLY
> 2.2 Every pass has to decide only by looking and analyzing GPOLY if it
> can be applied.
> 3. Optimizing a program is applying a lot of PASSES on GPOLY to generate
> better scattering and/or better data accesses.
> 4. Graphite will read GPOLY and following the description in GPOLY
> generate the GIMPLE code.
> 
> It might be possible that this will not work or is to slow. If there is
> a limitation in GPOLY the solution I see is to extend GPOLY officially
> (e.g. to handle arbitrary conditions, allow changing the data
> accesses, ...).

Sounds good.

Of course, analyzing GPOLY does not necessarily imply recomputing the 
dependence polyhedra.

But I agree it should always be possible to re-analyze dependence polyhedra.

Without an exact Z-polyhedral enveloppe, we'll never guarantee that we 
do not lose key information...

Unfortunately, stripmining will ALWAYS be one of the worst 
transformations in terms of information loss on a rational enveloppe. 
Whatever the encoding you can think of. The only workaround is to delay 
it as much as possible. For example, Pluto does not effectively 
strip-mine until all the heuristic transformation (finding hyperplanes 
and fusion/distribution options) is complete.

Parametric tiling approaches remove strip-mining from the polyhedral 
representation altogether, but they have limitations, see Renganarayanan 
et al. (multidimensional tiling for the price of one, PLDI'07, SC'07) 
and Hartono et al. (ICS'09). We can discuss it later, this is still too 
incomplete.

> I thought the mail I was referring to is that we put restrictions on
> parameters in the context of CLooG. As we know that a parameter "k" is
> of type unsigned integer we know it the constraint 0 <= k <= MAX_INT is
> always true. By adding this constraint to the context we allow CLooG to
> remove some conditions, as the generated code assume that k will be in
> this limits.

This should be quite good in general: MAX_INT kind of constants only 
occur as the affine constant part, not as coefficient of variables. They 
allow to cut branches in complex unions of polyhedra and simplify the 
computation, without adding overhead or information loss. If those 
constants occur as coefficients, like for the strip-mining case, it 
hurts a lot (performancewise and precisionwise).

> If I got your comments right, you warned that adding large constants
> like MAX_INT might be bad for compile time performance. That is
> something I did not understand and as adding the constraint to the
> context improves the code generated by CLooG, I would like to keep
> adding these constraints as long as compile time allows.

Albert