[PPL-devel] Z-polytopes in PPL

[Michael Classen]

Hello,

On Thu, Jun 18, 2009 at 3:56 PM, P M Hill<hill at comp.leeds.ac.uk> wrote:
> What the PPL does also provide is a product domain as a templatic class
> (Partially_Reduced_Product). By instantiating the templatic arguments to
> Grid and C_Polyhedron (or NNC_Polyhedron), we can represent something like
> the Z-Polytopes in Polylib. There is a third templatic argument for this
> class for specifying a (partial) reduction procedure. If you let us know
> more exactly what you require for your Loopo interface, we can see if it is
> already available or if it would be straightforward to add the appropriate
> feature to the domain.

What I basically do is using Z-polytopes to describe a set of accessed
array elements that are reached from a subset (in our case a tile) of
a given iteration space. So we basically compute the disjoint union of
the image of a number of polytopes under a given affine linear array
access function. The result is a (union of) Z-Polytope(s). We then use
the Barvinok method for counting the integral number of points in this
(Z-)Polytope. We can't use a normal Polytope description, because most
access functions are not uni-modular and so we have to deal with
Z-Polytopes to keep a correct result for the integral numbers in a
disjoint union of those Z-Polytopes.

I just met some researcher from the Thales Group who works on a
similar topic and also needs the same Z-Polytope datatype. I think he
may contact you soon too about this.

I hope we can find some solution to integral polytope representations,
since I believe it is a very valuable tool for modern optimization
techniques.

thanks,
Michael Classen