WCET (Worst Case Execution Time) analysis: Exercises

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

Neeche, ek "cycle" processor clock ki ek tick hai — CPU jo sabse chhoti time unit count karta hai. Jab hum kehte hain ki ek block "5 cycles cost karta hai" to matlab hai: jis moment se CPU us straight-line code chunk ko start karta hai us moment tak jab wo finish karta hai, 5 ticks beette hain. Bus itna hi ek cycle hai: ek unit of time.

Do acronyms neeche baar baar aate hain, isliye inhe abhi yaad kar lo:

WCET — Worst-Case Execution Time: code jo sabse zyada time le sakta hai, ek safe upper bound.
BCET — Best-Case Execution Time: code jo sabse kam time mein kabhi finish ho sakta hai, ek safe lower bound. Jab bhi baad mein "best-case" padho, use BCET samjho.

Level 1 — Recognition

Exercise 1.1 (L1)

In chaar statements mein se WCET ki sahi definition kaun si hai?

(a) Bahut saare runs mein task ka average time.
(b) Task kitni jaldi kabhi finish ho sakta hai.
(c) Ek safe upper bound — ek aisa number jo har possible run mein real time se ≥ hone ki guarantee deta hai.
(d) Us run ka time jo tumne kal measure kiya tha.

Recall Solution

Answer: (c).

KYUN: WCET safe hona chahiye — reality se kabhi chhota nahi — kyunki hum ise deadlines meet hone ko prove karne ke liye use karte hain. Agar yeh average hota (a) ya lucky-fast run (b), to koi real execution ise exceed kar sakti thi aur deadline miss ho jaati. Ek single measurement (d) bilkul bhi bound nahi hai; agli input slower ho sakti hai.

Neeche jo figure hai wo kya dikhata hai (aage badhne se pehle padho): ek horizontal number line jiska axis execution time in cycles hai, left (fast) se right (slow) tak. Line par 40 chhote teal dots bikre hain — har dot ek real run ka measured time hai; ye beech mein cluster karte hain. Ek plum dashed vertical line un dots ke average par baithi hai, aur — yahi poora point hai — teal dots ka ek bada hissa uske right mein hai (average se slow runs), jo prove karta hai ki average safe ceiling nahi hai. Far left par ek teal dotted vertical line best case (BCET) mark karti hai, yani kisi bhi run ki sabse left position. Aakhir mein, far right par ek thick orange vertical line WCET hai: har single teal dot uske left mein hai, isliye koi run kabhi ise cross nahi karta. Orange arrow ise "right of every dot" label karta hai. Jo takeaway tumhe aankhon se dikhna chahiye: sirf orange wall ke paas kuch bhi nahi hai uske paar — yahi ise, average ko nahi, safe bound banata hai.

Figure — WCET (Worst Case Execution Time) analysis

Exercise 1.2 (L1)

Har hardware feature ko us reason se match karo ki kyun same instruction different runs mein different number of cycles kyun leti hai.

Cache 2. Pipeline 3. Branch predictor A. Galat guess half-done instructions ko flush kar deta hai, cycles waste hote hain. B. Data nearby-and-fast ho sakta hai ya far-and-slow. C. Instructions overlap karte hain, lekin ek stall overlap tod deta hai.

Recall Solution

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

Cache (B): ek memory value jo already nearby load hai (ek hit) kuch cycles cost karti hai; ek value jo far RAM se fetch karni ho (miss) 100+ cycles cost karti hai. Same load instruction, wildly different cost.
Pipeline (C): CPU instruction 1 finish hone se pehle instruction 2 start kar deta hai, jaise assembly line. Agar instruction 2 ko ek aisa result chahiye jo instruction 1 ne abhi produce nahi kiya, to line stall ho jaati hai aur overlap saving khatam ho jaati hai.
Branch predictor (A): CPU guess karta hai ki if kis taraf jaayega aur aage daudta hai. Sahi guess free hai; galat guess ka matlab hai speculative kaam phenkna — ek flush.

Level 2 — Application

Saare L2 problems ke liye yeh per-block costs (cycles) use karo (ek block straight-line code ka chunk hai jisme andar koi branches nahi hote):

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)

Ek loop for (i = 1; i < n; i++) run karta hai. If-body (block D) har iteration mein liya jata hai aur hamesha cache miss karta hai. $n$ ke terms mein WCET formula do, phir $n = 1000$ par evaluate karo. Saath mein yeh bhi batao ki formula degenerate inputs $n = 1$ aur $n = 0$ ke liye kya deta hai.

Recall Solution

KYA count karte hain: A aur E ek baar chalte hain (loop ke pehle/baad). Loop body $i = 1 \dots n - 1$ ke liye chalti hai, yaani $n - 1$ iterations. Har iteration B + C + D $= 3 + 4 + 6 = 13$ pay karti hai.

YE choices kyun: hum worst-case (sabse bada) time chahte hain. Do independent worst-case decisions ise drive karti hain: (1) if har iteration taken hai, isliye hum D (6) charge karte hain D' (1) nahi — taken branch strictly zyada kaam karta hai; (2) har array read cache miss karti hai, isliye hum miss cost 6 use karte hain, kyunki miss ek load ka sabse slow possible outcome hai. Har choice point par bada option chunna exactly wahi hai jo "worst case" ka matlab hai, aur yeh bound ko safe rakhta hai.

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

$n = 1000$ par: $13 \cdot 1000 - 6 = 12994$ cycles. Yeh parent note ke worked example se match karta hai — ek achha sanity anchor.

Boundary check. $n = 1$ par: loop test 1 < 1 false hai, isliye body zero baar chalti hai; formula deta hai $13 \cdot 1 - 6 = 7 = 5 + 0 + 2$ (sirf A + E) — correct. $n = 0$ par: loop phir bhi zero baar chalti hai (enter hi nahi karti), isliye asli cost abhi bhi $5 + 2 = 7$ hai, lekin algebra $13 \cdot 0 - 6 = - 6$ bakwaas hai. Gap kyun? Formula $13 n - 6$ silently assume karta hai $n - 1 \geq 0$ , yaani $n \geq 1$ ; $n \leq 0$ ke liye iteration count ko $max (n - 1, 0)$ par clamp karna hoga. Analyzers exactly isi bug mein faste hain — loop-bound formulas ko hamesha non-positive $n$ ke against guard karo.

Exercise 2.2 (L2)

Same loop, lekin ab if-body kabhi taken nahi hota (array already descending sort mein hai, isliye arr[i] > max hamesha false hai). $n = 1000$ par best-case execution time (BCET) do, aur $n = 1$ par behaviour check karo.

Recall Solution

KYA count karte hain: A aur E ek baar; loop body $n - 1$ baar chalti hai, lekin block D skip ho jaata hai, isliye har iteration sirf B + C $= 3 + 4 = 7$ pay karti hai.

YE choices kyun: yahan hum best-case (sabse chhota) time chahte hain, isliye har choice point par sasta option chunte hain — Ex 2.1 ka mirror image. if kabhi taken nahi hota, isliye D skip karte hain (0 charge karte hain, 1 ya 6 nahi); aur kyunki block D wahi tha jo array padhta tha, body mein koi array load nahi hota, isliye koi miss pay nahi karna padta. Har branch par chhota option chunna ise lower bound (BCET) banata hai, jo input-dependent scheduling slack ke liye useful hai.

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

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

Boundary check. $n = 1$ par: body zero baar chalti hai, cost $= 5 + 2 = 7 = 7 \cdot 1$ — formula agree karta hai. (Jaise 2.1 mein, $n \leq 0$ ke liye $n - 1$ ko 0 par clamp karna hoga; $7 n$ $n = 0$ par galat 0 dega instead of sahi 7.)

Note karo ki WCET (12994) BCET (7000) se "thoda zyada" nahi hai — yeh almost double hai. Yahi gap exactly woh reason hai kyun hum ek measured typical run ko bound ki tarah use nahi kar sakte.

Exercise 2.3 (L2)

Ab if-body har iteration mein taken hota hai, lekin pehle miss ke baad data cache mein rehta hai — isliye iteration 1 D (6, miss) pay karta hai aur iterations $2 \dots n - 1$ D' (1, hit) pay karte hain. $n = 1000$ par WCET compute karo, aur chhota case $n = 2$ check karo.

Recall Solution

KYA badla hai: branch abhi bhi har baar taken hai (isliye hum hamesha if-body pay karte hain), lekin sirf pehla body access miss karta hai; baad waale sab hit karte hain.

YE split kyun: worst case ka matlab phir bhi hai ki if har iteration mein taken ho (D ya D', kabhi skip nahi). Lekin cache hamesha ke liye adversarial nahi hai — ek baar value load hone ke baad, nearby data re-read karna hit karta hai. Isliye honest worst case hai ek miss (pehla, cold cache) aur phir hits. Har iteration par miss charge karna safe but loose hoga; pehle par hit charge karna tight but unsafe hoga. Exactly ek miss count karna sabse tight still-safe choice hai.

A ek baar: 5
iteration 1: B + C + D $= 3 + 4 + 6 = 13$
iterations 2..(n−1): in mein se $(n - 2)$ hain, har ek B + C + D' $= 3 + 4 + 1 = 8$
E ek baar: 2

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

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

Boundary check. $n = 2$ par: exactly ek iteration ( $i = 1$ ), jo miss iteration hai, aur " $(n - 2) = 0$ " hit-term vanish ho jaata hai: $5 + 13 + 0 + 2 = 20$ cycles. Correct — ek single pass ke saath koi "baad ke" hits count nahi hote. ( $n \leq 1$ ke liye loop kabhi run nahi karta; phir se clamp karna hoga taaki "iteration 1 miss" term tab hi charge ho jab kam se kam ek iteration ho.)

Level 3 — Analysis

Exercise 3.1 (L3)

Tumhe ek aisi task certify karni hai jiska asli WCET unknown hai. Method A (static analysis) 15000 cycles return karta hai. Method B (measurement, 10 000 runs) maximum 8004 cycles return karta hai, jisme tum 50-cycle margin add karte ho. Deadline 10000 cycles hai.

(a) Deadline ke against certify karne ke liye kaun sa number safe hai, aur kyun? (b) Kaun sa tighter hai, aur ise use karne ka risk kya hai?

Recall Solution

(a) Static analysis by construction sound hai: yeh ek model mein worst path explore karta hai jo reality ko over-approximate karta hai, isliye uska answer (15000) ek guaranteed upper bound hai. Lekin $15000 > 10000$ → yeh method kehta hai DEADLINE MISSED / certifiable nahi. Yeh ek safe verdict hai, chahe pessimistic lage.

(b) Measurement $8004 + 50 = 8054$ cycles deta hai, jo tighter hai (likely truth ke karib) aur 10000 deadline ke neeche hai. Risk: measurement ne sirf wahi inputs dekhe jo tumne try kiye. Ek untested input, ek rare cache-conflict, ya ek interrupt real time ko 8054 se upar push kar sakta hai. Measurement kabhi prove nahi kar sakti ki usne worst case find kar liya — isliye hard real-time / safety-critical system ke liye yeh, akele, certificate nahi hai.

Tension: static safe but loose hai (ek fine system ko reject kar sakta hai); measurement tight but unsound hai (ek actually unsafe system ko accept kar sakta hai). Yeh Static Program Analysis vs. measurement-based WCET ka core trade-off hai.

Exercise 3.2 (L3)

Same task ke liye do candidate WCET numbers: $W_{1} = 9500$ (proven safe) aur $W_{2} = 8000$ (proven safe, better analyzer se). Deadline 10000 hai aur scheduler ko CPU utilization $U = W /10000$ chahiye. Dono utilizations compute karo aur explain karo ki tighter safe WCET engineering effort kyun worth karta hai.

Recall Solution

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

Dono safe hain, isliye dono deadline certify karte hain. Lekin utilization wo hai jitna CPU task reserve karta hai. Looser bound ke saath $95%$ aside rakhna padega; tighter ke saath sirf $80%$ . Woh freed $15%$ kisi aur task ko ya slower/sasta CPU ko host kar sakta hai. Real-Time Scheduling Algorithms mein, tighter WCET directly matlab hai "zyada tasks fit hote hain" — pessimism hardware cost karta hai.

Level 4 — Synthesis

Exercise 4.1 (L4)

Is three-stage control loop ka WCET measured block ranges se, hybrid method (static path + measured block times) use karke banao:

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
}

Teen calls ke beech koi branches nahi hain (straight-line). control_loop ke ek call ka WCET do.

Recall Solution

KYA: straight-line code ⇒ WCET har block ki worst (largest) measured value ka sum hai; path choice maximize karne ke liye nahi hai.

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

HAR STAGE KA MAX KYUN, NA KI MAX TOTAL OBSERVED: independent stages ke sum ka worst case worst stages ka sum hai — chahe koi single recorded run teen maxima ek saath hit nahi kiya. Per-stage maxima lena safe (over-approximate) hybrid rule hai.

Exercise 4.2 (L4)

Same loop ek RTOS ke andar periodically run karta hai. Ek activation ke dauran, ek higher-priority interrupt ise preempt kar sakta hai. Interrupt handler ka WCET 90 cycles hai aur yeh ek activation mein zyada se zyada do baar fire ho sakta hai. Parent note ke response-time idea $R = C + I$ use karke worst-case response time $R$ compute karo, aur batao ki kya yeh 850 cycles ke deadline ko meet karta hai (is deadline ko $D_{ln}$ kaho — "ln" subscript deadline ke liye, jaanbujhkar L2 table ke block cost $D$ se alag, jo bilkul alag cheez hai).

Recall Solution

Pehle naming caution. Letter $D$ pehle L2 cost table mein block "if-body, cache miss" (6 cycles) ke roop mein aaya tha. Woh $D$ gone hai — woh sirf Levels 2–3 mein belong karta hai. Yahan jo quantity hum compare karte hain woh deadline hai, aur us block name se clash avoid karne ke liye hum ise $D_{ln}$ likhte hain. To: $D_{ln} = 850$ cycles ek time budget hai, block cost nahi.

Symbols ka matlab: $R$ = response time = task release hone se jab tak woh finish ho, wall-clock span. $C$ = task ka apna WCET (bina kisi interrupt ke uske instructions kitna time lete hain). $I$ = interference = higher-priority kaam ke liye CPU task se kitna time "chura" jaata hai.

$C$ aur $I$ kyun add karte hain: task tab tak finish nahi ho sakta jab tak do cheezein dono na ho jaayein — (1) uska apna saara kaam run ho, jisme $C$ lagta hai, aur (2) saara higher-priority kaam jo iske aage jump karta hai run ho, jisme $I$ lagta hai. Jab interrupt handler execute hota hai, tumhara task frozen hota hai: uska clock pause hai lekin wall clock chalta rehta hai, finish line baad mein push ho jaati hai. Isliye total elapsed time tumhara apna kaam plus har cycle jisme CPU kisi aur ke liye kaam karta hai — yahi precisely $R = C + I$ hai. Koi bhi term nahi chhorni: $C$ ignore karo to pretend karte ho ki task free hai; $I$ ignore karo to pretend karte ho ki koi tumhe kabhi preempt nahi karta.

Numbers plug in karo.

$C$ = task ka apna WCET = 620 (Ex 4.1 se).
$I$ = interference = handler WCET × max firings = $90 \times 2 = 180$ .

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

Deadline se compare karo. Kyunki $R = 800 \leq 850 = D_{ln}$ , task worst case mein deadline meet karta hai (50 cycles slack ke saath). Note karo ki interrupts ignore karna (sirf $C = 620$ use karna) $R$ ko 180 se understate karta — yeh ek classic tarika hai jisse ek aisa system certify ho jaata hai jo actually interrupt storm mein deadlines miss karta hai.

Level 5 — Mastery

Exercise 5.1 (L5)

$N = 100$ iterations ka ek loop har pass mein array element arr[i] read karta hai. Cache ek line mein 4 consecutive elements rakhta hai: ek line ka pehla access miss karta hai (cost 100), agle 3 hit karte hain (cost 4 each). Loop body ka baaki hissa (test + compute) har iteration mein fixed 20 cycles cost karta hai, aur array order mein arr[0], arr[1], ... walk ki jaati hai. Loop ka WCET compute karo (one-time entry/exit ignore karo).

Recall Solution

Cache kya karta hai: 4 elements per line ke saath, har 4th access ek miss hai aur baaki 3 hits hain. 100 iterations mein exactly $100/4 = 25$ misses aur $75$ hits hain.

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$

Neeche jo figure hai wo kya dikhata hai: 100 accesses mein se pehle 24 bars ke roop mein draw kiye hain. Tall orange bars misses hain (100 cycles) — ye indices 0, 4, 8, 12, … par aate hain, yaani har 4th access par, har ek fresh cache-line fetch mark karta hai. Baki kai short teal bars (4 cycles) hits hain jo unke beech ke gaps fill karte hain. Aankhein "one tall, three short" ka repeating rhythm pakad lengi — yahi ratio (1 miss : 3 hits per line of 4) exactly 25 misses aur 75 hits deta hai, isliye plot par annotated 2800-cycle memory total aata hai. Takeaway: miss count line geometry se set hoti hai, sirf total accesses ki count se nahi.

YE mastery case kyun hai: naive "har access misses" bound deta hai $100 \times 100 + 2000 = 12000$ — safe lekin wildly loose (2.5×). Naive "one miss then all hits" deta hai $100 + 99 \cdot 4 + 2000 = 2496$ — tight but unsafe, kyunki yeh bhoolta hai ki har 4 elements mein ek naya line fetch hota hai. Sahi answer, 4800, cache line geometry analyse karne se aata hai, exactly woh "always/first-hit" classification jo Cache Memory Architecture se hai.

Exercise 5.2 (L5)

Ek compiler 5.1 ke loop ko 4 se unroll karta hai — har machine loop ab 4 array elements handle karta hai per pass, isliye yeh $100/4 = 25$ passes run karta hai. Unrolling har 4 mein se 3 iterations par loop test hatata hai, har baar 3 cycles bachata hai. Cache behaviour unchanged hai. WCET upar jaata hai ya neeche, aur kitna? Naya value do.

Recall Solution

Unrolling kya badalta hai: cache costs (2500 misses + 300 hits = 2800) move nahi karte — same memory accesses same order mein. Body cost badalta hai: 100 logical iterations mein se, 75 ab apna 3-cycle loop test pay nahi karte.

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

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

YE kyun matter karta hai: compiler ne code ko faster banaya aur WCET lower kiya, lekin sirf isliye kyunki hum abhi bhi cache accesses classify kar sake. Aggressive optimization WCET analysis ko hurt bhi kar sakta hai source lines aur machine code ke beech mapping scramble karke — parent note ki teesri layer of complexity. Yahan usne help kiya; tumhe hamesha optimized binary par analysis re-run karni chahiye, source par kabhi nahi.

Recall Self-test summary (cloze)

WCET ek safe upper bound hai (kabhi exceed nahi hota), average nahi. BCET ek safe lower bound hai (kabhi undercut nahi hota), best case. Static analysis safe but loose hai ::: yeh over-approximate karta hai, ek fine system ko reject kar sakta hai. Measurement tight but unsound hai ::: yeh true worst case miss kar sakti hai. Response time formula ::: $R = C + I$ , apna WCET plus interference. 4 elements ki ek cache line deti hai ::: 1 miss + 3 hits per 4 accesses. Loop for(i=1;i<n;i++) chalata hai ::: $n - 1$ iterations (zero jab $n \leq 1$ ).