Data hazards and forwarding - bypassing — Hinglish notes

5.2.6 · Hardware › Processor Datapath & Pipelining

What Are Data Hazards?

Why RAW Hazards Dominate

Ek classic 5-stage pipeline mein (IF → ID → EX → MEM → WB):

Instruction 1: ADD R1, R2, R3    # R1 = R2 + R3
Instruction 2: SUB R4, R1, R5    # R4 = R1 - R5  (needs R1 from I1)

Forwarding ke bina timeline:

Clock: 1    2    3    4    5    6    7
ADD:   IF   ID   EX   MEMWB
SUB:        IF   ID   EX   MEM  WB
              ↑
         Reads R1 here (cycle 3)
         But R1 written in cycle 5!

SUB instruction R1 ko ID stage mein (cycle 3) read karti hai, lekin ADD, R1 ko WB stage mein (cycle 5) write karta hai. Two-cycle gap = galat data.

Solution 1: Stalling (The Naive Fix)

Worked example Stalling Example

Problem Code:

ADD R1, R2, R3    # I1: R1 = R2 + R3
SUB R4, R1, R5    # I2: R4 = R1 - R5  (hazard!)

Stall Solution: Pipeline bubbles (NOPs) insert karo jab tak data ready nahi ho jaata.

Clock: 1    2    3    4    5    6    7    8
ADD:   IF   ID   EX   MEM  WB
SUB:        IF   [ID] [ID] [ID] ID   EX   MEM
                 stall stall stall

Yeh kyun kaam karta hai: Cycle 6 tak, ADD ne R1 ko register file mein write kar diya hoga (cycle 5 WB complete), toh SUB cycle 6 mein safely read kar sakti hai.

Cost: 3 wasted cycles = 3 bubbles = is sequence ke liye 3× slowdown.

Stall cycles kitni chahiye — derivation:

Data EX stage mein produce hota hai (ALU ops ke liye) → cycle $n + 2$ mein available (EX at $n$ , MEM at $n + 1$ , WB at $n + 2$ )
Data dependent instruction ko ID stage mein chahiye
Agar dependent instruction cycle $m$ mein hai, use data cycle $m + 1$ tak chahiye (ID stage)
Stalls required: $(n + 2) - (m + 1) = n - m + 1$

Consecutive instructions ke liye ( $m = n + 1$ ): Stalls = $n - (n + 1) + 1 = 0$ stalls? Galat! Yeh ignore karta hai ki data register file mein WB complete hone ke baad hi likha jaata hai.

Correct calculation: Agar instruction $i$ cycle $n$ mein EX mein hai, toh result cycle $n + 2$ (WB ke end) par likha jaata hai. Agar instruction $i + 1$ cycle $n + 1$ mein ID mein hai, toh woh cycle $n + 1$ mein read karta hai. Gap = $(n + 2) - (n + 1) = 1$ cycle... lekin register file read clock edge ke pehle hoti hai jahan write hoti hai. Actual gap = 2 cycles ALU-to-ALU dependency ke liye.

Solution 2: Forwarding/Bypassing (The Smart Fix)

Forwarding Paths: The Architecture

Key components:

Forwarding unit (hazard detection + control logic)
Multiplexers ALU inputs par (register file data vs. forwarded data mein se choose karne ke liye)
Pipeline registers jo result values forward carry karte hain (EX/MEM, MEM/WB)

Formula Forwarding Conditions

EX/MEM register se EX stage ALU input par forward karo agar:

&\text{EX/MEM.RegWrite} = 1 \\ &\land \text{EX/MEM.RegisterRd} \neq 0 \\ &\land\ \text{EX/MEM.RegisterRd} = \text{ID/EX.RegisterRs} \end{align}$$ ya $$\text{EX/MEM.RegisterRd} = \text{ID/EX.RegisterRt}$$ **Har condition kyun?** - $\text{RegWrite} = 1$: Instruction actually ek register write karti hai (branch/store nahi) - $\text{RegisterRd} \neq 0$: Hardwired zero register mein nahi likh raha - $\text{RegisterRd} = \text{RegisterRs/Rt}$: Producer ka destination, consumer ke source se match karta hai **MEM/WB register** se EX stage mein forward karo agar: - Same conditions, lekin MEM/WB pipeline register check karo - **Priority**: EX/MEM forwarding, MEM/WB par precedence leta hai (more recent result)

Forwarding logic ka derivation:

Hazard condition se start karo: EX stage mein instruction ko EX, MEM, ya WB stage mein instruction se data chahiye.

Case 1: EX-to-EX forwarding (1 cycle door)

ADD R1, R2, R3    # Cycle n: EX stage computes R1
SUB R4, R1, R5    # Cycle n: ID stage, cycle n+1: EX stage needs R1

Cycle $n + 1$ par:

ADD result EX/MEM pipeline register mein hai (abhi EX stage se nikla)
SUB EX stage mein hai, ALU input ke liye R1 chahiye

EX/MEM.ALUOutput → ALU input MUX se forward karo.

Case 2: MEM-to-EX forwarding (2 cycles door)

ADD R1, R2, R3    # Cycle n: EX, cycle n+1: MEM
AND R6, R7, R8    # Cycle n+1: EX (R1 use nahi karta)
SUB R4, R1, R5    # Cycle n+2: EX stage needs R1

Cycle $n + 2$ par:

ADD result MEM/WB pipeline register mein hai
SUB EX stage mein hai

MEM/WB.ALUOutput → ALU input MUX se forward karo.

Priority rule ka derivation: Agar EX/MEM aur MEM/WB dono ke paas same register ka data hai, toh kaunsa forward karein?

ADD R1, R2, R3    # I1: Cycle n+1: MEM stage (result in MEM/WB)
ADD R1, R6, R7    # I2: Cycle n+1: EX stage (result in EX/MEM)
SUB R4, R1, R5    # I3: Cycle n+1: ID stage, cycle n+2: EX stage

I1 aur I2 dono R1 write karte hain, lekin I2 more recent hai. I3 ko I2 ka result use karna chahiye.

Rule: EX/MEM forwarding (more recent) MEM/WB forwarding ko override karta hai.

Worked example Forwarding Example: ALU-to-ALU

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

Forwarding ke saath timeline:

Clock:  1    2    3    4    5    6    7
ADD:    IF   ID   EX   MEM  WB
SUB:         IF   ID   EX   MEM  WB
                       ↑
                  Forward from EX/MEM
AND:              IF   ID   EX   MEM  WB
                            ↑
                       Forward from MEM/WB
OR:                    IF   ID   EX   MEM  WB
                               ↑
                       Read from register file (no hazard)

Har step kyun?

SUB (cycle 4): ADD MEM stage mein hai, result EX/MEM register mein → SUB ke EX stage ALU input mein forward karo
AND (cycle 5): ADD WB stage mein hai, result MEM/WB register mein → AND ke EX stage ALU input mein forward karo
OR (cycle 6): ADD ka WB complete ho chuka hai, R1 register file mein hai → normal read, koi forwarding nahi chahiye

Performance: Zero stalls! Original 3-cycle penalty khatam.

Load-Use Hazards: Jab Forwarding Kaafi Nahi Hota

Worked example Load-Use Hazard

LW  R1, 0(R2)     # I1: Load R1 from memory
ADD R4, R1, R3    # I2: needs R1 (load-use hazard!)

Timeline:

Clock:  1    2    3    4    5    6
LW:     IF   ID   EX   MEM  WB
ADD:         IF   ID   [ID] EX   MEM
                       stall

Stall kyun?

LW data MEM stage ke end mein produce karta hai (cycle 4)
ADD ko data EX stage ke start mein chahiye (cycle 4 bina stall ke)
Forwarding ke saath bhi, data cycle 4 tak ready nahi, lekin ADD ko cycle 3 mein chahiye

Solution: 1 stall cycle insert karo, phir MEM/WB register se forward karo.

Yeh step kyun? Memory read MEM stage ke dauran hoti hai, isliye data MEM complete hone tak available nahi hota. Koi bhi forwarding path data ko exist hone se pehle nahi la sakta.

Load-use stalls ka formula:

1 & \text{if next instruction uses load result} \\ 0 & \text{if one instruction between load and use} \end{cases}$$

Worked example Compiler Optimization: Instruction Scheduling

Original code (load-use hazard hai):

LW  R1, 0(R2)
ADD R4, R1, R3    # Stall here!
SUB R5, R6, R7

Optimized code (compiler ne reorder kiya):

LW  R1, 0(R2)
SUB R5, R6, R7    # Independent instruction gap fill karti hai
ADD R4, R1, R3    # No stall! R1 is ready

Yeh kyun kaam karta hai: Jab ADD EX stage tak pahuncha (cycle 5), LW MEM stage complete kar chuka (cycle 4), aur data MEM/WB register se forward ho sakta hai. SUB instruction "load delay slot fill" karti hai.

Performance gain: Critical loops mein har load-use pair par 1 kam stall = significant speedup.

Forwarding Unit Implementation

Control logic ka derivation:

ForwardA ke liye (ALU input 1, Rs ke corresponding):

if (EX/MEM.RegWrite 
    and EX/MEM.RegisterRd ≠ 0 
    and EX/MEM.RegisterRd = ID/EX.RegisterRs)
then ForwardA = 10

else if (MEM/WB.RegWrite 
         and MEM/WB.RegisterRd ≠ 0
         and MEM/WB.RegisterRd = ID/EX.RegisterRs
         and not(EX/MEM hazard condition))  // Priority check
then ForwardA = 01

else ForwardA = 00

Priority check kyun? Agar EX/MEM aur MEM/WB dono match karein, toh hum more recent value (EX/MEM) chahte hain, isliye MEM/WB forwarding tab hi hoti hai jab EX/MEM match nahi karta.

ForwardB logic identical hai, lekin ID/EX.RegisterRt se compare karti hai.

Worked example Double Hazard

ADD R1, R2, R3    # I1
ADD R1, R1, R4    # I2: overwrites R1
ADD R5, R1, R6    # I3: which R1? (should be I2's result)

Timeline:

Clock:  1    2    3    4    5
I1:     IF   ID   EX   MEM  WB
I2:          IF   ID   EX   MEM
I3:               IF   ID   EX

Cycle 5 par:

I1 ka result MEM/WB.RegisterRd mein hai (= R1)
I2 ka result EX/MEM.RegisterRd mein hai (= R1)
I3 EX stage mein hai, R1 chahiye

Kaunsa forward karein? I2 ka result (more recent).

Yeh kyun kaam karta hai: Priority rule ensure karta hai ki EX/MEM forwarding, MEM/WB forwarding ko override kare. Yeh "most recent write" semantics ko sahi se handle karta hai.

Performance Impact Analysis

Formula CPI with Hazards

Ideal CPI = 1 (ek instruction per cycle) se shuru karo, penalties add karo: $CPI_{actual} = 1 + stalls per instruction$

Ek program ke liye jisme:

$f_{load}$ = fraction of instructions jo loads hain
$p_{use}$ = probability ki agli instruction load result use karti hai
$f_{branch}$ = fraction of branches (control hazards, alag topic)

$CPI_{stall-only} = 1 + f_{load} \cdot p_{use} \cdot 1$

Forwarding ke saath: ALU-to-ALU stalls khatam, sirf load-use stalls bachti hain.

Typical values: $f_{load} \approx 0.25$ , $p_{use} \approx 0.5$ (compiler scheduling ke bina)

$CPI = 1 + 0.25 \times 0.5 \times 1 = 1.125$

Pure stalling par forwarding ka speedup: 30% ALU hazards + 12.5% load hazards wale programs ke liye:

Forwarding ke bina: CPI = 1 + 0.30×2 + 0.125×3 = 1.975
Forwarding ke saath: CPI = 1 + 0.125×1 = 1.125
Speedup = 1.975/1.125 = 1.76×

Common mistake "Forwarding Saare Data Hazards Solve Kar Deta Hai"

Kyun sahi lagta hai: Forwarding complete solution lagti hai — data available hai, toh hamesha forward kyun nahi karein?

Kyun galat hai:

Load-use hazards: Data tab tak exist nahi karta jab tak memory read complete nahi ho jaati (MEM stage ke end), lekin agli instruction ko EX stage ke start mein chahiye (ek stage pehle). Physics jeet jaata hai.
Structural hazards: Agar register file mein sirf ek write port hai, toh kuch designs mein hum simultaneously do instructions mein forward nahi kar sakte.
Complexity limits: Full forwarding, n pipeline stages ke liye O(n²) forwarding paths maangti hai, jo deep pipelines ke liye impractical ho jaata hai.

Fix: Samjho ki forwarding ek optimization hai, panacea nahi. Fundamental timing constraints ke liye stalls abhi bhi zaroori hain. Compiler scheduling doosri line of defense hai.

Connections

5.2.01-Five-stage-pipeline-basics - Pipeline stages ka foundation jahan hazards hote hain
5.2.07-Control-hazardsand-branch-prediction - Doosra major hazard type (control flow)
5.2.09-Pipeline-performance-analysis - Hazards overall CPI ko kaise affect karte hain
5.3.02-Superscalar-out-of-order-execution - Modern processors mein advanced forwarding
3.1.05-Register-file-design - Woh hardware jise forwarding bypass karti hai
6.2.03-Compiler-optimization-techniques - Hazards minimize karne ke liye instruction scheduling

Recall 12-Saal Ke Bacche Ko Samjhao

Socho tum ek assembly line par Lego spaceships bana rahe ho. Tumhare paas 5 stations hain: pieces uthao (IF), instructions check karo (ID), pieces jodo (EX), ek box se special parts lagao (MEM), aur finished section shelf par rakh do (WB).

Ab, Station 3 ek red wing bana raha hai, aur Station 2 (bilkul peeche) ko wahi red wing body par lagaane ke liye chahiye. Lekin wing abhi shelf par nahi hai — woh Station 3 par abhi bhi ban rahi hai!

Buri solution: Poori line rok lo aur intezaar karo jab tak wing shelf par nahi aa jaati. Slow!

Smart solution (forwarding): Station 3 seedha wing Station 2 ko de deta hai. Pehle shelf par kyun rakhein agar agli wali ko abhi chahiye?

Lekin kabhi kabhi tumhe special parts box (memory) se ek piece chahiye. Woh box slow hai — tumhe jaana padta hai, unlock karna padta hai, aur piece dhundna padta hai. Forwarding ke saath bhi, tumhe ek baar wait karna padega kyunki piece literally exist nahi karta jab tak box nahi khola jaata. Yahi load-use hazard hai.

Forwarding teamwork ki tarah hai: result seedha use pass karo jise abhi chahiye, instead of pehle sab kuch away rakhne ke rules follow karne ke.

#flashcards/hardware

Pipeline mein data hazard kya hota hai? :: Jab ek instruction ko ek register value chahiye jo ek pehli instruction ne abhi tak write nahi ki, kyunki woh pichli instruction abhi bhi pipeline mein hai. Dependent instruction stale data read kar leti.

Teen types ke data hazards kya hain?

RAW (Read After Write - true dependency), WAR (Write After Read - anti-dependency), WAW (Write After Write - output dependency). Simple pipelines mein RAW sabse common hota hai.

Forwarding/bypassing kya hota hai?

Ek technique jo computed results ko pipeline registers (EX/MEM ya MEM/WB) se seedha dependent instructions ke ALU inputs par route karti hai, register file mein write-back ka intezaar kiye bina.

Load-use hazard kya hota hai?

Jab load ke turant baad wali instruction loaded value use karti hai. Forwarding ke saath bhi ek stall cycle zaroori hota hai kyunki data load ke MEM stage complete hone tak exist nahi karta.

5-stage pipeline mein do main forwarding paths kaunse hain?

EX/MEM se EX stage tak (ek cycle purane results ke liye) aur MEM/WB se EX stage tak (do cycle purane results ke liye). Jab dono match karein toh EX/MEM ko priority milti hai.

Forwarding load-use hazards kyun eliminate nahi kar sakti?

Loaded data MEM stage ke end tak exist nahi karta, lekin dependent instruction ko EX stage ke start mein chahiye (ek stage pehle). Data ko exist hone se pehle forward nahi kiya ja sakta.

Load-use hazard mein forwarding ke saath kitne stall cycles chahiye?

Ek stall cycle. Forwarding ke bina, architecture ke hisaab se do ya teen cycles lagte.

Forwarding unit kya hota hai?

Combinational logic jo pipeline registers monitor karta hai, destination aur source registers compare karta hai, aur ALU input multiplexers ke liye ForwardA/ForwardB control signals generate karta hai.

EX/MEM forwarding ko MEM/WB forwarding par priority kyun milti hai?

Kyunki EX/MEM mein more recent result hota hai. Agar do instructions same register write karein, toh dependent instruction ko newer value use karni chahiye.

ForwardA = 10 ka kya matlab hai?

ALU result ko EX/MEM pipeline register se ALU input A (pehla operand) par forward karo. 10 EX/MEM forwarding ka encoding hai.

Hazards ke context mein instruction scheduling kya hota hai?

Ek compiler optimization jo independent instructions ko reorder karti hai taaki load delay slots fill ho sakein aur pipeline stalls minimize ho sakein, program semantics preserve karte hue.

EX-to-EX forwarding opportunity kab banti hai?

Jab EX/MEM.RegWrite = 1 ho, EX/MEM.RegisterRd ≠ 0 ho, aur EX/MEM.RegisterRd ya toh ID/EX.RegisterRs ya ID/EX.RegisterRt ke barabar ho.

Forwarding logic mein RegisterRd ≠ 0 kyun check karte hain?

Register 0 MIPS aur RISC-V jaise architectures mein hardwired zero hota hai, isliye usme writes se real dependencies nahi banti. R0 ke liye koi forwarding nahi chahiye.

Pipeline bubble kya hota hai?

Pipeline mein insert kiya gaya ek NOP (no operation) execution stall karne ke liye, effectively ek empty pipeline stage banata hai jahan koi useful kaam nahi hota.

Forwarding CPI kaise improve karta hai?

Zyaadatar ALU-to-ALU data hazard stalls eliminate karke. Typical improvement: CPI ≈ 1.975 (sirf stall) se CPI ≈ 1.125 (forwarding ke saath), 1.76× speedup.