[PPL-devel] New deterministic timeout facilities of the PPL and PWL

[Roberto Bagnara]

Sebastian Pop wrote:
> On Thu, Jul 9, 2009 at 07:12, Michael
> Classen<michael.classen at uni-passau.de> wrote:
>> Maybe it could also be possible to use the Parma Watchdog Library
>> (PWL) for providing a timeout for the precise method and falling back
>> to the more conservative method once a certain timeout is reached?
> 
> Not in GCC.
> This would make the compiler non deterministic.

We have uploaded a preview of PPL 0.11 at

     ftp://ftp.cs.unipr.it/pub/ppl/snapshots/

The new deterministic timeout facilities of the PPL and PWL (you need
both) can be exploited (using the C language interface) by using the
following functions:

   int ppl_set_deterministic_timeout(unsigned weight);
   int ppl_reset_deterministic_timeout(void);

The first function sets a maximum computational "weight".
After setting this weight threshold, some of the PPL library functions
(namely, those that may take an exponential amount of time) will
do the following:

a) charge the overall computation with their computational weight;
b) check, from time to time, whether the threshold has been reached.

In such a case, the computation will stop before completion (causing
no resource leaks) and the library function will return error code
PPL_TIMEOUT_EXCEPTION. Independently from whether or not such an
error code is obtained, the client code will need to dispose the
threshold previously set by calling the second function above.

Since the charged computation weights do not depend on actual
elapsed time, the timeout triggering is independent from the
given computational environment (CPU type, CPU speed, operating
system, ...).

As an example, the following code is taken from test file
interfaces/C/tests/weightwatch1.c:

   for (i = 0; i <= max_dimension; ++i) {
     ppl_new_NNC_Polyhedron_from_space_dimension(&ph, i, 0);
     open_hypercube(i, ph);
     ppl_set_deterministic_timeout(weight);  /* Setting threshold */
     result = ppl_Polyhedron_get_generators(ph, &gs);
     ppl_reset_deterministic_timeout();      /* Resetting threshold */
     ppl_delete_Polyhedron(ph);
     /* Check if the computation was stopped before completion. */
     if (result == PPL_TIMEOUT_EXCEPTION)
       /* Deterministic timeout expired */
       return;
     else if (result != 0)
       /* Unexpected error */
       exit(1);
   }

As said in the documentation:

   \warning
   The weight mechanism is under alpha testing. In particular,
   there is still no clear relation between the weight threshold and
   the actual computational complexity. As a consequence, client
   applications should be ready to reconsider the tuning of these
   weight thresholds when upgrading to newer version of the PPL.

At the moment we cannot provide meaningful hints regarding the
appropriate values to be given to these weight thresholds:
they mainly depend on the particular application and on the
particular problem instances considered. Some experimentation
and tuning are unavoidable.

Please test and let us know how it goes.  If you think you
want this in time for GCC 4.5.0, please advise so that our
release schedule matches the one of GCC.
Cheers,

    Roberto

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it