Superscalar execution: Exercises — Hinglish deep dive

5.3.1 · D4 · Hardware › Advanced Microarchitecture › Superscalar execution

Shuru karne se pehle, yeh woh ek formula hai jis par zyaadatar problems depend karti hain. Hum ise repeat kar rahe hain taaki koi bhi symbol use hone se pehle naam liya ja sake.

Formula IPC bottleneck formula

$IPC = min (W, min_{i} \frac{F _{i}}{p _{i}}, \frac{W \cdot ROB}{D \cdot L _{avg}})$ Har symbol ko plain words mein padhna:

$W$ = issue width — kitni instructions front-end har clock cycle mein fetch/decode/rename kar sakta hai. Ek hard ceiling.
$F_{i}$ = type $i$ ke functional units ki sankhya (jaise 3 integer ALUs → $F_{int} = 3$ ). Ek functional unit hardware ka woh tukda hai jo actually ek tarah ka kaam karta hai.
$p_{i}$ = chal rahe program mein un instructions ka fraction jo unit type $i$ ki zaroorat rakhte hain. Saare $p_{i}$ milake $1$ bante hain.
$\frac{F _{i}}{p _{i}}$ = woh throughput ceiling jo us unit type se impose hoti hai. Socho: "Main har cycle mein $F_{i}$ ye kaam kar sakta hoon, lekin mere kaam ka sirf ek fraction $p_{i}$ is type ka hai, isliye is unit ke choke hone se pehle main $F_{i} / p_{i}$ total instructions per cycle sustain kar sakta hoon."
Edge case $p_{i} = 0$ : agar koi program unit type $i$ ka bilkul use nahi karta, toh woh unit kabhi bottleneck nahi ban sakti, isliye hum simply us term ko $min$ se drop kar dete hain (formally $F_{i} /0 \to \infty$ , ek infinitely high ceiling jo kabhi sabse chhoti nahi ho sakti). $F_{i} /0$ ko kabhi ek number ke roop mein mat likho.
$ROB$ = reorder buffer size — ek baar mein machine kitni in-flight instructions track kar sakti hai (uski lookahead window).
$D$ = average dependency-chain length — ek row mein kitni instructions baithe hain jahan har ek apne se pehle wale ke result ka wait karti hai.
$L_{avg}$ = cycles mein average instruction latency (ek instruction start se result tak kitna time leti hai). Hum hamesha poora subscript $L_{avg}$ likhte hain — kabhi bhi bare $L$ nahi — taaki yeh kisi aur cheez se confuse na ho.
Overall $min$ sabse tight ceiling chunti hai — asli bottleneck.

Level 1 — Recognition

Worked example L1.1 — Hazard ka naam batao

Har pair ke liye, dependency type batao (RAW / WAW / WAR):

(a) ADD R1, R2, R3   then   MUL R4, R1, R5
(b) ADD R1, R2, R3   then   SUB R1, R6, R7
(c) SUB R8, R1, R9   then   ADD R1, R6, R7

Yeh bhi batao: inme se kaunse ko register renaming eliminate karti hai?

Recall Solution L1.1

(a) RAW (Read After Write): MUL woh R1 read karta hai jo ADD ne abhi write kiya. Yeh ek true data dependency hai — value genuinely flow karni chahiye. Renaming ise nahi hata sakti.
(b) WAW (Write After Write): dono instructions R1 write karti hain. Ek false (naam-wali) dependency. Renaming ise eliminate karti hai har write ko alag physical register pe bhejke.
(c) WAR (Write After Read): pehla R1 read karta hai, doosra R1 write karta hai. Ek false (anti-)dependency. Renaming ise eliminate karti hai taaki writer woh value na chhupa de jo reader ko abhi bhi chahiye.
Renaming (b) aur (c) hataati hai; (a) rehta hai.

Recall Solution L1.2

"4-wide" = front-end issue width $W = 4$ : har cycle mein zyaadase zyaada 4 instructions fetch/decode/rename hoti hain.
"6 execution ports" = 6 jagah jahan instructions execute ke liye bheji ja sakti hain har cycle mein, yaani total execution back-end 6/cycle accept kar sakta hai ( $F_{i}$ functional units mein spread hokar).
4 wala $W$ hai. Dhyan do ki back-end (6) front-end (4) se zyaada wide hai — yeh ek common design hai taaki narrow front-end back-end se kabhi starved na ho.

Level 2 — Application

Recall Solution L2.1

Har ceiling compute karo, phir min lo.

$W = 4$ .
Integer: $\frac{3}{0.4} = 7.5$
FP: $\frac{2}{0.2} = 10$
Memory: $\frac{2}{0.3} = 6.67$
Branch: $\frac{1}{0.1} = 10$ → tightest FU ceiling $= 6.67$ .
Dependency: $\frac{W \cdot ROB}{D \cdot L _{avg}} = \frac{4 \times 128}{3 \times 2} = \frac{512}{6} = 85.3$ . $IPC = min (4, 6.67, 85.3) = 4$ Front-end width bottleneck hai; machine ke paas kaafi units aur lookahead hai.

Recall Solution L2.2

Pehle, FP edge case. Is program mein $p_{FP} = 0$ hai: koi bhi instruction FP unit use nahi karti. Formula ke edge-case rule se, $F_{FP} / p_{FP} = 2/0 \to \infty$ — ek infinitely high ceiling jo kabhi sabse chhoti nahi ho sakti — isliye hum FP term ko bilkul drop kar dete hain aur woh neechey koi role nahi khelti.

$W = 4$ .
Integer: $\frac{3}{0.3} = 10$
FP: $p_{FP} = 0 \Rightarrow$ term dropped (kabhi bottleneck nahi).
Memory: $\frac{2}{0.6} = 3.33$ ← tightest
Branch: $\frac{1}{0.1} = 10$
Dependency: $\frac{W \cdot ROB}{D \cdot L _{avg}} = \frac{4 \times 128}{3 \times 2} = 85.3$ . $IPC = min (4, FU = 3.33 min (10, 3.33, 10), 85.3) = 3.33$ Bottleneck: memory ports. Sirf 2 load/store units hain, lekin 60% kaam unhe chahiye.

Figure dekho: har colored bar ek ceiling hai. Sabse chhota bar jeetता hai — yeh $min$ ka visual matlab hai. L2.1 mein width bar sabse chhota hai; L2.2 mein memory bar width bar se neechey gir jaata hai aur limiter ban jaata hai. Dhyan do ki L2.2 mein koi FP bar nahi hai — ek dropped $p_{i} = 0$ term simply appear hi nahi karta.

Level 3 — Analysis

Recall Solution L3.1

$W = 4$ .
FU ceilings unchanged (same 40/20/30/10 mix): $min (\frac{3}{0.4}, \frac{2}{0.2}, \frac{2}{0.3}, \frac{1}{0.1}) = min (7.5, 10, 6.67, 10) = 6.67$ (memory).
Dependency: $\frac{W \cdot ROB}{D \cdot L _{avg}} = \frac{4 \times 8}{4 \times 3} = \frac{32}{12} = 2.67$ . $IPC = min (4, 6.67, 2.67) = 2.67$ Ab dependency term dominate karta hai. Physically: ROB (lookahead window) itna chhota hai ki machine kaafi aage nahi dekh sakti taaki long chains stall hone par independent kaam dhundh sake. Functional units idle baithe hain wait mein — kaafi execution muscle hai, lekin koi independent instructions feed karne ke liye nahi hain.

Recall Solution L3.2

Current bottleneck (L2.2 se) memory hai: $F_{mem} / p_{mem} = 2/0.6 = 3.33$ . FP term drop hai ( $p_{FP} = 0$ ). Hum ab har fix ke liye $min$ ki teeno terms dikhate hain.

Fix A ( $W = 6$ ): sirf $W$ badalta hai. FU ceilings hain $min (\frac{3}{0.3}, \frac{2}{0.6}, \frac{1}{0.1}) = min (10, 3.33, 10) = 3.33$ . Dependency banta hai $\frac{6 \times 128}{3 \times 2} = \frac{768}{6} = 128$ . Toh $IPC_{A} = min (6, 3.33, 128) = 3.33.$ Memory abhi bhi sabse chhota hai — front-end widen karna aur window bada karna dono apni-apni terms badhate hain, lekin koi memory ceiling ko nahi chhota. IPC 3.33 rehta hai; silicon waste hota hai.
Fix B (3rd L/S unit): memory ceiling ban jaata hai $\frac{3}{0.6} = 5.0$ . FU ceilings $min (\frac{3}{0.3}, \frac{3}{0.6}, \frac{1}{0.1}) = min (10, 5.0, 10) = 5.0$ . Width $= 4$ , dependency $= \frac{4 \times 128}{3 \times 2} = 85.3$ . Toh $IPC_{B} = min (4, 5.0, 85.3) = 4 .$

Fix B kaam karta hai, IPC ko 3.33 se 4 tak uthata hai (ab width-limited hai: $4$ teeno mein sabse chhota hai). Asli bottleneck par attack karo, na ki sabse bada-sounding knob par.

Level 4 — Synthesis

Recall Solution L4.1

Target: har ceiling $\geq 4$ , aur $min = 4$ taaki width (cheapest) binding term ho. FP absent hai ( $p_{FP} = 0$ , term dropped).

Width: $W \geq 4$ chahiye. $W = 4$ chuno (sabse chhota jo IPC 4 allow karta hai).
Memory ( $p = 0.5$ ): $\frac{F _{mem}}{0.5} \geq 4 \Rightarrow F_{mem} \geq 2$ chahiye. 2 chuno.
Integer ( $p = 0.3$ ): $\frac{F _{int}}{0.3} \geq 4 \Rightarrow F_{int} \geq 1.2$ chahiye. 2 chuno (integer count hona chahiye, $1$ se $1/0.3 = 3.33 < 4$ milega).
Branch ( $p = 0.2$ ): $\frac{F _{br}}{0.2} \geq 4 \Rightarrow F_{br} \geq 0.8$ chahiye. 1 chuno. Saari terms check karo: $min (W 4, m i n (4, 6.67, 5) = 4 min (2/0.5, 2/0.3, 1/0.2), dep ≫ 4) = 4$ . ✔ Minimal design: $W = 4$ , 2 mem, 2 int, 1 branch. Dhyan do ki integer ko 2 (1 nahi) chahiye tha sirf isliye ki tum fractional unit nahi khareed sakte.

Recall Solution L4.2

In-flight writers ke renaming ke liye available physical registers $= 192 - 32 = 160$ .
Har in-flight writer ko ek chahiye. In-flight instructions mein write karne wali fraction $= 0.70$ .
Toh ROB $N$ entries rakh sakta hai jahan $0.70 \times N \leq 160 \Rightarrow N \leq \frac{160}{0.70} = 228.6$ .
Sabse bada usable ROB $= 228$ entries. Interpretation: agar ROB 228 se bada banaaya jaata, toh physical register file pehle dry ho jaati — dono structures ko saath mein size karna padta hai (dekho Register Renaming aur Reorder Buffer).

Level 5 — Mastery

Recall Solution L5.1

Design X: ceilings — $W = 6$ ; mem $2/0.5 = 4$ ; int $3/0.3 = 10$ ; branch $1/0.2 = 5$ ; dep $≫ 6$ . $IPC_{X} = min (6, 4, 10, 5, ≫ 6) = 4$ (memory-limited). Design Y: ceilings — $W = 4$ ; mem $3/0.5 = 6$ ; int $2/0.3 = 6.67$ ; branch $1/0.2 = 5$ ; dep $≫ 4$ . $IPC_{Y} = min (4, 6, 6.67, 5, ≫ 4) = 4$ (width-limited). Same IPC = 4 is workload par!

Power ke liye ship karo: Design Y. Yeh IPC 4 narrow front-end ( $W = 4$ ) se achieve karta hai. Front-end width ek core ka sabse zyaada power-hungry hissa hota hai (wide fetch, wide decode, wide rename, zyaada wakeup logic). Y yahan same throughput ke liye kam power burn karta hai — power budget mein sensible pick.
Jab X jeetता hai — alternate workload. Ek compute-heavy mix lo 15% memory / 65% integer / 20% branch (abhi bhi 0% FP). Dono designs ko us par recompute karo:
- Design X ( $W = 6$ , 2 mem, 3 int, 1 branch): mem $\frac{2}{0.15} = 13.33$ ; int $\frac{3}{0.65} = 4.62$ ; branch $\frac{1}{0.2} = 5$ ; dep $≫ 6$ . Toh $IPC_{X} = min (6, 13.33, 4.62, 5, ≫ 6) = 4.62$ (integer-limited).
- Design Y ( $W = 4$ , 3 mem, 2 int, 1 branch): mem $\frac{3}{0.15} = 20$ ; int $\frac{2}{0.65} = 3.08$ ; branch $\frac{1}{0.2} = 5$ ; dep $≫ 4$ . Toh $IPC_{Y} = min (4, 20, 3.08, 5, ≫ 4) = 3.08$ (integer-limited).
- Ab X jeetता hai, $4.62$ vs $3.08$ . Kam memory traffic aur zyaada integer kaam ke saath, X ka extra ALU (3 vs 2) aur uska wider front-end ( $6$ vs $4$ ) dono pay off karte hain, jabki Y ke 2 ALUs 65% integer stream par choke karte hain. Moral: koi bhi design "best" nahi hai — winner program ke mix par depend karta hai.

Neechey wala figure pehle (50/30/20) comparison ko bars mein convert karta hai. Ise aise padho: har design ke liye, sabse chhota bar woh ceiling hai jo bind karta hai. Design X ka memory bar (4) uska sabse chhota hai — X memory-limited hai. Design Y ka width bar (4) uska sabse chhota hai — Y width-limited hai. IPC 4 par dashed line dikhati hai ki dono alag-alag routes se ek hi height par land karte hain, jo is exercise ka poora point hai.

Recall Solution L5.2

"Instructions per branch" mein kaam karo as natural chunk.

Instructions ka fraction jo branches hain $= 0.20$ , toh average par har $1/0.20 = 5$ instructions mein 1 branch hoti hai.
Misprediction rate $= 1 - 0.92 = 0.08$ . Toh mispredict average par har $5/0.08 = 62.5$ instructions mein hota hai.
Un 62.5 instructions ke liye cycles: useful cycles $= 62.5/4 = 15.625$ (IPC 4 par running), plus ek penalty $= 14$ cycles.
Effective IPC $= \frac{62.5}{15.625 + 14} = \frac{62.5}{29.625} = 2.11$ . Lesson: ek deep-pipeline wide machine par 8% miss rate real throughput almost half kar deta hai — exactly isliye branch prediction accuracy itne silicon ki haqdar hai. Is dynamic-scheduling cost ko compiler-scheduled VLIW Architecture approach se compare karo, aur note karo ki Tomasulo's Algorithm woh out-of-order engine provide karta hai jo mispredicts ke beech IPC ko $W$ ke paas rakhta hai.