WCET (Worst Case Execution Time) analysis: Visual walkthrough

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

Hum WCET (Worst Case Execution Time) analysis pe build kar rahe hain, aur Control Flow Graph (CFG) ki picture-language aur Cache Memory Architecture ke timing ideas ka sahara lenge. Baaki sab kuch hum yahan zero se construct karenge.

Step 1 — "Execution time" ka matlab kya hota hai?

KYA. Ek program choti-choti machine instructions ki ek list hota hai. Jab CPU ek instruction run karta hai, use ek certain number of clock cycles chahiye hote hain — ek cycle bas CPU ke internal metronome ki ek tick hai. Agar CPU ek second mein 1 billion baar tick karta hai, toh ek cycle ek second ka ek-arb-waan hissa hota hai.

YEH YAHAN SE KYU SHURU KAREN. "Worst case" ki baat karne se pehle humein us unit pe agree karna hoga jo hum count kar rahe hain. Hum cycles count karte hain, seconds nahi, kyunki cycles woh cheez hai jo hardware guarantee karta hai; seconds clock speed pe depend karti hain. Aage ki har cheez cycle counts ka sum hoti hai.

PICTURE. Neeche, har instruction ek black tile hai; uski width yeh hai ki woh kitne cycles khata hai. Total time = total width. Execution time ka poora idea yahi hai: tiles ko line up karo, length mapo.

Step 2 — Instructions ko blocks mein group karo

KYA. Ek basic block instructions ka ek aisa run hota hai jisme ek taraf se andar jaate hain aur ek taraf se bahar nikalte hain — na koi jump beech mein land karta hai, na koi branch beech se nikalta hai. Ek baar enter karo, toh sabhi instructions run hote hain.

GROUP KYU KARTE HAIN. Individual instructions count karna thakaan wala kaam hai. Lekin ek basic block ke andar koi decision nahi hota, isliye uski cycle cost ek fixed number hoti hai jise hum ek baar calculate karke baar baar use kar sakte hain. Isse problem "hazaron instructions" se "thode se blocks" mein simat jaati hai.

PICTURE. Parent ka find_max code paanch blocks mein collapse ho jaata hai. Red block B dekho — yeh loop ka test hai, woh block jise hum baar baar hit karenge.

Step 3 — Blocks ko ek graph mein convert karo (CFG)

KYA. Har block ke liye ek node banao. Block $X$ se block $Y$ ki taraf arrow banao agar control $X$ se $Y$ mein flow kar sakta hai. Yeh picture hai Control Flow Graph (CFG).

GRAPH KYU. Execution time "sabhi blocks ek baar add karo" nahi hai. Kuch blocks skip hote hain (else path), kuch repeat hote hain (loop). Ek graph yeh capture karta hai ki kaun sa block kis ke baad aa sakta hai — bilkul woh information jo ek plain sum throw away kar deta hai.

PICTURE. Red arrow loop back-edge $D \to B$ hai: yeh woh aakela arrow hai jo upar ki taraf jaata hai, aur isiliye block B kai baar run karta hai. Uss arrow ko hata do aur koi loop nahi bachega.

Step 4 — Har block ko ek execution count do

KYA. Maan lo $x_{b}$ woh number hai jitni baar block $b$ function ke ek single run mein execute hota hai. Tab run ka total time ek weighted sum hota hai.

COUNTS KYU, PATHS KYU NAHI. $2^{branches}$ possible paths hote hain — list karne ke liye bahut zyada. Lekin sirf five counts hain $x_{A}, \dots, x_{E}$ . Agar hum un paanch numbers ko pin kar saken, toh hume paths enumerate kiye bina time mil jaata hai.

PICTURE. Har block ab ek badge pahinta hai $x_{b}$ = kitne copies uske stack up hote hain. Block B ka stack woh lamba red wala hai.

Step 5 — Loop ko bound karo, warna answer infinity hai

KYA. Har count kitna bada ho sakta hai? Loop for (i=1; i<n; i++) run karta hai jisme $n \leq 1000$ hai.

Body blocks C aur D $i$ ki har value ke liye $1$ se $n - 1$ tak ek baar run karte hain: yaani $n - 1$ baar.
Test block B body se ek baar zyada run karta hai: yeh $n - 1$ successful tests aur ek final baar i < n false discover karne aur loop se exit karne ke liye fire hota hai. Toh B $n$ baar run karta hai.

B EK EXTRA BAAR KYU RUN KARTA HAI. Ek for loop hamesha apni condition pehle check karta hai body run karne ka decide karne se. Aakhri check wahi hai jo kehta hai "ruko" — body iske baad run nahi karti, lekin test ab bhi apne cycles khata hai. Us final failing test ko bhoolne se hamaara bound bahut chhota ho jaata (unsafe), isliye hum ise rakhte hain.

BOUND LAGNA KYU ZAROORI HAI. Bina loop bound ke, graph mein woh upar ki taraf red arrow hota hai aur analyzer ko maan lena padta hai ki loop kabhi nahi ruka → $x_{B} = \infty$ → poora time estimate $\infty$ ho jaata. Ek bekar answer. Bound $n \leq 1000$ woh ek fact hai jo machine guess nahi kar sakti; ek insaan ya ek static analyzer ko yeh supply karna padta hai.

PICTURE. Baayein taraf, koi bound nahi: count column upar se off shoot karta hai (∞, red). Daayein taraf, bound ise cap karta hai — dhyan do B ka stack C aur D se ek zyada ऊंचा hai, woh extra tile failing exit test hai.

Step 6 — Har block ke andar worst case chuno: branch aur cache

KYA. Yahan do "worst-case" choices rehti hain.

Branch (block C ka if). Kya arr[i] > max true hai? Agar haan, toh block D run karta hai; agar nahi, D skip ho jaata hai. Safe rehne ke liye hum har single iteration mein zyada expensive option assume karte hain: D hamesha run karta hai.
Cache (D ke andar). arr[i] padhna cache hit ho sakta hai (kuch cycles) ya miss ho sakta hai. Safe rehne ke liye hum miss assume karte hain (see Cache Memory Architecture).

Number 6 ke baare mein ek baat. Real hardware pe cache hit kuch cycles ki hoti hai jabki miss 100–300 cycles tak cost kar sakti hai — do orders of magnitude zyada. Agar hum sahi miss cost use karte, toh $T_{D}$ shayad $105$ hota aur is page ke har number mein balloon aata. Derivation ki shape visible rakhne ke liye hum ek chhota stand-in use karte hain, $T_{D} = 6$ , matlab "costly branch." Real number ke saath method bilkul wahi hai; sirf digits change hote hain. Ek honest analysis mein tum measured miss penalty yahan plug in karte.

WORST ASSUME KYU KARTE HAIN BHI. WCET ek safe upper bound hona chahiye: yeh har real run se $\geq$ hona chahiye. Agar hum kabhi sasta option choose karen aur reality mehenga choose kare, toh hamaara bound bahut chhota hai aur safety proof collapse ho jaata hai — airbag late fire karta hai.

PICTURE. Do forks. Har fork pe red path expensive wali hai, aur WCET hamesha red leta hai. Left fork = branch taken; right fork = cache miss.

Step 7 — Poora run assemble karo

KYA. Ek-baar wale blocks (A aur E) ko loop ke around rakho, per-iteration cost ko loop bound se multiply karo, aur single final failing test add karo.

YEH SHAPE KYU. A entry pe ek baar execute hota hai, E exit pe ek baar — yeh run ki boundary hain, loop ke bahar. Middle mein 13-cycle worst iteration ke $(n - 1)$ copies hain. Phir ek akela $T_{B}$ exit test ke liye jo kisi bhi iteration ka nahi hai. Inhe add karo.

PICTURE. Ek timeline: baayein taraf ek fixed red cap ( $A$ ), daayein taraf ek fixed cap ( $E$ ), beech mein $(n - 1)$ identical 13-cycle tiles ka ek stretchable middle, aur $E$ se bilkul pehle ek akeli patli red tile (final failing test $T_{B}$ ).

Deadline-critical size $n = 1000$ plug in karo: $WCET (1000) = 13 \times 1000 - 3 = 13000 - 3 = 12, 997 cycles .$

Step 8 — Degenerate cases (reader ko koi unseen scenario nahi milni chahiye)

KYA. Woh edges check karo jahan formula break ho sakta hai.

KYU. Ek bound jo $n = 1000$ ke liye sahi hai lekin $n = 1$ ke liye galat hai, woh ab bhi galat hai. Safety-critical ka matlab hai sab inputs ke liye.

PICTURE. Chaar chote scenarios: $n = 1$ (loop body kabhi run nahi hoti, lekin test exit ke liye ek baar fire hota hai), $n = 2$ (exactly ek body pass), "all branches false" run (D har baar skip — yeh best case hai, dikhaya gaya hai taaki tum dekh sako WCET iske upar baitha hai), aur $n = 0$ (empty array — arr[0] read khud danger hai).

Case	Kya hota hai	$13 n - 3$ se	Concrete check
$n = 1$	body $0$ baar run hoti hai; A, ek failing test $T_{B}$ , E	$13 (1) - 3 = 10$	$T_{A} + T_{B} + T_{E} = 5 + 3 + 2 = 10$ ✓
$n = 2$	ek body pass, phir failing test	$13 (2) - 3 = 23$	$5 + 13 + 3 + 2 = 23$ ✓
sab branches false	D har pass skip (best case)	$13 n - 3$ se kam hona chahiye	$5 + (n - 1) (3 + 4) + 3 + 2 = 7 n + 3$ ; $n = 1000$ pe yeh $7003 < 12997$ ✓ safe
$n = 0$	`arr[0]` ek empty array se aage read karta hai — yeh ek bug hai, timing case nahi	formula $- 3$ deta hai (bakwaas)	WCET valid input assume karta hai; $n \geq 1$ guard karo

Ek-picture summary

Upar ki poori cheez ek single diagram mein compress hoti hai: source code → blocks → CFG → counted & bounded (extra exit test ke saath!) → worst-case chosen → $13 n - 3$ mein sum. Red thread loop hai, woh ek cheez jo WCET ko badhati hai.

Recall Feynman retelling — jaise kisi dost ko explain karo

"Program run karna matlab bas CPU instructions chaba raha hai, aur har ek kuch clock ticks cost karta hai, toh execution time sach mein bas ticks add up karna hai. Hazaron instructions track karne ki jagah main unhe blocks mein chipka leta hoon — ek entrance aur ek exit wale chunks, toh har block ki ek fixed price hoti hai. Phir main arrows draw karta hoon dikhane ke liye ki kaun sa block kis ke baad aa sakta hai; yeh control-flow graph hai. Trick yeh hai: mujhe parwah nahi ki kaunsa path run hota hai, mujhe parwah hai ki har block kitni baar run hota hai. Zyada tar blocks ek baar run karte hain, lekin loop test bahut baar run karta hai — aur yahan sneaky wali baat hai: test ek extra baar run karta hai yeh notice karne ke liye ki loop khatam ho gayi aur quit karo, isliye agar body $n - 1$ baar run karti hai toh test $n$ baar run karta hai. Mujhe ise cap karna hoga warna answer infinity hai, isliye main kehta hoon 'yeh loop zyada se zyada $n - 1$ body passes run karta hai.' Har fork pe main jaanboojhkar expensive side choose karta hoon — assume karo if hamesha taken hai, assume karo har memory read cache miss karti hai — kyunki ek worst-case bound tabhi useful hai jab koi real cheez use beat na kar sake. Phir main bas add karta hoon: block A ek baar (5), loop body $n - 1$ baar 13 cycles each, ek akela final test (3), aur block E ek baar (2). Constants $5 + 2 = 7$ bundle karo, extra test fold karo, aur nikalta hai $13 n - 3$ . Ek hazaar-element array ke liye yeh 12,997 cycles hai. Main chhote cases bhi check karta hoon: $n = 1$ 10 cycles deta hai (A, ek failing test, E — koi body nahi), aur best case jahan if kabhi fire nahi karta woh faster hai, safely meri bound ke neeche baitha hai. Woh aakhri part woh reason hai jisse main promise kar sakta hoon deadline meet hogi — hamesha, usually nahi. Aur notice karo main parent ke number mein ek bug dhundhne mein kamyab hua: usne exit test bhool gaya aur teen cycles se kam estimate kar diya."

Yeh bhi dekho: Real-Time Scheduling Algorithms (jahan yeh WCET response-time test mein $C_{i}$ ban jaata hai), Static Program Analysis (loop bounds automatically kaise milte hain), aur Compiler Optimizations (kyun jo machine code tum time karte ho woh source jaisi nahi hoti jo tumne likhi).