Instruction-level vs thread-level parallelism: Exercises

6.1.2 · D4 · Hardware › Parallelism & Multicore › Instruction-level vs thread-level parallelism

Ye exercises ek ladder climb karti hain. L1 Recognition (kya tum ise naam de sakte ho?) → L2 Application (kya tum formula mein plug in kar sakte ho?) → L3 Analysis (kya tum explain kar sakte ho kyun ek number aata hai?) → L4 Synthesis (kya tum ideas combine kar sakte ho?) → L5 Mastery (kya tum ek choice design aur defend kar sakte ho?).

Har problem ka ek full worked solution ek collapsible callout ke andar chhupa hua hai — use cover karo, khud try karo, phir reveal karo. Ye page tumhara self-test hai parent topic ke liye.

Shuru karne se pehle, ek shared toolbox. Hum Amdahl's Law ko baar baar use karenge, toh aao ensure karein ki har symbol samajh aaya ho.

Definition Woh do speedup formulas jo hum baar baar use karenge

Speedup ka matlab hai: purana time divided by naya time. Agar ek kaam 10 minute mein hota tha aur ab 2 mein hota hai, toh speedup $10/2 = 5 \times$ hai. Ye ek pure number hai, koi units nahi.

$S = \frac{1}{( 1 - x ) + \frac{x}{k}}$

$x$ = woh fraction of work jo parallel mein run ho sakta hai (0 aur 1 ke beech ka number).
$1 - x$ = bacha hua serial fraction — woh kaam jo ek step at a time hi hona chahiye, chahe kitna bhi hardware lagao.
$k$ = kitni cheezein ek saath run hoti hain — ILP ke liye instructions per cycle (IPC), ya TLP ke liye number of cores.

Jab hum ek thread ke andar instructions ki baat karte hain toh fraction ko $f$ aur width ko $n$ kehte hain. Jab hum cores ke across threads ki baat karte hain toh fraction ko $p$ aur count ko $N$ kehte hain. Same formula, alag kahani. Dekho Amdahls-Law.

Ek tasveer kyun serial part villain hai:

Level 1 — Recognition

Recall Solution 1.1

(a) ILP — bahut saare independent instructions, ek stream. Ye superscalar idea hai. (b) TLP — bahut saare independent streams (tabs), alag cores. (c) DLP — ek instruction, bahut saara data. Dekho SIMD-Vector-Processing. Ye ILP NAHI hai (sirf ek instruction!) aur TLP bhi NAHI hai (sirf ek thread!). (d) TLP — do threads ek core share karte hain. Ek core ke andar execution units share karna fir bhi thread-level hai, kyunki streams independent programs hain.

Recall Solution 1.2

Jhooth. Issue width $n$ ek ILP knob hai — ye ek thread ko uske apne independent instructions per cycle mein zyada execute karke faster khatam hone deta hai. Threads ki sankhya ek TLP knob hai (cores / hardware contexts). Ye orthogonal dials hain: tum ek badhao doosra fixed reh sakta hai.

Level 2 — Application

Recall Solution 2.1

Plug in karo: serial fraction $1 - f = 0.2$ , parallel part $f / n = 0.8/4 = 0.2$ . $S_{I L P} = \frac{1}{0.2 + 0.2} = \frac{1}{0.4} = 2.50 \times$ Dhyan do ki serial 0.2 already pura parallel part ke barabar hai — isliye hum $4 \times$ ke kareeb bhi nahi pohanchte.

Recall Solution 2.2

(a) $S = \frac{1}{0.05 + 0.95/8} = \frac{1}{0.05 + 0.11875} = \frac{1}{0.16875} = 5.93 \times$ . (b) $S = \frac{1}{0.05 + 0.95/64} = \frac{1}{0.05 + 0.0148438} = \frac{1}{0.0648438} = 15.42 \times$ . Aath guna zyada cores (8 → 64) se sirf ~2.6× zyada speedup mila. Serial 0.05 hume choke kar raha hai.

Recall Solution 2.3

ILP aur TLP yahan independent multiplicative factors hain (har thread individually ILP win enjoy karta hai): $S_{co mbin e d} = S_{I L P} \times S_{T L P} = 2.11 \times 7.46 = 15.74 \times$ (parent ke $15.7 \times$ se match karta hai).

Level 3 — Analysis

Recall Solution 3.1

(a) $S = \frac{1}{0.9 + 0.1/4} = \frac{1}{0.925} = 1.081 \times$ . ✓ (b) Serial dependency chain (pointer chasing — tum next load nahi kar sakte jab tak current load return nahi karta) $1 - f = 0.9$ pin karta hai; woh 0.9 term denominator dominate karta hai chahe machine kitni bhi wide ho. $n = 16$ : $S = \frac{1}{0.9 + 0.1/16} = \frac{1}{0.90625} = 1.103 \times$ . 4→16 wide jaane se hum 1.081 se 1.103 tak gaye — ek rounding error. Isliye Memory-Level-Parallelism aur pointer-chasing latency aisi code mein dominate karti hain.

Recall Solution 3.2

Design A (pure ILP): $S_{A} = \frac{1}{0.4 + 0.6/6} = \frac{1}{0.4 + 0.1} = \frac{1}{0.5} = 2.00 \times$ .

Design B (TLP × per-thread ILP): Per-thread ILP: $S_{I L P} = \frac{1}{0.4 + 0.6/2} = \frac{1}{0.7} = 1.4286 \times$ . TLP across 4 cores: $S_{T L P} = \frac{1}{0.1 + 0.9/4} = \frac{1}{0.325} = 3.0769 \times$ . Combined: $1.4286 \times 3.0769 = 4.396 \times$ .

Design B jeet jaata hai ( $4.40 \times$ vs $2.00 \times$ ) kyunki deep ILP diminishing returns hit karta hai (woh $f = 0.6$ ceiling), jabki cores mein kaam spread karna abundant algorithmic parallelism $p = 0.9$ exploit karta hai. Ye industry ka multicore ki taraf swing hai — dekho Power-Performance-Tradeoffs.

Level 4 — Synthesis

Recall Solution 4.1

Har ek ke liye: $S_{I L P} (n) = \frac{1}{0.3 + 0.7/ n}$ , $S_{T L P} (N) = \frac{1}{0.1 + 0.9/ N}$ , total $= S_{I L P} \cdot S_{T L P}$ .

$(N, n)$	$S_{I L P}$	$S_{T L P}$	Total
$(1, 8)$	$\frac{1}{0.3875} = 2.581$	$\frac{1}{1.0} = 1.000$	$2.581$
$(2, 4)$	$\frac{1}{0.475} = 2.105$	$\frac{1}{0.55} = 1.818$	$3.827$
$(4, 2)$	$\frac{1}{0.65} = 1.538$	$\frac{1}{0.325} = 3.077$	$4.734$
$(8, 1)$	$\frac{1}{1.0} = 1.000$	$\frac{1}{0.2125} = 4.706$	$4.706$

Best: $(4, 2)$ → $4.73 \times$ . Kyunki $p > f$ (threads mein zyada parallel fraction hai instructions se zyada), optimum zyada cores ki taraf lean karta hai — lekin poori tarah $(8, 1)$ tak nahi, kyunki thodi ILP width abhi bhi pay karti hai. Sweet spot interior mein hai.

Recall Solution 4.2

Pehle ceiling: jab $N \to \infty$ , $\frac{p}{N} \to 0$ , toh $S_{ma x} = \frac{1}{1 - p} = \frac{1}{0.1} = 10 \times$ . Acha — $6 \times$ ceiling se neeche hai, toh ye reachable hai.

Solve karo $\frac{1}{0.1 + 0.9/ N} \geq 6 \Rightarrow 0.1 + \frac{0.9}{N} \leq \frac{1}{6} = 0.16 \overline{6}$ $\Rightarrow \frac{0.9}{N} \leq 0.06 \overline{6} \Rightarrow N \geq \frac{0.9}{0.066 6} = 13.5$ . Toh $N = 14$ cores (integer tak round up karna padega). Check: $S (14) = \frac{1}{0.1 + 0.9/14} = \frac{1}{0.164286} = 6.087 \times$ ✓; $S (13) = \frac{1}{0.169231} = 5.909 \times$ (short).

Level 5 — Mastery

Recall Solution 5.1

$S_{I L P} (n) = \frac{1}{0.85 + 0.15/ n}$ , $S_{T L P} (N) = \frac{1}{0.3 + 0.7/ N}$ .

$(N, n)$	$S_{I L P}$	$S_{T L P}$	Total
$(1, 8)$	$\frac{1}{0.86875} = 1.151$	$1.000$	$1.151$
$(4, 2)$	$\frac{1}{0.925} = 1.081$	$\frac{1}{0.475} = 2.105$	$2.276$
$(8, 1)$	$1.000$	$\frac{1}{0.3875} = 2.581$	$2.581$

(a) $(8, 1)$ jeetataa hai ( $2.58 \times$ ). ILP yahan almost useless hai ( $f = 0.15$ ceiling $\approx 1.18 \times$ ), toh wide cores wasted silicon hain. Thread count hi ek lever hai jisme headroom hai.

(b) Haan, SMT plausibly teeno se behtar hai. Bottleneck latency hai, throughput nahi: har thread ek memory load return hone ka wait karta hua stall karta hai (pointer chasing). SMT ek core ko allow karta hai ki jab thread T1 ek load miss par stalled ho, tab thread T2 ki ready instructions execute kare — otherwise-dead cycles fill karke. Ye memory latency ko useful work mein convert karta hai bina algorithm ko zyada parallel kiye. Ye exactly us weakness (load-to-use stalls) par directly attack karta hai jo ILP aur naive multicore dono hide karne mein fail karte hain. Ye Memory-Level-Parallelism hai jo threading ke through harvest hota hai.

Recall Solution 5.2

$S = 100$ , $N = 128$ set karo: $\frac{1}{( 1 - p ) + p /128} = 100 \Rightarrow (1 - p) + \frac{p}{128} = 0.01$ . $1 - p + 0.0078125 p = 0.01 \Rightarrow 1 - 0.9921875 p = 0.01 \Rightarrow p = \frac{0.99}{0.9921875} = 0.997797$ .

Toh $p \approx 0.9978$ — 99.78% kaam parallel hona chahiye; sirf 0.22% serial ho sakta hai. Plain words mein: code almost perfectly dividable hona chahiye jisme essentially koi setup, synchronization, ya final-merge step na ho. Real reason fail hota hai: synchronization aur shared-data overhead (locks, 128 cores ke beech cache-coherence traffic, thread spawn/join) easily 0.22% se zyada kha jaata hai, effective serial fraction badhata hai aur speedup claim se kaafi neeche aa jaata hai.