Visual walkthrough — Simultaneous multithreading (SMT - hyperthreading)

5.3.14 · D2 · Hardware › Advanced Microarchitecture › Simultaneous multithreading (SMT - hyperthreading)

Parent note claim karta hai ki two-way SMT se throughput speedup lagbhag $1.6\times$ milta hai — na ki $2\times$ jo aap expect kar sakte ho. Yeh page us number ko bilkul zero se build karta hai, ek picture ek time pe. Hum kuch bhi assume nahi karte siway iss ke: ek processor har clock tick pe kaam karta hai, aur kabhi kabhi kaam nahi kar sakta.

Agar aapne abhi tak kai execution units ek saath kaam karne ka idea nahi dekha, toh pehle Superscalar Processors dekho — lekin jo bhi chahiye woh sab yahan re-build kiya gaya hai.

---

Step 1 — "Cycle" aur "execution unit" actually hote kya hain

KYA HOTA HAI. Ek processor clock ki beat pe chalta hai. Har tick ek cycle hota hai. Core ke andar chhote worker-machines hote hain jinhe execution units kehte hain — ek ALU numbers add karta hai, ek FPU decimals handle karta hai, ek load/store unit memory se baat karta hai. Hum in units ki sankhya $N$ likhte hain; hamare running example mein $N=4$ hai, toh ek tick mein chaar kaam ho sakte hain.

YEH KYUN shuru karein. Baad mein har quantity — utilization, IPC, speedup — bas har tick filled boxes ginne ki baat hai. Agar aap boxes dekh sako, toh algebra sirf bookkeeping hai.

PICTURE. Neeche diye grid ko dekho. Har column ek cycle hai (clock ki ek tick). Har row ek execution unit hai — toh $N=4$ rows hain. Filled box matlab "is unit ne is cycle mein useful kaam kiya"; empty box matlab "idle — kisi ke paas is ke liye kaam ready nahi tha."

---

Step 2 — Ek single thread boxes empty kyun chhod deta hai

KYA HOTA HAI. Ek thread ek running program hota hai: instructions ki ek stream jismein ek Program Counter (PC) mark karta hai "main kahan hoon." Apne $N=4$-wide core mein ek thread daalo aur filled boxes gino.

KYUN. Programs smooth nahi hote. Teen cheezein empty columns (jinhe parent bubbles kehta hai) create karti hain:

1. Data dependencies — instruction $I_2$ ko $I_1$ ka answer chahiye, toh use wait karna padta hai (dekho Pipeline Hazards).
2. Cache misses — memory bahut door hai; ek miss thread ko 50–200 cycles ke liye freeze kar deta hai (dekho Memory Hierarchy).
3. Branch mispredictions — galat guess kaam flush kar deta hai (dekho Branch Prediction).

PICTURE. Neeche red block ek cache-miss stall hai: har unit idle hai kyunki thread ke paas kisi ko dene ke liye koi ready instruction nahi hai. Hardware exist karta hai; bas uske paas koi kaam nahi hai.

$$\underset{\text{fraction of boxes filled}}{\underbrace{{\text{Utilization}}_{\text{single}}}}=\frac{\stackrel{\text{filled boxes / column}}{\overbrace{\text{IPC}}}}{\underset{\text{rows per column}}{\underbrace{N}}}\approx 20\text{–}40\%$$

Isse aise padho: filled boxes ÷ ek column ke saare $N$ boxes. Grid ka zyada hissa empty hai. Wahi waste poori opportunity hai.

---

Step 3 — IPC ko ek time (baseline number) mein badlo

KYA HOTA HAI. Hum ek concrete cycles figure chahte hain jisse compare kar sakein. Time sirf kaam divided by rate hota hai. $W=1000$ instructions per thread ka ek workload fix karo — hum yahi $W$ is page ke har case ke liye reuse karenge taaki comparisons honest rahein.

DIVISION KYUN. IPC hai "instructions per cycle." Ise ulta karo: cycles per instruction $1/\text{IPC}$ hai. Multiply karo kitne instructions dene hain aur cycles nikal aate hain. Yahi ek tool hai jo humein chahiye — koi calculus nahi, sirf ek rate ki definition.

$$T_{\text{single}}=\frac{\stackrel{=1000\text{instructions}}{\overbrace{W}}}{\underset{=1.5\text{work per cycle}}{\underbrace{\text{IPC}}}}=\frac{1000}{1.5}=667\text{cycles}$$

IPC $=1.5$ ke saath $N=4$-wide core pe, utilization $\frac{1.5}{4}=37.5\%$ hai — grid ka paanch-aatthwaan hissa empty pada rehta hai.

PICTURE. Bar 667 cycles ka wall-clock time dikhata hai, colour mein split karke — ~37.5% jo kaam kiya aur ~62.5% jo stalls mein waste hua.

---

Step 4 — Doosra thread empty boxes mein daalo

KYA HOTA HAI. Ab cheap state ko replicate karo — ek doosra PC aur ek doosra architectural register file — taaki core ek saath do thread contexts hold kare. Jo costly hai (chaar execution units, caches, branch predictor) woh sab shared rehta hai.

YEH KYUN kaam karta hai. Jab thread A stall karta hai (uska column empty hoga), thread B ke paas usually unrelated kaam ready hota hai — B ka cache miss aur A ka cache miss ek hi waqt nahi hote. Toh B ke filled boxes A ke empty walon mein slot ho jaate hain.

PICTURE. Step 1 waala hi grid, ab do-coloured: blue boxes = thread A, pink boxes = thread B. Dekho Step 2 ka red stall column ab mostly pink hai — B ne A ka hole fill kar diya.

---

Step 5 — Combined kaam gino, aur har thread thoda slow kyun hota hai

KYA HOTA HAI. Dono threads live hone ke saath, IPC phir se measure karo. Ab har thread IPC $=1.2$ pe chalta hai, apne solo $1.5$ se kam.

SLOWDOWN KYUN? Ab woh finite cheezein share karte hain:

• cache capacity → dono ke zyada misses (dekho Cache Coherence jab woh same data touch karte hain),
• reorder-buffer slots → har ek ka chota out-of-order window,
• ek branch predictor → dono ek doosre ki history overwrite karte hain.

Lekin combined rate badhta hai (phir bhi $N=4$ se cap hai):

$${\text{IPC}}_{\text{combined}}=\underset{\text{thread A}}{\underbrace{1.2}}+\underset{\text{thread B}}{\underbrace{1.2}}=2.4\le N$$

Utilization $\frac{2.4}{4}=60\%$ tak chadh jaati hai. Per thread time worse hai (same $W=1000$):

$$T_{\text{SMT}}=\frac{W}{\underset{\text{slower per-thread IPC}}{\underbrace{1.2}}}=\frac{1000}{1.2}=833\text{cycles}$$

...lekin dono threads usi 833 cycles mein finish ho jaate hain, kyunki woh saath saath chale, ek ke baad ek nahi.

PICTURE. Do stacked bars. Upar: solo thread, 667 cycles, mostly empty. Neeche: SMT, 833 cycles lekin do threads ka kaam karta hua — dikhne mein zyada bhara hua.

---

Step 6 — Speedup number

KYA HOTA HAI. Speedup = (SMT ke saath work rate) ÷ (SMT ke bina work rate).

RATIO KYUN. "Speedup" ka matlab sirf comparison ke roop mein hota hai. Har case ke liye total instructions over total cycles rakho, phir divide karo.

$$\text{Speedup}=\frac{\stackrel{\text{SMT: 2 threads’ work / shared time}}{\overbrace{2W/833}}}{\underset{\text{solo: 1 thread’s work / its time}}{\underbrace{W/667}}}=\frac{2.4}{1.5}=1.6\times$$

Numerator aur denominator dono bas "instructions ÷ cycles" hain, yaani IPC — $W$ cancel ho jaate hain — toh poori cheez $\frac{2.4}{1.5}$ pe aa jaati hai. $2\times$ ka sapna exactly utna fail hota hai jitna threads ne ek doosre ko slow kiya (Step 5).

---

Step 7 — Do extreme cases ("it depends" kyun)

KYA HOTA HAI. Speedup threads kya karte hain ke saath swing karta hai. Hum dono ends dikhate hain, same $W=1000$ instructions per thread rakhte hue jaise baaki jagah — sirf IPC badalta hai, toh neeche har cycle count bas $1000/\text{IPC}$ hai.

Case A — complementary (memory-bound + CPU-bound). Thread A pure compute hai, solo IPC $=2.0$; thread B ek pointer-chase hai jo zyaatar cycles stall karta hai, solo IPC $=0.5$.

• Solo cycles: A $=\frac{1000}{2.0}=500$, B $=\frac{1000}{0.5}=2000$.
• Sequential (pehle ek, phir doosra): $500+2000=2500$ cycles.
• SMT: A ka compute B ke stall-holes mein ghus jaata hai, toh A thoda slow hota hai (IPC $\to 1.8$) aur B thoda speed karta hai (IPC $\to 0.6$): A $=\frac{1000}{1.8}\approx 556$, B $=\frac{1000}{0.6}\approx 1667$.
• Dono saath chalte hain, toh finish $=\max (556,1667)=1667$.
• Speedup $=2500/1667\approx 1.5\times$. Bada gain — lamba memory pole A ka kaam apne andar chhupa leta hai.

Case B — identical (dono CPU-bound). Dono threads ALUs pe hammer karte hain, solo IPC $=2.5$ each.

• Solo cycles: har ek $=\frac{1000}{2.5}=400$.
• Sequential: $400+400=800$ cycles.
• SMT: koi empty boxes steal karne ke liye nahi, toh contention units split karta hai aur har ek IPC $=1.4$ pe aa jaata hai: har ek $=\frac{1000}{1.4}\approx 714$.
• Dono saath, toh finish $=714$ cycles.
• Speedup $=800/714\approx 1.12\times$. Almost kuch nahi.

DONO KYUN DIKHAO. SMT opportunistic hai, magic nahi: woh sirf woh boxes fill kar sakta hai jo empty the. Do greedy threads koi gap nahi chhodte.

PICTURE. Left panel: complementary threads puzzle pieces ki tarah interlock karte hue (near-full grid). Right panel: identical threads collide karte hue, grid already full toh koi gain nahi.

---

Step 8 — Degenerate limits aur unke peeche ka model

KYA HOTA HAI. Cases A aur B suggest karte hain ki answer depend karta hai kitni baar units idle baithte hain. Maano $f$ ek thread ke cycles ka woh fraction hai jo memory-bound hain (execution units idle, boxes empty) — toh $(1-f)$ woh fraction hai jo CPU-bound hai (units already full). Ab hum seedha in do fractions se SMT speedup ka formula banate hain.

TIMELINE YUN KYUN SPLIT KAREIN. SMT sirf wahan help kar sakta hai jahan empty box ho. Toh ek thread ka total time do prakar ke cycles mein split karo aur har ek ko apne taur pe handle karo:

• CPU-bound cycles, fraction $(1-f)$. Execution units already saturated hain — grid column full hai. Doosre thread ko koi empty box nahi milta, toh in cycles ko koi help nahi milti: woh abhi bhi apna pura share cost karte hain. Yeh SMT running time mein term $(1-f)$ contribute karta hai.
• Memory-bound cycles, fraction $f$. Column empty hai, toh doosra thread boxes fill kar sakta hai. Conservatively maano woh waste ka aadha kaam fill karta hai — do threads idle window share karte hain. Toh yeh chunk ab $f$ ki jagah sirf $\frac{f}{2}$ cost karta hai. Yeh term $\frac{f}{2}$ contribute karta hai.

Do chunks add karo SMT running time (solo time ke fraction ke roop mein) paane ke liye, phir invert karo "less time" ko "more speed" mein turn karne ke liye:

$${\text{time}}_{\text{SMT}}=\underset{\text{full cycles, no help}}{\underbrace{(1-f)}}+\underset{\text{idle cycles, 2nd thread fills half}}{\underbrace{\frac{f}{2}}}⟹\text{Speedup}=\frac{1}{(1-f)+\frac{f}{2}}$$

Upar ka $1$ solo running time hai (apna 100%); divide karne se milta hai kitni baar tez SMT hai.

PICTURE. $f=0$ se $f=1$ tak speedup curve: left par $1$ ke paas flat (fill karne ke liye kuch nahi), right par $2$ tak chadh ta hua (sab kuch fill ho sakta hai), teen checkpoints marked.

Ab sanity check ke liye $f$ ko uske edges tak push karo:

$f$ (memory-bound share)	matlab	speedup
$f=0$	kabhi stall nahi karta, grid hamesha full	$\frac{1}{1+0}=1.0\times$ (koi gain nahi)
$f=1$	hamesha stalling, grid hamesha empty	$\frac{1}{0+0.5}=2.0\times$ (ideal ceiling)
$f=0.6$	heavily memory-bound	$\frac{1}{0.4+0.3}\approx 1.43\times$

YEH KYUN MATTER KARTE HAIN. Yeh reality ko bracket karte hain. Aap $1\times$ se worse kabhi nahi kar sakte (SMT kabhi woh kaam nahi hatata jo already fit ho raha hai) aur do threads ke saath $2\times$ se better kabhi nahi (aapke paas boxes fill karne ke liye sirf do threads hain). Har real workload strictly beech mein padta hai.

---

Ek-picture summary

Upar sab kuch ek single frame mein: empty solo grid, doosra thread holes mein pouring karta hua, aur resulting $1.6\times$ arrow — saath mein reminder ki gain sirf empty boxes mein rehta hai.

Recall Feynman retelling — plain words mein kaho

Ek processor chaar machines ki ek factory row hai, har clock pe ek baar tick karti hai. Ek worker (ek thread) shayad hi kabhi charon ko busy rakhta hai — aadhe time woh parts ka intezaar karta hai jo door warehouse (memory) se aate hain, aur har machine bas wahan baithti hai. Toh hum doosre worker ko usi floor pe invite karte hain. Use apni machines nahi chahiye — woh woh machines use karta hai jo idle hain jab pehla worker atka hua hota hai. Ab, utne hi waqt mein, lagbhag dedh se do guna zyada parts bante hain. Lekin do catches hain: woh warehouse share karte hain, toh dono parts ke liye thoda zyada intezaar karte hain (akela chalne par dono thoda slow hote hain); aur agar dono workers sirf same machine chahte hain, toh koi idle machines share karne ke liye nahi hain aur almost kuch gain nahi hota. Toh SMT bahut worth hai jab do kaam alag cheezein maangein, aur almost kuch nahi jab woh same cheez maangein.

Recall

Woh single quantity kya hai, grid se padhke, jo "filled boxes per column" hai? ::: IPC (instructions per cycle) — average execution units har cycle useful kaam karte hue, $N$ pe cap. Why is two-way SMT speedup worked example mein $2\times$ ki jagah $1.6\times$ kyun hai? ::: Kyunki shared caches, ROB slots aur branch predictor har thread ko IPC $1.5$ se $1.2$ tak gira dete hain; combined $2.4/1.5=1.6$. Model mein $f=0$ aur $f=1$ pe aapko kya speedup milta hai? ::: $1.0\times$ (kabhi stall nahi karta, koi empty boxes fill karne ke liye nahi) aur $2.0\times$ (hamesha stalls, doosra thread sab kuch ka aadha fill karta hai). SMT kab sabse zyada help karta hai? ::: Jab threads complementary hon — ek memory-bound (holes chhod ta hai), ek CPU-bound (unhe bharta hai).