Instruction-level vs thread-level parallelism: Worked examples

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

Yeh page parent topic ka "koi bhi scenario chhootne nahi denge" wala companion hai. Shuru karne se pehle, ek vaada: yahan use hone wala har symbol pehli baar define kiya jayega. Agar tumne abhi tak Amdahls-Law nahi dekha, koi baat nahi — hum use neeche se rebuild karenge.

Definition Teen letters jinka hum poori page pe sahara lete hain

$f$ or $p$ :::= woh fraction jo parallelize ho sakta hai — $0$ (kuch bhi overlap nahi ho sakta) aur $1$ (sab kuch overlap ho sakta hai) ke beech ki sankhya. Yeh ek fraction hai, isliye iska koi unit nahi hai; yeh "pie ka kitna hissa baant sakte ho" hai.
$n$ :::= ILP (instruction-level parallelism) ke liye, kitni independent instructions hardware ek clock tick mein complete karta hai. Ek clock tick matlab ek "cycle". $n = 4$ matlab "ek tick mein zyada se zyada 4 instructions retire ho sakti hain."
$N$ :::= TLP (thread-level parallelism) ke liye, kitne alag cores/threads ek saath chalte hain. Ek thread instructions ki ek independent stream hai; ek core ek poora engine hai jo ek thread chala sakta hai.
$S$ :::= speedup = (pehle ka time) ÷ (baad ka time). $S = 2$ matlab "do guna fast", $S = 1$ matlab "koi bhi badlaav nahi."

Picture dekho: amber block serial part hai $(1 - x)$ — yeh kabhi shrink nahi hoti. Cyan blocks parallel part $x$ hain — inhe hum $k$ tukdon mein kaat dete hain. Total time hai amber + (ek cyan slice). Chahe $k$ kitna bhi bada ho jaaye, amber block ek aisi floor hai jiske neeche kabhi nahi ja sakte. Yahi ek idea is page pe har surprise drive karta hai.

Scenario matrix

Parallelism ka har problem jo tum mileoge in mein se kisi ek cell mein aayega. Neeche ke examples un cells ke saath label kiye gaye hain jo unhe cover karti hain, aur mil ke yeh sabhi ko hit karte hain.

Cell	Kya cheez ise khaas banati hai	Covered by
A. High- $x$ , high- $k$	Zyada kuch parallel, zyada workers (best case)	Ex 1
B. Low- $x$ (serial chain)	Dependencies dominate; parallelism fail ho jaata hai	Ex 2
C. $x = 0$ (degenerate)	Poora serial — sanity floor	Ex 3
D. $x = 1$ (degenerate)	Perfectly parallel — sanity ceiling	Ex 3
E. $k \to \infty$ (limiting)	Infinite hardware — ceiling kahan hai?	Ex 4
F. Combining ILP × TLP	Do speedups multiply karte hain	Ex 5
G. Word problem	Real workload, $x$ aur $k$ khud extract karne honge	Ex 6
H. Exam twist	"Speedup diya hai, $x$ nikalo" — ulta solve karo	Ex 7
I. Wrong category	SIMD ko ILP/TLP ki tarah mislabel karna (classic trap)	Ex 8

Forecast (pehle guess karo): aath cores — kya tum exactly 8× expect karte ho? Apna guess likh lo.

Pieces identify karo. Yeh step kyun? Master formula ko $x$ aur $k$ chahiye; unhe naam do taaki ILP aur TLP numbers mix na ho jayein. Yahan $x = p = 0.99$ aur $k = N = 8$ .
Serial part $= 1 - p = 1 - 0.99 = 0.01$ . Kyun? Yeh amber floor hai — woh 1% jo chahe kuch bhi ho chalti hai.
Parallel part shrunk $= \frac{p}{N} = \frac{0.99}{8} = 0.12375$ . Kyun? Cyan block 8 slices mein kata; hum sirf ek slice ka wait karte hain.
Jodo aur invert karo. $S_{T L P} = \frac{1}{0.01 + 0.12375} = \frac{1}{0.13375} = 7.48 \times$ Kyun? Master equation. Total time = floor + ek slice, aur speedup uska reciprocal hai.

Verify karo: 7.48× 8× se neeche hai (guess), jo sahi hai — 1% floor baaki cheen leta hai. Sanity: agar floor $0$ hoti, to kya hum exactly $1/ (0.99/8) = 8.08$ paate? Nahi — floor $0$ aur $p = 1$ ke saath hum exactly 8 paate. Sahi, hamara answer perfect ceiling ke thoda neeche hai, jaise hona chahiye.

Forecast: 4-wide hardware — pakka kam se kam 2× toh hoga? Guess karo.

Pieces naam karo: $x = f = 0.1$ , $k = n = 4$ . Kyun? Yeh ab ILP hai, isliye $f$ = instruction independence, $n$ = instructions/cycle. Dekho Pipelining-Hazards kyun chain stall hoti hai: yeh ek load-to-use hazard hai.
Serial part $= 1 - 0.1 = 0.9$ . Kyun? 90% instructions ko wait karna padta hai — ek bada amber floor.
Parallel part shrunk $= \frac{0.1}{4} = 0.025$ . Kyun? Sirf 10% overlap hota hai, 4 slots mein.
Combine karo: $S_{I L P} = \frac{1}{0.9 + 0.025} = \frac{1}{0.925} = 1.08 \times$

Verify karo: 1.08× ≈ almost kuch nahi. 4-wide machine waste ho rahi hai kyunki dependency chain dominate karti hai — yahi lesson hai: data structure, hardware width nahi, ceiling decide karta hai. Units check: $S$ ek ratio hai, dimensionless. ✓

Figure ek array (independent cyan arrows, sab ek saath fire karte hain) ko ek linked list (amber chain, har arrow ko pehle wale ka wait karna padta hai) se contrast karta hai. Isliye arrays ILP aur TLP dono mein jeette hain.

Forecast: har extreme par tum kya speedup expect karte ho?

Case $x = 0$ . Yeh step kyun? Yeh floor test hai — agar formula yahan galat behave kare, toh woh wrong hai. $S = \frac{1}{( 1 - 0 ) + \frac{0}{8}} = \frac{1}{1 + 0} = 1 \times$ Kuch bhi parallel nahi ⇒ koi speedup nahi. Sahi.
Case $x = 1$ . Kyun? Yeh ceiling test hai. $S = \frac{1}{( 1 - 1 ) + \frac{1}{8}} = \frac{1}{0 + 0.125} = 8 \times$ Sab kuch parallel ⇒ poora $N$ × speedup. Sahi.

Verify karo: $x = 0$ deta hai 1 (koi gain nahi) aur $x = 1$ deta hai exactly $k = 8$ (perfect scaling). Yeh har real answer ko bracket karte hain: koi bhi real program strictly inke beech mein hoga, isliye Ex 1 ka answer 7.48 (ceiling ke paas) aur Ex 2 ka 1.08 (floor ke paas) aaya. ✓

Forecast: infinite cores — kya speedup infinity tak blow up ho jaata hai?

Formula likho aur $N$ ko upar push karo. Kyun? Hum ceiling chahte hain, isliye $N \to \infty$ ki limit lete hain. $S = \frac{1}{( 1 - p ) + \frac{p}{N}}$
Shrinking term ko vanish hone do. Kyun? $\frac{p}{N} \to 0$ jab $N \to \infty$ — ek fixed number ko ever-bigger se divide karne par zero milta hai. $S_{m a x} = \frac{1}{( 1 - p ) + 0} = \frac{1}{1 - p}$
$p = 0.95$ plug karo: $S_{m a x} = \frac{1}{0.05} = 20 \times$ .

Verify karo: infinite hardware ke baad bhi, 5% serial part 20× par cap kar deta hai. Yeh amber floor ko numeric banata hai — yahi Figure 1 wali "floor jo kabhi nahi khod sakte" hai. Related trap Power-Performance-Tradeoffs mein: is point ke baad cores add karna zero gain ke liye power jalaata hai.

Curve dashed amber line ki taraf $20 \times$ par flatten ho jaata hai. Notice karo kitni jaldi yeh plateau ho jaata hai — 32 cores tak zyada faayda khatam ho jaata hai. Yahi flattening wajah hai ki scheduling aur low serial overhead raw core count se zyada matter karte hain.

Forecast: kya yeh add hote hain (2.11 + 7.46) ya multiply?

$S_{I L P}$ dobara calculate karo $f = 0.7$ , $n = 4$ ke saath. Kyun? Combine karne se pehle input confirm karo. $S_{I L P} = \frac{1}{0.3 + \frac{0.7}{4}} = \frac{1}{0.475} = 2.105 \times$
$S_{T L P}$ dobara calculate karo $p = 0.99$ , $N = 8$ ke saath. Kyun? Usi wajah se. $S_{T L P} = \frac{1}{0.01 + \frac{0.99}{8}} = 7.477 \times$
Multiply karo, add nahi. Kyun? ILP har core ka time 2.11× shrink karta hai; TLP phir already-shrunk time ko 7.46× aur shrink karta hai. Sequential shrinks compound hote hain. $S_{t o t a l} = 2.105 \times 7.477 = 15.7 \times$

Verify karo: agar hum add karte toh 9.57× milta, jo galat hai — shrinks independent multipliers hain, jaise do discounts stack kiye ho. SMT aur superscalar ILP layer par hain; cache coherence TLP layer ko govern karta hai — alag layers hain, isliye multiply karte hain. ✓

Forecast: 6 cores ke saath, final time guess karo.

Total serial baseline $= 3 + 27 = 30$ s. Kyun? $x$ ek fraction hai original single-thread time ka, isliye hume woh total chahiye.
$p$ calculate karo = parallel seconds ÷ total = $27/30 = 0.90$ . Kyun? Definition se $p$ original time ka woh fraction hai jo overlap hota hai.
Master formula apply karo, $x = p = 0.9$ , $k = N = 6$ . $S = \frac{1}{0.1 + \frac{0.9}{6}} = \frac{1}{0.1 + 0.15} = \frac{1}{0.25} = 4.0 \times$
Time mein convert karo: naya time $= 30/4.0 = 7.5$ s. Kyun? Speedup = old/new, isliye new = old/ $S$ .

Verify (units!): naya time serial part + parallel part on 6 cores ke barabar hona chahiye $= 3 + \frac{27}{6} = 3 + 4.5 = 7.5$ s. ✓ Exactly match karta hai, aur units poore time seconds mein hain.

Forecast: high ya low $p$ ? Solve karne se pehle guess karo.

Master formula se shuru karo aur $p$ ko unknown maan lo. Kyun? Hume $S$ aur $N$ pata hai; algebra $p$ recover karta hai. $3 = \frac{1}{( 1 - p ) + \frac{p}{8}}$
Dono sides invert karo. Kyun? Reciprocals lekar fraction se chhutkaara paao. $\frac{1}{3} = (1 - p) + \frac{p}{8}$
Right side expand karo. Kyun? $p$ terms collect karo. $\frac{1}{3} = 1 - p + \frac{p}{8} = 1 - p (1 - \frac{1}{8}) = 1 - \frac{7}{8} p$
$p$ ke liye solve karo. $\frac{7}{8} p = 1 - \frac{1}{3} = \frac{2}{3} \Rightarrow p = \frac{8}{7} \cdot \frac{2}{3} = \frac{16}{21} \approx 0.762$

Verify karo: $p = 16/21$ , $N = 8$ wapas plug karo: $(1 - p) = 5/21$ , $p /8 = 2/21$ , sum $= 7/21 = 1/3$ , reciprocal $= 3$ . ✓ To sirf 76% parallel tha — baaki 24% serial ne gain ko 3× par cap kar diya.

Forecast: kya student sahi hai?

Categories yaad karo. Kyun? Poori page ILP, TLP, aur DLP ko alag rakhne par tiki hai. Dekho SIMD-Vector-Processing.
- ILP = bahut saari independent instructions overlap karti hain.
- TLP = bahut saare independent threads.
- DLP (data-level) = ek instruction bahut saare data elements par (SIMD).
SIMD add classify karo. Kyun? Ek vaddps pipeline mein ek single instruction hai, chahe woh kitne bhi floats touch kare.
Sahi se count karo. Ek akela SIMD add ILP mein $n = 1$ contribute karta hai, 8 nahi. Woh "8" SIMD width (DLP) hai, ek bilkul alag axis — dekho Memory-Level-Parallelism ek aur orthogonal axis ke liye.

Verify karo (numeric): agar woh SIMD add akeli instruction hai per cycle, to ILP factor $n = 1$ hai, jo $S_{I L P} = \frac{1}{0 + 1/1} = 1 \times$ ILP se deta hai — speedup DLP se aaya tha, ILP se nahi. Student ne axis galat label kiya. ✓

Recall Self-test — answers chhupao

Kaunsi cell mein speedup hai jo chahe hardware kitna bhi ho, kabhi exceed nahi ho sakta? ::: Cell E — limit hai $1/ (1 - x)$ , serial floor. Agar ILP 2× deta hai aur TLP 5× deta hai, combined speedup kya hai? ::: $10 \times$ — yeh multiply karte hain, add nahi (Cell F). Ek pure SIMD add tumhare ILP count $n$ mein kya contribute karta hai? ::: Sirf $1$ — yeh data-level parallelism hai, ILP nahi (Cell I). 8 cores par measured 3× matlab roughly kaunsa parallel fraction? ::: Lagbhag $0.76$ (Cell H).