Data hazards and forwarding - bypassing: Worked examples

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

Yeh page parent topic ki "haath gande karo" wali companion hai. Parent ne bataya tha ki forwarding kya hoti hai. Yahan hum machine ko har tarah ke cases pe run karte hain — ek ke baad ek instruction pair — jab tak koi surprise na bache.

Shuru karne se pehle, ek vaada: hum koi bhi stage ka naam, register-name, ya pipeline-register name use nahi karenge bina pehle yeh bataye ki woh kya hai. Aao woh vocabulary ek baar picture ke form mein define kar lein, aur phir reuse karein.

Definition Pipeline registers — "stations ke beech ki shelves"

Do stations ke beech ek latching shelf hoti hai jo is instruction ke partial results ko ek tick aage le jaati hai. Hum ek shelf ko un do stations ke naam se bulate hain jo woh bridge karti hai:

ID/EX — source register numbers aur values hold karta hai jab instruction EX mein enter karti hai.
EX/MEM — jis waqt EX khatam hota hai, fresh ALU result hold karta hai.
MEM/WB — woh result ek tick baad hold karta hai, register file mein land hone se thodi der pehle.

Forwarding = answer ko directly inhi shelves (EX/MEM ya MEM/WB) se pakadna aur ALU input ko dena, register file tak pahunchne ka intezaar karne ki bajaye. ALU input pe chooser ek multiplexer (mux) hai: ek switch jo kaunsi wire ALU ko feed kare yeh decide karta hai.

Figure — Data hazards and forwarding - bypassing

Picture dekho: do shelves (EX/MEM, MEM/WB) mein se har ek ke paas ek red return wire hai jo ALU ke aage wale mux pe loop back karti hai. Saari forwarding ka kaam bas itna hai ki kab woh muxes flip karni hain.

Scenario matrix

Neeche har worked example un cell(s) ke saath tagged hai jo woh cover karta hai. Milaakar yeh poori table fill karte hain.

Cell	Kya vary karta hai	Kaun sa sawaal jawab karta hai
A. Distance = 1 (EX→EX)	producer 1 instr aage	EX/MEM se forward karo
B. Distance = 2 (MEM→EX)	producer 2 instr aage, beech mein gap	MEM/WB se forward karo
C. Distance ≥ 3	producer kaafi aage	No forward — register file mein already hai
D. Double hazard / priority	do producers same register mein likhte hain	Kaunsi shelf jeetegi?
E. Load-use (woh jo forwarding fix nahi kar sakti)	producer ek `LW` hai, distance 1	1 stall phir forward
F. Zero/degenerate: R0 destination	producer R0 mein likhta hai	Koi hazard hi nahi
G. Both operands hazarded	Rs aur Rt dono stale hain	Do muxes ek saath fire karte hain
H. Store-uses-result	consumer ek `SW` hai	MEM ko forward karo, EX ko nahi
I. Word problem (real code)	compiler-scheduled loop	Kitne stalls bache count karo
J. Exam twist	stall khatam karne ke liye reordering	Dekho 6.2.03-Compiler-optimization-techniques

Notation jo ab se use karenge (pehle define ki, phir reuse karenge):

$Rd$ = producer instruction ka destination register (jisme woh likhti hai).
$Rs, Rt$ = woh do source registers jo consumer padhta hai.
"EX/MEM.Rd" = shelf EX/MEM ki destination-number line pe woh value. MEM/WB ke liye bhi aisa hi.
Parent se forwarding rule, phir se bataya taaki hum ise apply kar sakein:

Ab, examples.

Worked example Example 1 — Cell A: distance-1, EX/MEM se forward

ADD R1, R2, R3   # I1: produces R1
SUB R4, R1, R5   # I2: needs R1, one instruction later

Forecast: Forwarding ke saath kitne stalls? R1 kaunsi shelf se aayega?

Steps

Inhe time mein line up karo. I1 cycle 3 pe EX mein hai, cycle 4 pe MEM mein. I2 cycle 4 pe EX mein hai. Yeh step kyun? Forwarding ek timing question hai — I2 ke liye ALU input exactly uske EX (cycle 4) pe chahiye. Hume pata hona chahiye ki I1 ka answer cycle 4 pe physically kahan hai.
Cycle 4 pe answer locate karo. I1 ne cycle 3 ke end pe EX choda, toh uska result cycle 4 ke dauran shelf EX/MEM pe hai. Yeh step kyun? Woh shelf sabse fresh copy hai — aur exactly woh wire hai jo mux grab kar sakta hai.
EX/MEM check apply karo. RegWrite=1 (ADD likhta hai), Rd = R1 ≠ 0, aur EX/MEM.Rd (R1) = I2 ka Rs (R1). ✔ EX/MEM se forward karo.
Stalls count karo. Value exactly tab available hai jab chahiye → 0 stalls.

Verify: distance-1 ALU→ALU with forwarding ka stall formula $0$ deta hai; forwarding ke bina parent ne 2-cycle gap dikhaya tha. Saved = 2 cycles. ✔ (ex1_stalls mein check kiya).

Worked example Example 2 — Cell B: distance-2, MEM/WB se forward

ADD R1, R2, R3   # I1: produces R1
AND R6, R7, R8   # I2: independent (R1 ko touch NAHI karta)
SUB R4, R1, R5   # I3: needs R1, two instructions later

Forecast: Example 1 wali shelf, ya koi alag?

Time-line. I1 EX@3, MEM@4, WB@5. I3 EX@5. Kyun: hum phir "kab chahiye" (I3 ka EX = cycle 5) ko "answer kahan hai" se compare karte hain.
Cycle 5 pe R1 locate karo. I1 ne do ticks pehle EX choda; uska result cycle 5 tak shelf MEM/WB pe slide ho gaya hai. Kyun: ek tick per shelf — cycle 4 pe EX/MEM, cycle 5 pe MEM/WB.
Checks apply karo. Cycle 5 pe EX/MEM mein I2 ka result (R6) hai, jo ≠ R1 → EX/MEM check fail. MEM/WB.Rd = R1 = I3 ka Rs → MEM/WB se forward karo.
Stalls = 0. Independent AND ne naturally gap fill kar diya.

Verify: distance-2 with forwarding → 0 stalls (ex2_stalls). ✔

Worked example Example 3 — Cell C: distance-3, koi forwarding nahi chahiye

ADD R1, R2, R3   # I1
AND R6, R7, R8   # I2
OR  R9, R7, R8   # I3
SUB R4, R1, R5   # I4: needs R1, three later

Forecast: Kya yahan koi hazard hai?

Time-line. I1 WB@5. I4 ID@5, EX@6. Kyun: ab hum I4 ke ID (cycle 5) se compare karte hain, jahan source registers file se padhe jaate hain.
Key timing fact — write-then-read split clock. Register files cycle ki pehli half mein likhti hain aur doosri half mein padhti hain ("write-before-read" file, dekho 3.1.05-Register-file-design). Cycle 5 pe, I1 ka WB pehli half mein R1 likhta hai; I4 ka ID doosri half mein ise padhta hai. Kyun: yahi exact reason hai ki distance-3 ko forwarding ki zarurat nahi — file already fresh value deliver kar deti hai.
Conclusion. Dono forwarding checks fail (I4 ke EX tak koi shelf R1 hold nahi kar rahi), aur kisi ki zarurat bhi nahi. 0 stalls, 0 forwards.

Verify: distance ≥ 3 → 0 stalls, 0 forwards (ex3_forwards). ✔

Worked example Example 4 — Cell D & G: double hazard + priority, dono operands

ADD R1, R2, R3   # I1: writes R1
ADD R1, R1, R6   # I2: writes R1 AGAIN (aur I1 se R1 padhta hai)
SUB R4, R1, R1   # I3: DONO operands ke liye R1 padhta hai

Forecast: I3 R1 do baar padhta hai — kis producer ka R1 milega, aur kya I2 ko bhi forward chahiye?

I2 ka apna hazard (Rs = R1 from I1). I2 ke EX (cycle 4) pe, I1 EX/MEM pe hai → I2 ke pehle ALU input ko EX/MEM se forward karo. (Cell A phir, nested.) Kyun: har dependency independently check hoti hai; I2 ek consumer bhi hai aur producer bhi.
I3 apne EX (cycle 5) pe. R1 kiske paas hai?
- EX/MEM mein I2 ka brand-new R1 hai (I2 ne cycle 4 pe EX choda).
- MEM/WB mein I1 ka purana R1 hai. Dono match karte hain! Priority rule kyun? I3 ko R1 ki sabse recent write use karni chahiye, jo I2 ki hai. EX/MEM jeetta hai.
I3 ke dono operands Rs=R1 aur Rt=R1 hain. Do alag muxes (ek per ALU input) dono EX/MEM select karte hain. Kyun: Rs aur Rt ki apni-apni forwarding logic hoti hai; dono ke ek saath fire karne mein koi rokaawat nahi.
Result: I3 ko I2 ka R1 dono inputs pe milta hai. 0 stalls.

Verify: correct value chain — agar R2=10,R3=5 toh I1:R1=15, I2:R1=15+R6(=2)=17, I3:R4=17−17=0 (ex4_r4). ✔

Worked example Example 5 — Cell E: load-use hazard jo forwarding CHUPA NAHI SAKTI

LW  R1, 0(R2)    # I1: LOAD — R1 sirf MEM ke baad milta hai
SUB R4, R1, R5   # I2: needs R1, distance 1

Forecast: Example 1 jaisa (0 stalls)? Dhyan se — load alag hota hai.

Load ka data kab ready hota hai? Ek ALU op EX mein khatam hota hai. Ek load sirf MEM ke baad khatam hota hai (memory read hi uska kaam hai). Toh I1 ka R1 cycle 4 ke end tak real nahi hota. Yeh step kyun: yahi poora point hai — producer ka result arithmetic ke liye ek station baad aata hai.
I2 ko kab chahiye? I2 ka EX cycle 4 hai — usi cycle jab load memory padh raha hai. Data exist hi nahi karta. Koi wire aisi value carry nahi kar sakti jo compute hi nahi hui.
Fix: 1 stall, phir forward. I2 ko ek cycle ke liye freeze karo (ek bubble). Ab I2 ka EX cycle 5 hai. I1 ka loaded R1 cycle 5 pe MEM/WB pe hai → MEM/WB ko I2 ke store-data path pe MEM mein forward karo. Kyun: stalling woh ek tick khareedta hai jo MEM ko chahiye; forwarding phir baaki ka gap cover kar leta hai.
Cost: exactly 1 stall — 2 nahi, kyunki forwarding abhi bhi ek bachata hai. Figure dekho: red forward arrow MEM/WB se shuru hoti hai, single grey bubble ke baad.

Verify: load-use with forwarding → exactly 1 stall (ex5_stalls). ✔

Worked example Example 6 — Cell F: producer R0 mein likhta hai (degenerate case)

ADD R0, R2, R3   # I1: R0 mein "likhta" hai — lekin R0 hardwired 0 hai
SUB R4, R0, R5   # I2: R0 padhta hai

Forecast: Distance 1 aur Rd = Rs... zaroor ek hazard hai?

EX/MEM check literally apply karo. RegWrite=1, EX/MEM.Rd = R0, aur R0 = I2 ka Rs. Teen mein se do match karte hain — lekin $\neq = 0$ guard fail ho jaata hai. Guard kyun exist karta hai: R0 MIPS/RISC-V mein hamesha 0 hota hai; register file uske writes ko ignore kar deti hai. Uski value kabhi change nahi ho sakti, toh woh kabhi stale nahi ho sakti.
Conclusion: forwarding suppressed. I2 file se constant 0 padhta hai. 0 stalls, 0 forwards.

Verify: R0 destination → forward=False (ex6_forward). ✔

Worked example Example 7 — Cell H: consumer ek store hai (MEM ko forward karo, EX ko nahi)

ADD R1, R2, R3   # I1: produces R1
SW  R1, 0(R6)    # I2: R1 ko memory mein STORE karta hai

Forecast: Kya R1 ALU ko forward hogi?

Store ko R1 kis kaam ke liye chahiye? Arithmetic ke liye nahi — ALU sirf address 0+R6 compute karta hai. R1 woh data hai jo likha ja raha hai, aur woh MEM stage mein use hoti hai. Yeh kyun matter karta hai: "EX pe chahiye" rule operands ke liye tha. Store-data ek station baad chahiye.
Timing. I2 ka MEM cycle 5 hai. I1 ka R1 cycle 5 pe MEM/WB pe hai → MEM/WB ko directly store-data path pe MEM mein forward karo (ek alag mux, "MEM forwarding"). Alag mux kyun: value ki destination memory-write port hai, ALU input nahi.
Stalls = 0. MEM ko forward karne ke liye ek station ka extra slack hai.

Verify: store consumer → 0 stalls (ex7_stalls). ✔

Worked example Example 8 — Cell I: real-world word problem (array increment loop)

Ek compiler yeh inner loop emit karta hai (har array element mein 1 add karo):

LW   R1, 0(R2)    # load A[i]
ADD  R1, R1, R3   # A[i] + 1   (R3 = 1)
SW   R1, 0(R2)    # store back
ADDI R2, R2, 4    # i++

Forecast: Full forwarding ke saath har loop iteration mein total kitne stall cycles?

LW → ADD. Load-use, distance 1 → 1 stall (Cell E). Loaded R1 bubble ke baad MEM/WB se forward hota hai. Kyun: loop mein yahi ek unavoidable stall hai.
ADD → SW. ADD EX mein R1 produce karta hai; SW usse store-data ke roop mein MEM pe chahiye → MEM/WB ko MEM pe forward karo (Cell H). 0 stalls.
SW, ADDI R1 se independent hain (ADDI R2 touch karta hai). Koi hazard nahi. 0 stalls.
Iteration per total = 1 stall.

Verify: total loop stalls = 1 (ex8_stalls). ✔ Us 1 stall/iteration ka performance impact 5.2.09-Pipeline-performance-analysis mein analyze kiya gaya hai.

Stall LW→ADD ke beech hai (woh adjacent hain). Agar koi independent instruction unke beech hoti, toh bubble useful kaam se fill ho jaata. Kyun: Example 2 yaad karo — ek independent instruction distance-1 ko distance-2 mein convert kar deti hai, aur distance-2 ko stall ki zarurat nahi.
ADDI R2,R2,4 R1 se independent hai — lekin yeh R2 mein likhta hai, jo SW ... 0(R2) aur agla LW 0(R2) use karte hain. Ise reorder karna addresses badal deta hai. Free nahi hai. Exam ka answer: next address ek scratch register mein compute karo, YA unroll karo taaki ek independent load slot fill kare. Kyun: twist test karta hai ki kya tum R2 side-dependency notice karte ho (ek WAR-flavoured concern) — tum ise blindly move nahi kar sakte.

Scheduled version (do elements unrolled, loads hoisted):

LW   R1, 0(R2)
LW   R4, 4(R2)     # independent load fills the LW->ADD gap
ADD  R1, R1, R3    # R1 now ready, no stall
ADD  R4, R4, R3
SW   R1, 0(R2)
SW   R4, 4(R2)
ADDI R2, R2, 8

Stalls ab = 0 — doosra load pehle ADD ke liye bubble slot occupy kar leta hai.

Verify: scheduled loop stalls = 0 (ex9_stalls). ✔ Yeh scheduling exactly wahi hai jo out-of-order engines hardware mein karte hain — dekho 5.3.02-Superscalar-out-of-order-execution.

Recall Self-check

Distance-1 ALU→ALU with forwarding mein kitne stalls lagte hain? ::: 0 (EX/MEM se forward). Ek load jo bilkul agali instruction ko feed kare mein kitne stalls lagte hain? ::: 1 (phir MEM/WB se forward). Do producers R5 mein likhte hain; consumer R5 padhta hai — kaunsi shelf jeetti hai? ::: EX/MEM (zyada recent result). Producer R0 mein likhta hai — forward karo ya nahi? ::: Nahi — $\neq = 0$ guard rok deta hai. SW ka stored register kis stage ko forward hota hai? ::: MEM (store-data port), EX ko nahi.