[PPL-devel] integer versus rational solutions

[Albert Cohen]

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.

In this framework, the typical/ideal flow of transformation construction 
is the following:

1. Compute dependence relations for all pairs and store it persistently.

2. Select a primitive transformation and apply it to the polyhedral 
representation.
   2.1. If the transformation involved strip-mining, update the 
dependence information such that all the polyhedra associated with the 
strip-mined statements get one extra "time column" filled only with 
zeroes; you may check that this is correct and strictly equivalent to 
recomputing dependence information in the case of the isolated 
application of strip-mining (not composed with other transformations) 
and of an exact integral polyhedral computation.

3. If the transformation computed so far is not good enough, compose 
with another one by iterating to step 2. For example, start with 
strip-mining, then interchange, to achieve tiling. Of course, much more 
complex schemes should be crafted later on.

4. When you are sick of composing more and more primitive 
transformations into a big complex one, check the legality of the result 
by comparing the transformed schedule with the stored dependence 
relations (updated through the strip-mining steps).

Of course, Step 2 should be a little careful to select only 
transformations that will not cause trouble later in step 4. A simple 
way is to add a Step 2.2 that checks for legality after transforming the 
schedule, and backtracks if it fails, attempting another transformation 
selection.

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.

If you do not agree or fully understand the motivations for this scheme, 
I'm happy to discuss it further, but I'll be barely available next week 
due to an overload of paper deadlines and the ACACES summer school of 
the HiPEAC network (where I would gladly invite you to apply, for next 
year :-)).

> It would be nice to read a post about what assumptions/solutions you
> want to take to make sure this complexity problems will not appear
> again. Do they limit our ability to run optimizations after we strip
> mined a loop?

No, as explained above, we only want to avoid running dependence 
ANALYSIS after applying transformations. Running dependence CHECK for 
legality should be fine, although for compilation time reasons it is 
better to avoid it whenever possible (other concrete algorithms exist to 
correct transformations, complement transformations, or constrain 
transformations to span only legal points, but we can look at this later).

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

Eventually, the bigger the constant the higher the loss of information 
when relaxing to rational polyhedra.

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!

Thanks,
Albert