[PPL-devel] integer versus rational solutions

[Tobias Grosser]

On Fri, 2009-07-10 at 17:23 +0200, Albert Cohen wrote:
> Thank you Roberto for the long and detailed email.
> 
> Indeed, we should keep in mind to always ask on the ppl mailing list 
> early on.
> 
> Regarding the need to solve integer programming problems, my view is 
> twofold:
> 1. For the case of Array Dataflow Analysis, it is critical to have a 
> parametric integer linear programming solver, in the form of the 
> evolution of PIP you are working on. We can leave without it for early 
> experiments, but it will be needed for any scalable (and precise) analysis.
> 2. For plain dependence analysis and testing (the problem that triggered 
> the whole thread), it is certainly not critical. It would of course 
> improve precision, but the problems raised by Konrad and Li were due to 
> a wrong design that was re-analysing the polyhedral representation AFTER 
> strip-mining of loops, itself responsible for the introduction of large 
> constants. Konrad is updating the dependence analysis and the 
> strip-minig API such that this won't be necessary anymore.

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.

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?

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?

Thanks

Tobi