Control hazards and pipeline flushes: Visual walkthrough

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

Koi bhi symbol aane se pehle, hum us picture par agree karte hain jis par sab kuch tika hai: the pipeline diagram.

Step 1 — Pipeline ko ek conveyor belt ki tarah draw karo

KYA HAI. Hum paanch stations ko left-to-right rakhte hain aur ek instruction ko har cycle mein ek station aage badhne dete hain. Agar har cycle mein ek nayi instruction IF mein enter karti hai, toh paanch instructions ek saath "in flight" hoti hain, har ek alag station mein.

KYUN. Poori hazard problem sirf isliye exist karti hai kyunki kai instructions time mein overlap karti hain. Aap ek galat guess ki cost tab tak nahi dekh sakte jab tak kai instructions ek saath coexist karte hue na dikhein. Toh belt woh stage hai jis par yeh drama khelti hai.

PICTURE. Neeche ki belt ek instruction ko right slide karte hue dikhati hai, ek station per tick. Dhyan do lal PC IF ko feed kar raha hai — woh arrow woh cheez hai jise ek branch baad mein hijack kar legi.

Yeh belt pipelining fundamentals waali hi belt hai; agar IF/ID/EX/MEM/WB shaky lagte hain, pehle woh revisit karo.

Step 2 — Dekho IF next address par commit kar leti hai EX ko jawab pata chalne se pehle

KYA HAI. Har cycle mein, IF jo bhi PC point kar raha hai use fetch karti hai, phir blindly PC ko 4 se badha deti hai. Yeh turant karta hai, IF ke end mein — yeh wait nahi kar sakta, kyunki agle cycle mein IF ko ek fresh instruction feed karni hai warna belt bhookhi reh jayegi.

KYUN. Yeh poori problem ka seed hai. Ek branch (dekho branch instructions) shayad PC ko kahin door jump karana chahti ho — lekin woh decision baad mein, EX mein hota hai. IF already aage badh chuki hai. Fetch ek bet hai jo result pata chalne se pehle lagayi jaati hai.

PICTURE. Lal arrow PC hai. Yeh apne aap $100 \to 104 \to 108$ advance karta hai, cycle after cycle, bina kisi idea ke ki uske peeche belt mein ek branch baithi hai.

Yahan har symbol, term-by-term:

$address IF will fetch PC_{next} = address just fetched PC_{now} + bytes per instruction 4$

Step 3 — Exactly kab branch ka "taken?" ka jawab milta hai, yeh pin down karo

KYA HAI. Ek branch jaise BEQ R1, R2, 200 ("200 par jao agar R1 equals R2 ho") ko equality test karne ke liye $R 1 - R 2$ subtract karna hoga. Woh subtraction ALU mein rehta hai, jo EX mein rehta hai. Toh jawab EX par aata hai — isse pehle nahi.

KYUN. Humein jawab ka exact cycle chahiye kyunki waste hone wali instructions ki ginti literally kitni instructions belt ne wait karte waqt nigal li hai. Earlier resolution → kam wasted; later → zyada. Yeh poori derivation ka pivot hai.

PICTURE. Branch (red) ko IF → ID → EX crawl karte hue follow karo. Hara "✓ decided" flag tabhi jalta hai jab woh EX tak pahunchta hai.

Maano $t$ woh cycle hai jab branch IF mein baithe. Toh:

$branch in EX at cycle IF \to ID \to EX, two hops t + 2$

Step 4 — Dekho kaun peeche se ghus aaya

KYA HAI. Jab branch IF (cycle $t$ ) → ID (cycle $t + 1$ ) → EX (cycle $t + 2$ ) travel karti hai, IF idle nahi baithi. Usne PC+4 par fall-through instructions fetch kar li (cycle $t + 1$ ke dauran) aur PC+8 (cycle $t + 2$ ke dauran).

KYUN. Woh do instructions wrong-path candidates hain. Yeh tabhi kaam aate hain agar branch not taken ho. Humne unhe Step 2 ke default "seedha aage" bet par fetch kiya — Step 3 ka jawab aane se pehle.

PICTURE. Cycle $t + 2$ par snapshot: branch EX mein hai (red), aur directly uske peeche do instructions hain jinhein belt already accept kar chuki hai — PC+4 ID mein, PC+8 IF mein. Woh do hain jo ek taken branch condemn karegi.

$wrong-path instructions in flight = cycle branch resolves (t + 2) - cycle branch fetched t = 2$

$(t + 2)$ — woh cycle jab jawab aata hai.
$t$ — woh cycle jab gate khula aur branch ke aage fetching shuru hui.
Unka difference extra fetches ki count hai, yaani branch penalty.

Yeh parent ka headline formula hai, ab dekha gaya:

$Penalty = (resolve stage index) - (fetch stage index) = EX - IF = 2.$

Step 5 — Flush: do intruders ko bubbles mein convert karo

KYA HAI. Cycle $t + 2$ par, EX taken declare karta hai. Hardware ek saath do kaam karta hai: (1) PC = target set karta hai taaki cycle $t + 3$ sahi instruction (OR@200) fetch kare, aur (2) IF/ID aur ID/EX pipeline registers mein wapas jaata hai jo do wrong-path instructions ko hold kar rahe hain aur unke control signals kill karta hai, unhe bubbles mein convert karta hai.

KYUN unhe delete nahi karte? Belt clocked hai — har station ko har tick kuch na kuch agale station ko dena hi hoga, warna downstream logic desynchronise ho jaata. Aap ek chalti chain se ek link nahi nikaal sakte. Toh uski jagah aap link ko neuter karte ho: woh chalti rehti hai lekin kuch nahi karti. (Yeh wahi bubble machinery hai jo data-hazard stalls ke liye use hoti hai, repurposed.)

PICTURE. Step 4 jaisa hi snapshot, lekin ab do lale intruders crossed out hain aur BUBBLE label ho gaye hain; lal PC arrow 108 se target 200 par snap karta hai.

Step 6 — Edge case: branch not taken ki cost zero hai

KYA HAI. Maano cycle $t + 2$ par EX not taken kehta hai. Toh PC+4 aur PC+8 sahi instructions the shuruaat se hi. Kuch flush nahi hota. Penalty = 0.

KYUN. Humara default fetch (Step 2) "seedha aage" par ek bet thi. Jab branch us bet se agree karta hai, bet rang layi — belt already sahi kaam se bhari hui hai. Yahi reason hai kyun predict-not-taken (parent note) not-taken branches par free hai.

PICTURE. Do belts side by side: taken (upar, do lale bubbles) vs not-taken (neeche, sab kuch black aur alive). Sirf mismatch wali guesses cycles cost karti hain.

$Penalty = flush count 2 \times fraction that betray the guess P (taken)$

Toh average cost is baat par depend karti hai ki guess kitni baar galat hoti hai — yahi poora reason hai kyun branch prediction aur speculation exist karte hain.

Step 7 — Edge case: ek stage pehle resolve karo, ek kam pay karo

KYA HAI. ID mein dedicated comparators add karo taaki equality ek stage pehle pata ho. Ab branch cycle $t + 1$ par resolve hoti hai.

KYUN dikhana? Yeh prove karne ke liye ki "2" magic nahi hai — yeh resolve − fetch hai. Resolution ko ek stage upar move karo aur arithmetic penalty ko exactly ek se drop kar deti hai.

PICTURE. Step 4 wali count-line dobara draw ki gayi hai "decided" flag ID par left move kiya gaya. Sirf ek instruction (PC+4) peeche se ghus payi hai.

$Penalty_{ID resolve} = (t + 1) - t = 1.$

Wahi formula, chhota gap. Wasted instructions ki count us distance ke barabar hai jahan hum guess karte hain aur jahan hum jaante hain ke beech ka.

Ek-picture summary

Ek diagram, poori kahani: branch (red) $t + 2$ par EX mein resolve hoti hai; $t + 1$ aur $t + 2$ par fetch ki gayi do instructions bubbles ban jaati hain; PC target par snap karta hai; gap $(t + 2) - t = 2$ penalty hai. Resolve point ko left slide karo → gap shrinks.

Recall Feynman retelling — plain words mein dobara bolo

Ek pipeline ek conveyor belt hai jahan ek instruction ko cross karne mein paanch ticks lagte hain (IF, ID, EX, MEM, WB). Har tick par, fetch station ko koi na koi instruction pakadni hi hoti hai, toh by default woh line mein agla pakad leti hai aur address 4 se badha deti hai — ek bet ki hum seedha ja rahe hain. Ek branch, though, tab tak nahi jaanti ki seedha jaana hai ya jump karna hai jab tak woh EX station tak nahi pahunch jaati, fetch hone ke do ticks baad. Un do ticks mein belt pehle hi do "seedha aage" instructions nigal chuki hoti hai. Agar branch kehti hai "jump karo!", woh do wrong-path garbage hain. Hum unhe chalti belt se yank nahi kar sakte, toh hum unke controls zero kar dete hain — unhe harmless bubbles mein turn kar dete hain — aur address ko real target par point kar dete hain. Cost: do wasted ticks. Number do special nahi hai; yeh bas (woh stage jo decide karta hai) minus (woh stage jo fetch karta hai) hai. Ek stage pehle decide karo aur ek kam waste hoga. Sahi guess karo (branch not taken) aur kuch bhi waste nahi hoga.

Recall

EX-resolved branches ke liye exactly 2 wasted instructions kyun? ::: EX, IF ke do stages baad hai, toh belt branch ka jawab aane se pehle 2 fall-through instructions fetch kar leti hai: $(t + 2) - t = 2$ . Bubble kya hai aur galat instructions ko delete kyun nahi karte? ::: Ek no-op jiske sare control signals zero hain; clocked belt ko har tick kuch na kuch forward dena hota hai, toh hum remove ki jagah neuter karte hain. Kya branch instruction itself kabhi flush hoti hai? ::: Nahi — yeh sahi hai aur isko finish karna hoga (PC update karo, WB tak pahuncho). Sirf branch ke baad fetch ki gayi instructions flush hoti hain. Predict-not-taken ke under not-taken branch par penalty kya hai? ::: Zero — fall-through instructions sahi path thin. ID mein resolve karna EX ki jagah penalty ko kaise change karta hai? ::: $(t + 1) - t = 1$ ; ek kam galat instruction fetch hoti hai.