Exercises — Out-of-order execution

• (a) RAW. I2, R1 read karta hai, jise I1 ne write kiya. Yeh ek true data dependency hai — value pehle actually produce honi chahiye. Renaming isse nahi hata sakti.
• (b) WAW. Dono R1 write karte hain. Sirf I2 ki write bachni chahiye. Yeh false hai (naam ka reuse). Renaming isse hata deti hai: I2 ko ek fresh physical register do.
• (c) WAR. I1, R1 read karta hai, phir I2 R1 overwrite karta hai. False — naam R1 ka reuse hi ek conflict hai. Renaming isse hata deti hai.
• (d) None. Alag-alag registers, poori tarah se independent, kisi bhi order mein execute ho sakte hain.

1. Fetch/Decode — in-order
2. Dispatch (reservation stations mein) — in-order
3. Execute — out of order (operands ready hone par fire karta hai)
4. Commit/Retire — in-order (ROB ke through, taaki precise exceptions rahe)

Memory hook: in — in — OUT — in. Sirf beech wala execute stage scramble karne ke liye free hai; dono ends ordered rehte hain taaki programmer ko kabhi pata na chale.

Har architectural register ki har write ko ek naye physical naam se map karo, aur har read ko sabse recent prior write ke physical naam se:

I1: T1 = R2 + R3
I2: R4 = T1 * R6      ; RAW on T1  -> must wait for I1
I3: T2 = R7 - R8      ; independent of everything above
I4: R9 = T2 + R5      ; RAW on T2  -> must wait for I3

• I1/I2 mein R1 T1 ban gaya; I3/I4 mein R1 T2 ban gaya. I1 aur I3 ke beech WAW (aur I2 aur I3 ke beech WAR) khatam ho gaye.
• Do independent chains bachi hain: {I1 → I2} aur {I3 → I4}. Woh parallel mein chalte hain.
• Unlimited ports aur 1-cycle ops ke saath: I1 aur I3 cycle 1 mein fire karte hain; I2 aur I4 cycle 2 mein fire karte hain. Poora block 2 cycles mein khatam hota hai 4 ki jagah.

Station CDB snoop karta hai, apna waiting tag P8 match hota dekh value capture kar leta hai: $\text{src1}\leftarrow 7,\text{Ready}(\text{src1})\leftarrow \text{true}.$ Ab $\text{Ready}(I)=\text{Ready}(\text{src1})\wedge \text{Ready}(\text{src2})=\text{true}\wedge \text{true}=\text{true}$. Dono operands cycle 4 ke end mein available hain ⇒ I agli cycle = cycle 5 mein fire karta hai, $7+12=19$ compute karta hai.

In-order. I2 kyun wait karta hai? Ek strict in-order machine mein koi instruction tabhi execute begin kar sakti hai jab har pehle wali instruction begin kar chuki ho (execute stage program order mein dispatch karta hai). To in-order machine mein bhi I2 ka I1 par koi dependency nahi hone ke bawajood, woh I1 ke peeche dispatch queue mein fansa hai aur tab tak start nahi kar sakta jab tak I1 ka 3-cycle LOAD execute slot clear na kar de. Yahi ek ordering rule hai jise OoOE relax karega. Har column neeche ek cycle hai; seedha neeche padhkar dekho ki kaun sa op kaun se cycle mein hai:

Cycle:  1    2    3    4    5    6
I1:    [L]  [L]  [L]
I2:                   [+]
I3:                        [-]
I4:                             [*]
Total span = 6 cycles

Out-of-order — do chains dekho: I1(3c) → I3(1c) aur I2(1c) → I4(1c). Free ports ke saath, dependencies (program order nahi) firing decide karti hain:

Cycle:  1    2    3    4
I1:    [L]  [L]  [L]
I2:    [+]                  (independent, fires cycle 1)
I4:         [*]             (needs I2 done end of cy1, fires cycle 2)
I3:                   [-]   (needs I1 done end of cy3, fires cycle 4)
Total span = 4 cycles

• Chain 1 critical length = $3+1=4$ cycles → yahi critical path hai.
• Chain 2 length = $1+1=2$ cycles, poori tarah chain 1 ke neeche chhup jaati hai.
• Speedup $=6/4=1.5\times$.

Limit critical-path-limited ILP hai: sabse lamba dependency chain. Yahan woh I1 → I3 hai length $3+1=4$ cycles ke saath. Infinite resources ke saath bhi tum I3 ko I1 ka LOAD result aane se pehle start nahi kar sakte (ek true RAW dependency hai), isliye 4 cycles hard floor hai. OoOE unrelated work ka wait hataata hai — woh apne inputs ka wait kabhi nahi hata sakta.

Commit head se in-order hota hai, $\text{Can\_Commit}(I_h)=\text{Complete}(I_h)\wedge \neg \text{Exception}(I_h)$ use karke.

• (a) Head aage badhta hai: I1 commit karta hai, I2 commit karta hai. Phir head = I3, jo complete hai lekin Exception true hai ⇒ ruk jao. To fault se pehle exactly 2 instructions ($I_1,I_2$) commit karti hain.
• (b) I4 aur I5 squash / flush ho jaate hain. Unki computed values sirf ROB ke andar rehti hain, kabhi architectural registers ya memory mein nahi jaatii, isliye woh simply khatam ho jaati hain. Isliye speculative results safe hain: fault ke baad kuch bhi kabhi visible nahi hua.
• (c) Exception handler chalta hai; architectural state = post-I2. OS cause fix kar sakta hai aur execution I3 par restart kar sakta hai. Programmer clean semantics dekhta hai: "I3 fault hua, iske baad kuch nahi hua."

Ek 100-cycle miss resolve hote waqt retiring jaari rakhne ke liye, window (ROB) mein commit rate ke hisaab se poori latency cover karne ke liye kaafi independent instructions honi chahiye: $\text{Window}\gtrsim \text{commit rate}\times \text{latency}=4\times 100=\boxed{400\text{ instructions}}.$ (Yahan issue rate ≥ commit rate hai, isliye ROB bharta hai aur commit rate woh hai jo miss ke baad sustain hona chahiye.) Yahi reason hai ki real designs windows ko 200–600 entries tak push karte hain — jitna gehri memory latency hide karni ho, utna bada window (aur ROB, physical register file, load/store buffers) hona chahiye. Is size se neeche ROB bharta hai, head outstanding LOAD par stall karta hai, aur commit halt ho jaata hai.

Ek port ke saath, port ek shared resource hai. Total work = $3+1+1+1=6$ port-cycles, isliye hum kisi bhi order mein cycle 6 se pehle khatam nahi ho sakte — execution-width-limited. Ek valid schedule (har column = ek cycle):

Cycle:  1    2    3    4    5    6
Port:  [L]  [L]  [L]  [+]  [*]  [-]
Op:     I1   I1   I1   I2   I4   I3

I2 aur I4 tab fire karte hain jab port cycle 4 par free hota hai (I4 cycle 5 mein I2 ka result end of cycle 4 milne ke baad); I3 last fire karta hai (uska input I1 cycle 3 ke end mein ready tha, lekin port cycle 6 tak busy hai).

• Span = 6 cycles, speedup $=6/6=1.0\times$. Reordering ne yahan kuch nahi diya.
• Lesson: OoOE tabhi help karta hai jab bottleneck ke alawa koi resource idle ho. Single port poori tarah occupied hone par, tum $\text{Execution width}$ se limited ho, jo is cheez ka middle term hai: $\text{IPC}\le \min (\text{Window-limited ILP},\text{Execution width},\text{Critical-path-limited ILP}).$ Yeh L3.2 ka flip side hai, jahan critical path binding limit tha.

• (a) Critical path. 26-deep RAW chain $\ge 26$ cycles force karta hai chahe kitne bhi ports ho ya window kitni bhi badi ho — tum apni khud ki dependencies se aage nahi bhaag sakte.
• (b) Window. Independent work exist karta hai aur ports plentiful hain, lekin tum ek baar mein sirf 8 instructions dekh sakte ho, isliye tum kabhi zyada der tak 4 ports feed nahi kar sakte. Window badhaao aur IPC badhega.
• (c) Execution width. Window (500) aur independence dono kaafi hain, isliye unhi mein se koi bind nahi karta. Limiting term 2 ports hai: zyada se zyada 2 adds per cycle start ho sakte hain, isliye 1000 independent adds $1000/2=500$ cycles lete hain. Zyada ports add karna speed up karega; bada window nahi.

Renaming se hatai jaane wali false dependencies hain ::: WAR aur WAW (RAW nahi) OoOE machine mein commit order hota hai ::: strictly in program order, ROB ke zariye Infinite resources ke saath completion time ka hard floor set karta hai ::: critical path (sabse lamba true-dependency chain) 4 commits/cycle par 100-cycle miss hide karne ke liye zaroori window lagbhag hai ::: 400 in-flight instructions L3.1 in-order vs OoOE (unlimited ports) ka speedup ::: 6/4 = 1.5×