WCET (Worst Case Execution Time) analysis: Exercises

Below, a "cycle" is one tick of the processor clock — the smallest unit of time the CPU counts in. When we say a block "costs 5 cycles" we mean: from the moment the CPU starts that straight-line chunk of code to the moment it finishes, 5 ticks pass. That is all a cycle is: a unit of time.

Two acronyms recur below, so pin them down now:

WCET — Worst-Case Execution Time: the longest the code can take, a safe upper bound.
BCET — Best-Case Execution Time: the shortest the code can ever take, a safe lower bound. Whenever you read "best-case" later, read it as BCET.

Level 1 — Recognition

Exercise 1.1 (L1)

Which of these four statements is the correct definition of WCET?

(a) The average time the task takes over many runs.
(b) The fastest the task can ever finish.
(c) A safe upper bound — a number guaranteed to be ≥ the real time on every possible run.
(d) The time of the run you happened to measure yesterday.

Recall Solution

Answer: (c).

WHY: WCET must be safe — never smaller than reality — because we use it to prove deadlines are met. If it were an average (a) or a lucky-fast run (b), some real execution could exceed it and blow a deadline. A single measurement (d) is not a bound at all; the next input could be slower.

What the figure below shows (read it before moving on): a horizontal number line where the axis is execution time in cycles, running left (fast) to right (slow). Scattered along the line are 40 small teal dots — each dot is one real run's measured time; they cluster around the middle. A plum dashed vertical line sits at the average of those dots, and — this is the whole point — a large fraction of the teal dots lie to its right (runs slower than average), proving the average is not a safe ceiling. A teal dotted vertical line at the far left marks the best case (BCET), the leftmost any run reaches. Finally, a thick orange vertical line on the far right is WCET: every single teal dot lies to its left, so no run ever crosses it. The orange arrow labels it "right of every dot". Take-away you should see with your eyes: only the orange wall has nothing beyond it — that is what makes it, and not the average, a safe bound.

Figure — WCET (Worst Case Execution Time) analysis

Exercise 1.2 (L1)

Match each hardware feature to why it makes the same instruction take a different number of cycles on different runs.

Cache 2. Pipeline 3. Branch predictor A. A wrong guess flushes half-done instructions, wasting cycles. B. Data may be nearby-and-fast or far-and-slow. C. Instructions overlap, but a stall breaks the overlap.

Recall Solution

1→B, 2→C, 3→A.

Cache (B): a memory value already loaded nearby (a hit) costs a few cycles; a value that must be fetched from far RAM (a miss) costs 100+ cycles. Same load instruction, wildly different cost.
Pipeline (C): the CPU starts instruction 2 before finishing instruction 1, like an assembly line. If instruction 2 needs a result instruction 1 hasn't produced yet, the line stalls and the overlap saving vanishes.
Branch predictor (A): the CPU guesses which way an if goes and races ahead. A correct guess is free; a wrong guess means throwing away the speculative work — a flush.

Level 2 — Application

For all L2 problems use these per-block costs (cycles): a block is a straight-line chunk of code with no branches inside it.

Block	Meaning	Cost
A	one-time init	5
B	loop test (per iteration)	3
C	if-compare (per iteration)	4
D	if-body, cache miss	6
D'	if-body, cache hit	1
E	return	2

Exercise 2.1 (L2)

A loop runs for (i = 1; i < n; i++). The if-body (block D) is taken every iteration and always misses cache. Give the WCET formula in terms of $n$ , then evaluate at $n = 1000$ . Also state what the formula gives for the degenerate inputs $n = 1$ and $n = 0$ .

Recall Solution

WHAT we count: A and E run once (before/after the loop). The loop body runs for $i = 1 \dots n - 1$ , i.e. $n - 1$ iterations. Each iteration pays B + C + D $= 3 + 4 + 6 = 13$ .

WHY these choices: we want the worst-case (largest) time. Two independent worst-case decisions drive it: (1) the if is taken every iteration, so we charge D (6) not D' (1) — a taken branch does strictly more work; (2) every array read misses cache, so we use the miss cost 6, because a miss is the slowest possible outcome of a load. Picking the larger option at each choice point is exactly what "worst case" means, and it keeps the bound safe.

$WCET (n) = 5 + (n - 1) \cdot 13 + 2 = 13 n - 6$

At $n = 1000$ : $13 \cdot 1000 - 6 = 12994$ cycles. This matches the parent note's worked example — a good sanity anchor.

Boundary check. At $n = 1$ : the loop test 1 < 1 is false, so the body runs zero times; the formula gives $13 \cdot 1 - 6 = 7 = 5 + 0 + 2$ (just A + E) — correct. At $n = 0$ : the loop still runs zero times (it never enters), so the true cost is still $5 + 2 = 7$ , but the algebra $13 \cdot 0 - 6 = - 6$ is nonsense. Why the gap? The formula $13 n - 6$ silently assumes $n - 1 \geq 0$ , i.e. $n \geq 1$ ; for $n \leq 0$ you must clamp the iteration count to $max (n - 1, 0)$ . Analyzers hit exactly this bug — always guard loop-bound formulas against non-positive $n$ .

Exercise 2.2 (L2)

Same loop, but now the if-body is never taken (the array is already sorted descending, so arr[i] > max is always false). Give the best-case execution time (BCET) at $n = 1000$ , and check its behaviour at $n = 1$ .

Recall Solution

WHAT we count: A and E once; the loop body runs $n - 1$ times, but block D is skipped, so each iteration pays only B + C $= 3 + 4 = 7$ .

WHY these choices: here we want the best-case (smallest) time, so at each choice point we pick the cheaper option — the mirror image of Ex 2.1. The if is never taken, so we skip D entirely (charge 0, not 1 or 6); and because block D is what read the array, no array load happens in the body, so there is no miss to pay. Picking the smaller option at every branch is what makes this a lower bound (BCET), useful for input-dependent scheduling slack.

$BCET (n) = 5 + (n - 1) \cdot 7 + 2 = 7 n$

At $n = 1000$ : $7 \cdot 1000 = 7000$ cycles.

Boundary check. At $n = 1$ : body runs zero times, cost $= 5 + 2 = 7 = 7 \cdot 1$ — the formula agrees. (As in 2.1, for $n \leq 0$ you must clamp $n - 1$ to 0; $7 n$ would wrongly give 0 at $n = 0$ instead of the true 7.)

Notice WCET (12994) is not just "a bit more" than BCET (7000) — it is nearly double. That gap is exactly why we can't use a measured typical run as a bound.

Exercise 2.3 (L2)

Now the if-body is taken every iteration, but after the first miss the data stays in cache — so iteration 1 pays D (6, miss) and iterations $2 \dots n - 1$ pay D' (1, hit). Compute WCET at $n = 1000$ , and check the small case $n = 2$ .

Recall Solution

WHAT changes: the branch is still taken every time (so we always pay the if-body), but only the first body access misses; every later one hits.

WHY this split: worst case still means the if is taken every iteration (D or D', never skipped). But the cache is not adversarial forever — once a value is loaded, re-reading nearby data hits. So the honest worst case is one miss (the first, cold cache) followed by hits. Charging a miss on every iteration would be safe but loose; charging a hit on the first would be tight but unsafe. Counting exactly one miss is the tightest still-safe choice.

A once: 5
iteration 1: B + C + D $= 3 + 4 + 6 = 13$
iterations 2..(n−1): there are $(n - 2)$ of them, each B + C + D' $= 3 + 4 + 1 = 8$
E once: 2

$WCET = 5 + 13 + (n - 2) \cdot 8 + 2$

At $n = 1000$ : $5 + 13 + 998 \cdot 8 + 2 = 20 + 7984 = 8004$ cycles.

Boundary check. At $n = 2$ : exactly one iteration ( $i = 1$ ), which is the miss iteration, and the " $(n - 2) = 0$ " hit-term vanishes: $5 + 13 + 0 + 2 = 20$ cycles. Correct — with a single pass there are no "later" hits to count. (For $n \leq 1$ the loop never runs; you must again clamp so the "iteration 1 miss" term is only charged when there is at least one iteration.)

Level 3 — Analysis

Exercise 3.1 (L3)

You must certify a task whose true WCET is unknown. Method A (static analysis) returns 15000 cycles. Method B (measurement, 10 000 runs) returns a maximum of 8004 cycles, to which you add a 50-cycle margin. The deadline is 10000 cycles.

(a) Which number is safe to certify against the deadline, and why? (b) Which is tighter, and what is the risk of using it?

Recall Solution

(a) Static analysis is sound by construction: it explores the worst path in a model that over-approximates reality, so its answer (15000) is a guaranteed upper bound. But $15000 > 10000$ → this method says DEADLINE MISSED / not certifiable. That is a safe verdict even if pessimistic.

(b) Measurement gives $8004 + 50 = 8054$ cycles, which is tighter (closer to the likely truth) and under the 10000 deadline. The risk: measurement only saw the inputs you tried. An untested input, a rare cache-conflict, or an interrupt could push the real time above 8054. Measurement can never prove it found the worst case — so for a hard real-time / safety-critical system it is not, by itself, a certificate.

The tension: static is safe but loose (may reject a system that's actually fine); measurement is tight but unsound (may accept a system that's actually unsafe). This is the core trade in Static Program Analysis vs. measurement-based WCET.

Exercise 3.2 (L3)

Two candidate WCET numbers for the same task: $W_{1} = 9500$ (proven safe) and $W_{2} = 8000$ (proven safe, from a better analyzer). The deadline is 10000 and the scheduler needs the CPU utilization $U = W /10000$ . Compute both utilizations and explain why a tighter safe WCET is worth engineering effort.

Recall Solution

$U_{1} = 9500/10000 = 0.95$ (that is $95%$ ). $U_{2} = 8000/10000 = 0.80$ (that is $80%$ ).

Both are safe, so both certify the deadline. But utilization is how much of the CPU the task reserves. With the looser bound you must set aside $95%$ ; with the tighter one only $80%$ . That freed $15%$ can host another task or a slower/cheaper CPU. In Real-Time Scheduling Algorithms, tighter WCET directly means "more tasks fit" — pessimism costs hardware.

Level 4 — Synthesis

Exercise 4.1 (L4)

Build the WCET of this three-stage control loop from measured block ranges, using the hybrid method (static path + measured block times):

void control_loop(sensor_data s) {
    int p = preprocess(s);          // measured 50..80
    int d = compute_control(p);     // measured 100..500
    actuate(d);                     // measured 30..40
}

There are no branches between the three calls (straight-line). Give the WCET of one call to control_loop.

Recall Solution

WHAT: straight-line code ⇒ WCET is the sum of each block's worst (largest) measured value; there is no path choice to maximise over.

$WCET = 80 + 500 + 40 = 620 cycles$

WHY the max of each, not the max total observed: the worst case of a sum of independent stages is the sum of the worst stages — even if no single recorded run happened to hit all three maxima at once. Taking per-stage maxima is the safe (over-approximate) hybrid rule.

Exercise 4.2 (L4)

The same loop runs periodically inside an RTOS. During one activation, a higher-priority interrupt can preempt it. The interrupt handler's WCET is 90 cycles and it can fire at most twice per activation. Using the response-time idea $R = C + I$ from the parent note, compute the worst-case response time $R$ , and state whether it meets a deadline of 850 cycles (call this deadline $D_{ln}$ — the subscript "ln" for deadline, deliberately not the block cost $D$ from the L2 table, which is a completely separate thing).

Recall Solution

Naming caution first. The letter $D$ appeared earlier in the L2 cost table as the block "if-body, cache miss" (6 cycles). That $D$ is gone — it belongs only to Levels 2–3. Here the quantity we compare against is a deadline, and to avoid clashing with that block name we write it $D_{ln}$ . So: $D_{ln} = 850$ cycles is a time budget, not a block cost.

WHAT the symbols mean: $R$ = response time = the wall-clock span from when the task is released to when it finishes. $C$ = the task's own WCET (how long its instructions take with no one interrupting). $I$ = interference = time the CPU is stolen from this task by higher-priority work.

WHY we add $C$ and $I$ : the task cannot finish until two things have both happened — (1) all of its own work has run, costing $C$ , and (2) all the higher-priority work that jumps ahead of it has run, costing $I$ . While the interrupt handler executes, your task is frozen: its clock is paused but the wall clock keeps ticking, pushing your finish line later. So the total elapsed time is your own work plus every cycle the CPU spent on someone else — that is precisely $R = C + I$ . Neither term can be dropped: ignore $C$ and you pretend the task is free; ignore $I$ and you pretend no one ever preempts you.

Plug in the numbers.

$C$ = the task's own WCET = 620 (from Ex 4.1).
$I$ = interference = handler WCET × max firings = $90 \times 2 = 180$ .

$R = C + I = 620 + 180 = 800 cycles$

Compare to the deadline. Since $R = 800 \leq 850 = D_{ln}$ , the task meets its deadline in the worst case (with 50 cycles of slack to spare). Note that ignoring interrupts (using just $C = 620$ ) would have understated $R$ by 180 — a classic way to certify a system that actually misses deadlines under an interrupt storm.

Level 5 — Mastery

Exercise 5.1 (L5)

A loop of $N = 100$ iterations reads array element arr[i] each pass. The cache holds a line of 4 consecutive elements: the first access to a line misses (cost 100), the next 3 hit (cost 4 each). The rest of the loop body (test + compute) costs a fixed 20 cycles per iteration, and the array is walked in order arr[0], arr[1], .... Compute the loop's WCET (ignore one-time entry/exit).

Recall Solution

WHAT the cache does: with 4 elements per line, every 4th access is a miss and the other 3 are hits. Over 100 iterations that's exactly $100/4 = 25$ misses and $75$ hits.

miss cost: $25 \times 100 = 2500$
hit cost: $75 \times 4 = 300$
fixed loop-body cost: $100 \times 20 = 2000$

$WCET = 2500 + 300 + 2000 = 4800 cycles$

What the figure below shows: the first 24 of the 100 accesses drawn as bars. Tall orange bars are the misses (100 cycles) — they appear at indices 0, 4, 8, 12, … , i.e. every 4th access, each marking a fresh cache-line fetch. The many short teal bars (4 cycles) are the hits filling the gaps between them. The eye should catch the repeating "one tall, three short" rhythm — that ratio (1 miss : 3 hits per line of 4) is exactly what gives 25 misses and 75 hits, hence the 2800-cycle memory total annotated on the plot. Take away: the miss count is set by the line geometry, not by the total number of accesses alone.

WHY this is the mastery case: the naive "every access misses" bound gives $100 \times 100 + 2000 = 12000$ — safe but wildly loose (2.5×). The naive "one miss then all hits" gives $100 + 99 \cdot 4 + 2000 = 2496$ — tight but unsafe, because it forgets a new line is fetched every 4 elements. The correct answer, 4800, comes from analysing the cache line geometry, exactly the "always/first-hit" classification from Cache Memory Architecture.

Exercise 5.2 (L5)

A compiler unrolls the loop of 5.1 by 4 — each machine loop now handles 4 array elements per pass, so it runs $100/4 = 25$ passes. Unrolling removes the loop test on 3 of every 4 iterations, saving 3 cycles each of those. The cache behaviour is unchanged. Does WCET go up or down, and by how much? Give the new value.

Recall Solution

WHAT unrolling changes: the cache costs (2500 misses + 300 hits = 2800) don't move — same memory accesses in the same order. The body cost changes: of the 100 logical iterations, 75 no longer pay their 3-cycle loop test.

Saving: $75 \times 3 = 225$ cycles.

$WCET_{unrolled} = 4800 - 225 = 4575 cycles$

WHY this matters: the compiler made the code faster and WCET-lower, but only because we could still classify the cache accesses. Aggressive optimization can also hurt WCET analysis by scrambling the mapping between source lines and machine code — the parent note's third layer of complexity. Here it helped; you must always re-run the analysis on the optimized binary, never the source.

Recall Self-test summary (cloze)

WCET is a safe upper bound (never exceeded), not an average. BCET is a safe lower bound (never undercut), the best case. Static analysis is safe but loose ::: it over-approximates, may reject a fine system. Measurement is tight but unsound ::: it may miss the true worst case. Response time formula ::: $R = C + I$ , own WCET plus interference. A cache line of 4 elements gives ::: 1 miss + 3 hits per 4 accesses. Loop for(i=1;i<n;i++) runs ::: $n - 1$ iterations (zero when $n \leq 1$ ).