Timing schema

In tree-based methods, the final WCET is generated by a bottom-up traversal of the tree representing the program. The analysis results for the basic blocks are used to make timing estimations for larger parts of the program. The set of basic formulae given by Puschner and Koza, originally proposed for a processor without caches, branch prediction, or pipelines, gives the maximum execution time of every control construct according to the syntax tree structure .

Construct S

S₁;;S_n WCET(S)= Sum ⁿ_i=1 WCET(S_i)

if (tst) then S₁else S₂ WCET(S)=WCET(Test)+ max(WCET(S₁),WCET(S₂))

for (;tst;inc) S₁
WCET(S)=maxiter × (WCET(Test)+WCET(S₁)+WCET(Incr))
+WCET(Test) +WCET(Exit)

basic block B_x WCET(S)=MAXT(B_x)

MAXT(B_x) is the maximum execution time for a basic block B_x.

maxiter is the maximum number of iterations of a loop.

Original timing schema

This timing schema uses a simple basic block WCET represented by a scalar. To use the basic block our WCET results, we have to define a new timing schema suitable for more complex data (see Worst Case Execution Time Analysis for a Processor with Branch Prediction for details).

dernière mise à jour : 02 02 2001
	english version		acolin@irisa.fr		©copyright