Control hazards and pipeline flushes — Hinglish notes

5.2.8 · Hardware › Processor Datapath & Pipelining

Control Hazard Kya Hota Hai?

"Control" kyun? Kyunki branches execution ka control karti hain—woh decide karti hain ki next instruction kaun si aayegi. Data hazards (operand dependencies) ke unlike, control hazards ka matlab hai kaunsi instruction execute karni hai, na ki kaunsa data use karna hai.

Control Hazards Kab Aate Hain

Ek 5-stage pipeline consider karo (IF, ID, EX, MEM, WB):

Cycle 1: Branch instruction IF mein enter karti hai
Cycle 2: Branch ID mein enter karti hai (condition decode karo, target compute karo)
Cycle 3: Branch EX mein enter karti hai (condition resolve karo: taken hai ya nahi?)
Isi dauran: Hum cycle 2 mein PC+4 aur cycle 3 mein PC+8 already fetch kar chuke hain

Agar branch cycle 3 par taken hoti hai, toh PC+4 aur PC+8 waali instructions galat path se hain. Unhe flush karna padega (no-ops mein convert karo).

Branch Decision Timeline

Yeh kyun matter karta hai: Har flushed instruction ek wasted cycle hai. 20% branches aur 2-cycle penalty waale program mein $0.2 \times 2 = 0.4$ cycles per instruction average pe waste hoti hain—yeh 40% performance hit hai!

Pipeline Flush Mechanism

Flush Kaise Karein: Control Signal Kill Switch

Step-by-step:

Misprediction detect karo: EX stage mein, branch condition result ko prediction se compare karo (ya static "not taken" assume karo)
Agar (misprediction) hai:
- PC = branch_target set karo (EX/MEM pipeline register se)
- IF/ID aur ID/EX registers mein pipeline bubbles inject karo
Bubble implementation: Control signals ko 0 force karo:
- RegWrite = 0 (registers mat likho)
- MemWrite = 0 (memory mat likho)
- ALUOp = 0 (harmless NOP operation)

Bubbles kyun, sirf "delete" kyun nahi? Pipeline stages synchronized hoti hain. Kisi instruction ko mid-flight remove nahi kar sakte—isse pipeline desynchronize ho jaayegi. Iske bajaaye, usse ek do-nothing operation mein convert karte hain jo normal instruction ki tarah flow karta hai lekin kuch change nahi karta.

Worked example Do Instructions Flush Karna

Code:

100: BEQ R1, R2, 200   # Branch to 200 if R1 == R2
104: ADD R3, R4, R5    # Wrong-path instruction 1
108: SUB R6, R7, R8    # Wrong-path instruction 2
...
200: OR R9, R10, R11   # Correct target

Cycle-by-cycle (branch taken): | Cycle | IF | ID | EX | MEM | WB | |-------|----------|-------------|-----| | 1 | BEQ@100 | ... | ... | ... | ... | | 2 | ADD@104 | BEQ@100 | ... | ... | ... | | 3 | SUB@108 | ADD@104 | BEQ@100 ✓ | ... | ... | | 4 | OR@200 | BUBBLE | BUBBLE | BEQ | ... | | 5 | ... | OR@200 | BUBBLE | ... | BEQ | Cycle 3 kyun? BEQ EX mein resolve hoti hai: R1 == R2 true hai, toh branch taken hai.

ADD aur SUB flush kyun? Woh pipeline mein yeh assume karke aaye ki BEQ not taken thi (PC har cycle 4 se badha). Ab hum jaante hain unhe execute nahi karna chahiye.

Cycle 4: OR@200 (correct instruction) fetch hoti hai. ADD aur SUB bubbles ban jaate hain (table mein BUBBLE dikhaayi diya hai—woh EX aur MEM mein kuch nahi karte).

Cost: 2 wasted cycles (woh cycles jo ADD aur SUB ne pipeline mein bubbles banne se pehle guzaare).

Branch Prediction ke Types (Flush Avoidance)

Flushes kam karne ke liye, processors branch outcomes predict karte hain:

1. Static Prediction

Not-taken predict kyun? Simpler hardware (koi prediction table nahi). Forward branches ke liye achha kaam karta hai (if-then-skip patterns).

2. Static Predict-Taken

Assume karo ki saari branches taken hain. Target address speculatively fetch karo.

Problem: ID mein target compute karna padega (adder + PC forwarding chahiye)
Flush if not taken: $Penalty = 1 cycle (ID resolution) \times P (not taken)$

3. Dynamic Prediction (Branch Prediction Buffer)

PC se indexed ek Branch History Table (BHT) use karo:

$BHT index = PC [n : 2] mod 2^{k}$

jahan $k$ index bits ki sankhya hai (jaise 10 bits = 1024 entries).

Har entry: 1-bit ya 2-bit saturating counter

2-bit counter states: Strongly Taken (11) → Weakly Taken (10) → Weakly Not-Taken (01) → Strongly Not-Taken (00)
Prediction: Taken agar counter ≥ 10 (binary)

2 bits kyun? Loop mein ek misprediction tolerate karta hai (jaise exit condition). 1-bit predictor do baar mispredict karta: loop entry aur loop exit.

Worked example Loop ke liye 2-Bit Predictor

Code:

for (i = 0; i < 100; i++) {
    // loop body
    BEQ continue_loop  # Taken 99 times, not taken 1 time
}

1-bit predictor:

Taken predict karta hai (99 baar sahi)
Loop exit karta hai (not taken) → misprediction #1
Agla loop: Not-Taken predict karta hai (galat!) → misprediction #2
Total: 2 mispredictions per loop (entry + exit)

2-bit predictor (Strongly Taken = 11 se shuru):

99 iterations: Taken (sahi), counter 11 rehta hai
Exit: Not-Taken → counter 10 pe drop karta hai (Weakly Taken), misprediction #1
Agla loop: Phir bhi Taken predict karta hai (counter = 10) → sahi!, counter wapas 11
Total: 1 misprediction per loop (sirf exit)

Yeh kyun kaam karta hai: 2-bit counter ko prediction flip karne ke liye do consecutive galat predictions chahiye. Ek exit "trend" ko fully nahi badalta.

Control Hazards Samajhne Mein Common Mistakes

Advanced: Branch Target Buffer (BTB)

BHT ke saath combined: Modern CPUs dono use karte hain:

BTB batata hai kahan jump karna hai (agar branch taken hai)
BHT batata hai kya jump karna hai (taken vs. not-taken prediction)

Recall Ek 12-Saal ke Bacche ko Explain Karo (Feynman Technique)

Socho tum ek "Choose Your Own Adventure" book padh rahe ho. Page 10 ke neeche likha hai, "Agar tum dragon se lado, page 45 par jao. Agar tum bhaago, page 12 par jao."

Tumhe choice karni hai, lekin yahan ek trick hai: tumhara dost pehle se time bachane ke liye aage padh raha hai. Tumhare decide karne se pehle, usne page 12 padhna shuru kar diya (yeh assume karke ki tum bhaagoge).

Lekin phir tum fight choose karte ho! Ab tumhare dost ko page 12 se jo bhi padha sab phenk dena padega (yeh galat story path hai) aur page 45 se dobara shuru karna padega. Woh time jo unhone galat page padhne mein lagaya woh barbaad hua—yehi "pipeline flush" hai.

Ek "branch predictor" tumhare dost ki tarah hai jo guess karta hai ki tum kya choose karoge, pichli baar kya choose kiya tha uske basis par. Agar sahi guess kiya, toh koi time waste nahi! Agar galat guess kiya, toh wapas aana padega. Jitna achha guess karein, utni tezi se book khatam hogi.

Connections

5.2.01-Pipelining-fundamentals — Control hazards teen hazard types mein se ek hain (structural, data, control)
5.2.05-Data-hazards-and-forwarding — Data hazards bhi stalls cause karte hain, lekin forwarding help karta hai; control hazards mein flushing chahiye (PC ke liye koi forwarding nahi)
5.2.09-Branch-prediction-techniques — Dynamic predictors (2-bit, gshare, perceptron) accuracy improve karte hain
5.2.11-Speculative-execution — Modern CPUs speculatively dono paths execute karte hain, correct ek commit karte hain
4.3.08-Branch-instructions — Branch types ka ISA-level view (conditional, unconditional, register-indirect)

Flashcards

#flashcards/hardware

Pipelined processor mein control hazard kya hota hai? :: Ek hazard jo tab hota hai jab pipeline yeh determine nahi kar pati ki next instruction kaunsi fetch karni hai kyunki branch instruction ka outcome abhi resolve nahi hua, aur pipeline ko stall, predict, ya wrong-path instructions flush karne ki zaroorat padti hai.

Mispredicted branch ke baad pipeline instructions kyun flush karti hai?

Kyunki pipeline ne galat path se instructions speculatively fetch ki thi (yeh assume karke ki branch not taken hai). In instructions ko no-ops (bubbles) mein convert karna padta hai taaki woh architectural state ko galat tarike se modify na karein.

Hardware mein pipeline flush kaise implement hoti hai?

IF/ID aur ID/EX pipeline registers mein bubbles (no-ops) inject karke, control signals (RegWrite, MemWrite) ko 0 set karke taaki wrong-path instructions EX, MEM, aur WB stages se flow karte waqt kuch na karein.

5-stage pipeline ke liye jo EX stage mein branches resolve karti hai, branch penalty kitni hai?

2 cycles (PC+4 aur PC+8 waali instructions flush karni padti hain agar branch taken hai), assuming koi branch prediction nahi ya static predict-not-taken.

Loops ke liye 2-bit branch predictor 1-bit predictor se behtar kyun perform karta hai?

2-bit predictor ko apni prediction change karne ke liye do consecutive mispredictions chahiye, isliye ek akela loop exit predictor flip nahi karta. 1-bit predictor dono loop exit (not taken) aur agla loop entry (exit se not-taken predict karta hai, lekin loop taken ke saath re-enter karta hai) mispredict karta hai, is tarah ek loop mein 2 mispredictions hoti hain.

Branch History Table (BHT) aur Branch Target Buffer (BTB) mein kya farq hai?

BHT predict karta hai kya branch taken hai (direction), jabki BTB taken branches ka target address store karta hai taaki usse ID stage mein compute na karna pade. Modern CPUs dono saath use karte hain.

Control hazards ko data hazards ki tarah forwarding se kyun solve nahi kiya ja sakta?

Forwarding ek hi instruction stream ke liye baad ke pipeline stages se pehle waale stages mein data pass karta hai. Control hazards ke liye pipeline mein kaunsi instructions hain yeh change karna padta hai (wrong-path instructions flush karke nayi fetch karna), sirf data forward nahi karna.