WCET (Worst Case Execution Time) analysis

5.5.13 · Coding › Embedded Systems & Real-Time Software

Isse ek bridge design karne ki tarah socho: tum average traffic ke liye load capacity calculate nahi karte—tum worst possible scenario ke liye calculate karte ho (maximum trucks, wind, earthquake ek saath). WCET wahi worst-case thinking hai, code execution time ke liye.

What Problem Does WCET Solve?

The Real-Time Scheduling Challenge

Ek hard real-time system mein, tasks ki deadlines hoti hain. Schedulability prove karne ke liye (ki saare tasks deadlines meet karein), tumhe chahiye:

$R_i=C_i+I_i\le D_i$

Jahaan:

• $R_i$ response time (jab task complete hoti hai)
• $C_i$ = worst-case execution time (WCET)
• $I_i$ = interference higher-priority tasks se
• $D_i$ = deadline

Yeh formula kyun? Response time = apni execution + doosron ke block karne ka time. Agar yeh tumhari deadline se zyada ho jaaye, tum fail ho gaye. Accurate WCET ke bina, yeh analysis bekar hai—garbage in, garbage out.

Key properties:

• Safe: WCET ≥ actual execution time SAARI runs ke liye
• Tight: WCET reality ke jitna close ho sake (bahut loose → wasted resources, unschedulable systems)
• Platform-dependent: CPU, cache, memory, compiler ke saath badalta hai

The WCET Analysis Problem: Why It's Hard

Three Layers of Complexity

1. Path Complexity (Control Flow) Tumhare code mein branches, loops, function calls hain. Code ke through kaunsa path sabse lamba hai?

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;
}

Mushkil kyun? Tumhare paas $2^{\text{branches}}$ possible paths hain. Loops ki data-dependent iteration counts ho sakti hain. Sabse lamba path dhundhna generally NP-hard hai.

2. Processor Complexity (Hardware Timing) Modern CPUs instructions ko fixed time mein execute nahi karte:

• Pipelines: instructions overlap hoti hain, stalls hote hain
• Caches: hit = 1 cycle, miss = 100+ cycles
• Branch prediction: correct = fast, misprediction = pipeline flush
• Interrupts: execution ko unpredictably delay kar sakte hain

Yeh kyun matter karta hai? Wohi instruction 1 cycle ya 300 cycles le sakti hai, cache state par depend karte hue. Ek loop jo arrays access karta hai uski timing har iteration par wildly different ho sakti hai.

3. Compiler Optimizations Compiler tumhara code transform kar deta hai:

• Functions inline kar deta hai
• Instructions reorder karta hai
• Loops unroll karta hai
• Branches merge/eliminate karta hai

Mushkil kyun? Jo execute hota hai woh tumhara source code nahi hai. Machine code ki timing characteristics bilkul alag ho sakti hain.

$\text{WCET}={\sum }_{\text{paths}}{\max }_{\text{path}}\left({\sum }_{\text{blocks in path}}{T}_{\text{block}}\right)$

Jahaan $T_{\text{block}}$ depend karta hai:

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

Isse derive karte hue: "Execution time = instruction times ka sum" se shuru karo. Lekin kaun si instructions execute hoti hain? Yeh path problem hai. Aur har ek kitni time leti hai? Yeh hardware problem hai. WCET saare possible paths par maximum hai, us path par worst-case hardware behavior consider karte hue.

WCET Analysis Approaches

1. Static Analysis (Analytical Method)

Code ko run kiye bina analyze karo. Control flow aur hardware timing ke models banao.

Kaise kaam karta hai:

Step 1: Control Flow Graph (CFG) Banao

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

Har block = straight-line code (koi branches nahi). Edges = control flow.

Step 2: Flow Constraints Se Annotate Karo User ya automated analysis constraints add karta hai:

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

Constraints kyun? Inke bina, analyzer infinite loops ya har branch par worst-case assume kar leta hai, jo absurdly large WCET deta hai.

Step 3: Hardware Timing Model Karo Har block ke liye, timing compute karo considering:

• Cache analysis: kaun se accesses hit/miss hain
• Pipeline analysis: stalls, hazards
• Branch prediction: mispredictions

Step 4: Longest Path Ke Liye Solve Karo Yeh ek Integer Linear Programming (ILP) problem ban jaata hai:

$\max {\sum }_i{x}_i\cdot T_i$

Subject to:

• $x_i\in \{0,1\}$ (block execute hua ya nahi)
• Flow constraints: ${\sum }_{\text{in edges}}={\sum }_{\text{out edges}}$ (conservation)
• Loop bounds: $x_{\text{loop back}}\le N\cdot x_{\text{loop header}}$

ILP kyun? Yeh optimal path dhundhta hai jo execution time maximize kare, saare constraints respect karte hue. Model ke liye yeh exact hai.

Analysis:

• Block A: 5 cycles (hamesha ek baar execute hota hai)
• Loop: $n-1$ iterations
  • Block B: 3 cycles/iteration
  • Block C: 4 cycles/iteration
  • Block D: worst case = har iteration par taken (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$

$n=1000$ ke liye: WCET = 12,994 cycles

Yeh step kyun?

• Block A, E ek baar execute hote hain: boundary conditions
• Loop worst case: saari iterations longest path leti hain (if-branch hamesha taken)
• Block D timing: cache miss assume karo (array access ke liye worst case)

2. Measurement-Based Analysis

Actual hardware par code run karo carefully chosen inputs ke saath, execution time measure karo, safety margin add karo.

Kaise kaam karta hai:

Step 1: Test Cases Generate Karo Aisi inputs banao jo trigger karti hain:

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

Step 2: Execution Time Measure Karo Hardware timers ya trace tools use karo har test case ka timing capture karne ke liye.

Step 3: Statistical Analysis Agar exhaustive testing possible nahi hai:

• Bahut saare random inputs run karo
• Measurements ko distribution fit karo
• Tail estimate karne ke liye Extreme Value Theory (EVT) use karo

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

Safety margin kyun? Tum saare possible inputs/states test nahi kar sakte. Margin untested scenarios account karta hai.

10,000 runs ke measurements:

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

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

Yeh kyun kaam karta hai? Agar tumhari testing thorough hai, toh observed maximum true WCET ke close hota hai. Margin cover karta hai:

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

Limitation: Tum kabhi 100% sure nahi ho sakte ki tumne worst case dhundh liya.

3. Hybrid Analysis

Static aur measurement approaches combine karo:

• Control flow, loop bounds ke liye static analysis use karo
• Basic block timing ke liye measurements use karo (chhote code segments measure karna asaan hai)
• Unhe combine karo: static solver measured block times use karta hai

Hybrid kyun? Static analysis complex hardware (cache, pipeline) ke saath struggle karta hai. Measurements real hardware capture karti hain lekin control flow exhaustively test nahi kar sakti. Hybrid dono ke best features leta hai.

Cache Analysis: Sabse Mushkil Problem

Caches sabse badi timing variability cause karti hain. ==Cache hit 1-5 cycles, miss = 100-300 cycles==.

Cache Behavior Classification

Har memory access ke liye, classify karo as:

1. Always Hit (AH): Definitely cache mein hai

   • Example: Chhoti array par loop jo cache mein fit ho jaaye

2. Always Miss (AM): Definitely cache mein nahi hai

   • Example: Kisi bhi data ka pehla access, ya eviction ke baad access

3. Unknown (U): History par depend karte hue hit ya miss ho sakta hai

   • Example: Data-dependent address wala access

WCET analysis: Har access ke liye worst case assume karo

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

Analysis:

• Pehli iteration: $\text{arr}[0]$ = cache miss (AM) → 100 cycles
• Agar array size ≤ cache size: baad ke $\text{arr}[i]$ = cache hit (AH) → 5 cycles each
• Agar array size > cache size: saare accesses = miss (AM) → 100 cycles each

Case 1: Chhoti array (cache mein fit ho jaaye) $\text{WCET}=100+(N-1)\times 5$

Case 2: Badi array (fit nahi hoti) $\text{WCET}=N\times 100$

Yeh difference kyun? Cache reuse! Chhoti arrays resident rehti hain, badi arrays khud ko hi evict karti rehti hain.

Common WCET Analysis Tools

• aiT: Commercial static analyzer, complex processors support karta hai (ARM, PowerPC)
• Bound-T: Open-source, simple microcontrollers par focus
• Chronos: Academic tool, caches aur pipelines handle karta hai
• RpiTime: Instrumentation ke saath measurement-based
• OTAWA: Custom WCET analyzers banane ka framework

Galti 1: Average-Case ya Typical Measurements Use Karna

❌ Galat:

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

Kyun sahi lagta hai: 80 cycles sabse bura hai jo tumne dekha, toh safe lagta hai.

Fix: Tumne saare inputs/states test nahi kiye. True worst case 200 cycles ho sakta hai. Measurement-based ke liye hamesha safety margin add karo, ya guarantees ke liye static analysis use karo.

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

Galti 2: Cache Effects Ignore Karna

❌ Galat:

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

Kyun sahi lagta hai: Tumne instruction timing lookup kiya, usne kaha "load = 5 cycles."

Fix: Woh cache-hit timing hai. Agar big_array cache mein fit nahi hoti, toh har access miss hai (100 cycles). Real WCET ≈ 100,000 cycles—20× underestimate!

✅ Sahi: Cache analysis karo. Agar array > cache size hai, misses assume karo: $\text{WCET}=1000\times 100=100,000$ cycles.

Galti 3: Constraints Ke Bina Unbounded Loops

❌ Galat:

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

Kyun sahi lagta hai: "Sensor driver yeh handle karta hai, theek rahega."

Fix: Static analyzers ko explicit bounds chahiye. Inke bina, WCET infinite ya absurdly large hoga.

✅ Sahi: Annotation ya code constraint add karo:

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

Ab analyzer finite WCET compute kar sakta hai.

Practical WCET-Aware Programming

Analyzability Ke Liye Design Karo

1. Unbounded Loops Avoid Karo

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

2. Critical Paths Mein Data-Dependent Branches Avoid Karo

// Analyze karna mushkil:
if (sensor_value > threshold) { /* variable path */ }
 
// Asaan (agar possible ho):
result = calculate_bothpaths();  // Straight-line code

3. Cache Interference Minimize Karo

• Hot loops chhote rakho (instruction cache mein fit ho jaayein)
• Predictable data access patterns use karo (sequential, random nahi)

4. Code Ko Constraints Se Annotate Karo

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

Task: Fuel injection calculation, har 1ms mein complete honi chahiye (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! ✓

Har step kyun?

• Summing: Tasks sequentially execute hoti hain (worst case: koi overlaps nahi)
• Individual WCETs: Har function ki static analysis + measurement se
• Check: $300<1000$ → Deadline 70% margin ke saath meet hoi

Agar WCET 1100 µs hota, toh deadline miss hota—engine misfire karta.

Verification aur Validation

Hum Kaise Jaanein Ki Hamara WCET Correct Hai?

1. Static Analysis: Mathematically sound agar model accurate hai

   • Validation: Measurements se compare karo (WCET ≥ saare measured times hone chahiye)

2. Measurement-Based: Sufficient testing ke saath hi sound hai

   • Validation: Confidence intervals, stress testing, mutation testing use karo

3. Certification: Safety-critical systems ke liye (DO-178C, ISO 26262)

   • Tool qualification required hai
   • Traceable analysis artifacts
   • Independent review

WCET bilkul waisi hi hai, lekin computer programs ke liye. Jab ek computer koi important cheez control kar raha hota hai (jaise car ke brakes ya plane ka autopilot), toh program ko ek deadline tak apna kaam khatam karna hota hai. Agar woh late hua, toh buri cheezein hoti hain—brakes kaam nahi karte, plane crash ho jaata hai!

Toh engineers poochhhte hain: "Is program ko lene mein WORST-CASE time kitna hai?" Average time nahi, usual time nahi, balki absolute sabse slow jo KABHI BHI ho sake. Wahi WCET hai.

Yeh figure out karna mushkil kyun hai? Kyunki:

1. Tumhare program ke alag-alag paths hain (jaise bus stop tak alag-alag routes lene ki tarah—kuch zyada lambe hain)
2. Computer ki speed badlati rehti hai (jaise kabhi tum tez chalte ho, kabhi thake hone ki wajah se slow)
3. Computer ke "memory shortcuts" kabhi kaam karte hain, kabhi nahi (jaise kabhi tumhare joote darwaze ke paas hote hain, kabhi unhe dhundhna padta hai)

WCET analysis aise hai jaise HAR possible subah map out karo, including sabse worst wali jab SAB KUCH galat ho jaaye (joote kho gaye, toothbrush nahi mil raha, bag chhupi hui hai), aur ensure karo ki us subah bhi tum bus pakad lo. Isi tarah engineers ensure karte hain ki real-time computer systems hamesha safe rahein!

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

Connections

• Real-Time Scheduling Algorithms — WCET schedulability analysis ka input hai (Rate Monotonic, EDF)
• Cache Memory Architecture — Cache behavior samajhna WCET ke liye crucial hai
• Control Flow Graph (CFG) — Static WCET analysis ki foundation
• Interrupt Handling — Interrupts non-determinism add karte hain, WCET complicate karte hain
• Static Program Analysis — WCET abstract interpretation, data flow analysis use karta hai
• Formal Verification Methods — WCET analysis formal timing verification ka part hai
• Safety-Critical Software Development — DO-178C, ISO 26262 certification ke liye WCET zaroori hai
• Embedded Linux and RTOS — RTOS WCET ke liye better timing predictability provide karta hai
• Compiler Optimizations — Optimizations WCET affect karti hain, WCET-aware compilation chahiye

#flashcards/coding

WCET kya hai aur real-time systems ke liye kyun critical hai? :: WCET (Worst-Case Execution Time) wo maximum time hai jo ek task saare possible inputs aur hardware behaviors ke across execute hone mein le sakta hai. Yeh critical hai kyunki real-time systems WCET use karke schedulability prove karte hain—ki tasks deadlines meet karengi. Accurate WCET ke bina, tum hard real-time systems mein safety guarantee nahi kar sakte.

Measurement-based WCET analysis ki fundamental limitation kya hai? :: Tum saare possible inputs, initial states, aur hardware behaviors exhaustively test nahi kar sakte. Measured maximum true worst case nahi ho sakta. Iske liye safety margins add karne padte hain, lekin tumhare paas static analysis jaisi mathematical certainty kabhi nahi hoti.

Concept Map