Control hazards and pipeline flushes: Worked examples

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

Yeh page parent topic ka "drill ground" hai. Hum har tarah ki situation lete hain jo ek branch pipeline mein create kar sakti hai, aur unhe numbers ke saath grind karte hain. Agar aapne abhi tak pipeline, stage, flush, ya bubble words nahi sune, toh rukiye aur pehle 5.2.01-Pipelining-fundamentals aur parent note padh lijiye — yahan hum un pictures ko assume karke seedha arithmetic pe aate hain.

Scenario matrix

Neeche har cell ek alag case class hai. Jo 8 worked examples follow karte hain, woh announce karte hain ki woh kaun se cell(s) cover karte hain, aur milke woh sab ko hit karte hain.

Cell	Case class	Kya alag banata hai isse
A	Branch not taken, predict-not-taken	Lucky case: prediction sahi, zero flush
B	Branch taken, EX mein resolve	2 bubbles — classic penalty
C	Branch taken, ID mein resolve	1 bubble — early resolution
D	Degenerate: resolve-in-IF wali pipeline	0 bubbles — limiting "no penalty" case
E	Mixed program CPI with branch fraction $f$	Average-case performance formula
F	2-bit predictor state walk (loop)	Counter ka sign/direction kaafi iterations mein
G	Real-world word problem	Mispredictions se Speedup ka loss
H	Exam twist: nested / back-to-back branches	Ek saath do branches in flight

Har jagah use hone wale Symbols (ek baar define kiye):

Example B (aur D, C) — penalty kahan se aati hai?

Forecast: Padhne se pehle guess karo — bada $n$ matlab zyada ya kam bubbles? Abhi apne teen numbers likho.

Figure — Control hazards and pipeline flushes

Steps.

Fetch stage 1 (IF) mein hota hai. Yeh step kyun? Jis moment branch fetch hoti hai, agli cycle mein hum already following (straight-line) instruction fetch kar lete hain. Fetching kabhi pause nahi karti.
IF ke strictly baad aur resolve stage tak (inclusive) belt slots count karo. Kyun? "Branch IF mein" aur "branch resolved" ke beech har cycle exactly ek nayi straight-line instruction ko IF mein load karti hai. Woh doomed wali hain. Count $n - 1$ hai.
$n$ plug karo:
- IF mein resolve ( $n = 1$ ): $b = 1 - 1 = 0$ . → Cell D, limiting no-penalty case.
- ID mein resolve ( $n = 2$ ): $b = 2 - 1 = 1$ . → Cell C.
- EX mein resolve ( $n = 3$ ): $b = 3 - 1 = 2$ . → Cell B, the classic.

Verify: Parent ke cycle table mein (BEQ EX mein resolve karti hai), exactly ADD@104 aur SUB@108 bubbles ban gaye — yeh 2 hai, $b = 3 - 1 = 2$ se match karta hai. ✓ Units: instructions/cycles ka count, dimensionless. ✓

Recall Quick recall

Stage $n$ mein resolve ke liye penalty ::: $b = n - 1$ bubbles. Resolve-in-IF (b=0) sirf theoretical kyun hai? ::: Aap usi cycle mein branch outcome nahi jaaan sakte jisme aap use fetch karte ho — aapne abhi use decode bhi nahi kiya.

Example A — lucky path: prediction sahi, zero flush

Forecast: Zero? One? Two?

Steps.

Humne speculatively PC+4, PC+8 fetch kiye jab branch IF→ID→EX flow ki. Kyun? Predict-not-taken ka matlab hai "straight chalte raho" — exactly wahi jo PC+4 fetch karna karta hai.
Branch EX mein not-taken resolve karti hai. Yeh kyun matter karta hai? Jo straight-line instructions humne fetch ki thi woh sahi wali thi. Undo karne ko kuch nahi.
Bubbles insert kiye $= 0$ . Penalty $= 0$ cycles.

Verify: Prediction ("not taken") = outcome ("not taken") ⇒ sahi ⇒ $b = 0$ . Sanity: isliye predict-not-taken straight-line code par free hota hai aur sirf tab cost karta hai jab branch genuinely taken ho. ✓

Example E — ek real program ka average CPI

Forecast: Slowdown 20% se bada ya chhota? Ek guess likho.

Steps.

Branch per penalty (average) $= p_{t} \cdot b = 0.60 \times 2 = 1.2$ cycles. Multiply kyun? Sirf taken branches flush karti hain; not-taken wali 0 cost karti hain, toh hum $p_{t}$ se weight karte hain.
Saari instructions par spread penalty $= f \times (p_{t} \cdot b) = 0.20 \times 1.2 = 0.24$ . $f$ se multiply kyun? Sirf ek-paanchvaan instructions branches hain; instruction per average extra cost accordingly dilute hoti hai.
Effective CPI $= ideal CPI + penalty per instr = 1 + 0.24 = 1.24$ .
Slowdown $= \frac{1.24 - 1}{1} = 0.24 = 24%$ .

$CPI_{eff} = 1 + f p_{t} b = 1 + 0.20 \times 0.60 \times 2 = 1.24$

Verify: Units: cycles/instruction, dimensionless slowdown. Sanity: agar $p_{t} = 0$ (kabhi taken nahi) toh CPI→1 (free), aur agar $f = 1, p_{t} = 1, b = 2$ toh CPI $= 3$ (har instruction fully stall) — dono extremes sense karte hain. ✓

Example C — early resolution ek bubble bachata hai

Forecast: 1.24 se better ya worse?

Steps.

Naya penalty $b = n - 1 = 2 - 1 = 1$ bubble. Kyun? Ek stage pehle resolve ⇒ ek kam wrong-path instruction fetch ki gayi.
$CPI_{eff} = 1 + f p_{t} b = 1 + 0.20 \times 0.60 \times 1 = 1.12$ .
Example E se improvement $= 1.24 - 1.12 = 0.12$ CPI bachaa.

Verify: $b$ ko halve karna (2→1) branch penalty term ko halve karta hai ( $0.24 \to 0.12$ ), toh CPI 1.24 se 1.12 ho jaata hai. ✓ Yahi hai early-resolve hardware ka faayda — aur aage jaane ke liye 5.2.09-Branch-prediction-techniques dekho.

Example F — 2-bit predictor state walk

Forecast: 1 miss per loop? 2? Exit ke baad counter kahan land karta hai?

Steps.

Taken outcome ⇒ counter $\to min (3, c + 1)$ ; Not-taken ⇒ $\to max (0, c - 1)$ . Saturating kyun? Values 0 aur 3 par clamp hoti hain, toh "taken" ka lamba run confidence build karta hai par overflow nahi ho sakta.
99 taken outcomes: counter $3$ par pinned hai (already max, 3 rehta hai). Har baar Taken predict ⇒ 0 misses. Kyun? $3 \geq 2$ ⇒ predict Taken = actual Taken. ✓
Exit (not-taken): predicted Taken (counter=3 $\geq 2$ ) lekin actual Not-taken ⇒ 1 misprediction. Counter $\to 3 - 1 = 2$ (Weakly Taken).
Doosre loop ki pehli iteration (taken): counter $= 2 \geq 2$ ⇒ predict Taken = actual Taken ⇒ sahi, counter $\to 3$ phir se.
Per loop total = 1 misprediction (sirf exit). Do loops ⇒ 2 mispredictions total.

Verify: 1-bit predictor se compare karo: woh dono exit aur next-entry par miss karta = 2 per loop ⇒ do loops mein 4. 2-bit use half karta hai. Pehle exit ke baad final counter $= 2$ . ✓ Parent ke claim "1 misprediction per loop" se match karta hai. Aur behtar karne ke liye 5.2.09-Branch-prediction-techniques mein two-level predictors dekho.

Example G — word problem: mispredictions se speedup ka loss

Forecast: Kya hum phir bhi $5 \times$ ke kareeb pahunchte hain, ya branching use kha jaati hai?

Steps.

Effective CPI $= 1 + f p_{m} b = 1 + 0.25 \times 0.10 \times 2 = 1 + 0.05 = 1.05$ . Yahan $p_{t}$ nahi, $p_{m}$ kyun? Ek real predictor ke saath sirf mispredicted branches flush karti hain — woh fraction $p_{m}$ hai.
Real speedup 5-cycle non-pipelined machine ke against $= \frac{5}{CPI _{eff}} = \frac{5}{1.05} \approx 4.76$ .
Ideal ka fraction deliver kiya $= \frac{4.76}{5} = 0.952 = 95.2%$ .

Verify: $5/1.05 = 4.7619...$ ; pipeline promised $5 \times$ ka 95.2% hai. Sanity: ek perfect predictor ( $p_{m} = 0$ ) CPI 1 aur pura $5 \times$ deta hai; ek terrible wala ( $p_{m} = 1$ ) CPI $1.5$ , speedup $3.33$ deta hai. Hamara jawab sensibly beech mein baithta hai. ✓ Units: cycles cancel hote hain, speedup dimensionless hai. ✓

Example H — exam twist: do branches back-to-back

Worked example Ek branch jiska target dusri branch hai (Cell H)

Predict-not-taken, EX mein resolve ( $b = 2$ ). Instruction stream:

100: BEQ ... , 300   # Branch 1 — TAKEN
104: ADD            # wrong-path
108: SUB            # wrong-path
300: BEQ ... , 500   # Branch 2 (sahi target) — bhi TAKEN

Dono branches taken hain. Do branches mein total kitne bubbles hain, aur Branch 2 ke baad pehli useful instruction tak pahunchne mein kitne cycles lagte hain?

Forecast: Kya penalties add hoti hain? Overlap hoti hain? Ek bubble count guess karo.

Steps.

Branch 1 taken, EX mein resolve ⇒ 2 bubbles (ADD@104, SUB@108 flushed). Kyun? Standard $b = 2$ ; predicted straight-line path galat thi.
Flush ke baad, PC = 300; hum BEQ@300 fetch karte hain. Yeh ab ek fresh branch hai — pipeline ko yeh bhi nahi pata ki yeh ek branch hai, toh phir predict-not-taken 304, 308 fetch karta hai.
Branch 2 taken, EX mein resolve ⇒ 2 aur bubbles. Woh overlap kyun nahi karte? Branch 2 pipeline mein tab tak thi hi nahi jab tak Branch 1 ne PC redirect finish nahi kiya; unki penalties sequential hain, hidden nahi.
Total bubbles $= 2 + 2 = 4$ .
Branch 2 ke baad pehli useful post-instruction tak cycles: har taken branch apne correct target ke flow hone se pehle apna $b = 2$ penalty add karta hai, toh normal flow ke upar $2 + 2 = 4$ wasted cycles.

Verify: Resolve-in-EX ke saath do independent taken branches ⇒ $2 b = 2 \times 2 = 4$ total bubbles; penalties overlap nahi karti kyunki doosri branch ka fetch pehli ke redirect par depend karta hai. ✓ Yeh chained cost exactly wahi hai jis par 5.2.11-Speculative-execution aur achhe predictors (5.2.09-Branch-prediction-techniques) attack karte hain. Branch encoding details 4.3.08-Branch-instructions mein milti hain.

Recall Full self-test

Stage $n$ mein resolve ke liye penalty? ::: $b = n - 1$ bubbles. Predict-not-taken, branch not taken — bubbles? ::: 0 (prediction sahi). Master CPI formula? ::: $CPI_{eff} = 1 + f p_{m} b$ . Example E ka answer (f=0.20, p_t=0.60, b=2)? ::: CPI = 1.24, yaani 24% slowdown. Resolve EX→ID move karo: naya penalty? ::: b 2→1 drop karta hai, CPI 1.24→1.12. 2-bit predictor, loop do baar run, har baar 99 taken + 1 exit? ::: Total 2 mispredictions (1 per exit). Example G real speedup (f=0.25, p_m=0.10, b=2, ideal 5×)? ::: CPI 1.05, speedup ≈ 4.76 (ideal ka 95.2%). Do back-to-back taken branches, EX mein resolve? ::: Total 4 bubbles (penalties sequential hain).