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