RTSync - Timing Graph Generation

The compiler works in a visitor pattern, the codevisitor object moves around the syntax tree and parses each node differently.

When the compiler reaches a fun_decl_node, or a node in which a method for an actor is declared, a <method> block is generated in the graph information file (which after debugging is done will be replaced with a string stream).

In each method, calls to other methods are recorded in the graph. A list of the scope expressions in which the call is made is recorded (ie. if the call is in an if statement, then the conditional expression is recorded). After this is listed, the actor and method names are recorded as a call.

Synchronizers are recorded in a similar fashion, except they are recorded in a <sync> block.

The graph information is then parsed by a “sanity checker” which tests the graph for timing violations. It is not possible to check for all timing violations at compile time, but in the case that the maximum and minimum time constraints of a synchronizer are equal to functions f and g respectively and f < g for all combinations of values for the independent variables of f and g, then there will always be a timing violation for this synchronizer. For example, if: 

  f(y) = y + 1000
  g(y) = y + 2000

then we have a timing violation for all values of y that may be passed to this function. Currently the sanity checker does not check for such a complex constraint, it only works if f and g are constant. A math library that can simplify an equation of the form f < g would be able to determine whether there is a definite timing violation or not. However if the simplified version of this equation contains variables which may result in this equality being true depending on the values, then there is not a definite timing violation.

The Sanity Checker

The sanity checker sets up a call graph that lists the calls made from each method, as well as a cost graph in which the nodes of the graph are the various methods and the edges are the costs to call each method. Since time constraints may be directed, the graph is also directed.

After the graph is constructed, a matrix of edges is created. An edge represents two values, a minimum constraint value (which we will call min) and a maximum constraint value (which we will call max). Most edges in the graph are regular edges that are not constrained (the minimum value is set to zero and the maximum value is set to infinity).

Edges may have three states:

  • Null state: No edge exists here.
  • Unknown state: An edge exists, but the constraints cannot be verified.
  • Normal state:An edge exists with normal constraints.

Since the edges are in a matrix, there must be ways to add or multiply them together. Here is a description of how these operations are performed:

  • Addition: z = x + y: If either x or y is in an unknown state, then z is in an unknown state. Otherwise, if both x and y are in a null state, then z is also in a null state. Regardless of states, the constraint values of z are as follows:
        z.min = min(x.min, y.min)
    z.max = max(x.max, y.max)
  • Multiplication: z = x * y: If either x or y is in a null state, then z is in a null state. The same goes for if x or y are in an unknown state. If both are normal, then the constraint values of z are as follows:
        z.min = x.min + y.min
    z.max = x.max + y.max

    Note that this is normal integer arithmetic, if either operand is equal to infinity, then the sum is equal to infinity.

In the matrix, the cost of an edge (a, b) that goes from node a to node b is at location M[a][b]. The cost along the diagonal is set to an impossible cost.

After the matrix is created, two more matrices are created that are clones of the first matrix, called A. These two matrices are the result matrix, R, and the incremental matrix, I. The sanity checker then iterates over the result matrix and sets any edge that is not normal to an impossible state (min = infinity, max = 0).

The sanity checker then goes into a loop that iterates k times, where k is equal to the number of nodes in the graph. During each iteration, A is set to A * I. Then, for all A[i][j].min < R[i][j].min, R[i][j].min is set to A[i][j].min and for all A[i][j].max > R[i][j].max, R[i][j].max is set to A[i][j].max.

There is a problem with this method in that indirect max constraints may grow unboundedly due to loops. The sanity checker finds the loops in the graph by setting A = A^2 after all the iterations. If a max constraint is still increasing at this point, we have gone past k iterations and so this constraint must be in a cycle. Since this is growing without bounds, we set the max constraint in R equal to infinity.

Finally, the sanity checker scans the global constraints for inconsistencies or impracticalities. An inconsistencies is when the minimum constraint is greater than the maximum constraint and an impracticality is when they are equal.