[PPL-devel] PPL and polyhedra comparisons

[Enea Zaffanella]

Sebastian Pop wrote:
> On Sat, Aug 23, 2008 at 5:48 AM, Enea Zaffanella <zaffanella at cs.unipr.it> wrote:
>> In the current sources of cloog_ppl, we have the following:
>>
>> static int
>> cloog_domain_polyhedron_compare (CloogMatrix *m1, CloogMatrix *m2,
>>                                 int level, int nb_par, int dimension)
>>
>> I can guess (please correct me if I am wrong) that:
>>
>>  a) `m1' and `m2' are the constraints describing polyhedra p1 and p2;
>>
>>  b) the two polyhedra have space dimension `dimension';
>>
>>  c) `nb_par' should be the number of parameters and it must satisfy the
>> precondition 0 <= nb_par <= dimension;
>>
>>  d) `level' seems to identify a dimension of the polyhedron and, according
>> to a comment to the corresponding code in polylib, it must satisfy the
>> precondition
>>      1 <= level <= dimension
>> However, from the way it is used, it seems to me (but I am not sure about
>> it) that it should also satisfy the stronger precondition
>>      1 <= level <= dimension - nb_par
>> (as a side note, this stronger property would imply dimension > 0).
>>
> 
> Yes, all this is correct.
> 
>> Now, looking at the code for the cloog function above I see this formal
>> parameter `level' playing a non-trivial role, so that it seems strange to me
>> that it is not mentioned at all in the comment quoted by Roberto.
>>
>> Can you please clarify its meaning?
>>
> 
> A little more detail of what nb_par and level are: nb_par represents
> the number of variables that are not known at compile time but that do
> not vary in the loop nest that is considered.  For example, parameters
> can be loop bounds.  The first dimensions in a polyhedron represent
> iteration domains: 1 <= level <= dimension - nb_par, and level is one
> of these loop iterators.  Polyhedra are sorted following the value of
> their constraints in dimension "level".
> 
>> Note that any strengthening of the preconditions above
>> (e.g., replacing a non-strict inequality <= by a strict inequality <)
>> will be really helpful.
> 
> Remember that in PolyLib format, the first column of a constraint
> matrix represents the {eq, ineq} boolean for the row.  In PPL format:
> 0 <= level < dimension - nb_par
> dimension - nb_par <= parameter < dimension
> 
> Does this help?
> 
> Sebastian

Yes, thanks, this was useful to help me understand the implementation.

This functionality is indeed ad-hoc for your purposes:
it assumes some very specific meaning for the space dimensions,
hence it is difficult to provide it with a *clean* specification.

I doubt its inclusion in the PPL would be a good thing.

On the other hand, having worked on it, I can fairly say that such an 
inclusion in the PPL would not buy much in terms of efficiency:
all the potential efficiency improvements that I spot when looking at 
your code are indeed available through the current PPL public interface.
See the attached file: it is C++ (due to my own taste), but it shouldn't 
be difficult to convert it so as to use the C interface of the library.

The main improvements wrt your version are the following:

(1) Before computing the intersection polyhedron q, you first throw away 
all constraints on the non-parameter variables having index >= level-1.
This can be coded (in a simpler way) using C function

   int ppl_Polyhedron_unconstrain_space_dimensions
   (ppl_Polyhedron_t ph, ppl_dimension_type ds[], size_t n);

where ds is the array of space dimension indices, of length n, encoding 
the set of vars to be unconstrained (this function is new to PPL 0.10).

(2) When the code tests for conditions for returning -1, you have two 
nested loops iterating on the constraints of q1 and q2 (named q_x and 
q_y in my C++ code). Here, we have two kinds of improvements:

(2a) use iterating functions on PPL constraint systems instead of 
converting back and forth between PPL and cloog matrix representations.

(2b) MORE IMPORTANTLY, the test for non-empty intersection in the inner 
loop can be coded more efficiently using the "relation_with" 
functionality of the PPL, i.e., the C function

   int ppl_Polyhedron_relation_with_Constraint
   (ppl_const_Polyhedron_t ph, ppl_const_Constraint_t c);

and testing whether the result *entails* the value
   PPL_POLY_CON_RELATION_IS_DISJOINT
(i.e., testing if this bit is set in the returned value).
This should be a big win, as it avoids the creation/disposal of a 
quadratic number of polyhedra.

Hope the explanation above, together with the attached C++ code, is 
helpful enough. The easier way would be to write a C stub calling the 
attached C++ code ... provided you allow for compiling some C++ in cloog.

Ciao,
Enea.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: compare.cc
Type: text/x-c++src
Size: 4654 bytes
Desc: not available
URL: <http://www.cs.unipr.it/pipermail/ppl-devel/attachments/20080825/49d93c95/attachment.cc>