WCET Analysis

The natural way

Here is a recursion function, generating Fibonacci number.

int fib (int z) {
    int r;
    if (z == 0)
        r = 0;
    else if (z == 1)
        r = 1;
    else
        r = fib(z-1) + fib(z-2);
    return r;
}

The first two items of the Fib are 0 and 1. So it is very nature to write the code like this. But it is under-optimized, in a "Fibonacci-way".

Now we do the WCET(worst case execution time) analysis, assuming:

Each declaration or assignment statement costs 1 time unit
Each compare statement costs 1 time unit
Each return statement costs 1 time unit
Each addition or subtraction operation costs 4 time units.
A function call costs 2 time units plus WCET for the function in question.
All other language constructs can be assumed to take 0 time units to execute.

Let's make $f(z)$ to be the WCET of the fib(z), so $f(0)$ is the WCET of the fib(0) function execution. For different z value, the code being executed is different, with different length, and different WCET.

Now divide the code snippet to 3 parts, and analyze them seperately:

// path a (z=0): 4
int fib (int z) {
    int r; // declaration (1)
    if (z == 0) // compare (1)
        r = 0; // assignment (1)
    return r; // return (1)
}

For path a, the WCET of fib(0) is 4, that is $f(0)=4$

// path b (z=1): 5
int fib (int z) {
    int r; // declaration (1)
    if (z == 0) // compare (1)
    	;
    else if (z == 1) // compare (1)
    	;
    else
        r = 1; // assignment (1)
    return r; // return (1)
}

For path b, $f(1)=5$ because we have one more comparison executed with the if-else statement.

// path c (z>=2): 21+f(z-1)+f(z-2)
int fib (int z) {
    int r; // declaration (1)
    if (z == 0) // compare (1)
        ;
    else if (z == 1) // compare (1)
        ;
    else
        r = fib(z-1) + fib(z-2); // 3*4+2*2+f(z-1)+f(z-2)
    return r; // return (1)
}

For r = fib(z-1) + fib(z-2); it takes 3 ALUs(add/sub), 2 function calls, 1 assignment, and it contains the code of other 2 fib calling. So $f(z)=21+f(z-1)+f(z-2)$ for path c. And you may noticed that, we need to do one more comparison, same as path b.

For a if-else code snippet, the structure/placement matters, especially it will be called recursively.

if (cond1)
    func1(); // execute after cond1
else if (cond2)
    func1(); // execute after cond1, cond2
else if (cond3)
    func1(); // execute after cond1, cond2, cond3
else
    func1(); // execute after cond1, cond2, cond3

Let me use some real numbers, if we want to compute the WCET for fib(5), we'll have:

$$
\begin{align*}
f(2)=f(1)+f(0)+c=a+b+c \\
f(3)=f(2)+f(1)+c=a+2b+2c \\
f(4)=f(3)+f(2)+c=2a+3b+4c \\
f(5)=f(4)+f(3)+c=3a+5b+7c \\
\end{align*}
$$

The WCET of fib(5) is composed of some path a, more path b, much more path c. And try to look at it vertically, you may understand why I said, this is under-optimized in a Fibonacci-way.

The weight of path A grows in a Fibonacci-way; the weight of path B grows in a same fashion but one step ahead (one step in Fibonacci...). And for path C? Also grows in a Fibonacci fashion, but every time 1 is added to the weight (for the execution of path c itself).

For this natural version code, the WCET of fib(5) is $3\times 4+5\times 5+7\times 21=184$

Better Structure, nature way for the machine

int fib (int z) {
    int r;
    if (z > 1)
        r = fib(z-1) + fib(z-2);
    else if (z == 1)
        r = 1;
    else
        r = 0;
    return r;
}

If we switch the position of path C with path A, it will save one comparison for path C and add one to path A, which makes WCET of the new fib function is $3\times 5 + 5\times 5 + 7\times 20=180$. The difference is 4 time units of comparison.

For a computation of fib(10), the difference will be 54 time units.

For a computation of fib(20), the difference will be 6764 time units...