Basics of software performance analysis (Part 2)
Keywords:timing analysis Abstract interpretation WCET FIR filter path property
Bounding the number of iterations taken by a loop is particularly important for WCET analysis given that much of the execution time of most programs is spent in loops. Some loops, such as the FIR filter, are easy to analyse.
for (i = 0; i < N; i+)
y [i ] = c [i ] * x [i ];
But loops with conditionals create problems.
for (i = 0; i < N; i++)
for ( j = 0; j < M; j ++)
if (i ! = j )
c[ i ][j ] = a[i ]*b[ i ][j ];
else
c[i ][j ] = 0;
The algorithm of Healy et al [Hea99a] bound loop iterations in four phases:
• It first uses an iterative algorithm to identify branches that affect the number of iterations.
• It then identifies the loop iteration on which a loop-dependent branch changes direction.
• It determines when the branches found in step 1 are reached.
• Finally, it uses these results to calculate the iteration bound.
Figure 1 shows an example of loop iteration bounding from Healy et al [Hea99a]. The loop can be exited by a complex condition.
Figure 1: An example of loop iteration bounding. |
In the first step, it identifies the four control flow boxes with jumps as the points at which loop-dependent branches can change direction. It then determines that the first conditional branch, j > 75, occurs on iteration 26 (since j is incremented by 3 on each iteration). The condition j > 300 is taken on iteration 101, as is the condition j < 100. This gives a bound on the number of iterations as a minimum of 26 and a maximum of 101.
Figure 2: Program flow constraint in an if statement. |
Figure 3: Example code (top) and flow facts and clusters (bottom). |
Vivancos et al. [Viv01] proposed a parametric timing analysis method to determine the timing behaviour of programs with indefinite loops. They iteratively test the worst-case execution time of the program, starting with zero iterations and increasing the number of iterations by one at each step. Their testing terminates when the WCET stabilises. Figure 2 shows a simple conditional, its associated CDFG, and the flow variables assigned to the edges in the CDFG.
Ermedahl et al. [Erm05] use a clustering technique to determine which parts of a program must be handled as a unit. They annotate the control flow graph of the program with flow facts, which include the defining scope, a context specifier, and a constraint expression. The constraints may involve execution count variables and constants. As illustrated in figure 3, they cluster facts together to find the maximum scopes over which flow facts apply, such as in nested loops.
Related Articles | Editor's Choice |
Visit Asia Webinars to learn about the latest in technology and get practical design tips.