Global Sources
EE Times-India
Stay in touch with EE Times India
EE Times-India > Embedded

Basics of software performance analysis (Part 2)

Posted: 08 Aug 2013     Print Version  Bookmark and Share

Keywords:timing analysis  Abstract interpretation  WCET  FIR filter  path property 

Several techniques are utilised to analyse path timing at different levels of abstraction. Abstract interpretation analyses the behaviour of the program in detail to more accurately understand the execution states of the program. Data flow analysis provides a more detailed view of how the program behaves. The most concrete technique is simulation, which is used to determine the details of how the processor responds to the program.

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 ];
      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.

1 • 2 • 3 Next Page Last Page

Comment on "Basics of software performance analy..."
*  You can enter [0] more charecters.
*Verify code:


Visit Asia Webinars to learn about the latest in technology and get practical design tips.


Go to top             Connect on Facebook      Follow us on Twitter      Follow us on Orkut

Back to Top