Closed versus NNC polyhedra
Konrad Trifunovic
my discussions on dependence analysis (and integer versus rational
solutions) provoked another,I think very fundamental discussion:
whether do we use NNC or C polyhedra? Since we are operating only on
integer solutions, there is really no need to have constraints like
'i < 10' since they can be represented (accurately) by 'i <= 9'. PPL
documentation says, that we should use Closed (with no '<'
constraints) polyhedra, since operations on Closed polyhedra are
faster (this is the feature of the algorithms that are used inside
PPL).
Now the question is, whether do we agree to move to C polyhedra? Even
if it seems that it is just a matter of
grepping all '_NNC' and replacing them by '_C', the problems might
always arise (I'm especially concerned about
dependence analyser and Cloog-PPL).
Konrad
Albert Cohen
earlier. There is absolutely no reason to use NNC in Graphite. Neither
now nor in the 50 years to come, as far as 100% of the litterature can
tell :-).
Albert
Tobias Grosser
On Thu, 2009-07-09 at 15:13 +0200, Konrad Trifunovic wrote:
> Hi all,
>
> my discussions on dependence analysis (and integer versus rational
> solutions) provoked another,I think very fundamental discussion:
> whether do we use NNC or C polyhedra? Since we are operating only on
> integer solutions, there is really no need to have constraints like
> 'i < 10' since they can be represented (accurately) by 'i <= 9'. PPL
> documentation says, that we should use Closed (with no '<'
> constraints) polyhedra, since operations on Closed polyhedra are
> faster (this is the feature of the algorithms that are used inside
> PPL).
you are right. I thought about waiting for the discussion about
switching to real integer polyhedron. But actually the conversion should
be easy. Just "sed -e 's/NNC_/C_/g' -i" and maybe some fixes while
generating inequalities. I will work on a patch.
Than we can retest your patchs with the C_Polyhedron. Maybe they are
faster.
Tobi
Michael Claßen
Trifunovic<konrad.t...@gmail.com> wrote:
>
> Hi all,
>
> my discussions on dependence analysis (and integer versus rational
> solutions) provoked another,I think very fundamental discussion:
> whether do we use NNC or C polyhedra? Since we are operating only on
> integer solutions, there is really no need to have constraints like
> 'i < 10' since they can be represented (accurately) by 'i <= 9'. PPL
> documentation says, that we should use Closed (with no '<'
> constraints) polyhedra, since operations on Closed polyhedra are
> faster (this is the feature of the algorithms that are used inside
> PPL).
1. I am surprised that in this context of integral solutions, 'i < 10'
and 'i <= 9' have any difference in semantics?
2. How can you make sure that you always use only integer solutions,
even when performing other operations like image under affine
functions that might be non-unimodular, e.g. 'f(x) = 2x' ?
3. Wouldn't we need a certain specialized datatype for this purpose (I
am in a discussion with Patricia Hill from the PPL in another thread
of the ppl mailing list about this new datatype, which would be
consisting of a product of a C_Polyhedra and some integer Grid).
> Now the question is, whether do we agree to move to C polyhedra? Even
> if it seems that it is just a matter of
> grepping all '_NNC' and replacing them by '_C', the problems might
> always arise (I'm especially concerned about
> dependence analyser and Cloog-PPL).
I am thinking about an algorithm for a more precise dependence
analysis, which wouldn't only "test" for a dependence, but also
deliver an exact description of the dependence relations (I talked
about that with Tobias). And for this purpose, runtime complexity will
be even more of a problem, so we definitely should use C polyhedra as
much as possible.
Michael
Tobias Grosser
> On Thu, Jul 9, 2009 at 3:13 PM, Konrad
> Trifunovic<konrad.t...@gmail.com> wrote:
> >
> >
> > my discussions on dependence analysis (and integer versus rational
> > solutions) provoked another,I think very fundamental discussion:
> > whether do we use NNC or C polyhedra? Since we are operating only on
> > integer solutions, there is really no need to have constraints like
> > 'i < 10' since they can be represented (accurately) by 'i <= 9'. PPL
> > documentation says, that we should use Closed (with no '<'
> > constraints) polyhedra, since operations on Closed polyhedra are
> > faster (this is the feature of the algorithms that are used inside
> > PPL).
>
> and 'i <= 9' have any difference in semantics?
They do not. However at the moment we are working on R^n. We should move
to integral polyhedron.
Tobi
Michael Classen
> to integral polyhedron.
>
> Tobi
You say that as if it is very easy... is there already a simple way of
dealing with integral polyhedrons in PPL? If so, I should maybe tell
Patricia that she shouldn't work too hard on this new datatype...?
Michael
Tobias Grosser
> > They do not. However at the moment we are working on R^n. We should move
> > to integral polyhedron.
> >
> > Tobi
>
> dealing with integral polyhedrons in PPL? If so, I should maybe tell
> Patricia that she shouldn't work too hard on this new datatype...?
No. I am waiting for Patricia's work. I think this is the way to go.
Tobi
Roberto Bagnara
Hi there.
Can you please explain what you mean by "integral polyhedron",
"new datatype" and "Patricia's work"? Please do not be afraid
to (re)state the obvious: I am sure there is one or more
misunderstandings here.
Cheers,
Roberto
--
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bag...@cs.unipr.it
Michael Classen
this is basically what I was referring to:
---------- Forwarded message ----------
From: P M Hill <hi...@comp.leeds.ac.uk>
Date: Wed, Jul 8, 2009 at 9:52 PM
Subject: Re: [PPL-devel] integer versus rational solutions
To: Michael Classen <michael...@uni-passau.de>
Cc: ppl-...@cs.unipr.it, "gcc-gr...@googlegroups.com"
<gcc-gr...@googlegroups.com>
On Wed, 8 Jul 2009, Michael Classen wrote:
>> HTH. Let me know if you have further queries wrt this domain, we will glad
>> to help.
>>
>> Pat
>
> Hi Pat,
>
> I basically just want to know if I can get correct integer results
> when using this combination of datatypes. I want to use operations
> like union, intersection, projection, basically most standard
> operations you want to use on polytopes.
Yes. These are already available in the latest release, but the best
version of the product domain is in the products branch of the GIT
repository. I would recommend you to use that if possible.
Sorry, I did not reply sooner to your previous email. I did try and
see what could be done to help solve the problem you described. (i.e.,
transforming a grid x polyhedron product to one where the grid is the
integer lattice). In fact, I have a proposal for adding a method to
the product domain that I hope would be sufficient for what you need
while, from the point of view of the PPL, fits into the existing
structures. In particular, I am believe that the implementation work
would be small!
That is:
In the product domain, (assuming for this explanation that the first
domain is a grid and the second a C polyhedron) there would be a
method such as:
bool
Partially_Reduced_Product<Grid, C_Polyhedron, R>
::affine_lattice_transform(const Grid& gr1)
that assigns to *this = <gr, ph> the product <gr1, ph1> such that
there is an affine function (ie a sequence of affine image mappings)
T, T(gr) = gr1 and T(ph) = ph1.
If there is no invertible affine function T such that T(gr) = gr1,
then the method could return false and otherwise true.
If you call the method with gr1 = integral lattice, and gr as a full
dimensional discrete grid you will get the polyhedron transformed to
one where the integral points correspond to the grid points and you
can use whatever tools you like to count the number of integer points.
By calling the same method with this* = <gr1, ph1> with the argument
gr, you will
be able to invert the operation.
I can try and implement something like this next week (while away at a
conference) as I think this would be useful anyway for other
applications.
Best wishes,
Pat
Roberto Bagnara
> Hello Roberto,
>
> this is basically what I was referring to:
Hi Michael,
thanks for clarifying. I need to understand more about what you
mean by:
>> I basically just want to know if I can get correct integer results
>> when using this combination of datatypes. I want to use operations
>> like union, intersection, projection, basically most standard
>> operations you want to use on polytopes.
What do you mean by "correct integer results"?
What I am worried about is that you may believe the PPL supports
the computation of the integer hull of a convex rational polyhedron
(i.e., the smallest polyhedron containing only the integer points
of the given rational polyhedron). The PPL does not provide an
algorithm to solve this (difficult!) problem.
What the PPL provides is:
1) the C_Polyhedron class that you know;
2) the Grid class that is able, in particular, to express
the integer lattice;
3) a generic Partially_Reduced_Product class that allows
to combine two domains, given a reduction procedure
that propagates _some_ information from one to the
other. I am wondering if this is the same notion
of "combination" you use above.
In point (3) the key words are "partially" and "some".
If _all_ the information was propagated from the Grid
component to the C_Polyhedron component, we would be
able to compute the integer hull, but this is not the
case.
Going back to the expression "correct integer results",
a Partially_Reduced_Product among a C_Polyhedron and
a Grid encoding the integer lattice provides (as far as
we know) correct, but possibly (and often) imprecise
results.
Michael Classen
basicall, what I need Z-polytopes for is a problem like the following:
Assume we have a certain loop-nest with some statements that access a
certain array:
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
A[2*i][2*j] = ...
A[i][i] = ...
}
}
(in general, array accesses can be arbitrary affine functions of loop
variables and structural parameters)
What I want to analyze is the array elements that are accessed by this
program. I want to count the number of array elements that are needed
during this computation. Unfortunately, the resulting sets are not
always convex polytopes, e.g. in this case, the first array access
function yields a set of points with only even numbers for coordinate
entries.
So I have to use Z-polytopes to describe this set and count the number
of points it contains. For this purpose, I have to calculate a
disjoint union of the two Z-polytopes resulting from mapping each
array access function (2i,2j) and (i,i) on the index space of each
statement. Then, I can use the Barvinok algorithm to count the number
of elements for each set in the resulting (disjoint) union.
I have implemented this method using the PolyLib, but unfortunately
there seem to be fundamental problems with the implementation of
Z-polytopes. So I was hoping that I could use PPL to achieve something
equivalent.
I hope this will clear up a few of the misunderstandings? But feel
free to ask further questions.
I also intend to follow the graphite telephone conference call this
Wednesday at 3pm.
greetings,
Michael Classen
Roberto Bagnara
[Copying here my reply to another message to ppl-...@cs.unipr.it]
I propose you to start from the beginning. But this time, let us
avoid anything that is not precisely defined.
My understanding is that you are interested in Z-polytopes.
A polytope is a bounded, convex polyhedron, right?
And a Z-polytope is the intersection between a polytope and
an integer lattice, right?
(Note: in the PPL "integer lattices" are called "integral grids".)
The PPL provides a way to "combine" a Grid (which can represent
any integer lattice), with a C_Polyhedron (which can represent
any polytope). But the combination is loose, because the tight
integration is computationally intractable.
Now, what operations do you require? I guess you need to know
if a Z-polytope is empty, right? This requires to answer,
for a given polytope P in R^n described by a system
of constraints with rational coefficients, the question:
Is P intersected with Z^n empty?
We currently use a standard, branch-and-bound mixed integer programming
optimizer: it may fail to terminate, it may be ridiculously expensive.
Can we do better?
We got in touch with three leading experts in the field. Two did not bother
to reply. *The* leading expert told us that "[Lenstra's algorithm,
the algorithm of Gr\"otschel, Lov\'asz and Schrijver,
and the algorithm of Lov\'asz and Scarf] are essentially theoretical.
I don't know of any implementations."
If you know the algorithm we should use, please share.
If we want the tight integration between C_Polyhedron and Grid,
we also need to compute a representation of the "integer hull" of
P, that is, the convex polyhedral hull of P intersected with Z^n.
Which cutting plane algorithm(s) should we use?
So far, we got no answer from the experts we contacted.
Do you know the answer?
Perhaps I have misunderstood what you mean by a "precise way of
dealing with something like Z-polytopes"? Please let us know.