Precise exceptions in pipelines: Visual walkthrough

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

Kuch bhi aur karne se pehle, teen simple words jo hum poore page mein use karenge:

Poori problem, ek sentence mein: ek pipeline instructions ko time mein overlap karke chalati hai, isliye woh program order se bahar finish ho sakti hain — lekin bahar ki duniya ko kabhi notice nahi hona chahiye.

Step 1 — Pipeline ko conveyor belt ki tarah draw karo

KYA. Paanch work-stations ek row mein socho. Ek instruction unke through conveyor belt par sawari karta hai, clock ke ek tick (ek cycle) mein ek station. Paanch stations hain:

IF (fetch): instruction ko memory se pakdo.
ID (decode): samjho iska matlab kya hai, iske input registers padho.
EX (execute): arithmetic karo.
MEM (memory): zaroorat ho toh memory read ya write karo.
WB (write-back): jawab official registers mein likho.

YEH PAANCH KYUN. Kaam ko split karne se paanch instructions ek saath progress mein ho sakti hain — jab $I_{1}$ WB par hai, $I_{2}$ MEM par hai, aur aage bhi. Woh overlap hi pipelining ki poori speed jeet hai.

PICTURE. Har column ek station hai; har colored block ek instruction hai. Ek vertical slice padho yeh dekhne ke liye ki "ek pal mein sabke paas kya hai."

Step 2 — Ek clock tick freeze karo aur khatre ko dhundho

KYA. Belt ko cycle 5 par freeze karo. Paanch alag instructions ek saath paanch stations mein hain:

IF I_{5} ID I_{4} EX I_{3} MEM I_{2} WB I_{1}

Term by term: har $I$ ke neeche chota word woh station hai jisme woh instruction abhi khadi hai. $I_{1}$ (sabse purani) sabse aage hai; $I_{5}$ (sabse nayi) abhi abhi fetch hui.

FREEZE KYUN. Ek precise exception ek pal mein define hoti hai. Hume fault ke waqt yeh kehna hona chahiye, "jo bhi purani hai woh done hai, jo bhi nayi hai woh undo hai." Isliye hum ek frozen instant padhte hain.

PICTURE. Ab $I_{3}$ phatt jaye: woh hai DIV R6,R7,R0 — divide by zero — aur divide-by-zero EX mein discover hoti hai. Laal burst use mark karta hai.

Step 3 — Woh rule jo ise fix karta hai: purana finish hota hai, naaya gayab ho jaata hai

KYA. Hum frozen instant ko faulting instruction $I_{3}$ ke relative do groups mein split karte hain:

purane \to finish hone do I_{1}, I_{2} fault + naaye \to NOPs mein badal do I_{3}, I_{4}, I_{5}

"purane" = $I_{3}$ se chota program-order number. Inhe complete aur write back karna hi hai.
NOP ("no-operation") = ek fake instruction jo kuch nahi karta aur kuch nahi likhta. $I_{3}, I_{4}, I_{5}$ ko NOPs mein badalna flushing kehlaata hai — yeh guarantee karta hai ki woh kabhi official state touch nahi karenge.

KYUN. Yeh precise ki definition hai (parent se): all-older-done, faulting-and-younger-undone. Hum abhi clever nahi ho rahe — hum bas definition ko haath se enforce kar rahe hain.

PICTURE. $I_{1}, I_{2}$ ke liye WB se green check-marks nikl rahe hain. Laal X's $I_{3}, I_{4}, I_{5}$ ko khaali "bubbles" mein stamp kar rahe hain.

Step 4 — "In-order write-back" kyun quietly hero hai

KYA. Simple 5-stage pipeline mein stations physically ek line mein hain, isliye instructions WB par usi order mein pahunchte hain jisme unhone IF enter kiya. Program order apne aap us ek station par preserve hoti hai jahan matter karta hai.

Maano $c (I)$ = woh cycle jisme instruction $I$ WB par pahunchti hai. Kyunki belt kabhi ek instruction ko doosre ko overtake nahi karne deti:

I_{a} program order mein I_{b} se pehle ⟹ c (I_{a}) < c (I_{b})

Padho aise: purana hamesha pehle write back karta hai. Arrow $⟹$ matlab hai "guarantee karta hai."

YEH KYUN MATTER KARTA HAI. Precision chahti hai "official state mein saare purane results hain, koi bhi naaya result nahi hai." Agar write-backs strictly oldest-first hoti hain, toh jis pal $I_{2}$ WB finish karta hai, $I_{3}$ se purani har cheez committed hai aur koi bhi nayi cheez commit nahi hui — kyunki nayi cheezein belt par $I_{2}$ ke peeche hain. Wall khud ban jaati hai.

PICTURE. Ek timeline: WB events ek staircase mein line up hain, sabse purani sabse neeche-baaye, aur hum "commit frontier" mark karte hain — done aur not-done ko alag karne wali line — jo sirf program order mein rightward move hoti hai.

Step 5 — Belt todo: out-of-order execution ko wall chahiye

KYA. Fast modern CPUs ek instruction ko EX karne dete hain jaise hi uske inputs ready hote hain, chahe ek purani instruction stuck ho (dekho data hazards). Ab Step 4 ki guarantee gayi: $I_{4}$ apni arithmetic $I_{3}$ se pehle finish kar sakta hai.

Agar arithmetic finish karne ka matlab official registers likhna hota, toh precision toot jaati. Isliye hum execute-units ko bilkul official state likhne se mana karte hain. Balki har result Reorder Buffer (ROB) kehlaane wale waiting room mein park ho jaata hai.

ROB = ek queue of slots, ek per in-flight instruction, program order mein rakha gaya (woh order jisme woh issue hue, nahi ki jisme woh finish hue).
Har slot mein hai: konsi instruction, uski status (empty / done / faulted), aur uska computed result (abhi official nahi).

PROGRAM ORDER MEIN QUEUE KYUN. Execution timing scramble karta hai; ROB order wapas restore karta hai nikalne par. Yeh exactly Step-4 belt hai, ek data structure ke roop mein rebuild ki gayi taaki out-of-order EX se bach sake. Superscalar machines isi par lean karti hain — dekho superscalar mein ROB.

PICTURE. Execute units ek jumble mein fire karte hain (curvy arrows out of order pahunchte hain), lekin ROB slots neat program order mein rehte hain, done/faulted tags se bharte hain.

Step 6 — Commit: woh ek gate jo official state ko touch karta hai

KYA. Sirf ROB ke head par slot (sabse purani instruction) commit kar sakta hai — apna parked result official registers/memory mein copy karta hai aur chala jaata hai. Commit strictly head-first hoti hai, matlab program order mein.

Maano head slot mein instruction $I_{h}$ hai. Commit gate yeh maanta hai:

commit (I_{h}) ⟸ ⎩ ⎨ ⎧ status (I_{h}) = done status (I_{h}) = faulted status (I_{h}) = empty \Rightarrow result \to official state copy karo, head aage badhaao \Rightarrow yahan exception lo \Rightarrow wait karo (is cycle mein kuch nahi)

Term by term: $⟸$ matlab hai "commit gate is par decide karta hai"; done = result ready aur koi fault nahi; faulted = is instruction ne exception raise ki; empty = abhi finish nahi hua, isliye hum gate stall karte hain.

YEH AUTOMATICALLY PRECISE KYUN HAI. Kyunki official state sirf commit par change hoti hai aur commit strictly program order mein hoti hai, jab $I_{3}$ (faulted) head par pahunchta hai, har purani instruction pehle hi commit ho chuki hai (woh uske aage thi aur pehle chali gayi) aur koi bhi nayi instruction commit nahi ho sakti (woh queue mein uske peeche hain). Yahi precise-exception definition hai, queue ki geometry se enforce ki gayi.

PICTURE. ROB jisme $I_{1}, I_{2}$ committed hain (green mein ja rahe hain), $I_{3}$ head par faulted laal mein stamped hai, $I_{4}$ uske peeche ek finished-but-unpublished result liye baith hai.

Recall

$I_{4}$ leak kyun nahi ho sakta jab tak usne pehle finish kiya? Kyunki $I_{4}$ ROB queue mein $I_{3}$ ke peeche baitha hai aur sirf head commit karta hai. $I_{3}$ faulted hai, isliye gate wahan rok deta hai aur $I_{4}$ flush ho jaata hai — uska finished result kabhi official state tak nahi pahunchta. ::: Queue order, finish order nahi, decide karta hai kaun publish karta hai.

Step 7 — Edge case A: fault ek wrong-guess path par tha

KYA. CPU guess karta hai ki branch kis taraf jaata hai aur aage fetch karta hai (dekho branch prediction). Maano usne "not taken" guess kiya aur $I_{2} =$ DIV ..., R0 fetch kiya jo fault karta hai. Baad mein branch resolve hota hai: woh actually taken tha, isliye $I_{2}$ kabhi run hona hi nahi chahiye tha.

Rule: fault tabhi real hai jab instruction true path par ho — matlab tabhi jab woh kabhi ROB head par ek real (non-flushed) instruction ke roop mein pahunche.

exception raise karo ⟺ I ROB head tak pahunche AND I branch se squash na ho

$⟺$ matlab hai "exactly jab." Ek wrong-path instruction squash ho jaati hai pehle ki woh kabhi committing head ho sake, isliye uska fault silently gayab ho jaata hai.

KYUN. Precision matlab sequential semantics hai — aur ek sequential machine ne kabhi wrong-path instruction execute nahi ki hoti, isliye usne kabhi woh fault nahi dekha hota. Hum use discard karke uski nakal karte hain.

PICTURE. Do forked paths; guessed (wrong) branch ek red-fault $I_{2}$ carry karta hai; jab branch resolve hota hai toh wrong fork ek bade X se erase ho jaata hai, fault aur sab kuch, aur sahi fork continue karta hai.

Step 8 — Edge case B: ek hi cycle mein do faults

KYA. Do instructions ek saath exceptions signal karti hain. Maano $I_{3}$ (purani, EX mein divide-by-zero) aur $I_{4}$ (nayi, ID mein illegal opcode) dono cycle 5 mein chillate hain. Kaun jeetta hai?

Rule: purane waale ko program order mein report karo. Har fault ko uski instruction ke sequence number $n (I)$ (ROB mein uski position) ke saath tag karo aur minimum chuno:

fault taken = ar g I faulted min n (I)

Term by term: $n (I)$ program-order index hai; $ar g min$ matlab hai "woh $I$ jiske paas sabse chota aisa index hai" — sabse purana. $I_{4}$ samet baaki sab nayi flush ho jaati hain.

KYUN. Ek sequential machine $I_{3}$ tak pehle pahunchti hai $I_{4}$ se, isliye woh $I_{3}$ par rukti hai aur kabhi $I_{4}$ ke illegal opcode tak nahi pahunchti. Pipeline ne $I_{4}$ ki fault time mein pehle detect ki, lekin time matter nahi karta — program order karta hai. ROB pehle se hi program order se sort karta hai, isliye "head par fault lo" yeh apne aap de deta hai.

PICTURE. Ek frozen column mein do laal bursts; purani wali ( $I_{3}$ ) "winner" ki tarah circle ki gayi hai, nayi wali ( $I_{4}$ ) flushed ki tarah cross out ki gayi hai. Ek chhota side-note same-instruction priority list karta hai: fetch-fault > illegal/privilege > arithmetic (dekho memory/page faults).

Ek-picture summary

Upar sab kuch ek idea hai alag alag angles se dekha gaya: official state sirf ek single in-program-order gate par change ho sakti hai, isliye us gate par li gayi exception automatically precise hai. Final figure simple pipeline (Steps 1–4) aur ROB machine (Steps 5–8) ko ek flow mein fuse karta hai: instructions execution ke through scramble hoti hain, ROB mein wapas line up hoti hain, aur ek ek karke commit wall se pass karti hain — purani-done baaye taraf, faulted-aur-nayi daaye taraf flush.

Recall Feynman retelling — kisi dost ko samjhane jaisi baat

Ek bakery socho. Bakers (execute units) cakes kisi bhi order mein finish kar sakte hain — ek simple cake ek fancy wali se pehle jo pehle shuru hui, koi problem nahi. Lekin ek cashier (commit gate) hai aur saamne ek strict numbered line (ROB) hai. Cashier sirf line ke head wale ko serve karta hai, number order mein, aur sirf wahan ek cake actually shop se nikalta hai (official state banta hai).

Ab ek order impossible hai — "divide by zero," kuch nahi se bani cake. Baker us ticket ko "spoiled" tag karta hai. Uske peeche ki cakes already baki hain aur boxed hain, lekin woh nahi nikal sakti, kyunki cashier spoiled ticket tak pahunchta hai aur line rok deta hai. Spoiled ticket se aage ke sabhi log pehle hi nikal gaye — woh official hain. Isliye jis pal hum ruke: har purani cheez bahar hai, buri order aur har nayi cheez abhi bhi andar hai aur phenk di jaati hai. Yahi ek precise exception hai — aur woh precise hai clever timing ki wajah se nahi, balki one-cashier-in-numbered-order rule ki wajah se.

Do aur twists: (1) agar ek ticket ek guess se aayi jo galat nikli (ek mispredicted branch), toh hum use cashier tak pahunchne se pehle hi faad dete hain — uska "spoiled" tag kabhi count nahi hota. (2) Agar do tickets ek saath spoiled hain, cashier sirf chhote number wali ki parwah karta hai, kyunki ek-ek-karke ki duniya mein woh pehle usi tak pahunchta. ::: Wall, line, single cashier — yahi poori trick hai.

Dekho bhi: Hinglish version · 5.2.1-Pipelining-basics · 6.3.4-Reorder-buffer-in-superscalar.