WCET (Worst Case Execution Time) analysis

Think of it like designing a bridge: you don't calculate load capacity for average traffic—you calculate for the worst possible scenario (maximum trucks, wind, earthquake simultaneously). WCET is that worst-case thinking for code execution time.

What Problem Does WCET Solve?

The Real-Time Scheduling Challenge

In a hard real-time system, tasks have deadlines. To prove schedulability (that all tasks meet deadlines), you need:

$R_i = C_i + I_i \leq D_i$

Where:

• $R_i$ response time (when task completes)
• $C_i$ = worst-case execution time (WCET)
• $I_i$ = interference from higher-priority tasks
• $D_i$ = deadline

WHY this formula? Response time = your own execution + time blocked by others. If this exceds your deadline, you've failed. Without accurate WCET, this analysis is worthless—garbage in, garbage out.

Key properties:

• Safe: WCET ≥ actual execution time for ALL runs
• Tight: WCET should be as close to reality as possible (too loose → wasted resources, unschedulable systems)
• Platform-dependent: Changes with CPU, cache, memory, compiler

The WCET Analysis Problem: Why It's Hard

Three Layers of Complexity

1. Path Complexity (Control Flow) Your code has branches, loops, function calls. Which path through the code is longest?

void sensor_process(int readings[], int n) {
    int max = readings[0];
    for (int i = 1; i < n; i++) {          // Loop: n iterations
        if (readings[i] > max) {           // Branch: taken or not?
            max = readings[i];
            log_new_max(max);              // Function call: how long?
        }
    }
    return max;
}

WHY hard? You have $2^{\text{branches}}$ possible paths. Loops can have data-dependent iteration counts. Finding the longest path is NP-hard in general.

2. Processor Complexity (Hardware Timing) Modern CPUs don't execute instructions in fixed time:

• Pipelines: instructions overlap, stalls happen
• Caches: hit = 1 cycle, miss = 100+ cycles
• Branch prediction: correct = fast, misprediction = pipeline flush
• Interrupts: can delay execution unpredictably

WHY this matters? The same instruction can take 1 cycle or 300 cycles depending on cache state. A loop that accesses arrays can have wildly different timing on each iteration.

3. Compiler Optimizations The compiler transforms your code:

• Inlines functions
• Reorders instructions
• Unrolls loops
• Merges/eliminates branches

WHY hard? Your source code is not what executes. The machine code can have completely different timing characteristics.

$\text{WCET} = \sum_{\text{paths}} \max_{\text{path}} \left( \sum_{\text{blocks in path}} T_{\text{block}} \right)$

Where $T_{\text{block}}$ depends on:

• Instruction timing (base cycles)
• Cache behavior (hits/misses)
• Pipeline effects (stalls, flushes)
• Memory access patterns

Deriving this: Start from "execution time = sum of instruction times." But which instructions execute? That's the path problem. And how long does each take? That's the hardware problem. WCET is the maximum over all possible paths, considering worst-case hardware behavior on that path.

WCET Analysis Approaches

1. Static Analysis (Analytical Method)

Analyze code without running it. Build models of control flow and hardware timing.

HOW it works:

Step 1: Build Control Flow Graph (CFG)

[Entry]
   ↓
[Block A: init]
   ↓
[Block B: loop header] ←┐
   ↓                │
[Block C: if condition] │
   ↓          │
[Then]    [Else]        │
   ↓          │
[Block D: loop back] ──┘
   ↓
[Exit]

Each block = straight-line code (no branches). Edges = control flow.

Step 2: Annotate with Flow Constraints User or automated analysis adds constraints:

Loop B-D: iterates ≤ 100 times
Branch C: then-branch taken ≤ 10 times per loop

WHY constraints? Without them, the analyzer assumes infinite loops or worst-case on every branch, giving absurdly large WCET.

Step 3: Model Hardware Timing For each block, compute timing considering:

• Cache analysis which accesses hit/miss
• Pipeline analysis: stalls, hazards
• Branch prediction: mispredictions

Step 4: Solve for Longest Path This becomes an Integer Linear Programming (ILP) problem:

$\max \sum_i x_i \cdot T_i$

Subject to:

• $x_i \in \{0, 1\}$ (block executed or not)
• Flow constraints: $\sum_{\text{in edges}} = \sum_{\text{out edges}}$ (conservation)
• Loop bounds: $x_{\text{loop back}} \leq N \cdot x_{\text{loop header}}$

WHY ILP? It finds the optimal path that maximizes execution time while respecting all constraints. It's exact for the model.

Analysis:

• Block A: 5 cycles (always executes once)
• Loop: $n - 1$ iterations
  • Block B: 3 cycles/iteration
  • Block C: 4 cycles/iteration
  • Block D: worst case = taken every iteration (6 cycles)
• Block E: 2 cycles

WCET calculation: $\text{WCET} = 5 + (n-1) \times (3 + 4 + 6) + 2$ $= 5 + 13(n-1) + 2 = 13n - 6$

For $n = 1000$: WCET = 12,994 cycles

Why this step?

• Block A, E execute once: boundary conditions
• Loop worst case: all iterations take longest path (if-branch always taken)
• Block D timing: assume cache miss (worst case for array access)

2. Measurement-Based Analysis

Run the code on actual hardware with carefully chosen inputs, measure execution time, add safety margin.

HOW it works:

Step 1: Generate Test Cases Create inputs that trigger:

• Maximum loop iterations
• Longest branches
• Worst-case cache behavior

Step 2: Measure Execution Time Use hardware timers or trace tools capture timing for each test case.

Step 3: Statistical Analysis If exhaustive testing is impossible:

• Run large number of random inputs
• Fit distribution to measurements
• Use Extreme Value Theory (EVT) to estimate tail

$\text{WCET}_{\text{estimate}} = \max(\text{measurements}) + \Delta_{\text{safety}}$

WHY safety margin? You can't test all possible inputs/states. The margin accounts for untested scenarios.

Measurements over10,000 runs:

• Observed maximum: 612 cycles
• 99.9th percentile: 580 cycles
• Mean: 250 cycles

WCET estimate: $612 + 50 = 662$ cycles (50-cycle safety margin)

Why this works? If your testing is thorough, the maximum observed is close to true WCET. The margin covers:

• Rare hardware events (cache conflicts)
• Untested input combinations
• Measurement uncertainty

Limitation: You can never be 100% sure you found the worst case.

3. Hybrid Analysis

Combine static and measurement approaches:

• Use static analysis for control flow, loop bounds
• Use measurements for basic block timing (easier to measure small code segments)
• Combine them: static solver uses measured block times

WHY hybrid? Static analysis struggles with complex hardware (cache, pipeline). Measurements capture real hardware but can't exhaustively test control flow. Hybrid gets the best of both.

Cache Analysis: The Hardest Problem

Caches cause the biggest timing variability. ==Cache hit 1-5 cycles, miss = 100-300 cycles==.

Cache Behavior Classification

For each memory access, classify as:

1. Always Hit (AH): Definitely in cache

   • Example: Loop iterating over small array that fits in cache

2. Always Miss (AM): Definitely not in cache

   • Example: First access to any data, or access after eviction

3. Unknown (U): Could hit or miss depending on history

   • Example: Access with data-dependent address

WCET analysis: Assume worst case for each access

• AH → count as hit
• AM, U → count as miss

Analysis:

• First iteration: $\text{arr}[0]$ = cache miss (AM) → 100 cycles
• If array size≤ cache size: subsequent $\text{arr}[i]$ = cache hit (AH) → 5 cycles each
• If array size > cache size: all accesses = miss (AM) → 100 cycles each

Case 1: Small array (fits in cache) $\text{WCET} = 100 + (N-1) \times 5$

Case 2: Large array (doesn't fit) $\text{WCET} = N \times 100$

WHY this difference? Cache reuse! Small arrays stay resident, large arrays keep evicting themselves.

Common WCET Analysis Tools

• aiT: Commercial static analyzer, supports complex processors (ARM, PowerPC)
• Bound-T: Open-source, focuses on simple microcontrollers
• Chronos: Academic tool, handles caches and pipelines
• RpiTime: Measurement-based with instrumentation
• OTAWA: Framework for building custom WCET analyzers

Mistake 1: Using Average-Case or Typical Measurements

❌ Wrong:

Measured 1000 runs:
- Average: 50 cycles
- Maximum observed: 80 cycles
WCET = 80 cycles  // DANGEROUS!

Why it feels right: 80 cycles is the worst you've seen, so it feels safe.

The fix: You haven't tested all inputs/states. True worst case could be 200 cycles. Always add safety margin for measurement-based, or use static analysis for guarantees.

✅ Right: $\text{WCET} = 80 \times 1.5 = 120$ cycles (50% margin), or use static analysis.

Mistake 2: Ignoring Cache Effects

❌ Wrong:

int sum = 0;
for (int i = 0; i < 1000; i++) {
    sum += big_array[i];  // Assume 5 cycles per access
}
WCET = 1000 × 5 = 5000 cycles

Why it feels right: You looked up instruction timing, it says "load = 5 cycles."

The fix: That's cache-hit timing. If big_array doesn't fit in cache, each access is a miss (100 cycles). Real WCET ≈ 100,000 cycles—20× underestimate!

✅ Right: Perform cache analysis. If array > cache size, assume mises: $\text{WCET} = 1000 \times 100 = 100,000$ cycles.

Mistake 3: Unbounded Loops Without Constraints

❌ Wrong:

while (sensor_ready()) {  // How many iterations?
    process_data();
}
// Static analyzer: "Loop bound unknown, WCET = ∞"

Why it feels right: "The sensor driver handles this, it'll be fine."

The fix: Static analyzers need explicit bounds. Without them, WCET is infinite or absurdly large.

✅ Right: Add annotation or code constraint:

int count = 0;
while (sensor_ready() && count < MAX_READS) {  // Bounded!
    process_data();
    count++;
}

Now analyzer can compute finite WCET.

Practical WCET-Aware Programming

Design for Analyzability

1. Avoid Unbounded Loops

// Bad: while(condition) - unknown bound
// Good: for(i = 0; i < MAX; i++) if (condition)

2. Avoid Data-Dependent Branches in Critical Paths

// Harder to analyze:
if (sensor_value > threshold) { /* variable path */ }
 
// Easier (if possible):
result = calculate_bothpaths();  // Straight-line code

3. Minimize Cache Interference

• Keep hot loops small (fit in instruction cache)
• Use predictable data access patterns (sequential, not random)

4. Annotate Code with Constraints

#pragma WCET loop_bound 100
for (int i = 0; i < n; i++) { ... }

Task: Fuel injection calculation, must complete every 1ms (deadline).

void fuel_injection_control(void) {
    sensor_data s = read_sensors();      // WCET: 50µs
    int rpm = calculate_rpm(s);          // WCET: 100 µs
    int load = calculate_load(s);        // WCET: 80 µs
    int fuel = lookup_fuel_map(rpm, load); // WCET: 30 µs (cache hit)
    adjust_injector(fuel);               // WCET: 40 µs
}

WCET analysis: $\text{WCET} = 50 + 100 + 80 + 30 + 40 = 300 \, \mu\text{s}$

Deadline: 1 ms = 1000 µs

Safety margin: $1000 - 300 = 700 \, \mu\text{s}$ → Safe! ✓

Why each step?

• Suming: Tasks execute sequentially (worst case: no overlaps)
• Individual WCETs: From static analysis + measurement of each function
• Check: $300 < 1000$ → Deadline met with 70% margin

If WCET was 1100 µs, we'd have a deadline miss—engine would misfire.

Verification and Validation

How Do We Know Our WCET Is Correct?

1. Static Analysis: Mathematically sound if model is accurate

   • Validation: Compare against measurements (WCET should be ≥ all measured times)

2. Measurement-Based: Sound only with sufficient testing

   • Validation: Use confidence intervals, stress testing, mutation testing

3. Certification: For safety-critical systems (DO-178C, ISO 26262)

   • Requires tool qualification
   • Traceable analysis artifacts
   • Independent review

WCET is like that, but for computer programs. When a computer is controlling something important (like a car's brakes or a plane's autopilot), the program has to finish its job by a deadline. If it's late, bad things happen—brakes don't work, plane crashes!

So engineers ask: "What's the WORST-CASE time this program could take?" Not the average time, not the usual time, but the absolute slowest it could EVER be. That's WCET.

Why is it hard to figure out? Because:

1. Your program has different paths (like taking different routes to the bus stop—some are longer)
2. The computer's speed changes (like sometimes you walk fast, sometimes slow because you're tired)
3. The computer's "memory shortcuts" sometimes work, sometimes don't (like sometimes your shoes are by the door, sometimes you have to search for them)

WCET analysis is like mapping out EVERY possible morning, including the worst one where EVERYTHING goes wrong (shoes lost, tothbrush missing, backpack hidden), and making sure even on THAT morning, you still catch the bus. That's how engineers make sure real-time computer systems are always safe!

Remember: Cache Misses = Catastrophe Risks (alliteration for cache being the hardest problem)

Connections

• Real-Time Scheduling Algorithms — WCET is input to schedulability analysis (Rate Monotonic, EDF)
• Cache Memory Architecture — Understanding cache behavior is crucial for WCET
• Control Flow Graph (CFG) — Foundation of static WCET analysis
• Interrupt Handling — Interrupts add non-determinism, complicate WCET
• Static Program Analysis — WCET uses abstract interpretation, data flow analysis
• Formal Verification Methods — WCET analysis is part of formal timing verification
• Safety-Critical Software Development — WCET required for DO-178C, ISO 26262 certification
• Embedded Linux and RTOS — RTOS provides better timing predictability for WCET
• Compiler Optimizations — Optimizations affect WCET, need WCET-aware compilation

#flashcards/coding

What is WCET and why is it critical for real-time systems? :: WCET (Worst-Case Execution Time) is the maximum time a task can take to execute across all possible inputs and hardware behaviors. It's critical because real-time systems use WCET to prove schedulability—that tasks will meet deadlines. Without accurate WCET, you cannot guarantee safety in hard real-time systems.

What are the three main layers of complexity in WCET analysis? :::1) Path complexity—finding the longest execution path through branches and loops; 2) Processor complexity—timing variability from caches, pipelines, branch prediction; 3) Compiler effects—optimizations that transform code timing. All three interact to make WCET analysis challenging.

What is the fundamental limitation of measurement-based WCET analysis? :: You cannot exhaustively test all possible inputs, initial states, and hardware behaviors. The measured maximum might not be the true worst case. This requires adding safety margins, but you never have mathematical certainty like static analysis provides.

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)