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