Exponential behavior in ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron

[Sebastian Pop]

Hi,

there seems to be an exponential behavior when calling

ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
(&ps, context);

to build the scop context for the 437.leslie3d benchmark:

(gdb) p debug_ppl_polyhedron_matrix (context)
42 23
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2147483648
1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2147483647
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 9223372036854775807
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 9223372036854775808
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 9223372036854775807
$35 = void

this is equivalent to
-2147483648 <= p0 <= 2147483647
-9223372036854775808 <= p1 <= 9223372036854775807
etc.

For now, I am thinking to limit the scops that we are handling based
on the number of parameters that we have to handle to avoid for now
this kind of problems.

Roberto, is there some other output more interesting for the PPL folks
and that I should report?

Thanks,
Sebastian

PS: here is a backtrace after I stopped the execution randomly

(gdb) bt
#0 0x00002aaaab4d7f83 in Parma_Polyhedra_Library::subset_or_equal(Parma_Polyhedra_Library::Bit_Row const&, Parma_Polyhedra_Library::Bit_Row const&) () from /usr/lib/libppl.so.7
#1 0x00002aaaab4da9c0 in Parma_Polyhedra_Library::Polyhedron::conversion(Parma_Polyhedra_Library::Linear_System&, unsigned long, Parma_Polyhedra_Library::Linear_System&, Parma_Polyhedra_Library::Bit_Matrix&, unsigned long) () from /usr/lib/libppl.so.7
#2 0x00002aaaab4dc16b in Parma_Polyhedra_Library::Polyhedron::minimize(bool, Parma_Polyhedra_Library::Linear_System&, Parma_Polyhedra_Library::Linear_System&, Parma_Polyhedra_Library::Bit_Matrix&) () from /usr/lib/libppl.so.7
#3 0x00002aaaab497620 in Parma_Polyhedra_Library::Polyhedron::update_generators() const () from /usr/lib/libppl.so.7
#4 0x00002aaaab0ff407 in ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron () from /usr/lib/libppl_c.so.2
#5 0x00000000010188c6 in build_scop_context (scop=0x19f0390) at ../../gcc/graphite-sese-to-poly.c:1554

[Albert Cohen]

Sebastian Pop wrote:
> Hi,
>
> there seems to be an exponential behavior when calling
>
> ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
> (&ps, context);
>
> to build the scop context for the 437.leslie3d benchmark:

Hi Sebastian,

The PPL also offers a deterministic watchdog to stop extra-long
computations. Why not using it in this case?

Albert

[Roberto Bagnara]

Hi Sebastian!

On 03/09/2010 05:06 AM, Sebastian Pop wrote:
> there seems to be an exponential behavior when calling
>
> ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
> (&ps, context);

This has indeed worst-case exponential complexity. A powerset,
do to its nonredundancy property, should not contain empty elements.
So the implementation (lazily) performs an emptiness check,
whose complexity is exponential in the worst case.

> For now, I am thinking to limit the scops that we are handling based
> on the number of parameters that we have to handle to avoid for now
> this kind of problems.

This is one way to go. Another way is to use the constructors with
limited complexity:

int
ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron_with_complexity
(ppl_Pointset_Powerset_C_Polyhedron_t* pph, ppl_const_Pointset_Powerset_C_Polyhedron_t ph, int complexity);

While the interfaces for these methods are all there, the implementation
is still incomplete: there are many places where we could honor the
PPL_COMPLEXITY_CLASS_SIMPLEX, expecially now that our implementation
of the simplex is being improved with sparse matrices.

Another possibility (which is actually the best one) would be for you to
begin using the deterministic timeout facilities we have added to the PPL
following the Graphite Workshop in Austin. This would give you a general
solution for all your scalability problems.

> Roberto, is there some other output more interesting for the PPL folks
> and that I should report?

In this case it is not necessary, but in order for us to quickly
reproduce a problem, you could use the *ascii_dump() functions
to generate a text file that allow to reconstruct the PPL objects
you are observing.
Cheers,

Roberto

--
Prof. Roberto Bagnara
Applied Formal Methods Laboratory
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bag...@cs.unipr.it

[Sven Verdoolaege]

On Mon, Mar 08, 2010 at 07:06:18PM -0600, Sebastian Pop wrote:
> For now, I am thinking to limit the scops that we are handling based
> on the number of parameters that we have to handle to avoid for now
> this kind of problems.

Or you could use isl... :-)
isl doesn't have any problems with polyhedra like that.
It will at most compute a sample value and that doesn't
take too much time

skimo@purples:~$ time ~/obj/isa/isl/isl_polyhedron_sample < /tmp/437.leslie3d-context
[1,-2147483648,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

real 0m0.021s
user 0m0.016s
sys 0m0.008s

skimo