Data Structure for Complexity Models

May 6, 2022

Import statement from "ri.newgen"

(Avoids conflicts between number types and types defined by the RI)

External Ppolynome

The domain Ppolynome is used to represent the complexities of the statement as function of parameters, variables and indices of loops with lobal coverage. A Ppolynome is a list of monomials, each monomial being constited of a floating coefficient and a Pvecteur representing the product of variables with their expopents.

Complexity = eval:Ppolynome x varcount x rangecount x ifcount

In the course of the evaluation, a field complexity is associated with each statement. The sub-domain eval contains a polynome Approching the complexity of the statement. The sub-domains varcount, rangecount and ifcount give the information statistics concerning the mnner in which the evaluation of the complexity took place, therefore also of the complexity itself. They count and in so doing classify the different types of variables/loops/tests encountered in the course of the complexity’s evaluation.

Varcount = symbolic:int x guessed:int x bounded:int x unknown:int

• symbolic = the number of variables which we would like to see appear in symbolic form in the expression of the complexity (”parameters” Fortran, loop indices, formal parameters of a subroutine). This gives false resultats of thois type of variable is modified in the course of execution.
• guessed = the number of variables the values of which which we have guessed thanks to semantic analysis.
• bounded = the number of variables for whih we have determined a maximum or minimum thanks to semantic analysis.
• unknown = the number of for which e have found no information, and which the user has not asked to se displayed in the complexity. These variables are all replaced by the pseudo-variable UNKNOWN_VARIABLE, which takes at the end of the evaluation a default value.

Rangecount = profiled:int x guessed:int x bounded:int x unknown:int

• profiled = the number of loops for which the limits have been measured by means of profiling.
• guessed = the number of loops for which the limits were at worst variable polynomes of type symbolic or guessed
• bounded = the number of loops for which the min./max limits were deterlined thanks to semantic analysis.
• unknown = the number of loops for which the number of loops could not be discovered. In consequence 0 after profiling pass. All these numbers are replaced by the pseudo-variable: UNKNOWN_RANGE, which will be given a default value at the end.

Ifcount = profiled:int x computed:int x halfhalf:int

• profiled = the number of tests for which the probability was messured by mens of profiling .
• computed = the number of tests for which the probability the probability was calculated. In particular in this case where the boolean expression depends only on the indices of those loops whose coverage global and whose ranges are of type guessed.
• halfhalf = the number of tests the probability of which was determined to be equal to a by defaut.