WCET (Worst Case Execution Time) analysis: Worked examples

5.5.13 · D3 · Coding › Embedded Systems & Real-Time Software › WCET (Worst Case Execution Time) analysis

Yahan sab kuch ek imaginary lekin consistent cost model use karta hai taaki numbers haath se check ho sakein. Model ek baar padhlo:

Scenario matrix

Har WCET puzzle basically inhi cells mein se ek (ya mix) hota hai. Neeche ke examples un cell(s) ke saath tagged hain jo woh cover karte hain, aur milake yeh poora grid fill karte hain.

Cell	Case class	Kya tricky banata hai	Covered by
C1	Fixed loop, no branch	Baseline: body cost ko iteration count se multiply karo	Ex 1
C2	Branch inside loop	Kaun si side longer hai? Worst case har baar long side leta hai	Ex 2
C3	Zero-iteration loop	Loop jo 0 baar bhi chal sakta hai — boundary condition	Ex 3
C4	Cache: cold vs warm	Pehla access miss, baaki hit — miss ek baar hota hai, har baar nahi	Ex 4
C5	Nested loops	Inner count, outer count se multiply hoti hai	Ex 5
C6	Data-dependent bound + infeasible path	Do branches jo dono ek saath nahi ho sakte → naive sum over-count karta hai	Ex 6
C7	Interrupt interference	Tumhare apne code ke upar external time add hoti hai	Ex 7
C8	Word problem / schedulability	WCET number ko pass/fail deadline decision mein convert karo	Ex 8
C9	Exam twist: average ≠ worst	Measurement-based trap; mean jhooth bolta hai	Ex 9

Example 1 — Fixed loop, no branch (cell C1)

Worked example Statement

void clear(int buf[], int n) {   // n is FIXED at 20
    for (int i = 0; i < n; i++)  // Block B: loop test = 1 cycle
        buf[i] = 0;              // Block C: store = 1 cycle
}

Block A (i=0 set karna) = 1 cycle, ek baar chalta hai. WCET kitne cycles mein hai?

Forecast: abhi ek number guess karo. (Hint: test kitni baar chalta hai vs body?)

Har block kitni baar chalta hai yeh count karo. Yeh step kyun? WCET = (block ka cost) × (kitni baar execute hota hai). Pehle counts pakki karni hogi.
- Block A: ek baar → 1 execution.
- Block B (test i < n): yeh har body se pehle ek baar chalta hai aur loop khatam detect karne ke liye ek extra baar. n = 20 ke liye yeh $20 + 1 = 21$ executions hai.
- Block C (body): exactly n = 20 baar chalta hai.
Cost × count multiply karo aur sum karo. Yeh step kyun? Yeh straight loop ka core WCET formula hai jisme koi branch nahi — koi path choice nahi hai, toh longest path hi ek hi path hai. $WCET = A 1 + B 21 \times 1 + C 20 \times 1 = 1 + 21 + 20 = 42 cycles$

Verify: Loop-test count sanity-check karo. Ek for loop jo 20 bodies karta hai hamesha apni condition 21 baar evaluate karta hai (aakhri wala fail hota hai aur exit karta hai). Units: cycles + cycles = cycles. ✓ 42 cycles.

Example 2 — Branch inside the loop (cell C2)

Worked example Statement

for (int i = 0; i < 10; i++) {   // B: test = 1 cycle
    if (data[i] > threshold) {   // C: compare = 1 cycle
        big_work(data[i]);       // D: this branch = 8 cycles
    } else {
        small_work();            // E: this branch = 2 cycles
    }
}

Block A (init) = 1 cycle. WCET?

Forecast: worst case kaun si branch leta hai — aur kitni baar?

Branch ka worst side pick karo. Yeh step kyun? WCET longest route maangta hai. Block D (8) Block E (2) se bada hai. Worst case tab hota hai jab if har ek iteration mein true ho — problem mein kuch bhi isko forbid nahi karta. $worst body cost = C 1 + max (D 8, E 2) = 1 + 8 = 9 cycles$
Fixed bound = 10 ke saath executions count karo. Yeh step kyun? Ex 1 jaisi hi counting rule: test $10 + 1 = 11$ baar chalta hai, body 10 baar. $WCET = A 1 + B 11 \times 1 + worst body 10 \times 9 = 1 + 11 + 90 = 102 cycles$

Verify: Best case se compare karo (har baar else): $1 + 11 + 10 \times (1 + 2) = 42$ . Worst (102) > best (42), jaisa hona chahiye. ✓ 102 cycles.

Example 3 — Woh loop jo shayad na chale (cell C3)

Worked example Statement

void process(int n) {            // n can be 0..50
    setup();                     // A: 4 cycles, always
    for (int i = 0; i < n; i++)  // B: test = 1 cycle
        step();                  // C: body = 3 cycles
    finish();                    // F: 2 cycles, always
}

Saare allowed n ke liye WCET? (Yaad raho 0..50 matlab 0 se 50 tak har integer.)

Forecast: kya n = 0 worst case deta hai, ya best?

Kaunsa n time maximize karta hai yeh dhundho. Yeh step kyun? Yahan n ek range hai, fixed number nahi. WCET poori range pe max hota hai. Har iteration cost add karti hai, toh zyada iterations = zyada time → worst case sabse bada allowed n hai, jo hai 50.
Pehle degenerate n = 0 case check karo taaki floor pata ho. Yeh step kyun? Boundary conditions wahan hain jahan bugs chhupte hain. Agar n = 0, loop body kabhi nahi chalta; test ek baar chalta hai (turant fail hota hai). $T (n = 0) = A 4 + B 1 + F 2 = 7 cycles (yeh BEST case hai)$
Ab worst case, n = 50. Yeh step kyun? Maximize karne wala n loop formula mein daalo: test $50 + 1 = 51$ baar chalta hai, body 50 baar. $WCET = A 4 + B 51 \times 1 + C 50 \times 3 + F 2 = 4 + 51 + 150 + 2 = 207 cycles$

Verify: $T (0) = 7 < WCET = 207$ , aur general formula $T (n) = 4 + (n + 1) + 3 n + 2 = 4 n + 7$ deta hai $T (0) = 7$ ✓ aur $T (50) = 207$ ✓. $n$ mein monotone increasing hai, toh max $n = 50$ par hai. ✓ 207 cycles.

Example 4 — Cache: cold miss ek baar, warm hits baad mein (cell C4)

Figure dekho: woh dikhata hai usi array ko 8 baar touch kiya ja raha hai, aur kaise miss sirf har cache line ke pehle touch par lagti hai.

Figure — WCET (Worst Case Execution Time) analysis

Figure — arr[0..7] ke liye cache line mapping. 8 array cells ko left to right boxes ke roop mein draw kiya gaya hai labeled arr[0] … arr[7]. Inhe 4 ke do cache lines mein group kiya gaya hai: cache line 0 arr[0..3] cover karta hai, cache line 1 arr[4..7] cover karta hai (har group ke upar blue double-arrows). Har line ka pehla box — arr[0] aur arr[4] — red hai aur "MISS 10 cyc" mark hai, kyunki ise pehli baar touch karne se slow memory se fetch force hota hai jo poori line le aata hai. Baaki chhe boxes — arr[1..3] aur arr[5..7] — green hain aur "hit 1 cyc" mark hain, kyunki line pehle se resident hai. Yellow summary line reads: 2 misses + 6 hits → 20 + 6 = 26 memory cycles.

Forecast: 8 misses? 2 misses? Kuch beech mein?

Memory lines count karo, accesses nahi. Yeh step kyun? Miss poori line cache mein laata hai. arr[0] miss hota hai aur arr[0..3] ko le aata hai; phir arr[1], arr[2], arr[3] hits hain. arr[4] miss hota hai (nayi line), aur arr[5..7] hit hote hain. Toh misses = distinct lines ki count = $8/4 = 2$ .
- Misses: 2 accesses × 10 cycles = 20.
- Hits: 6 accesses × 1 cycle = 6.
Plain per-iteration work add karo. Yeh step kyun? 2-cycle work saari 8 iterations pe hota hai regardless of cache. $memory = 20 + 6 = 26, work = 8 \times 2 = 16$ $WCET = 26 + 16 = 42 cycles$

Verify: Do extreme (galat) guesses cross-check karo. "Sab miss" = $8 \times 10 + 16 = 96$ (bahut zyada pessimistic — ek safe but loose bound). "Sab hit" = $8 \times 1 + 16 = 24$ (unsafe — cold cache ignore karta hai). Hamara 42 beech mein hai, aur line-based "First-Miss" classification se match karta hai. ✓ 42 cycles.

Example 5 — Nested loops (cell C5)

Worked example Statement

for (int i = 0; i < 4; i++)        // B_out: test = 1
    for (int j = 0; j < 5; j++)    // B_in: test = 1
        work();                    // C: body = 3

Init blocks: outer init A_out = 1 (ek baar), inner init A_in = 1 (har outer iteration pe ek baar). WCET?

Forecast: body 4×5 = 20 baar chalta hai — lekin har test kitni baar chalta hai?

Body count = bounds ka product. Yeh step kyun? Inner body outer passes mein se har ek ke liye inner baar chalta hai. $body executions = 4 \times 5 = 20 \Rightarrow cost = 20 \times 3 = 60$
Inner test aur inner init counts. Yeh step kyun? Har outer pass mein inner test $5 + 1 = 6$ baar chalta hai, aur inner init ek baar. 4 outer passes hain.
- Inner tests: $4 \times 6 = 24$ → 24 cycles.
- Inner inits: $4 \times 1 = 4$ → 4 cycles.
Outer test aur outer init. Yeh step kyun? Outer test $4 + 1 = 5$ baar chalta hai; outer init ek baar.
- Outer tests: 5 cycles. Outer init: 1 cycle.
Sab kuch add karo. $WCET = A_{o u t} 1 + B_{o u t} 5 + A_{in} 4 + B_{in} 24 + C 60 = 94 cycles$

Verify: Body akela 60 hai; loop scaffolding 34 add karta hai. Reasonable — control overhead real work ka ek fraction hai. ✓ 94 cycles.

Example 6 — Data-dependent bound + infeasible path (cell C6)

Yeh woh case hai jahan naive "har baar worst branch" over-count karta hai, kyunki do expensive branches dono ek saath nahi ho sakte.

Worked example Statement

if (mode == FAST) {      // path P: 3 cycles
    quick();             // Q: 4 cycles
} else {                 // path R: 3 cycles
    slow();              // S: 40 cycles
}
log();                   // L: 5 cycles, always
 
if (mode == FAST) {      // second test, 3 cycles
    tidy();              // T: 30 cycles
} else {
    nop();               // N: 1 cycle
}

Ek static analyzer jaanta hai ki mode dono ifs mein SAME hai. WCET?

Forecast: naive answer har if ka biggest branch add karta hai. Kya woh reachable hai?

Naive (galat, loose) bound: har if ka max independently pick karo. Yeh step kyun? Trap expose karne ke liye. Pehla if max = slow() = $3 + 40 = 43$ . Doosra if max = tidy() = $3 + 30 = 33$ . Naive total $= 43 + 5 + 33 = 81$ .
Infeasible path pakdo. Yeh step kyun? slow() tab chalta hai jab mode != FAST. tidy() tab chalta hai jab mode == FAST. Yeh contradict karte hain — mode ki koi bhi single value dono ko trigger nahi kar sakti. Naive 81 ek impossible route count karta hai. Yahi woh hai jo ILP mein flow constraints forbid karte hain.
Do real possibilities evaluate karo. Yeh step kyun? Sirf do feasible worlds exist karte hain; bada lo.
- mode == FAST: $quick 3 + 4 + L 5 + tidy 3 + 30 = 7 + 5 + 33 = 45$ .
- mode != FAST: $slow 3 + 40 + L 5 + nop 3 + 1 = 43 + 5 + 4 = 52$ . $WCET = max (45, 52) = 52 cycles$

Verify: True WCET 52 < naive 81. Naive bound safe hai (kabhi reality se neeche nahi) lekin loose hai; infeasible-path constraint ise tighten karta hai. ✓ 52 cycles.

Example 7 — Interrupt interference (cell C7)

Forecast: interrupt ek bounded number of times fire hota hai — kitni baar, aur kya uska time window ko lamba karta hai, aur bhi zyada interrupts ko andar aane deta hai?

Cycles ko wall-clock time mein badlo taaki units samajh aayein. Yeh step kyun? "Cycle" ek count hai; deadline ek real time hai. Inhe bridge karta hai clock rate: cycles per second. 2 million cycles per second pe, ek cycle $1/ (2, 000, 000)$ second $= 0.5$ microseconds (µs) rehti hai, kyunki 1 second = 1,000,000 µs toh $1, 000, 000/2, 000, 000 = 0.5$ µs per cycle. $200 cycles \times 0.5 \frac{µs}{cycle} = 100 µs$ Toh raw code ek 100 µs window occupy karta hai — yahi hai jahan se "100 µs" aata hai; yeh bas 200 cycles hain time mein measure kiye gaye.
Base window mein max interrupt arrivals count karo. Yeh step kyun? Interference arrival rate se bounded hoti hai. 200 cycles pe, har 40 cycles mein zyada se zyada ek → $⌈ 200/40 ⌉ = 5$ arrivals. (⌈ ⌉ brackets ka matlab hai "agli poori number tak round up karo" — fraction of an interrupt nahi ho sakta.)
Interference apne WCET mein add karo. Yeh step kyun? Parent ka response-time formula hai $R_{i} = C_{i} + I_{i}$ . Yahan $C_{i} = 200$ (tumhara apna code) aur $I_{i} = 5 \times 30 = 150$ (interrupts). $R = C_{i} + I_{i} = 200 + 150 = 350 cycles$

Verify: Interrupts ke bina, 200 cycles. Interference 150 add karta hai — 75% inflation, yahi wajah hai ki interrupts ko response-time analysis mein ek first-class term mana jaata hai, kabhi ignore nahi kiya jaata. Aur 200 cycles × 0.5 µs/cycle = 100 µs time conversion confirm karta hai. ✓ 350 cycles (100 µs raw code).

Example 8 — Word problem: kya yeh deadline meet karta hai? (cell C8)

Forecast: total worst-case response vs 500 µs — pass ya fail?

Har higher-priority task se interference sum karo. Yeh step kyun? Interference $I = \sum (cost per preemption \times max preemptions)$ across all tasks jo time chura sakte hain. Interferer 1 contribute karta hai $60 \times 2 = 120$ µs; interferer 2 contribute karta hai $20 \times 1 = 20$ µs. $I = (60 \times 2) + (20 \times 1) = 120 + 20 = 140 µs$
Response time compute karo. Yeh step kyun? Parent ka schedulability formula apply karo $R = C + I$ : tumhara apna worst-case work plus tumse charaaye gaye har cycle. $R = C + I = 350 + 140 = 490 µs$
Response time ko deadline se compare karo. Yeh step kyun? Ek task schedulable hota hai exactly tab jab uska worst-case response uski deadline ke andar fit ho: $R \leq D$ . $R = 490 µs \leq D = 500 µs \Rightarrow schedulable.$

Verify: Slack $= D - R = 500 - 490 = 10$ µs $> 0$ , toh pass hota hai — lekin bahut kum se. Agar WCET estimate 3% bhi loose hoti (lagbhag 15 µs) toh response 500 µs exceed kar jaata aur failure ho jaati. Yeh razor-thin margin exactly yahi reason hai kyun safety-critical systems mein tight WCET matter karta hai: ek zindagi pacemaker ke deadline se pehle fire hone par depend karti hai. ✓ R = 490 µs, PASS, 10 µs slack.

Example 9 — Exam twist: average jhooth bolta hai (cell C9)

Figure measurement histogram ki shape dikhata hai: mean ke paas ek tall cluster aur true worst case tak pahunchti ek lambi patli tail.

Figure — 10,000 measured run-times ka histogram (blue bars): horizontal axis execution time cycles mein hai, vertical axis dikhata hai kitne runs wahan aaye. Zyatdar runs 250 cycles ke aaspaas pile up karte hain (the mean, green dashed line). Daayein taraf bars ek lambi tail mein patale hote hain; ek yellow arrow use label karta hai "long thin tail = rare slow runs". Teen aur vertical markers daayein taraf badhte hain: 99.9th percentile 580 par (yellow), observed maximum 612 par (red), aur aakhir mein reported WCET 662 par (white), jo har ek bar ke daayein baitha hai — ek safe upper bound ko saare measurements par dominate karna chahiye.

Forecast: 250, 580, 612 mein se kis par build karte ho?

Mean ko reject karo. Yeh step kyun? Mean (250) woh hai jahan code usually land karta hai. Ek deadline jo 0.1% time miss ho woh bhi ek patient ko maar sakti hai. WCET ko tail bound karna chahiye, toh 250 immediately disqualify ho jaata hai.
99.9th percentile bhi reject karo. Yeh step kyun? 580 ko 1000 mein se 1 run exceed karta hai — phir bhi ek aise case mein jo eventually guaranteed miss hoga. Ek safe bound ko har observed value par ya usse upar rehna chahiye, 99.9% par nahi.
Observed maximum par build karo, phir pad karo. Yeh step kyun? Humne sirf 10,000 ek near-infinite input space ka test kiya; true worst case shayad humne jo dekha usse zyada ho. Margin untested inputs aur rare cache/pipeline events cover karta hai (Extreme Value Theory is padding ko formalize karta hai). $WCET_{report} = max + Δ = 612 + 50 = 662 cycles$

Verify: $662 > 612 > 580 > 250$ — reported bound har measurement par dominate karta hai, jaisa ek safe upper bound ko karna chahiye. ✓ 662 cycles.

Recall

Recall WCET branch costs ka average hota hai. Sahi ya galat?

Galat — yeh har baar longest branch leta hai, kabhi average nahi. (Ex 2)

Recall N body count wala ek

for loop apna test kitni baar evaluate karta hai? $N + 1$ ::: N baar har body se pehle plus ek aakhri failing test exit karne ke liye. (Ex 1)

Recall 8 array reads, cache line = 4 elements, cold start — kitni misses hoti hain?

Distinct lines = 8/4 ::: 2 misses; baaki 6 accesses hit hote hain. (Ex 4)

Recall Naive "har if ka max branch" kyun over-count kar sakta hai?

Kuch expensive branches infeasible paths par hain ::: woh ek doosre ko contradict karte hain aur ek hi execution mein sab nahi chal sakte. (Ex 6)

Recall Schedulability test ek line mein?

$R = C + I \leq D$ ::: worst-case response = apna WCET + interference, deadline ke andar fit hona chahiye. (Ex 8)

Recall Mean ki jagah observed-max + margin kyun report karte hain?

Mean typical hai, worst nahi ::: ek safe bound ko har observed value ke upar rehna chahiye aur untested inputs ke liye pad karna chahiye. (Ex 9)