Data hazards and forwarding - bypassing: Exercises

5.2.6 · D4 · Hardware › Processor Datapath & Pipelining › Data hazards and forwarding - bypassing

Yeh page tumhara self-test workbench hai data hazards aur forwarding ke liye. Har problem L1 (Recognition) se L5 (Mastery) tak graded hai. Problem padho, khud try karo, phir collapsible solution kholo. Har level ke baad ek [!mistake] callout hai jo us level ka sabse common trap steel-man karke batata hai.

Shuru karne se pehle, vocabulary fix kar lete hain taaki koi bhi symbol bina earn kiye na aaye.

Figure — Data hazards and forwarding - bypassing

Definition Pipeline registers — stages ke beech "shelves"

Har do stages ke beech ek chhota storage latch hota hai jo instruction ka data exactly ek cycle ke liye hold karta hai phir aage bhej deta hai. Hum inhe un do stages ke naam se bulate hain jinke beech yeh baitha hai:

ID/EX — jo ID ne produce kiya usse hold karta hai, EX ko feed karta hai.
EX/MEM — jo EX ne produce kiya usse hold karta hai (including ALU result), MEM ko feed karta hai.
MEM/WB — jo MEM ne produce kiya usse hold karta hai, WB ko feed karta hai.

Forwarding ke liye yeh kyun matter karte hain: freshly computed ALU result physically EX ke ek cycle baad EX/MEM register mein rehta hai, aur EX ke do cycles baad MEM/WB register mein. Yahi jagah hai jahan forwarding wire usse tap karti hai — WB ka wait karne ki zarurat nahi.

Prerequisites agar yeh sab shaky lag raha hai: 5.2.01-Five-stage-pipeline-basics aur 3.1.05-Register-file-design.

L1 — Recognition

Recall Solution 1.1

RAW hazard ke liye chahiye $Rd (i) = Rs (j) or Rt (j)$ aur $Rd (i) \neq = R0$ .

(a) Rd = R1, agli instruction R1 padh rahi hai. Hazard. ✅
(b) Rd = R1, agli instruction R6, R5 padh rahi hai — kabhi R1 nahi. No hazard.
(c) Destination R0 hai (hardwired zero, ise likhna no-op hai). R0 padhne se hamesha 0 milta hai, toh koi real hazard nahi.
(d) LW R1 likhta hai, agli instruction R1 padh rahi hai. Hazard — aur ek special wala (load-use hazard, L3 mein iske baare mein aur padhenge).

Recall Solution 1.2

Sources ID stage mein padhе jaate hain.
ALU results WB stage mein likhe jaate hain. Yeh gap (pehle padho, baad mein likho) hi poora reason hai ki hazards exist karte hain.

L2 — Application

Worked example Exercise 2.1 — Stall cycles count karo (no forwarding)

Back-to-back ALU instructions:

ADD R1, R2, R3
SUB R4, R1, R5

Sirf stalling ke saath (no forwarding), SUB sahi R1 padhe uske liye kitne bubble cycles insert karne honge? Register file ek cycle ki pehli half mein likhti hai aur doosri half mein padh ti hai (standard "write-then-read" register file).

Recall Solution 2.1

ADD R1 apne WB stage mein likhta hai. SUB R1 apne ID stage mein padh ta hai. Cycles align karo: ADD cycles 1–5 mein IF ID EX MEM WB occupy karta hai. SUB ka ID naturally cycle 3 mein hai. Write-then-read register file ke saath, SUB usi cycle mein padh sakta hai jab WB hota hai (cycle 5) kyunki write pehle complete hoti hai. Toh SUB ka ID cycle 5 tak push karna hoga. Iska natural ID cycle 3 tha → cycle 5 tak push karo → 2 bubbles. ✅

$stalls = (WB cycle of i) - (natural ID cycle of j) = 5 - 3 = 2$

Recall Solution 2.1... err, 2.2

ADD ka ALU result EX ke end (cycle 3) par exist karta hai, cycle 4 mein EX/MEM register mein baitha hai. SUB ko yeh apne EX ke start (cycle 4) par chahiye. Forwarding wire ise exactly time par deliver kar deti hai. 0 stalls. ✅ Yahi forwarding ka poora fayda hai ALU→ALU dependencies ke liye.

Worked example Exercise 2.3 — Kaunsa forwarding path?

ADD R1, R2, R3   # I1
OR  R6, R7, R8   # I2  (independent)
SUB R4, R1, R5   # I3  needs R1

Forwarding ke saath, kya SUB ko R1 EX/MEM register se milega ya MEM/WB register se? Kitne stalls?

Recall Solution 2.3

Cycle-align karo: I1 EX cycle 3 mein, toh I1 MEM mein (cycle 4) aur WB mein (cycle 5) hai. I3 EX cycle 5 mein hai. Cycle 5 mein, I1 ka result MEM/WB register mein aa chuka hai (yeh EX/MEM do cycles pehle chhod chuka tha). Toh SUB MEM/WB se forward karta hai. 0 stalls — independent OR ne conveniently gap fill kar diya.

L3 — Analysis

Worked example Exercise 3.1 — Load-use hazard jise forwarding

nahi hata sakta

LW  R1, 0(R2)    # I1: load
ADD R4, R1, R5   # I2: uses R1

Load ka data sirf MEM ke end par ready hota hai, EX par nahi. Full forwarding ke saath, kitne stalls unavoidable hain, aur forward kahan se aayega?

Recall Solution 3.1

LW ka data MEM ke end (cycle 4) par appear karta hai. ADD ko yeh apne EX ke start (cycle 4) par chahiye. Yeh same cycle mein overlap karte hain — tum ek value ko same cycle mein exist hone se pehle backward forward nahi kar sakte. Toh 1 bubble insert karo: ADD ka EX cycle 5 tak push karo. Ab LW ka data MEM/WB register mein hai aur cleanly forward hota hai. 1 stall, MEM/WB se forward. ✅ Yeh ek hazard hai jise forwarding akele poori tarah hide nahi kar sakta — dekho 6.2.03-Compiler-optimization-techniques jisme compilers is slot ko fill karne ke liye code reorder karte hain.

Worked example Exercise 3.2 — Double-write priority

ADD R1, R2, R3   # I1
ADD R1, R6, R7   # I2  (overwrites R1)
SUB R4, R1, R5   # I3  needs R1

Jab SUB EX tak pahunche, toh I1 aur I2 dono ne R1 produce kar diya hai. Ise kaunsa value use karna chahiye, aur kaunsa pipeline register yeh supply karta hai?

Recall Solution 3.2

Cycle-align karo: I2 EX cycle 4 mein → iska result EX/MEM mein cycle 5 mein hai. I1 ka purana result MEM/WB mein cycle 5 mein hai. I3 ka EX cycle 5 mein hai. SUB ko sabse recent R1 padhna chahiye, jo I2 ka hai. Forwarding unit priority rule use karta hai: EX/MEM forwarding, MEM/WB ko override karta hai. Toh EX/MEM se forward karo (I2 ki value). MEM/WB se lena stale I1 value pakad leta — ek subtle bug. ✅

Recall Solution 3.3

Input A (Rs side) ke liye EX/MEM condition check karo: $RegWrite = 1 \land Rd = 5 \neq = 0 \land Rd = 5 = Rs = 5$ → sab true. Toh ALU input A EX/MEM se forward hota hai. MEM/WB bhi match karta hai, lekin priority EX/MEM ko deti hai. Input B: Rt = 9, na Rd = 5 se match karta hai na kisi se → input B normally register file se padha jaata hai.

L4 — Synthesis

Worked example Exercise 4.1 — Poora block analyze karo

LW  R2, 0(R1)    # I1
LW  R3, 4(R1)    # I2
ADD R4, R2, R3   # I3
SW  R4, 8(R1)    # I4

Full forwarding ke saath, is block ko total kitne stall cycles chahiye? Har dependency aur uska resolution identify karo.

Recall Solution 4.1

Dependencies:

I3 R2 (I1 se) aur R3 (I2 se) use karta hai.
I4 R4 (I3 se) use karta hai.

Har ek check karo:

I2→I3 (R3): I2 ek load hai, I3 immediately next instruction hai jo ise use kare → classic load-use → 1 stall, phir MEM/WB se forward.
I1→I3 (R2): I1 ka data I3 se kaafi pehle available hai (I3 2 instructions baad hai, plus stall) → koi extra stall nahi, forward ho jaata hai.
I3→I4 (R4): ALU result → store. Store ko R4 apne MEM stage ke liye chahiye; forwarding usse time par deliver kar deta hai → 0 stalls.

Total = 1 stall cycle. ✅ Sirf tight load-use pair (I2→I3) kuch cost karta hai.

Recall Solution 4.2

Load-use gap mein ek independent instruction move karo. Yahan hum swap kar sakte hain taaki dono loads dependent ADD se pehle finish ho jaayein... lekin woh already adjacent hain. Trick yeh hai ki doosre load ko uske use se alag karo:

LW  R2, 0(R1)    # I1
LW  R3, 4(R1)    # I2
ADD R4, R2, R3   # I3  -- R3 par abhi bhi tight hai

Sirf inhi chaar instructions ke saath koi independent instruction hoist karne ke liye nahi hai, toh honest answer yeh hai: is exact block ke liye 1 stall irreducible hai. 0 reach karne ke liye, compiler ko zyada bade window se independent kaam dhundna hoga — jaise koi baad wala address computation upar le aana:

LW  R2, 0(R1)
LW  R3, 4(R1)
ADD R7, R1, R1   # independent filler yahan hoist kiya
ADD R4, R2, R3   # R3 ab MEM/WB forward se ready, 0 stalls
SW  R4, 8(R1)

0 stalls. ✅ Yahi instruction scheduling karta hai.

L5 — Mastery

Recall Solution 5.1

CPI = total cycles ÷ instructions.

Base cycles (ideal fill/drain) $= 100 + 4 = 104$ .
Without forwarding: $30 \times 2 = 60$ stall cycles add karo → $104 + 60 = 164$ cycles. $CPI = 164/100 = 1.64$ .
With forwarding: stalls remove ho gaye → $104$ cycles. $CPI = 104/100 = 1.04$ .
Speedup $= 164/104 \approx 1.577$ . ✅

Method 5.2.09-Pipeline-performance-analysis se liya gaya.

Worked example Exercise 5.2 — Mixed hazards, exact cycle count

LW   R1, 0(R10)   # I1
ADD  R2, R1, R11  # I2
SUB  R3, R2, R1   # I3
AND  R4, R3, R2   # I4

Full forwarding. Total stalls aur saari chaar instructions complete karne ke liye total cycles count karo.

Recall Solution 5.2

I1→I2 (R1): load-use, I2 immediately follow karta hai → 1 stall, phir MEM/WB forward.
I2→I3 (R2): ALU→ALU adjacent → EX/MEM forward → 0 stalls.
I3→I4 (R3): ALU→ALU adjacent → EX/MEM forward → 0 stalls.
I1→I3 (R1) aur I2→I4 (R2): do instructions apart → data ready, 0 stalls.

Total stalls = 1. Cycles = base fill/drain $(4 + 4 = 8)$ + 1 stall = 9 cycles. ✅

Recall Solution 5.3

ADD R1, R2, R3   # I1
OR  R6, R7, R8   # I2  (independent)
SUB R4, R1, R5   # I3  needs R1

Exercise 2.3 se, I3 ko R1 MEM/WB se milta hai (I1 WB mein hai jab I3 EX mein hai). Woh path hata do aur I3 ko feed nahi ho sakta → use 1 cycle stall karna padega jab tak register file khud R1 write-then-read se provide kare. Toh MEM/WB forwarding hatana area ke badle exactly 2 instructions apart wali har dependency par ek stall laata hai. ✅

Recall Quick self-quiz

ALU→ALU dependency, no forwarding, kitne stalls ::: 2 Load-use dependency, with full forwarding, kitne stalls ::: 1 Jab do writes same register ko target karein, kaunsa path jeetta hai ::: EX/MEM (most recent) Kaunsa stage source registers padhta hai ::: ID Kaunsa pipeline register same-cycle EX→next-EX forward ko feed karta hai ::: EX/MEM

Related deeper reading: 5.2.07-Control-hazardsand-branch-prediction, 5.3.02-Superscalar-out-of-order-execution.