Precise exceptions in pipelines: Exercises — Hinglish deep dive

5.2.12 · D4 · Hardware › Processor Datapath & Pipelining › Precise exceptions in pipelines

Intuition Is page ko kaise use karein

Neeche har problem L1 (Recognition) se shuru hoti hai — kya tum idea ko pehchaan sakte ho? — aur L5 (Mastery) tak jaati hai — kya tum khud ek scheme invent kar sakte ho? Har ek problem ko Solution callout collapse karke try karo, phir kholo. Har level ke baad ek [!mistake] callout hai jo woh trap dikhata hai jo sahi lagta hai par hai nahi.

Yeh page self-contained hai: har woh term jo problem mein use hoti hai, use pehle neeche define kiya gaya hai. Wikilinks — the parent note, 5.2.1-Pipelining-basics, 5.2.8-Data-hazardsand-forwarding, 5.2.11-Branch-prediction, 6.3.4-Reorder-buffer-in-superscalar, 7.2.5-Virtual-memory-exceptions, 3.4.7-Exception-handling-in-ISA — deeper jaane ke liye hain, in problems ko solve karne ke liye gaps bharne ke liye nahi.

Shuru karne se pehle, ek picture saari vocabulary fix kar deti hai jis par hum is poore page mein rely karenge.

Figure — Precise exceptions in pipelines

Figure s01 — 5 pipeline stages ek left-to-right assembly line ke roop mein draw kiye gaye hain. Har rounded box ek stage hai; navy arrows dikhate hain ki ek instruction exactly ek box aage badhti hai har clock cycle mein. Orange boxes (IF, ID) pipe ka "front" hain jahan nayi work enter karti hai; magenta box (EX) woh jagah hai jahan arithmetic faults detect hote hain; violet boxes (MEM, WB) "back" hain jahan memory faults appear hote hain aur jahan results finally architectural state tak pahunchte hain. Stage indices 1–5 jo boxes par print hain woh numbering convention hai jo Exercise 2.3 mein use hoti hai.

Definition Paanch stages, unke indices, aur woh words jo hum use karte hain

Ek pipeline instructions ke liye ek assembly line hai. Har instruction 5 rooms mein se walk karti hai, aur hum stages ko 1 se 5 number karte hain us order mein jis order mein ek instruction unhe visit karti hai (yeh numbering Ex. 2.3 ki arithmetic mein use hoti hai):

Stage 1 = IF = Instruction Fetch — memory se instruction grab karo.
Stage 2 = ID = Instruction Decode — figure out karo yeh kya hai, registers read karo.
Stage 3 = EX = Execute — arithmetic karo (add, divide, compare). Arithmetic faults yahan detect hote hain.
Stage 4 = MEM = Memory — data memory read/write karo (loads/stores ke liye). Page faults yahan detect hote hain.
Stage 5 = WB = Write Back — result ko register file mein write karo.

Architectural state = woh cheezein jo ek programmer dekh sakta hai: registers aur memory. Ek instruction tabhi sach mein hui maani jaati hai jab usne architectural state update kar li ho. Program order = woh order jisme instructions program text mein appear hoti hain. Instruction $i$ , $i + 1$ se older hai. Pipeline mein older instruction woh hoti hai jo aage hoti hai (higher stage number, WB ke kareeb). EPC = Exception Program Counter — ek register jo yaad rakhta hai "fault kahan tha" taaki handler wapas aa sake.

Definition Teen operations jinhe aapko confuse nahi karna chahiye: write-back, flush, commit

Yeh teen verbs is poore page mein aate hain. Inhe abhi pin down karo:

Write-back (WB stage) — ek simple in-order pipe mein, yeh result ko register file mein likhne ka physical act hai. In-order pipe mein, WB tak pahunchna hi woh moment hota hai jab instruction architectural state update karti hai.
Flush — ek instruction jo abhi pipe ke andar hai use NOP ("No Operation" bubble) mein badal kar cancel karo. Ek flushed instruction kuch nahi likhti, kuch nahi padhti, koi state change nahi karti — jaise kabhi fetch hi nahi ki gayi. Flushing hi woh tarika hai jisme hum faulter aur usse younger sab ko "disappear" kara dete hain.
Commit (a.k.a. retire) — out-of-order machines mein Reorder Buffer ke saath use hota hai. Ek instruction execute karna jaldi finish kar sakti hai aur apna result ROB (ek private scratchpad) mein park kar sakti hai, bina architectural state ko touch kiye. Commit woh alag, strictly-in-program-order step hai jo us parked result ko ROB se nikaal kar real registers/memory mein copy karta hai. To: execute = answer compute karo; commit = answer ko official banao. Ek not-yet-committed instruction ko flush karna free hai — uska result sirf ROB mein tha kabhi.

Definition Stall-on-exception strategy (Ex. 2.1 se aage use hoti hai)

Yeh sabse simple tarika hai jisse ek in-order pipeline precise exceptions achieve karti hai. Jis moment koi bhi instruction kisi stage mein fault signal raise kare, control logic exactly yeh karta hai:

Front ko freeze karo. IF aur ID stages ke liye "advance" enable de-assert (band) karo: program counter ka incrementing band ho jaata hai aur koi nai instruction decode nahi hoti. Hardware mein yeh ek stall signal hai jo IF/ID pipeline registers se wired hai.
Faulter aur younger ke liye bubbles inject karo. Faulting instruction aur usse younger har instruction ko hold karne wale pipeline registers pe flush signal assert karo, har ek ko NOP se overwrite karo. Yeh bubbles MEM/WB mein ride karenge kuch bhi write kiye bina.
Older instructions ko drain hone do. Faulter se older instructions (already MEM/WB mein) apna advance enable rakhti hain aur normally apne write-backs finish karti hain — woh run hone waali thein, isliye complete hona zaroori hai.
Return point record karo. Faulting instruction ka address EPC mein copy karo.
Redirect karo. Jab older instructions drain ho jayen, PC ko exception handler ke entry address par set karo aur front ko un-freeze karo.

Cost woh kuch cycles hain step 3 mein jab older instructions drain ho rahi hain — yahi exactly woh hai jo Ex. 2.3 count karta hai.

Level 1 — Recognition

Exercise 1.1

Inme se kaunsa ek precise exception ka exact promise hai? Ek choose karo. (a) Faulting instruction aur uske baad ki sab complete ho gayi; pehle ki sab cancel ho gayi. (b) Faulting instruction se pehle ki sab complete ho gayi; faulting instruction aur uske baad ki sab ne kuch modify nahi kiya. (c) Pipeline mein har instruction cancel ho jaati hai jab bhi koi fault aata hai. (d) Exception us moment report hoti hai jab detect hoti hai, kisi bhi order mein.

Recall Solution

Answer: (b). Picture se rebuild karo: ek precise exception pipeline ko aisa dikhaati hai jaise ek slow one-at-a-time machine exactly faulting instruction par ruk gayi ho. To saari older instructions (usse pehle ki) registers/memory update karna finish kar chuki honi chahiye, aur faulting instruction plus saari younger ones (uske baad ki) ne kuch touch nahi kiya hona chahiye.

(a) time-reversed hai — exactly wrong wale rakhta hai.
(c) woh kaam bhi throw away karta hai jo already correctly complete ho chuka tha (older instructions).
(d) definition se imprecise hai: order program order follow karna chahiye, detection time nahi.

Exercise 1.2

Har abbreviation ko uske kaam se match karo. EPC · WB · ROB · NOP

Recall Solution

EPC — Exception Program Counter: handler ke liye faulting instruction ka address store karta hai.
WB — Write Back: woh stage jahan result finally register file (architectural state) mein jaata hai.
ROB — Reorder Buffer: finished-but-not-yet-committed results hold karta hai taaki unhe program order mein commit kiya ja sake.
NOP — "No Operation": ek bubble jo kuch nahi karta; hum flushed instructions ko inhi mein convert karte hain taaki woh koi state touch na karein.

Exercise 1.3

True ya false: "Ek instruction jo WB tak pahunch gayi hai lekin abhi likhi nahi, aur ek instruction jo abhi IF mein hai, dono 'committed' hone se same distance par hain."

Recall Solution

False. WB mein instruction architectural state update karne se ek micro-step door hai — almost done hai. IF mein instruction mein abhi shuruat hi hui hai (4 stages baaki hain). "Committed" ka matlab hai "registers/memory par iska effect lock in hai," aur simple in-order pipe mein sirf WB yeh karta hai.

Level 2 — Application

Exercise 2.1

Ek 5-stage pipeline (IF, ID, EX, MEM, WB) har cycle mein ek stage advance karti hai. Cycle 5 mein snapshot yeh hai:

IF: I5    ID: I4    EX: I3 (FAULT)    MEM: I2    WB: I1

Stall-on-exception strategy (upar define ki gayi) use karte hue, kis cycle mein last older instruction (I2) apna WB finish karti hai, taaki I3 se pehle ki saari instructions complete ho jayen?

Recall Solution

Strategy apply karo: IF/ID freeze karo (to I4, I5 ruk jaate hain), I3/I4/I5 ko NOPs mein flush karo, aur older instructions I1, I2 ko drain hone do. Cycle 5 se older instructions ko aage walk karo:

I1 is cycle mein (cycle 5) WB mein hai — yeh cycle 5 ke end mein finish ho jaata hai.
I2 cycle 5 mein MEM mein hai, isliye woh cycle 6 mein WB enter karta hai aur cycle 6 ke end mein finish ho jaata hai.

To cycle 6 ke baad, I1 aur I2 dono write back ho chuke hain. I3, I4, I5 NOPs mein convert ho gaye aur kuch touch nahi kiya. I3 ka PC EPC mein save karo aur handler par jump karo. Answer: cycle 6.

Exercise 2.2

2.1 jaisa hi snapshot. Kitni instructions ko NOPs mein convert (flush) karna hoga, aur kaunsi kaunsi?

Recall Solution

Faulting instruction aur usse younger saari flush karo: woh hain I3, I4, I5 → 3 instructions. I1 aur I2 older hain, isliye unhe flush nahi kiya jaata — precision ke liye unhe complete hona zaroori hai.

Exercise 2.3

Pipeline $k$ stages deep hai, aur stages ko $1$ (IF) se $k$ (WB) tak visit order mein number kiya gaya hai, exactly jaisa figure par print hai. Ek fault EX stage mein detect hota hai, jo stage number 3 hai. Worst case mein, pipeline kitne cycles stall karti hai jab tak saari older instructions WB se drain ho jaati hain?

Recall Solution

Step 1 — kaun older hai aur abhi unfinished hai? Older instructions EX ke baad wali stages mein hoti hain. IF=1, ID=2, EX=3, MEM=4, WB=5 numbering ke saath, EX ke baad wali stages hain MEM (4) aur WB (5). Yeh $k - 3 = 5 - 3 = 2$ stages hain.

Step 2 — har ek ko end (WB) tak pahunchne mein kitna time lagta hai?

WB (stage 5) mein already instruction is cycle mein finish ho jaati hai → 0 further advances, 1 cycle ke baad done.
MEM (stage 4) mein instruction ko MEM→WB advance karna hai → yeh 2 cycles baad finish hoti hai.

Step 3 — drain time sabse peechhe wali older instruction se set hoti hai, jo MEM wali hai. Use stage 4 se stage 5 tak climb karna hai = 1 aur advance, lekin woh WB se poora ek cycle peeche enter hui, isliye poora drain 2 cycles baad complete hota hai. Yeh EX ke baad wali stages ki count se match karta hai.

General rule (ab numbering fix hone se ambiguous nahi): drain hone wali older instructions ki sankhya (EX ke baad wali stages) $= k - (stage index of EX)$ ke barabar hai. Yahan $= 5 - 3 = 2$ . Answer: 2 cycles.

Level 3 — Analysis

Exercise 3.1

Do faults same cycle mein appear hote hain:

ID: I4 — illegal opcode
EX: I3 — divide by zero

Kaunsi exception report hoti hai, aur doosri instruction ka kya hota hai?

Recall Solution

I3 EX (stage 3) mein hai, I4 ID (stage 2) mein hai — I3 pipe mein deeper hai (higher stage number), matlab woh pehle enter hui, matlab woh program order mein older hai. Precise semantics oldest fault report karti hain. Report karo: I3 ka divide-by-zero. I4: woh faulter se younger hai, isliye use NOP mein flush kar diya jaata hai — uska "illegal opcode" fault discard ho jaata hai. Usne kabhi architecturally execute nahi kiya, isliye uski fault report nahi honi chahiye. (Agar program baad mein resume hota hai aur I3 se dubara chalata hai, to I4 re-fetch hogi aur tab uski illegal-opcode fault legitimately surface hogi.)

Exercise 3.2

Commit time par Reorder Buffer mein yeh entries hain:

Entry | Inst | Status    
1     | I1   | COMPLETE  
2     | I2   | COMPLETE  
3     | I3   | FAULTED (div-by-zero)
4     | I4   | COMPLETE

ROB order mein head (entry 1) se commit karta hai. Kitni instructions architectural state update karti hain, aur kaunse ROB entries flush hote hain?

Recall Solution

ROB program order mein head se commit karta hai, chahe execution kisi bhi order mein finish hua ho. Yaad karo commit = parked result ROB se nikaal kar real registers mein copy karna; flush = parked result discard karna.

I1 commit karo → architectural R1 likhta hai. ✔
I2 commit karo → architectural R4 likhta hai. ✔
Head I3 tak pahunchta hai, jo FAULTED hai → committing band karo, yahan exception lo.
I3 aur I4 (entries 3 aur 4) flush karo. Chahe I4 already execute ho chuki hai, uska result sirf ROB mein hai, architectural registers mein nahi — isliye use discard karna free aur safe hai.

Architectural updates: 2 instructions (I1, I2). Flushed entries: 3 aur 4 (2 entries). Yeh exactly precise hai: older done, faulter aur younger cancelled — chahe I4 real time mein I3 se pehle execute ho gayi. ROB hi woh cheez hai jo out-of-order execution ko finish line par in-order dikhata hai. Dekho 6.3.4-Reorder-buffer-in-superscalar.

Exercise 3.3

Ek branch not taken predict hoti hai, isliye pipeline fall-through instruction I2 fetch karti hai, jo ek DIV R3,R4,R0 hai. I2 EX mein fault karti hai (divide by zero). Phir branch taken resolve hoti hai — I2 wrong path par thi. Kya exception report hogi?

Recall Solution

Nahi. I2 speculative thi — branch outcome pata hone se pehle fetch ki gayi. Jab branch taken resolve hoti hai, I2 wrong path par hai, isliye use flush kar diya jaata hai aur uski fault vanish ho jaati hai. Ek instruction jo run honi hi nahi chahiye thi woh precise exception cause nahi kar sakti. Hardware I2 ko "faulted, speculative" mark karta hai aur sirf tabhi mark ko real exception mein convert karta hai jab I2 correct path par commit point tak pahunche. Yahan woh kabhi nahi pahuchti. Dekho 5.2.11-Branch-prediction.

Level 4 — Synthesis

Exercise 4.1

Ek load instruction I2 MEM mein page fault cause karti hai (uska page disk par hai — dekho 7.2.5-Virtual-memory-exceptions). Older instruction I1 WB mein hai; younger I3, I4 EX aur ID mein hain. Poora precise-exception sequence describe karo taaki handler page lane ke baad execution resume ho sake aur I2 correctly re-run ho sake.

Recall Solution

I2 ke MEM stage mein page fault detect karo. I2 ko faulting mark karo; use kuch bhi write karne mat do (ek page-faulting load ke paas write back karne ke liye koi valid data nahi hoti).
I1 finish hone do — woh older hai, isliye use WB complete karke architectural state update karni hi chahiye.
I2, I3, I4 ko NOPs mein flush karo — faulter aur saari younger instructions kuch modify nahi karti.
I2 ka PC EPC mein save karo. Yeh critically I2 ka apna address hai, agla instruction nahi — kyunki page load hone ke baad hume I2 re-execute karni hai, use skip nahi karna.
Page-fault handler par jump karo. Woh EPC read karta hai, page tables walk karta hai, missing page disk se load karta hai, use present mark karta hai.
Handler "return-from-exception" instruction ke through return karta hai jo PC = EPC set karta hai, isliye I2 re-run hoti hai, is baar memory mein hit karti hai, aur I3, I4 fresh re-fetch hoti hain.

Kyunki I1 complete ho gayi aur I2/I3/I4 ne koi state touch nahi ki, restart seamless hai — machine exactly aisi dikhti hai jaise I2 se pehle pause hua ho. Yeh resumability hi woh poora reason hai ki page faults precise exceptions demand karti hain.

Exercise 4.2

Design question: In-order pipeline mein, arithmetic faults (divide-by-zero, overflow) EX mein detect karna safe kyun hai lekin memory-access faults (page faults) sirf MEM par — aur kya inhe reorder karna kabhi ek single instruction ke andar precision break kar sakta hai?

Recall Solution

Detection stage wahan follow karta hai jahan kaam hota hai: arithmetic EX (stage 3) mein hoti hai, memory access MEM (stage 4) mein, isliye har fault naturally apni stage mein discover hoti hai. Ek instruction ke andar, earlier-stage fault jeetni chahiye agar dono fire ho sakein, kyunki sequential execution mein fetch/decode/arith checks logically memory access se pehle aate hain. Ek single instruction ke liye ISA ek priority order fix karti hai (fetch fault > illegal-opcode > privilege > arithmetic > memory). Pipeline jo ISA rank karta hai use record karti hai aur us same instruction ke liye baad ke-stage detections suppress kar deti hai. Isliye yeh kabhi "precision break" nahi karti jab tak hardware ISA ki fixed intra-instruction priority honor kare. Dekho 3.4.7-Exception-handling-in-ISA.

Level 5 — Mastery

Exercise 5.1

Aapko 6 entries ke Reorder Buffer wala ek 2-wide superscalar, out-of-order core diya gaya hai. Ek cycle mein, teen instructions faults signal karti hain:

ROB entry 2 : I2  — overflow (executed early, out of order)
ROB entry 5 : I5  — page fault
ROB entry 3 : I3  — illegal opcode

ROB head abhi entry 1 (I1, abhi bhi executing, abhi complete nahi) par hai. Saari doosri entries execute ho chuki hain. Exact commit/flush behaviour, cycle by cycle do, aur final EPC. Assume karo commit rate 2 per cycle hai jab instructions ready hain.

Recall Solution

Strictly ROB rule se reason karo: head se order mein commit karo; fault par tab act karo jab uski entry head ban jaaye. Entries 2, 3, 5 par faults us moment flags ke roop mein record hote hain jab detect hote hain — woh kuch nahi karte jab tak unki entry head na ban jaaye.

Cycle 1: head = entry 1 (I1) abhi bhi executing hai → head ready nahi hai → kuch commit nahi. Hum wait karte hain. (2/3/5 par faults flags ke roop mein baithte hain.)

Cycle 2 (maano I1 ab complete ho gayi, fault-free): 2-wide commit port ke saath hum head se do tak instructions commit karne ki koshish karte hain:

Slot A: I1 commit karo → R1 ka architectural update. ✔
Slot B: agla head entry 2 = I2, overflow flagged hai. Ek flagged entry commit karna matlab state update karne ki jagah uski exception lena hai. Kyunki I2 program order mein oldest faulting instruction hai, yahi exception hum lete hain. Commit yahan rok deta hai — I2 state update nahi karta.

Cycle 2, same cycle — flush: I2 ki exception select karke, I2 itself aur har younger entry flush karo: entries 2, 3, 4, 5, 6. Yeh I3 ka illegal-opcode flag aur I5 ka page-fault flag discard karta hai — dono vanish ho jaate hain, exactly jaisa required hai, kyunki I2 unse older hai.

Final tally:

Instructions jo architecturally commit hoti hain: 1 (sirf I1).
Exception li gayi: I2 ka overflow (oldest faulting entry).
Entries flushed: 2, 3, 4, 5, 6 → 5 entries (faulter I2 plus 4 younger).
EPC = I2 ka address.

Key insight: I5 par page fault aur I3 par illegal opcode — dono "time par" detect hue — irrelevant hain. Program order akela decide karta hai, aur I2 oldest hai. Isliye ek out-of-order core bhi perfectly precise rehta hai.

Exercise 5.2

Ek scheme invent karo. Precise exceptions drain/flush cycles ki cost laati hain. Kuch purani machines imprecise exceptions offer karti theen (faults late aur out of order report karo) hardware bachane ke liye. Ek hybrid propose karo: exceptions ko resumable faults (page faults) ke liye precise rakho lekin fatal faults (illegal opcode jo program anyway terminate karega) ke liye imprecise allow karo. Ek benefit aur ek danger batao.

Recall Solution

Scheme: Har exception type ko ek chhote ISA field mein resumable ya fatal tag karo.

Resumable faults (page fault, TLB miss): poori precise machinery ke through route karo — deferred, sirf in-order commit par materialized, EPC = faulting PC. Correctness demand karta hai, kyunki hume restart karna hai.
Fatal faults (illegal opcode, unrecoverable): imprecise reporting allow karo — jis moment detect ho raise karo, debugger ke liye "best-effort" register snapshot dump karo, aur terminate karo. Kyunki hum kabhi resume nahi karenge, exact sequential state strictly required nahi hai.

Benefit: fatal faults drain/flush latency aur ROB-ordering wait avoid karti hain, aur rare fatal case ke liye hardware simplify karta hai. Danger: debugger jo register/memory snapshot dekhta hai woh inconsistent ho sakta hai (kuch younger instructions commit ho gayi, kuch older nahi), isliye post-mortem debugging mislead kar sakti hai — ek register mein value ek aisi instruction reflect kar sakti hai jo "abhi run nahi honi chahiye thi." Saath hi, agar baad mein fault recoverable nikle (jaise debugger illegal opcode patch kare), aap cleanly resume nahi kar sakte. Yahi trade-off hai jo modern ISAs sab kuch precise banati hain — hardware cost debugging aur OS pain of imprecision ke relative sasta ho gaya hai.