Control hazards and pipeline flushes: Exercises — Hinglish deep dive

5.2.8 · D4 · Hardware › Processor Datapath & Pipelining › Control hazards and pipeline flushes

Ye problems pehchaanane se shuru hote hain ki flush kya hota hai, aur aage jaake penalty budgets aur predictor behaviour design karne tak jaate hain. Har solution ek collapsible callout ke andar chhupa hai taaki tum pehle khud try kar sako. Agar koi term unfamiliar lage, toh Control hazards and pipeline flushes dobara padh lo — yahan kuch bhi aisa use nahi kiya gaya jo wahaan pehle na aaya ho.

Prerequisite muscles: 5.2.01-Pipelining-fundamentals (paanch stages IF, ID, EX, MEM, WB), 4.3.08-Branch-instructions (branch hota kya hai), aur 5.2.05-Data-hazards-and-forwarding (bubbles ek concept ke roop mein).

Definition Do words jinpar hum rely karenge: CPI aur control signals

CPI = cycles per instruction. Yeh average number of clock cycles hai jo processor ek instruction ke liye poore program mein kharach karta hai. Ek perfect pipeline har cycle mein ek instruction run karta hai, isliye uska base $CPI = 1$ hota hai. Har flush wasted cycles add karta hai, CPI ko 1 se upar dhakelta hai. Kam CPI = faster machine (same kaam ke liye kam cycles).

Control signals woh chhote on/off wires hain jo decoder har instruction ke saath attach karta hai, datapath ko batane ke liye kya karna hai. Yahan do matter karte hain:

RegWrite — ek 1-bit wire; jab 1 ho toh instruction apna result ek register mein likhne ki permission rakhta hai, jab 0 ho toh kuch nahi likhta.
MemWrite — ek 1-bit wire; jab 1 ho toh instruction memory mein store kar sakta hai, jab 0 ho toh kuch store nahi karta.

Ek bubble simply ek aisa in-flight instruction hota hai jiska RegWrite aur MemWrite dono forcefully 0 kar diye gaye hain — yeh stages mein flow karta rehta hai lekin kuch bhi observable nahi badalta. Physically flush isi tarah kiya jaata hai.

Figure — Control hazards and pipeline flushes

Figure 1 — Pipeline timeline. Teal BEQ branch cycle 3 mein EX par resolve hota hai. Do orange instructions (ADD, SUB) jo uske peeche cycles 2 aur 3 mein fetch hue the woh wrong path par hain; cycle 4 mein woh hatched "BUB" bubbles ban jaate hain. "Jahaan hum fetch karte hain (IF)" aur "jahaan resolve hota hai (EX)" ke beech ki horizontal distance exactly utni hi hai jitne instructions throw away kiye jaate hain.

Figure dekho: branch teal mein hai, cycle 3 mein EX par resolve ho raha hai. Uske peeche fetch hue do orange boxes (cycles 2 aur 3) wrong-path instructions hain. "Jahaan hum fetch karte hain" (IF) aur "jahaan resolve hota hai" (EX) ke beech ka gap exactly utna hi hai jitne instructions humein throw away karne padte hain.

Intuition KYUN penalty teen numbers ka

product hoti hai Neeche har exercise "extra cycles per instruction" ko aise compute karta hai: $P (branch) \times P (misprediction) \times (flush count) .$ Ise left to right ek lambe instruction stream par filters ki chain ki tarah padho:

Saare instructions mein se, sirf $P (branch)$ fraction hi branches hain — baaki kabhi control hazard cause nahi karte.
Un branches mein se, sirf $P (misprediction)$ fraction hi galat guess karte hain — sahi guess se zero cycles waste hote hain.
Har galat guess exactly (flush count) wasted cycles kharach karti hai (wrong-path instructions bubbles mein convert ho jaate hain).

Multiply karne se average wasted cycles milte hain jo har instruction par spread ho jaate hain. Hum multiply karte hain (add nahi) kyunki har factor pehle waale group ko narrow down karta hai: instructions mein se branches, phir branches mein se mispredicts, phir mispredict ke cycles. Woh average precisely CPI ka 1 ke base se upar uthna hai.

Level 1 — Recognition

Exercise 1.1

Ek classic 5-stage RISC pipeline (IF, ID, EX, MEM, WB) mein jahaan branch EX stage mein resolve hota hai, branch taken hone par kitne instructions flush karne padte hain?

Recall Solution

Branch cycle $t$ par fetch (IF) hota hai. Yeh cycle $t + 2$ par EX reach karta hai (IF→ID→EX do hops hain). Beech mein fetcher aage bhag gaya:

Cycle $t + 1$ : woh instruction fetch hua jo ab ID mein baitha hai.
Cycle $t + 2$ : woh instruction fetch hua jo ab IF mein baitha hai.

Yeh 2 instructions wrong path par hain. Page ke upar ki stage numbering use karke ( $IF = 1$ , $EX = 3$ ): $flush count = (stage where resolved) - (stage where fetched) = 3 - 1 = 2$ Answer: 2 instructions.

Exercise 1.2

Blank bharo: Ek flushed instruction ko bubble mein convert kiya jaata hai, matlab uske control signals RegWrite aur MemWrite ko kis value par set kiya jaata hai, aur kyun?

Recall Solution

Dono 0 par set kiye jaate hain (page ke upar control-signal definition yaad karo).

RegWrite = 0 → instruction koi register nahi likhta.
MemWrite = 0 → instruction koi memory nahi likhta.

Inhe 0 set karne se instruction architecturally invisible ho jaata hai: yeh baaki stages mein kisi bhi dusre instruction ki tarah flow karta hai, lekin kuch bhi jo programmer observe kar sake wo nahi badalta. Hum ise delete nahi karte, kyunki beech mein ek slot delete karna perfectly-clocked stages ko desynchronise kar deta.

Level 2 — Application

Exercise 2.1

Ek program mein 20% branch instructions hain. Pipeline branches ko EX mein resolve karti hai (2-cycle penalty) aur har taken branch par flush karta hai. Agar 60% branches taken hain, toh average extra cycles per instruction (CPI penalty) kya hai?

Recall Solution

Sirf taken branches par flush ka cost hota hai (yeh design implicitly predict-not-taken assume karta hai — ek taken branch ka matlab hai fetch kiye gaye not-taken instructions galat the), isliye yahan $P (misprediction) = P (taken)$ . Intuition box se product rule apply karo: $penalty per instr = P (branch) \times P (taken) \times flush cycles$ $= 0.20 \times 0.60 \times 2 = 0.24 cycles/instruction$ Answer: 0.24 extra cycles per instruction (yaani CPI 1 se 1.24 ho jaata hai).

Exercise 2.2

2.1 jaisi hi machine lekin ek hardware trick branches ko ID mein resolve karne deti hai (1-cycle penalty). CPI penalty recompute karo, aur 2.1 ke upar percentage improvement batao.

Recall Solution

Flush cycles 2 se 1 ho jaati hain: $0.20 \times 0.60 \times 1 = 0.12 cycles/instruction$ Improvement: $\frac{0.24 - 0.12}{0.24} = 0.50 = 50%$ Answer: 0.12 cycles/instruction, branch penalty mein 50% reduction. Kyun: ek stage pehle resolve hone ka matlab hai fetcher sirf ek galat instruction se aage bhaga hai do ke bajaye, isliye exactly aadha wasted work khatam ho jaata hai.

Level 3 — Analysis

Exercise 3.1

Ek processor static predict-not-taken use karta hai, 2-cycle EX resolution ke saath. Branches instructions ka 20% hain. Measurements dikhate hain ki branches 65% time taken hoti hain. (a) Average branch penalty per instruction kya hai? (b) Architect static predict-taken propose karta hai jisme target ID mein compute hota hai (guess galat hone par 1-cycle penalty). Assume karo predict-taken exactly tab galat hoti hai jab branch not taken ho. Kaun sa scheme better hai?

Recall Solution

(a) Predict-not-taken. Galat hota hai jab branch taken ho (penalty 2): $0.20 \times 0.65 \times 2 = 0.26 cycles/instruction$

(b) Predict-taken. Galat hota hai jab branch not taken ho ( $1 - 0.65 = 0.35$ ), penalty 1: $0.20 \times 0.35 \times 1 = 0.07 cycles/instruction$

Compare: $0.07 < 0.26$ , isliye yahan predict-taken better hai — yeh zyada common outcome bhi sahi guess karta hai aur galat hone par chhota penalty deta hai (1 vs 2 cycles). Answer: (a) 0.26; (b) 0.07 — predict-taken jeet jaata hai.

Exercise 3.2

Ek 2-bit saturating counter trace karo (states: 00 Strongly-NT, 01 Weakly-NT, 10 Weakly-T, 11 Strongly-T; predict taken agar state ≥ 10 ho). Yeh 11 (Strongly Taken) se start karta hai. Ek loop branch 4 baar taken hoti hai phir ek baar not-taken (loop exit), aur yeh poora pattern repeat hota hai. Steady state mein ek poore loop pass mein kitne mispredictions hote hain?

Solve karne se pehle, Figure 2 mein state machine study karo — yeh exactly dikhata hai ki "taken" aur "not-taken" outcomes counter ko left aur right kaise dhakelte hain, aur kyun do beech wale "weak" states ise memory dete hain.

Figure 2 — 2-bit saturating counter. Char states left (Strongly Not-Taken, 00) se right (Strongly Taken, 11) tak chalte hain. Teal "taken" arrows state ko ek step right push karte hain; orange "not-taken" arrows ek step left push karte hain; ends saturate ho jaate hain (wahi ruk jaate hain). Predictor do right states (≥ 10) ke liye taken guess karta hai aur do left states (≤ 01) ke liye not-taken. Ek single galat outcome sirf ek step nudge karta hai, isliye prediction flip karne ke liye do consecutive galat outcomes chahiye.

Recall Solution

Counter walk karo, har step track karne ke liye Figure 2 use karo. "Predicts T" matlab state ≥ 10. Taken → count up (max 11); Not-taken → count down (min 00).

Actual	State before	Predict	Correct?	State after
T	11	T	✓	11
T	11	T	✓	11
T	11	T	✓	11
T	11	T	✓	11
NT (exit)	11	T	✗	10
T (re-enter)	10	T	✓	11

Exit ke baad counter sirf 10 par slip karta hai (phir bhi "taken", Figure 2 ka right-hand teal region), isliye agli taken iteration sahi predict hoti hai aur ise 11 par wapas le jaati hai. Answer: exactly 1 misprediction per loop pass — exit wali.

Isliye 2 bits, 1 bit se better hai: ek single anomaly (exit) prediction flip nahi kar sakti, kyunki do bits do consecutive galat outcomes maangti hai trend change karne ke liye.

Level 4 — Synthesis

Exercise 4.1

Design-budget problem. Tumhare paas 5-stage pipeline hai, base CPI = 1. Instruction mix: 20% branches, aur branches mein 70% taken hain. Tum transistors ek cheez par kharch kar sakte ho:

Option A: branch resolution ko ID mein move karo → galat guess par penalty 1 cycle, predict-not-taken rakho.
Option B: 90% accuracy wala dynamic predictor add karo, 2-cycle EX resolution rakho.

Har ek ka resulting CPI compute karo aur winner choose karo.

Recall Solution

Yaad raho $CPI = 1 + branch penalty$ , aur branch penalty $= P (branch) \times P (misprediction) \times flush count$ .

Option A (predict-not-taken, galat sirf tab jab taken, penalty 1): $penalty = 0.20 \times 0.70 \times 1 = 0.14$ $CPI_{A} = 1 + 0.14 = 1.14$

Option B (predictor saare branches mein se 10% galat, regardless of direction, penalty 2): $penalty = 0.20 \times 0.10 \times 2 = 0.04$ $CPI_{B} = 1 + 0.04 = 1.04$

Compare: $1.04 < 1.14$ , isliye Option B (dynamic predictor) jeetta hai. Uski high accuracy (sirf 10% galat) Option A ko beat karta hai jo sasta flush deta hai lekin phir bhi kaafi baar galat hota hai. Answer: CPI_A = 1.14, CPI_B = 1.04 → Option B choose karo.

Exercise 4.2

4.1 ke dono improvements combine karo: dynamic predictor 90% accuracy ke saath aur resolution ID mein move (penalty 1). Same mix (20% branches). CPI kya hai, aur us base machine ke upar speedup kya hai jo har taken branch par 2 cycles flush karta hai (70% taken)?

Recall Solution

Base machine (no prediction, predict-not-taken, 2-cycle EX): $CPI_{ba se} = 1 + 0.20 \times 0.70 \times 2 = 1 + 0.28 = 1.28$

Combined machine (10% mispredict, 1-cycle penalty): $CPI_{co mb o} = 1 + 0.20 \times 0.10 \times 1 = 1 + 0.02 = 1.02$

Speedup (same clock, same instruction count → CPI ratio, kyunki kam cycles per instruction matlab proportionally kam total time): $speedup = \frac{CPI _{ba se}}{CPI _{co mb o}} = \frac{1.28}{1.02} \approx 1.255$ Answer: CPI ≈ 1.02, speedup ≈ 1.25× (lagbhag 25% faster).

Level 5 — Mastery

Exercise 5.1

Upar define ki gayi 7-stage deep pipeline use karte hue, ek branch EX3 (stage 5) mein resolve hota hai jabki fetch stage 1 mein hoti hai. Instruction mix: 25% branches, 60% taken. Ek predictor ki accuracy $a$ hai. (a) Flush count $f$ , misprediction rate $(1 - a)$ , aur branch fraction $b$ ke terms mein general penalty formula likho. (b) Minimum accuracy $a$ nikalo jo chahiye taaki branch penalty per instruction 0.05 cycles se zyada na ho.

Recall Solution

(a) Flush count $f = (resolve stage) - (fetch stage) = 5 - 1 = 4$ instructions. Flush sirf misprediction par hota hai, rate $(1 - a)$ par, aur sirf branch fraction $b$ ke liye — wahi teen-factor product jaise har pehle exercise mein tha: $penalty = b \times (1 - a) \times f = 0.25 \times (1 - a) \times 4$

(b) Require karo ki penalty $\leq 0.05$ : $0.25 \times (1 - a) \times 4 \leq 0.05$ $1.0 \times (1 - a) \leq 0.05 \Rightarrow (1 - a) \leq 0.05$ $a \geq 0.95$ Answer: (a) penalty $= b (1 - a) f$ ; (b) $a \geq 95%$ accuracy chahiye. Dhyan do ki taken-fraction 60% kabhi appear nahi hoti — ek directional predictor ke saath, jo matter karta hai woh yeh hai ki guess sahi hai ya nahi, branch actually kis direction mein gayi yeh nahi. Deep pipelines (bada $f$ ) bahut accurate predictors demand karte hain precisely kyunki har mistake 4 flushed slots ka kharch karti hai.

Exercise 5.2

Cycle-count synthesis. Neeche wala loop apna body 1000 baar chalata hai. Bottom branch BNE 999 baar taken hai (loops back) aur ek baar not-taken (exit). Resolution EX mein hai (2-cycle flush). (a) predict-not-taken aur (b) Strongly-Taken se start karne wale 2-bit predictor ke under total flush cycles compare karo.

loop: ...          # loop body (no branches)
      BNE loop      # taken 999, not-taken 1

Recall Solution

(a) Predict-not-taken. Predictor hamesha "not taken" guess karta hai, isliye yeh har taken branch (unhe mein se 999) par galat hota hai, har baar 2 flush cycles ka cost. Single not-taken exit sahi predict hoti hai (0 cost). $999 \times 2 = 1998 flush cycles$

(b) 2-bit predictor, Strongly-Taken (11) se start. Yeh saari 999 taken iterations ke liye taken sahi predict karta hai (counter 11 par pinned, kabhi strongly-taken state nahi chhodta). Yeh sirf single exit (1 event) par mispredict karta hai, 2 cycles ka cost: $1 \times 2 = 2 flush cycles$

Answer: (a) 1998 cycles waste, (b) 2 cycles waste — 999× reduction.

Concluding discussion: 2-bit predictor loops ke liye dramatically better hai kyunki yeh common (taken) case sahi guess karta hai, jabki predict-not-taken ek backward-branching loop ke liye exactly ulta hota hai — yeh practically har iteration galat guess karta hai. Yeh single example isliye important hai ki real machines loops ke liye predict-not-taken par kabhi rely nahi karti aur dynamic prediction use karti hain (ya kam se kam "backward branches predicted taken" heuristic). 1998 wasted cycles mein se almost sab simply khatam ho jaate hain.

Recall Self-check summary (sab try karne ke baad reveal karo)

Branch penalty hamesha ek product hoti hai ::: $P (branch) \times P (misprediction) \times (flush count)$ Flush count formula ::: (resolve stage index) − (fetch stage index) CPI ka matlab kya hai ::: average cycles per instruction; base 1, har flush se upar uthta hai 2-bit loops mein 1-bit se kyun better hai ::: ek anomaly (loop exit) 2-bit prediction flip nahi kar sakti, isliye re-entry abhi bhi sahi predict hoti hai Bubble actually kya hota hai ::: ek in-flight instruction jiska RegWrite=0, MemWrite=0 — flow karta hai lekin kuch nahi badalta

Dekho bhi: 5.2.11-Speculative-execution ke liye kya hota hai ek achi prediction ke baad (aage run karna), aur Hinglish mein 5.2.08 Control hazards and pipeline flushes (Hinglish) walkthrough.