Data hazards and forwarding - bypassing: Visual walkthrough

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

Step 1 — Do instructions, ek shared register

KYA. Hum do instructions line up karte hain jahan doosri instruction woh reads karti hai jo pehli writes karti hai.

ADD R1, R2, R3   # I1: put (R2 + R3) into R1
SUB R4, R1, R5   # I2: needs R1, then R4 = R1 - R5

KYUN. Kuch bhi fix karne se pehle, hume collision dekhni padegi. Word data hazard ka simple matlab hai: reader writer ke khatam hone se pehle aa jaata hai. Ise concrete banane ke liye hume ek producer (I1) aur ek consumer (I2) chahiye jo register R1 share karein.

PICTURE. Har instruction paanch boxes ki train hai — paanchon pipeline stages. Kyunki pipeline overlap karti hai, I2 ek clock baad I1 ke start hoti hai. Dono rows ko do trainen samjho jo ek platform ke farak pe hain.

Figure — Data hazards and forwarding - bypassing

Step 2 — "Produce" aur "consume" ke exact clock cycles mark karo

KYA. Hum do moments pe clock number stamp karte hain jo matter karte hain: jab R1 paida hota hai aur jab R1 chahiye hota hai.

KYUN. Hazard ek timing problem hai, isliye hume ise cycles mein measure karna hoga, vibes mein nahi. Do sawaal:

R1 ki value produce kab hoti hai? ALU use I1 ke EX stage ke end pe finish karta hai.
R1 ki value register file mein kab likhi jaati hai? I1 ke WB stage ke end pe — do cycles baad.
I2 R1 kab read karta hai? I2 ke ID stage ke dauran.

PICTURE. Red dot woh hai jab ALU R1 produce karta hai (end of EX, cycle 3). Blue dot woh hai jab I2 register file se R1 read karne ki koshish karta hai (uska ID, cycle 3). Purple dot woh hai jab R1 actually register file mein store hota hai (end of WB, cycle 5).

Dots dekho: I2 cycle 3 mein read karta hai, lekin value cycle 5 tak file nahi hoti. Yahi gap hai.

Value read in cycle 3 vs. value stored in cycle 5 — so I2 grabs the OLD R1

exactly why forwarding is needed

Step 3 — "Produced early" kyun poora opportunity hai

KYA. Hum kuch hopeful notice karte hain: R1 exist karta hai (end of EX, cycle 3) usse kaafi pehle jab yeh file hota hai (end of WB, cycle 5).

KYUN. Naive fix — stalling — I2 ko register file ka intezaar karvata hai. Lekin register file ek slow middle-man hai. Result pehle se hi ALU output par ek wire pe baitha hai jis pal EX khatam hota hai. Hum jo tool reach karte hain woh "wait" nahi hai; woh hai "re-route". produce → register file → read ki jagah hum karte hain produce → seedha agle ALU tak.

PICTURE. Lamba detour (grey, register file ke through) versus shortcut (mint, seedha across). Shortcut hi woh hai jo "forwarding" literally hai.

Step 4 — Result physically kahan wait karta hai? Pipeline registers

KYA. Hum un chhote latches ko naam dete hain jo stages ke beech hain aur ek result ko exactly ek cycle ke liye hold karte hain: ID/EX, EX/MEM, MEM/WB.

KYUN. Value forward karne ke liye hume pata hona chahiye ki jis waqt hume chahiye, woh kis wire pe rehti hai. Har do stages ke beech ek pipeline register baitha hai — flip-flops ki ek row jo ek stage ka output agle cycle mein carry karti hai. I1 ke EX chhodne ke baad, uska ALU result gayab nahi hota; woh EX/MEM register mein park ho jaata hai. Ek cycle baad woh MEM/WB register mein slide ho jaata hai.

PICTURE. Datapath skeleton: chaar pipeline registers vertical bars ke roop mein, ALU EX mein, aur register file ID mein. ALU output EX/MEM bar ko feed karta hai (ALUOutput label ke saath).

Step 5 — Case A: 1-cycle-away neighbour (EX→EX forward)

KYA. I2 seedha I1 ke baad aati hai. Hum EX/MEM se I2 ke EX stage mein forward karte hain.

KYUN. Jis cycle mein I2 EX mein hai aur R1 chahiye, I1 ka result kahan hai? I1 bilkul ek stage aage hai — MEM mein — toh uska ALU result EX/MEM register mein baitha hai. Yahi sabse fresh copy hai. Wahan se grab karo.

PICTURE. Mint arrow follow karo: woh EX/MEM bar se nikalta hai aur I2 ke ALU ke top input pe land karta hai. Register file (blue) poori tarah bypass ho jaati hai.

Step 6 — Case B: 2-cycles-away producer (MEM→EX forward)

KYA. Producer aur consumer ke beech ek unrelated instruction hai. Hum MEM/WB se instead forward karte hain.

ADD R1, R2, R3   # I1: produces R1
AND R6, R7, R8   # I2: does NOT use R1
SUB R4, R1, R5   # I3: needs R1, two behind I1

KYUN. Jab I3 EX tak pahunchta hai, I1 do stages aur aage chal chuka hai — woh ab WB mein hai, toh uska result MEM/WB register mein rehta hai, EX/MEM mein nahi. Same idea, alag pipeline register. Teen ya zyada instructions peeche koi bhi producer register file mein time pe likh chuka hota hai, toh forwarding ki zaroorat nahi.

PICTURE. Coral arrow MEM/WB bar se start hota hai (Step 5 ke source se ek bar daayein) aur I3 ke ALU input pe land karta hai.

Step 7 — Tie-breaker: jab do match karein toh kaunsi copy?

KYA. Jab EX/MEM aur MEM/WB dono same register number hold karein, hum newer wala (EX/MEM) choose karte hain.

KYUN. Do writes to R1 ek read se pehle consider karo:

ADD R1, R2, R3   # I1: old R1
ADD R1, R6, R7   # I2: newer R1  ← this is the one I3 must see
SUB R4, R1, R5   # I3: reads R1

Jab I3 EX mein hai: I2 ka result EX/MEM mein hai (fresh), I1 ka result MEM/WB mein hai (stale). Program order kehta hai I3 ko latest writer, I2, ki value use karni chahiye. Toh EX/MEM jeet ta hai.

PICTURE. Do arrows I3 ke ALU ki taraf aim kar rahe hain. Mint wala (EX/MEM, newer) solid hai aur chosen hai; coral wala (MEM/WB, older) dashed hai aur ek chhote "×" se block hai.

Two producers of R1 in flight — which does the consumer get?

the more recent one, forwarded from EX/MEM (EX/MEM overrides MEM/WB)

Step 8 — Woh ek case jise forwarding nahi bacha sakta: load-use hazard

KYA. Jab producer ek load (LW) hai, uski value EX ke end pe ready nahi hoti — woh MEM ke end pe aati hai. Ek unavoidable stall rehta hai.

LW  R1, 0(R2)    # value of R1 lands only at end of MEM
SUB R4, R1, R5   # needs R1 in its EX — one cycle too soon

KYUN. ALU op ke liye result EX ke baad exist karta hai, toh ek EX→EX forward next instruction ko time pe pahunch sakta hai. Load ke paas EX ke baad forward karne ke liye kuch nahi hai — data abhi bhi memory se aa raha hai. Jab tak woh exist karta hai (end of MEM), consumer ka EX already guzar chuka hota hai. Forwarding value ko time mein sideways shift kar sakta hai zero cycles se, peeche nahi. Toh hum exactly ek bubble insert karte hain, phir MEM/WB se forward karte hain.

PICTURE. Load ki value ek box too late appear hoti hai; ek single grey bubble SUB ko ek cycle delay karta hai, jiske baad coral MEM/WB arrow use reach kar sakta hai.

Why can't forwarding fully cure a load-use hazard?

the load's data isn't ready until end of MEM, one cycle too late for the next instruction's EX, so one stall is unavoidable

Ek picture summary

Upar ki saari cheez, compressed: ALU result EX/MEM latch pe paida hota hai, MEM/WB latch mein age badhta hai, aur har ALU input pe ek multiplexer freshest available copy choose karta hai — EX/MEM pehle, phir MEM/WB, warna register file — jabki ek load single bubble force karta hai.

Recall Feynman retelling — ek story ki tarah bolo

Do instructions naak-se-naak chalti hain. Pehli ek number banati hai jis pal uska ALU fire hota hai, lekin pipeline ke rules kehte hain "teen steps baad register cabinet mein file karo." Doosri instruction, itne mein, cabinet ke paas bahut jaldi sprint kark aati hai aur kal ka number pakad leti.

Trick simple hai: number ko cabinet ke lamba raaste se mat bhejo. Number pehle se ek wire pe baitha hai — ALU ke baad wali chhoti holding latch mein (EX/MEM), ya ek latch aur aage (MEM/WB). Toh hum us latch se seedha doosri instruction ke ALU tak ek shortcut wire chalate hain. Ek chhota switch (multiplexer) choose karta hai: freshest latch use karo agar uske paas number hai, warna purana latch, warna cabinet pe fall back karo.

Agar do pehle ki instructions ne same register mein likha hai, hum hamesha newer wala lete hain (EX/MEM), kyunki cabinet eventually wahi hold karti. Aur ek zidd ka case hai — load — jahan number memory se aata hai aur ALU crowd se ek step baad tak ready hi nahi hota; wahan hum exactly ek wasted cycle nigal lete hain, phir usually forward karte hain.

Yeh bhi dekho: control hazards ek alag tarah ke stall (branches) handle karte hain, aur superscalar / out-of-order machines forwarding ko full dependency networks mein generalize karti hain.