[PPL-devel] integer versus rational solutions

[Albert Cohen]

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.

I hope the problems raised on this thread will disappear (for now) when 
this is fixed.

Thanks,
Albert

Roberto Bagnara wrote:
> 
> Konrad Trifunovic wrote:
>> indeed, when changed to C_Polyhedron this example was solved quickly.
>> It made me think that changing all the polyhedrons to C_Polyhedron would
>> solve the problems, unfortunately I have found some other examples 
>> that take
>> a long time, even when being expressed as C_Polyhedrons. Stay tuned, I 
>> will send
>> an examples.
> 
> Hi All.
> 
> I propose we start from the very beginning.
> 
> The first thing I would like to do is to solve the communication problem.
> There must be a communication problem because it is only by chance that
> I discovered gcc-graphite at googlegroups.com and that, on it, people
> was discussing about problems they have with the PPL.  The same happened
> already at least a couple of times on the gcc mailing lists: people had
> troubles using the PPL and they did not mail ppl-devel at cs.unipr.it.
> However, we made it very clear that we have a 100% determination to support
> all our users, GCC and Graphite in particular.  So, please, do talk with
> us as soon as what appears to be a problem shows up.  Even better: please
> let us know in advance what you plan to do with the PPL and how.  Believe
> me: we can help.
> 
> Now, the complexity problems.  I am not sure I understand what you are 
> trying
> to accomplish, but it seems to me that you call for the solution of 
> (pure or
> mixed) integer programming problems.  As integer programming is NP-complete
> (and very tough also in practical terms), there is no way you can obtain
> efficiency _unless_ the problems you are trying to solve have a peculiar
> structure and you use algorithms that are able to exploit it.  Concerning
> the PPL, MIP problems are solved using a textbook implementation of
> branch-and-bound, which, in turn, uses a textbook implementation of primal
> simplex.  Branch-and-bound is not even guaranteed to terminate and can
> generate zillions of subproblems.  So the only sensible way to use it is
> by either:
> 
> a) ensuring the problem is small enough and solvable by branch-and-bound;
>    and/or
> 
> b) guarding the computation with a time threshold and a memory threshold
>    (the PPL provides support for both).
> 
> A possibility to obtain a better performance would be to use the PPL/GLPK
> interface.  This is already available in the `simplex' branch of the main
> PPL Git repository.  The reason we do not merge this with `master' is that
> until now we failed to convince the GLPK people to move the bignum simplex
> interface to the installed glpk.h: that interface is currently only 
> available
> by using an header file that is not installed.  Note that this would not
> substantially transform your problem: you will have to set time/memory
> threshold anyway.
> All the best,
> 
>    Roberto
> 
> P.S. Concerning point (b) above, we are installing in the main Git 
> repository
>      mechanisms to impose (deterministic) limits to the computation 
> performed
>      by expensive PPL computation (including those that take place in 
> MIP_Problem).
> 
> P.S. I have checked that the issue I mentioned witth respect to GLPK is 
> still
>      present in the latest version (4.38).  There was also another issue 
> with it,
>      but I have no time right now to check if this is still present: even
>      in the bignum simplex solver, GLPK was making unsafe approximations
>      in order to keep the coefficients small.  Perhaps this is no longer
>      the case.
>