WCET (Worst Case Execution Time) analysis: Question bank

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

Shuru karne se pehle, kuch symbols aur words jo BILKUL sharp hone chahiye, kyunki har trap unhi par tika hai.

Neeche kuch items parent note se liya response-time inequality use karte hain. Yahan uske har symbol ko seedhi bhaasha mein explain kiya gaya hai, taaki hum unpe lean karne se pehle sab clear ho. Ek single task (isko task $i$ kaho) ko ek kaam ki tarah samjho jo ek stopwatch khatam hone se pehle khatam ho jaana chahiye:

Definition Response-time ke symbols

Ek task, task $i$ , ko consider karo jo doosre tasks ke saath chal raha hai. Chaar quantities batati hain ki woh "time par khatam hoga ya nahi":

$C_{i}$ = task $i$ ka ==worst-case execution time (WCET)== — uska khud ka code longest path par kitna time leta hai, koi interruption count kiye bina. Yahi woh number hai jiske baare mein poora page hai.
$I_{i}$ = ==interference== — woh total time jitna task $i$ ko ek taraf dhakela jaata hai jab higher-priority tasks uski jagah run karte hain. Isko calculate kiya jaata hai by summing ki har higher-priority task task $i$ ko uske window mein kitni baar preempt kar sakta hai, times us task ka khud ka WCET.
$R_{i}$ = ==response time== — woh total wall-clock time jab se task $i$ release hota hai jab tak woh khatam hota hai, yaani uska khud ka kaam aur saari interference: $R_{i} = C_{i} + I_{i}$ .
$D_{i}$ = ==deadline== — stopwatch ki limit; woh moment jab tak task $i$ zaroori taur par khatam ho jaana chahiye. Task schedule karne ke liye safe hai jab response time kabhi deadline cross na kare: $R_{i} = C_{i} + I_{i} \leq D_{i}$ . Figure s01 dekho in chaaron ko ek timeline par laid out dekhne ke liye.

Do acronyms bhi traps mein baar baar aate hain; unhe ek baar yahan define karte hain:

Figure s02 ek nazar mein dikhata hai ki ek safe bound true worst case par ya uske upar kyun honi chahiye jabki tight wala usse chipakta hai — yahi woh mental picture hai jo is page ke almost har trap ke peeche hai.

True or false — justify

The maximum observed time in a test campaign is a safe WCET bound.

False. Measurement sirf un inputs aur hardware states ko sample karta hai jo tumne happen to hit kiye; true worst case ke liye ek aisa untested input, cache layout, ya interrupt timing chahiye jo tumne kabhi trigger nahi kiya, isliye observed max real WCET se neeche baith sakta hai.

Adding a fixed safety margin to the measured maximum makes measurement-based WCET provably safe.

False. Margin ek guess hai. Koi bhi cheez prove nahi karti ki true worst case us margin ke andar hai jo tumne dekha, isliye result zyada likely safe hai, guaranteed safe nahi.

WCET sirf program ki property hai.

False. WCET program + hardware + compiler hai. Bilkul wahi C function ka Cortex-M0 par alag WCET hoga aur out-of-order Cortex-A par alag, aur phir ek compiler flag change ke baad bhi alag.

Ek fixed bound of 100 iterations wala loop hamesha exactly 100 × (body time) contribute karta hai.

False. Iterations alag ho sakti hain: pehli iteration aksar cache miss karti hai jabki baad wali hit karti hain, aur body ke andar data-dependent branches alag sub-paths le sakti hain. Tum sum ko bound karte ho, 100 identical copies ko nahi.

Static analysis tumhare real system ka exact WCET deti hai.

False. Woh apne model ke liye exact answer deti hai. Agar cache ya pipeline ka model conservative hai (jaisa safe rehne ke liye hona chahiye), toh number safe hai lekin pessimistic — model ke liye exact, reality ke liye ek over-estimate.

Agar tum ek program ko average par faster run karne ke liye optimise karo, toh uska WCET bhi zaroori drop kare.

False. Caching, branch prediction, ya speculative work jaisi optimisations best aur worst case ke beech ka gap bada kar sakti hain; worst path actually slower bhi ho sakta hai jabki average improve hoti hai.

Cache band kar dena hamesha WCET analysis aasaan banata hai aur WCET chota karta hai.

Easy ke liye mostly true, smaller ke liye false. Cache disable karne se hit/miss uncertainty khatam hoti hai isliye analysis simpler aur tighter hoti hai, lekin har access ab memory latency pay karta hai, isliye actual WCET usually barhta hai.

Response-time formula

R_{i} = C_{i} + I_{i} \leq D_{i}

mein sirf task

i

ka WCET chahiye.

False. Interference term

I_{i}

har higher-priority task ke WCETs (yaani

C

values) se banta hai, isliye kisi bhi task ka WCET under-estimate karna ek aisi schedule ko falsely "prove" kar sakta hai jo actually deadlines miss karta hai.

Extreme Value Theory (EVT) measurements ko mathematically safe bound mein convert karti hai.

False. EVT observed data par ek tail distribution fit karti hai; woh ek rare-event bound estimate karti hai lekin statistical assumptions par rely karti hai (independence, ki tail representative hai). Woh ek probabilistic bound deti hai, guaranteed safe nahi.

Ek tighter WCET hamesha ek looser se better hoti hai.

False — sirf tab agar woh safe rahe. Ek tighter number jo quietly true worst case se neeche chali jaati hai ek loose safe number se buri hai, kyunki woh ek unschedulable system ko schedulable dikhaa sakti hai.

Spot the error

"Humne har function ko isolation mein measure kiya aur maxima ko sum kar diya, isliye humara total WCET safe hai."

Per-function maxima incompatible states mein ho sakti hain — woh input jo A ko slow karta hai ho sakta hai cache ko aisi state mein chhode jo B ko bhi slow kare, lekin dono ek saath nahi ho sakti. Isolated maxima ko sum karna over-pessimistic ho sakta hai; isse bura, woh cross-function timing effects (pipeline, cache) miss kar sakta hai, isliye woh na guaranteed tight hai na guaranteed safe.

"Hamara loop data-dependent hai, isliye humne ILP solver ko source se iteration count figure out karne diya."

Ek ILP-based WCET solver loop bounds invent nahi kar sakta; usse ek supplied flow constraint chahiye. Bound ke bina CFG mein unbounded weight ka ek cycle hai aur solver infinity return karta hai (ya refuse karta hai). Loop bounds human annotation ya ek alag value analysis se aate hain.

"Humne C source se CFG banaya, isliye yoh exactly represent karta hai jo run hota hai."

Compiler inline, unroll, reorder aur merge karta hai blocks ko, isliye machine-code CFG source CFG se alag hoti hai. WCET ka analysis compiled binary par hona chahiye, source par nahi.

"WCET plus interference response time ke barabar hai, aur agar woh deadline se kam hai toh hum done hain — interrupts consider karne ki zaroorat nahi."

Interrupts extra, aksar asynchronous, execution add karte hain aur interference term ko inflate kar sakte hain. Agar unhe

I_{i}

ke andar model nahi kiya gaya (ya alag se bound nahi kiya gaya), toh response-time proof unsound hai.

"Cache miss = 200 cycles, humare block mein 3 accesses hain, isliye worst-case block time = base + 600."

Sab accesses miss assume karna safe hai lekin aksar bahut loose hota hai. Sahi cache analysis accesses ko classify karta hai (Always-Hit / Always-Miss / First-Miss); e.g. ek loop mein reuse hoti small array "first-miss then always-hit" hai, isliye sirf pehla pass 200 pay karta hai.

"Path complexity

2^{branches}

hai, isliye longest dhundhne ke liye hume har path enumerate karna hoga."

Tum paths enumerate nahi karte. Isliye hi WCET tools longest-path search ko block execution counts par ek ILP mein reduce karte hain flow-conservation constraints ke saath — polynomial-sized, not exponential-enumerated.

Why questions

WCET formula paths par max kyun leta hai average ya sum ki jagah?

Kyunki ek task, kisi run par, apna single longest path follow karega, aur safety ka matlab hai us run ko cover karna. Average usse under-count karta hai; sab paths sum karna un runs ko count karta hai jo kabhi simultaneously nahi hote.

Longest program path dhundhna generally NP-hard kyun hai, phir bhi WCET tools scale karte hain?

Arbitrary constraints ke saath general longest-path problem NP-hard hai, lekin real CFGs structured hoti hain (reducible loops, bounded nesting) aur flow constraints ke saath ILP formulation practical cases ko quickly solve karta hai.

Flow constraints (loop bounds, mutually-exclusive branches) ki zaroorat hi kyun hai?

Unke bina analyser har branch par worst assume karta hai aur ek unbounded loop, infinite ya absurdly bada WCET deta hai. Constraints woh semantic facts inject karte hain jo raw CFG express nahi kar sakti.

Same loop ki do consecutive iterations ka execution time alag kyun ho sakta hai?

Cache aur pipeline state carry over hoti hai: pehli iteration miss karke cache fill kar sakti hai, baad wali hit karti hain; branch predictors bhi "warm up" hote hain. Instructions identical hain lekin hardware context nahi.

Pure static ya pure measurement ke upar hybrid analysis prefer kyun karein?

Static analysis control flow aur loop bounds ko soundly handle karta hai lekin complex hardware ko pessimistically model karta hai; measurement real hardware timing capture karta hai lekin control flow ko exhaustively cover nahi kar sakta. Hybrid structure ke liye static aur small basic blocks ke liye measured times use karta hai.

Safety-critical certification usually pure measurement ke upar static (ya hybrid) analysis kyun demand karta hai?

Certification ko ek provable upper bound (soundness) chahiye, aur pure measurement sirf statistical confidence offer kar sakta hai, kabhi guarantee nahi ki worst input hit hua.

WCET ko bahut loose banana real harm kyun karta hai, sirf waste nahi?

Ek over-pessimistic

C_{i}

schedulability test mein har response time inflate karta hai, isliye ek system jo actually apni deadlines meet karta woh wrongly unschedulable declare ho jaata hai, jisse costlier hardware ya dropped features ki zaroorat padti hai.

Edge cases

Ek loop jiska bound ek aisi input par depend karta ho jise analyser bound nahi kar sakta, uska WCET kya hai?

Agar koi bound establish nahi ho sakta, toh sound answer unbounded (infinite) WCET hai — code as written WCET-analysable nahi hai. Fix hai ki iteration count par ek hardware/software cap enforce karo.

Ek purely straight-line program jisme koi branches ya loops nahi hain uske liye WCET analysis kya hoti hai?

CFG ek single path hai, isliye path analysis trivial hai; WCET worst-case hardware state mein sirf block times ka sum hai — hardware modelling hi ek remaining difficulty hai.

Agar ek function worst-case path par kabhi call nahi hota, toh kya uska WCET caller ke WCET mein contribute karta hai?

Nahi — ILP us block/call ko winning path par execution count zero assign karta hai, isliye uska time drop out ho jaata hai. Sirf longest feasible path par jo code hai wahi count hota hai.

Ek task ke liye jisme zero interference hai (

I_{i} = 0

, highest priority, koi interrupts nahi), kya

R_{i} = C_{i}

hoga?

Haan — koi higher-priority work nahi aur koi interrupt ya blocking delay nahi, toh response time task ke khud ke WCET par collapse ho jaata hai. Yahi woh ideal isolated case hai jahan se scheduling analysts shuru karte hain.

Kya hoga agar true worst-case input infeasible ho — logically impossible ho real system ke liye produce karna?

Toh safe-but-untight WCET ek aisi run count karti hai jo kabhi ho nahi sakti, over-estimating. Extra flow constraints (infeasible-path elimination) solver ko use exclude karne kehte hain, bound tighten karte hain bina safety todhe.

Same code ke do builds alag optimisation levels ke saath — kya -O2 ka WCET -O0 se bada ho sakta hai?

Haan, kabhi kabhi. Aggressive optimisation worst path ko aise reorder ya speculate kar sakti hai jo use worsens kare (e.g. added misprediction ya code-layout cache effects) jabki typical runs speed up hoti hain. WCET ko har build ke liye re-analyse karna padta hai.

Agar measured max = 612 aur 99.9th percentile = 580 hai, kya hard real-time deadline ke liye 600 ka bound acceptable hai?

Nahi. 600 ek already-observed value (612) se neeche baitha hai, isliye yoh demonstrably unsafe hai — unseen worst case toh door ki baat. Koi bhi hard bound saare observations se zyada hona chahiye aur unseen tail ko account karna chahiye.

Recall Ek-line self-test

Woh do properties batao jinhe har WCET bound ko trade off karna hota hai, priority ke order mein. ::: Safety (soundness) pehle — kabhi true worst case se neeche nahi; phir tightness — jitna ho sake uske karib.