Exercises — Simultaneous multithreading (SMT - hyperthreading)

Hum kya karte hain: busy units ko total units se divide karo. Kyun: utilization $N$ units ka woh fraction hai jo use mein hai, aur IPC already hume average busy number bata deta hai. $\text{Utilization}=\frac{\text{IPC}}{N}=\frac{1.5}{4}=0.375=37.5\%$ Figure s01 ka left panel dekho: average mein sirf $1.5$ of $4$ lanes filled hain — baaki hollow, wasted boxes hain.

Rule: jo sasta aur per-thread state ho use duplicate karo (kuch registers), jo bada aur expensive ho use share karo (compute machinery).

• (a) Program Counter — duplicated (har thread ko apna "main kahan hoon" pointer chahiye).
• (b) ALUs — shared (yahi toh poora point hai: unke idle slots bharo).
• (c) L1 cache — shared (badi SRAM, copy karna bahut costly hai).
• (d) architectural register file — duplicated (har thread ke variables independent rehne chahiye).

Throughput. SMT idle execution slots ko doosre thread se bharta hai, isliye har second mein zyada total kaam finish hota hai. Yeh kisi bhi single task ko faster nahi banata — actually ek thread aksar contention ki wajah se thoda slow ho jaata hai.

$T=\frac{M}{\text{IPC}}=\frac{1000}{1.5}=666.\overline{6}\text{cycles}\approx 667$ Kyun divide karte hain: rate instructions per cycle hai; cycles pane ke liye isko flip karo — cycles per instruction $\times$ instructions.

Throughput (rates add hoti hain — same cycle, same units): ${\text{IPC}}_{\text{total}}=1.2+1.2=2.4$ Utilization: $\frac{2.4}{4}=0.60=60\%$ Ex 1.1 ke single-thread $37.5\%$ se compare karo — doosre thread ne bahut saare pehle-hollow boxes colour kar diye (figure s01, right panel).

Old work-rate: ek thread $1.5$ IPC par $\Rightarrow 1.5$ instructions/cycle. New work-rate: do threads $\Rightarrow 2.4$ instructions/cycle. $\text{Speedup}=\frac{2.4}{1.5}=1.6\times$ $2\times$ kyun nahi? Har thread $1.5$ se $1.2$ par aa gaya kyunki ab woh caches, reorder buffer, aur TLB share karte hain — contention cost hai. Isliye $2\times 1.2=2.4$, na ki $2\times 1.5=3.0$.

Plug in karo: $\text{Speedup}=\frac{1}{(1-0.6)+\frac{0.6}{2}}=\frac{1}{0.4+0.3}=\frac{1}{0.7}=1.43\times$ $(1-f)$ ko kyun help nahi milti: CPU-bound fraction ke dauran units already saturated hain — doosre thread ke liye koi idle slots nahi hain, isliye woh time unchanged hai (coefficient $1$). $f/2$ kyun, $f$ nahi: memory-bound cycles ke dauran doosra thread fill in karta hai, lekin conservatively hum assume karte hain ki woh sirf half idle capacity tak pahunchta hai (woh bhi stall karta hai, same starved memory system ke liye compete karta hai). Isliye memory-bound time $f$ se shrink hokar $f/2$ ho jaata hai.

$T_A=\frac{1000}{2.0}=500,T_B=\frac{1000}{0.5}=2000$ $T_{\text{seq}}=500+2000=2500\text{cycles}$

Har thread ka finish time: $T_A=\frac{1000}{1.8}=555.\overline{5}\approx 556,T_B=\frac{1000}{0.6}=1666.\overline{6}\approx 1667$ Job tab done hota hai jab slow wala finish kare: $T_{\text{SMT}}=\max (556,1667)=1667\text{cycles}$ Speedup: $\frac{2500}{1667}=1.50\times$ Yeh kaisa dikhta hai (figure s02): B ke lambe memory stalls hollow boxes hain; A ka compute unhe colour in karta hai, isliye A "free mein" B ke wait ke neeche finish ho jaata hai. Lamba pole B ki memory latency hai, lekin idle time ab A ka useful kaam karta hai.

(a) Sequential: $T=\frac{1000}{2.5}+\frac{1000}{2.5}=400+400=800\text{cycles}$ (b) SMT (dono $1.4$ par, saath run karo, max lo — lekin woh symmetric hain): $T_{\text{SMT}}=\frac{1000}{1.4}=714.28\dots \approx 714\text{cycles}$ (c) Speedup: $\frac{800}{714}=1.12\times$ (d) Itna chhota kyun: dono CPU-bound hain, isliye fill karne ke liye almost koi idle slots nahi hain — units already near-saturated thay. SMT sirf idle capacity donate kar sakta hai, aur yahan woh bahut kam hai. Ex 3.3 ke $1.50\times$ se compare karo, jahan B ke stalls ne bade gaps chhode.

P choose karo (memory-bound thread). Model se tied reasoning: resident CPU-bound thread zyaatar lanes fill karta hai jab woh run karta hai — lekin woh har cycle run nahi karta agar woh bhi kabhi kabhi stall kare, aur ek saturated thread bhi scattered hollow boxes chhod jaata hai. Memory-bound co-runner ki complementary needs hain: woh ALUs ko barely touch karta hai (woh DRAM ka wait kar raha hai), isliye woh hollow boxes mein bina ladai ke fit ho jaata hai. Q, CPU-bound hone ki wajah se, exactly same ALUs chahiye — yeh seedha takkar hai (yeh Ex 4.1 ka $1.12\times$ situation hai). Lesson: SMT complementary resource profiles ko reward karta hai.

Model ko target ke barabar set karo: $\frac{1}{(1-f)+\frac{f}{2}}=1.25$ Denominator simplify karo: $(1-f)+\frac{f}{2}=1-\frac{f}{2}$. Toh $\frac{1}{1-\frac{f}{2}}=1.25⟹1-\frac{f}{2}=\frac{1}{1.25}=0.8$ $\frac{f}{2}=0.2⟹f=0.4(40\%)$ Interpretation: is conservative model ke under SMT $1.25\times$ throughput gain reach karne ke liye tumhe kam se kam $40\%$ cycles memory-bound chahiye. Usse neeche, gains $1\times$ ki taraf fade ho jaate hain.

Limit lo $f\to 1$: $\text{Speedup}=\frac{1}{(1-1)+\frac{1}{2}}=\frac{1}{0.5}=2\times$ Toh model ki ceiling exactly $2\times$ hai, sirf idealized all-memory-bound limit mein reach hoti hai. Model $2\times$ par kyun cap hota hai (zyada nahi): denominator term $f/2$ dekho. "$/2$" fill-half assumption hai — even ek fully idle stretch mein, model doosre thread ko sirf half idle time reclaim karne deta hai, isliye memory-bound time $f$ se shrink hokar $f/2$ hota hai, kabhi $0$ nahi. Agar hum assume karte ki doosra thread sab idle time reclaim kar leta ($f\to 0$ denominator mein), toh limit $1/0=\infty$ hoti. Yahi conservative $f/2$ factor — model ki built-in acknowledgement ki doosra thread bhi stall karta hai aur compete karta hai — ceiling ko $2\times$ par pin karta hai. (Real hardware to isse bhi neeche $1.2$–$1.4\times$ par aata hai, kyunki shared cache, ROB, aur TLB contention add karte hain jo model include nahi karta.)

Cycle-by-cycle:

1. A mispredicts → uske in-flight wrong-path instructions squash hote hain; A ke paas ~15 cycles ke liye kuch ready nahi jab tak correct path refetch hota hai.
2. SMT ke bina, woh 15 cycles pure hollow boxes hain (figure s02, B ke memory stalls jaisa same hollow-slot pattern) — wasted.
3. SMT ke saath, scheduler ki ready-queue mein abhi bhi B ki instructions hain. Un 15 cycles mein se har ek mein, woh B se issue karta hai, un lanes ko colour karta hai jo A ne chhod diye.
4. Jab A ka correct path aata hai, A ready-queue mein wapas join karta hai aur dono interleave karte hain.

Do shared structures jo gain ko erode karte hain:

• Shared branch predictor — B ki branches aur A ki branches ek predictor ki history/tables update karti hain; inter-thread interference (aliasing) dono ko zyada mispredict kara sakta hai, isliye A ke flushes pehli jagah par zyada frequent ho jaate hain.
• Shared cache / TLB (Memory Hierarchy) — A ke flush ke dauran B run karke B ka data pull in karta hai, potentially A ke working set ko evict karta hai, isliye jab A wapas aata hai toh fresh cache misses face karta hai. Stolen slots free the, lekin cache pollution A par delayed cost laata hai.

Net: SMT A ke 15 flush cycles ko useful B-work ke roop mein reclaim karta hai (woh win hai), lekin shared predictor aur shared cache/TLB quietly dono threads ki miss aur mispredict rates badha sakte hain (woh tax hai). Gain real hai lekin bounded — exactly is poore page ki $1.2$–$1.4\times$ story.

Work aur rate se time ::: $T=M/\text{IPC}$. SMT speedup $2\times$ se kam kyun hai ::: threads caches, ROB, TLB share karte hain → contention har thread ki IPC girata hai. Do threads ka parallel finish time ::: $\max (T_A,T_B)$, sum nahi. SMT ke under kaun se threads best pair karte hain ::: complementary resource needs (CPU-bound + memory-bound). Amdahl-SMT model ::: $\frac{1}{(1-f)+f/2}$, ceiling $2\times$ as $f\to 1$.