Out-of-order execution — Hinglish notes

5.3.2 · Hardware › Advanced Microarchitecture

Out-of-order execution kya hai?

YEH kyun chahiye?

In-order processors tab stall ho jaate hain jab unhe data dependency ya cache miss milti hai
Modern instructions ki latencies bahut alag hoti hain: register ops (1 cycle), L1 cache (4 cycles), memory (100+ cycles)
OoOE ke bina, CPU cycles waste karta hai wait karte hue, chahe independent kaam maujood ho

YEH kaise kaam karta hai? CPU instruction lifecycle ko alag phases mein separate karta hai jo independently operate kar sakte hain:

Fetch/Decode (in-order): Instructions pipeline mein enter karte hain
Dispatch (in-order): Instructions reservation stations mein allocate hoti hain
Execute (OUT-OF-ORDER): Instructions tab fire hoti hain jab operands ready hon
Commit/Retire (in-order): Results program order mein write back hote hain

Tomasulo algorithm ka foundation

Modern OoOE Tomasulo's algorithm (IBM 360/91, 1967) se trace hoti hai. Chaliye first principles se key insight derive karte hain.

Problem: Register renaming aur dynamic scheduling.

Yeh code consider karo:

R1 = R2 + R3    ; (I1)
R4 = R1 * R5    ; (I2) - I1 par depend karta hai
R1 = R6 - R7    ; (I3) - I1 ke saath WAW hazard
R8 = R1 + R9    ; (I4) - I3 par depend karta hai, I1 par NAHI

In-order execution: I2 waits for I1, I3 waits for I2, I4 waits for I3 → serial execution.

Insight: R1 ke do uses alag logical values hain. Agar hum unhe rename karein:

T1 = R2 + R3    ; (I1) renamed
R4 = T1 * R5    ; (I2) 
T2 = R6 - R7    ; (I3) renamed
R8 = T2 + R9    ; (I4)

Ab I3 aur I1 parallel mein execute ho sakte hain! I4 sirf I3 par depend karta hai, I1 par nahi.

YEH step kyun? False dependencies todne se true data-flow graph expose hota hai. CPU ab koi bhi instruction issue kar sakta hai jiske inputs ready hain.

Reservation stations aur execution

Ready condition ka derivation:

Maano instruction $I$ ko operands $src_{1}, src_{2}$ chahiye. Har operand ya toh:

Ready hai: value reservation station mein hai
Waiting hai: producer instruction $P_{j}$ ke tag ke saath

$Ready (I) = Ready (src_{1}) \land Ready (src_{2})$

Jab producer $P_{j}$ complete hota hai, woh CDB par (tag: Pj, value: V) broadcast karta hai. Sare reservation stations CDB snoop karte hain aur:

$\forall I : (src_{i} = P_{j}) \Rightarrow (src_{i} \leftarrow V, Ready (src_{i}) \leftarrow true)$

Broadcast kyun? Multiple instructions ek hi result ka wait kar sakti hain. Sare stations ko parallel mein broadcast karna sequential wakeup delays se bachata hai.

Worked example Worked example: OoOE in action

Yeh sequence consider karo. Maano sab ops 1 cycle lete hain except LOAD jo 3 cycles leta hai. Hum ek cycle "used" count karte hain har us cycle ke liye jisme instruction execute ho raha hai, aur ek dependent instruction tab fire hoti hai jab uska last operand available ho, us cycle ke baad.

I1: R1 = LOAD [addr1]   ; 3 cycles
I2: R2 = R3 + R4        ; 1 cycle
I3: R5 = R1 + R2        ; 1 cycle - I1 aur I2 par depend karta hai
I4: R6 = R7 * R8        ; 1 cycle - independent

In-order execution timeline:

Cycle: 1   2   3   4   5   6
I1:    L   L   L
I2:                +
I3:                    +
I4:                        *
Total: 6 cycles

I2, I4 slow load aur uski dependent chain ke peeche unnecessarily wait karte hain.

Out-of-order execution timeline:

Cycle: 1   2   3   4   5
I1:    L   L   L
I2:    +
I4:        *
I3:                +
Total: 5 cycles

Yeh step kyun? I2 aur I4 ka I1 par koi dependency nahi hai, isliye woh free execution ports par jaldi execute ho jaate hain (I2 cycle 1 mein, I4 cycle 2 mein). I1 ka LOAD cycles 1–3 occupy karta hai (uska poora 3-cycle latency). I3 ko I1 ka result chahiye (cycle 3 ke end mein ready) aur I2 ka result (cycle 1 ke end mein ready), isliye I3 cycle 4 mein fire karta hai. Pipeline drain hoti hai aur I3 ka result cycle 4 ke end tak available ho jaata hai; commit settling samait total span 5 cycles hai.

Speedup: $6/5 = 1.2 \times$ is chote example par. Key point yeh hai ki OoOE I2 aur I4 ke unnecessary stalls hatata hai; residual latency genuine dependency chain I1 → I3 se aati hai. Real code mein zyada independent kaam aur longer chains ke saath 2–3× improvements dikhte hain.

Reorder buffer (ROB)

Problem: Out-of-order execution out-of-order completion create karta hai. Lekin humein precise exceptions chahiye: agar instruction 5 fault kare, toh instructions 1-4 commit honi chahiye, 6+ nahi.

Commit logic ka derivation:

ROB entries ko ${I_{1}, I_{2}, \dots, I_{n}}$ maano program order mein. Head $h$ par:

$Can_Commit (I_{h}) = Complete (I_{h}) \land \neg Exception (I_{h})$

Agar $Exception (I_{h})$ ho:

$h$ ke baad ke sab entries flush karo
Architectural state ko $I_{h}$ ke input par roll back karo
OS ko exception signal karo

In-order commit kyun? Yeh illusion maintain karne ke liye ki instructions sequentially execute hue. External observers (memory system, interrupts, debuggers) results aise dekhte hain jaise program in-order chala ho.

Formula Speculation window (qualitative model)

Instruction window woh set hai in-flight instructions ka fetch aur commit ke beech. Larger window CPU ko aage dekhne deta hai independent kaam dhundne ke liye. Qualitatively, achievable IPC teen competing limits se bounded hai: $IPC \leq min (Window-limited ILP, Execution width, Critical-path-limited ILP)$

Jahan:

Window-limited ILP: aap sirf un instructions ko reorder kar sakte ho jo abhi window mein hain
Execution width: parallel execution units / issue ports ki sankhya
Critical-path-limited ILP: infinite resources bhi longest dependency chain ko beat nahi kar sakta

Modern CPUs: window size ~200-300 instructions (Intel, AMD) se ~600+ tak (Apple M-series).

Yeh bound kyun (koi precise formula nahi): Yeh ek conjecture-level upper bound hai, koi derived closed form nahi. Window itni badi honi chahiye ki independent kaam expose ho sake, lekin agar dependencies dominate karein toh aap critical-path limit par pahunch jaate ho, aur agar resources dominate karein toh execution-width limit par. Real IPC branch prediction accuracy, cache behavior, aur memory-level parallelism par depend karta hai jinhe koi single clean equation capture nahi kar sakti.

Worked example ROB commit with exception

ROB: [I1✓, I2✓, I3(fault), I4✓, I5✓]
          ^head

I1 aur I2 already committed hain. I3 head par hai aur fault hua hai (e.g., divide-by-zero). I4 aur I5 execute ho gaye hain lekin speculatively execute hue hain.

Commit logic:

I3 fault karta hai → exception handler trigger hota hai
I4, I5 ko ROB se flush karo (unke results discard ho jaate hain)
Architectural state = post-I2
OS exception handle karta hai, possibly fix karke I3 par restart karta hai

Yeh step kyun? User code clean semantics dekhta hai: "I3 faulted, uske baad kuch nahi hua." Chahe I4 aur I5 ne internally results compute kiye, woh results kabhi visible nahi hue (architectural registers/memory mein kabhi commit nahi hue).

Common mistakes

Common mistake Mistake 3: "OoOE stores ko freely reorder kar sakta hai"

Kyun sahi lagta hai: Agar stores independent hain, toh speed ke liye unhe out-of-order execute karo.

Steel-man: Yeh memory consistency models todta hai. Consider karo:

Thread 1:        Thread 2:
store [X] = 1    load r1 = [Y]
store [Y] = 1    load r2 = [X]

Agar Thread 1 stores reorder kare, toh Thread 2 r1=1, r2=0 dekh sakta hai (Y likha gaya lekin X nahi abhi tak), sequential consistency violate ho jaata hai.

Fix: OoOE ko memory ordering rules respect karne chahiye:

x86: Total Store Order (TSO) → stores program order mein commit hote hain
ARM/RISC-V: relaxed models reordering allow karte hain lekin fence instructions provide karte hain Store buffer stores ko queue karta hai aur unhe order mein drain karta hai (ya explicit fences ke saath).

Memory model interaction

OoOE multi-core ke saath kaise interact karta hai:

Har core ka OoOE engine single-threaded illusion maintain karta hai. Lekin caches shared/coherent hain. Memory consistency model define karta hai ki kaunse reorderings cores ke beech visible hain.

x86 TSO ke liye, allowed aur forbidden reorderings yeh hain:

Loads older loads ke saath reorder NAHI hote (Load→Load order preserved)
Loads alag address par older stores ko pass KAR SAKTE hain (Store→Load reordering allowed; yeh woh ek relaxation hai jo TSO permit karta hai)
Stores older stores ke saath reorder NAHI hote (Store→Store order preserved, commit par enforce hota hai)
Stores older loads ke saath reorder NAHI hote (Load→Store order preserved)

Yeh rules kyun? Performance balance karna (common Store→Load relaxation ko store buffer ke through allow karna) vs. programmer sanity (baaki jagah intuitive ordering preserve karna).

Worked example OoOE + cache coherence

Core 0:              Core 1:
store [X] = 1        load r1 = [Y]
store [Y] = 1        load r2 = [X]

Core 0 ka OoOE dono stores jaldi compute kar sakta hai, lekin woh store buffer mein baithe hain. ROB unhe in-order commit karta hai, program order mein cache coherence invalidations send karta hai. Core 1 ke loads MESI protocol ke through yeh invalidations snoop karte hain. TSO ke under, Core 1 ke dono loads bhi order mein rehte hain, isliye woh r1=1 (Y=1) ke saath r2=0 (X still 0) observe nahi kar sakta.

Performance metrics

ILP wall: typical programs mein average ~2-3 independent instructions per cycle hoti hain. Perfect OoOE bhi is limit ko hit karta hai. Modern CPUs ise compensate karte hain:

Wider issue (4-6 wide dispatch)
Deeper speculation (branch prediction)
Simultaneous multithreading (SMT/Hyper-Threading)

Connections

5.1.01-Pipelining: OoOE pipelining extend karta hai stages ko decouple karke
5.3.01-Superscalar-architecture: OoOE superscalar enable karta hai (multiple issue per cycle)
5.3.03-Speculative-execution: OoOE + branch prediction = speculative execution
5.3.04-Register-renaming: RAT mechanism detail mein
5.4.01-Cache-coherence: OoOE multicore mein MESI/MOESI kaise respect karta hai
5.5.02-Memory-consistency-models: TSO, relaxed models, aur fence instructions
6.2.03-Branch-prediction: Control flow predict karna window ko full rakhne ke liye
7.1.01-Instruction-level-parallelism: Theoretical limits (data-flow graphs)

Recall Ek 12-saal ke bacche ko explain karo

Socho tum homework kar rahe ho 5 problems ke saath. Problem 1 ke liye library se ek book chahiye (tumhare parent 10 minute mein laayenge). Problem 2, 3, 4 easy math hai jo tum abhi kar sakte ho. Problem 5 ko problem 1 ka answer chahiye.

Buri strategy (in-order): Problem 1 ka wait karo (10 min), karo, phir 2, 3, 4, phir 5. Total: 10 + 1 + 1 + 1 = 14 minutes.

Smart strategy (out-of-order): Problems 2, 3, 4 abhi karo (3 min). Jab book aaye, 1 karo (1 min), phir 5 (1 min). Total: 3 + 1 + 1 = 5 minutes.

Tum 3× faster finish karte ho! CPU bhi yahi karta hai: slow memory ka wait karte waqt ("library book"), woh dusri instructions par kaam karta hai ("easy math"). Final answers sahi order mein rakhta hai taaki teacher (programmer) ko kabhi pata na chale ki tumne out-of-order kiya.

#flashcards/hardware

In-order aur out-of-order execution mein key difference kya hai?

In-order instructions ko strictly program order mein execute karta hai, dependencies par stall karta hai. Out-of-order execution ko dynamically reorder karta hai taaki instructions tab issue hon jab operands ready hon, saath mein correct architectural state ke liye in-order commit maintain karta hai.

Teen types ke hazards kya hain, aur register renaming kaun se eliminate kar sakta hai?

RAW (Read-After-Write) = true dependency, eliminate nahi ho sakta. WAR (Write-After-Read) aur WAW (Write-After-Write) = false dependencies jo register reuse se hoti hain, alag physical registers par rename karke eliminate ho jaati hain.

Reorder buffer (ROB) ka purpose kya hai?

ROB in-order commit maintain karta hai chahe execution out-of-order ho. Yeh precise exceptions enable karta hai fault ke baad speculative instructions flush karke, aur ensure karta hai ki architectural state program order mein update ho.

Ek reservation station ko kaise pata chalta hai ki instruction execute ke liye ready hai?

Ek instruction ready hoti hai jab sab source operands ya toh (1) values ke saath already present hain, ya (2) unke producer tags Common Data Bus (CDB) par broadcast ho chuke hain. Station CDB snoop karta hai aur results aane par operands update karta hai.

x86 TSO ke under, kaun sa ek reordering allowed hai?

Sirf alag addresses par Store→Load reordering: ek load ek older store ko alag address par pass kar sakta hai (store buffer ke through). Load→Load, Store→Store, aur Load→Store orderings sab preserve hote hain.

Infinite instruction window size ke saath bhi IPC scaling ko kya limit karta hai?

Critical path (longest dependency chain) aur Amdahl's law. Programs mein data dependencies ki wajah se limited instruction-level parallelism hoti hai, isliye unlimited resources bhi serial bottlenecks ko parallelize nahi kar sakta. Typical saturation IPC ≈ 2-4 par hoti hai.