[PPL-devel] integer versus rational solutions

[Tobias Grosser]

On Mon, 2009-07-13 at 12:07 +0200, Albert Cohen wrote:
> Tobias Grosser wrote:
> > On Fri, 2009-07-10 at 23:57 +0200, Albert Cohen wrote:
> >> Hi Tobias.
> >>
> >> Tobias Grosser wrote:
> >>> Stop. Do I understand this correctly. You do not want to check
> >>> dependencies after strip mining? I am very concerned about that, as one
> >>> of the benefits of working on the polytop model I thought is, that we
> >>> can schedule transformations in an arbitrary order. So it is required to
> >>> to reanalyze strip mined loops. This is also necessary for the
> >>> dependency checking we use for autopar.
> >> As presented in Austin in November, it is much preferable to follow the 
> >> transformation composition approach of Girbal and Vasilache that does 
> >> not require intermediate steps of dependence analysis and legality checking.
> > 
> > You are referring to "Facilitating the search for compositions of
> > program transformations"?
> 
> Yes. The 2d+1 encoding and the additional invariants/rules allow to 
> compose and generalize classical transformations to a polyhedral 
> representation that may have diverged arbitrarily far from the original 
> syntax tree.

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.
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.


> 
>  > (...)
> 
> >> Konrad is working on Step 2.1 (enhancing strip-mine to update the 
> >> dependence info). Then, if you agree, he will help restructure the API 
> >> such a that dependence computation and dependence checking are ALWAYS 
> >> called explicitely, rather than implicitely in the transformation 
> >> primitives.
> > 
> > Sure. I would like us to be even able to call them after any single
> > transformation.
> > 
> > A loop like would be nice for the optimizations.
> > 
> > while (select_and_apply_transform (scop)) {
> > 	check_dependencies();
> > }
> 
> Yes. Skipping some checks require stronger technology to guarantee that 
> transformation steps will be legal or will eventually be legal/checked, 
> or even corrected/completed via enabling transformations (see 
> Vasilache's PACT'07 paper).
> 
> As a concrete, more original example: together with Razya and Konrad, we 
> are thinking about enabling parloops and interchange with an automatic 
> privatization "corrective step". We would ignore memory-based 
> dependences when looking for interchange combinations that improve both 
> parloops and autovect (using an extended cost model), then check which 
> ones were eventually violated in the selected transformation sequence, 
> and eventually privatize only those scalars/arrays that need to be 
> privatized to effectively remove those memory-based dependences.

That sounds interesting. We also thought about memory optimizations, so
I would like the poly_drs to not be read only, but read/write. This
means that we can analyze the data accesses on the polyhedral model,
change them in the polyhedral data accesses and graphite will take care
of creating the required GIMPLE code.

This should allow a lot of nice optimizations, like reduce memory
footprint if only a part of an array is written to or allow more
parallelism by trading memory for less dependencies.


> > I know this will be expensive and we want to disable this in the
> > production compiler. But I want us to be able to use this loop for
> > debugging.
> 
> Sure.
> 
> > I totally agree that it is useful to avoid polyhedral computations, as
> > they tend to be expensive. However I still want to be able to do CHECK
> > and ANALYSIS at every single step, as it will show us assumptions that
> > we took to optimize compile time.
> > If we take any assumptions (that might be necessary), I would like them
> > to not be hidden by avoiding dependency ANALYSIS, but I want our
> > (nightly) test to fail.
>  >
> > This will allow a analysis/discussion of the assumptions we took. Maybe
> > we can avoid them, if not we know we have to document them. Every
> > assumption has to be written down at a well known place so that future
> > developers will not be surprised.
> 
> OK. But running the ANALYSIS itself after transformation makes little 
> sense to me, even in debugging mode. Can you explain why?

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.

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.

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, ...).

> >>> Another thing I do not understand is that you are often referring to
> >>> "large constants". I thought complexity problems mainly appear because
> >>> of a high number of dimensions, but not because of high values in a
> >>> (in)equality. Can you explain this to me?
> >> As mentioned several times, big constants tend to break the "structure" 
> >> of ILP problems or other polyhedral operations, leading to combinatorial 
> >> explosions. This is well known even in the case of simple algorithms 
> >> like Fourier Motzkin. They also increase the risk of memory overflow.
> > 
> > OK. I definitely believe you, but as this seems to become one of the
> > important points for Graphite performance I would like to understand
> > this well. Maybe we can also write a Wiki page to explain which
> > constructs should be avoided. We already learned NNC_Polyhedron are bad,
> > but what else is dangerous.
> > 
> > Here I am still not getting the problem. I looked again into Fourier
> > Motzkin and on the first look I could not find anything in it's
> > complexity depending on the values of the dimensions of the
> > (in)equalities. Any pointer or example that might help me understanding
> > this problem would be really helpful.
> 
> FM blows away when it generates too many inequalities. To avoid this, 
> people generally favor eliminations that generate 0 or 1 inequality, first.

Sure. I understand that the number of dimensions and/or (in)equalities
is a limitation. What I do not understand is why the values in an
(in)equality are problematic. This is why 

1 > i might be easier to handle than 99999999 > i

Or did I get you wrong and you did not say anything about this?

> >> Eventually, the bigger the constant the higher the loss of information 
> >> when relaxing to rational polyhedra.
> > 
> > OK. However when we do not put the additional restrictions the
> > information would never have been available. Or are we loosing other
> > information because of putting additional restrictions?
> 
> Sorry, I missed that part. Can you re-explain?

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.

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.

> >> All of this is very informal/intuitive of course. There are some/few 
> >> theoretical results about this, but Roberto and other experts are better 
> >> placed than myself to answer it!
> > 
> > @Roberto:
> > Can you give us some hints, what is really expensive and what should we
> > avoid when constructing polyhedrons in the PPL?
> > 
> > Tobi
>