Heterogeneous computing concepts: Worked examples — Hinglish deep dive

6.1.12 · D3 · Hardware › Parallelism & Multicore › Heterogeneous computing concepts

Intuition Yeh page kis kaam ki hai

Parent note ne tumhe heterogeneous computing ki formulas di thi: data-movement break-even, pipeline speedup, aur heterogeneous Amdahl's Law. Yeh page uska ulta karta hai — koi hand-waving nahi. Hum har tarah ki situation enumerate karte hain jo un formulas ke saamne aa sakti hai — bada work, chota work, zero serial fraction, infinite GPU, ek bottleneck stage wala pipeline — aur har ek ko number tak grind karte hain. Agar exam mein inme se koi bhi aaya, tum pehle se dekh chuke hoge.

Tumhe kuch naya memorise nahi karna. Tumhe teen quantities aur ek habit chahiye:

Work $W$ = task ko kitne floating-point operations chahiye (unit: FLOP).
Data $D$ = processors ke beech kitne bytes ship karne padte hain (unit: byte).
Bandwidth $B$ = link kitni tezi se bytes ship karta hai (unit: byte/second).
Habit: har example se pehle, answer Forecast karo. Pehle guess karna hi ek formula ko intuition mein badalta hai. Related ideas Rofline Performance Model, Amdahl's Law and Scalability, aur Memory Hierarchy and Caching mein milti hain.

Parent topic par wapas jao: parent topic.

Scenario matrix

Is topic ka har problem kuch giney-chune shapes mein se ek hota hai. Neeche ki table poora menu hai. Har worked example neeche us cell ke saath tagged hai jo wo cover karta hai, aur saath milake har row ko touch karte hain.

Cell	Scenario class	Yeh kya test karta hai	Degenerate / limiting edge
A	High arithmetic intensity	Kya $W$ itna bada hai ki transfer ko beat kare?	$W \to \infty$ : GPU hamesha jeetega
B	Low arithmetic intensity	Same, lekin task data-heavy hai	$W \to 0$ : kabhi offload mat karo
C	Exact break-even	Kahan hetero = CPU-only?	$T_{h e t er o} = T_{C P U}$
D	Amdahl with serial floor	Kitna serial fraction speedup ko maar deta hai?	$f_{s} = 0$ : pure parallel
E	Amdahl, infinite GPU	Woh ceiling jo koi nahi tod sakta	$S_{GP U} \to \infty$
F	Transfer-tax dominance	Jab PCIe tax, compute nahi, rule karta hai	$t_{x f er}$ large
G	Pipeline, balanced stages	$n \to \infty$ par Speedup	sab $t_{i}$ equal
H	Pipeline, one bottleneck	Sabse slow stage throughput cap karti hai	ek $t_{i} ≫$ baaki
I	Real-world word problem	English → symbols translate karo	—
J	Exam twist (unified memory)	$t_{x f er}$ ko poori tarah hataana	$t_{x f er} = 0$

Hum parent se yeh master formulas baar baar use karte hain, ek baar restate kiye taaki har symbol earned ho:

Example 1 — Cell A: high arithmetic intensity (GPU badi jeet)

Forecast: matrix multiply GPUs ka poster child hai ( $O (n^{3})$ work, $O (n^{2})$ data). Guess: haan, asaani se.

Break-even work threshold compute karo. Yeh step kyun? Formula humein woh minimum $W$ batata hai jisse offloading pay kare; phir hum apna real $W$ usse compare karte hain. $W_{min} = \frac{2 ( 0.0503 ) ( 1 ) ( 10 )}{32 ( 10 - 1 )} TFLOP = \frac{1.006}{288} \approx 3.49 \times 1 0^{- 3} TFLOP = 3.49 GFLOP .$
Compare karo. Kyun? Offload tab worth it hai jab actual work threshold se zyada ho. Actual $W \approx 1.72 \times 1 0^{10}$ FLOP $= 17.2$ GFLOP. $17.2 GFLOP ≫ 3.49 GFLOP \Rightarrow offload karo.$

Verify: actual hetero time $= \frac{2 D}{B} + \frac{W}{F _{GP U}} = \frac{2 ( 0.0503 )}{32} + \frac{0.0172}{10} s = 3.14 \times 1 0^{- 3} + 1.72 \times 1 0^{- 3} = 4.86 ms$ . CPU-only $= \frac{0.0172}{1} = 17.2$ ms. Hetero $3.5 \times$ faster hai — "offload" ke consistent. ✓

Example 2 — Cell B: low arithmetic intensity (GPU haarta hai)

Forecast: teen memory touches par ek add — yahi woh "GPUs ke liye terrible" case hai jiske baare mein parent ne warning di thi. Guess: offload mat karo.

Break-even threshold. Kyun? Pehle jaisa test, ab ek data-heavy task ke saath. $W_{min} = \frac{2 ( 1.2 ) ( 1 ) ( 10 )}{32 ( 9 )} = \frac{24}{288} \approx 0.0833 TFLOP = 83.3 GFLOP .$
Compare karo. Kyun? Actual $W = 0.1$ GFLOP. $0.1 GFLOP ⋘ 83.3 GFLOP \Rightarrow offload NAHI karo.$

Verify: hetero time $= \frac{2 ( 1.2 )}{32} + \frac{0.0001}{10} = 0.075 + 0.00001 = 75.01$ ms; CPU-only $= \frac{0.0001}{1} = 0.1$ ms. Hetero 750× slower hai — transfer tax ne trivial compute ko daba diya. ✓ (Arithmetic intensity $= \frac{1 0 ^{8} FLOP}{1.2 \times 1 0 ^{9} B} \approx 0.083$ FLOP/byte, $\sim$ 70 FLOP/byte crossover se kaafi neeche.)

Example 3 — Cell C: exact break-even point

Forecast: parent ne yeh kaam kiya tha aur $\approx 69$ GFLOP mila tha. Confirm karte hain aur dekhte hain.

Figure — Heterogeneous computing concepts

Donon times barabar set karo. Kyun? Break-even by definition $T_{h e t er o} = T_{C P U}$ hai. $\frac{2 ( 1 )}{32} + \frac{W}{10} = \frac{W}{1} .$
$W$ ke liye solve karo. Kyun? Hum crossover work chahte hain. $0.0625 = W (1 - \frac{1}{10}) = 0.9 W \Rightarrow W = \frac{0.0625}{0.9} \approx 0.0694 TFLOP \approx 69.4 GFLOP .$

Verify: $W = 0.0694$ TFLOP par, hetero $= 0.0625 + 0.00694 = 0.0694$ s aur CPU $= 0.0694$ s — barabar. ✓ Figure dekho: amber line ke daayein GPU jeetega (Cell A), baayein CPU jeetega (Cell B). Ek line poori duniya split kar deti hai.

Example 4 — Cell D & F: Amdahl with serial floor aur transfer tax

Forecast: GPU 50× hai lekin serial + tax isko crush kar denge — guess low double digits.

Heterogeneous Amdahl mein plug karo. Kyun? Yeh master speedup formula hai. $S = \frac{1}{0.05 + \frac{0.95}{50} + 0.02} = \frac{1}{0.05 + 0.019 + 0.02} = \frac{1}{0.089} \approx 11.24 \times .$
Loss attribute karo. Kyun? Dekhne ke liye ki kaunsa term hurt karta hai. Serial $0.05$ contribute karta hai, tax $0.02$ , parallel sirf $0.019$ denominator mein. Donon fixed costs ( $0.07$ ) compute term ko dwarf karte hain.

Verify: $\frac{1}{0.089} = 11.236 \dots$ — parent ke $\approx 11.2 \times$ se match karta hai. ✓

Example 5 — Cell E: infinite GPU (ceiling)

Forecast: $f_{p} / S_{GP U}$ term vanish ho jaayega, sirf fixed costs bachenge. Guess: around 14×.

Limit lo. Kyun? Woh hard ceiling dhundho jo koi hardware nahi tod sakta. $lim_{S_{GP U} \to \infty} S = \frac{1}{f _{s} + t _{x f er}} = \frac{1}{0.05 + 0.02} = \frac{1}{0.07} \approx 14.29 \times .$

Verify: $1/0.07 = 14.285 \dots$ ✓ Figure mein curve 14.29 par rise karke flatten ho jaata hai — proof ki ek point ke baad faster GPU khareedna tumhe kuch nahi deta. Yeh exactly Amdahl's Law and Scalability hai heterogeneous kapdon mein.

Example 6 — Cell D edge: zero serial fraction

Forecast: koi serial floor nahi — 50× ke kaafi kareeb hona chahiye.

Substitute karo. Kyun? Degenerate best case dekhne ke liye. $S = \frac{1}{0 + \frac{1}{50} + 0.02} = \frac{1}{0.02 + 0.02} = \frac{1}{0.04} = 25 \times .$

Verify: $1/0.04 = 25$ . ✓ Notice karo: zero serial code ke saath bhi answer 25 hai, 50 nahi — sirf transfer tax ne ise half kar diya. Tax ek serial cost hai chhupe hue roop mein.

Example 7 — Cell J: unified memory tax hataa deta hai

Forecast: denominator se 0.02 hatane se hum 14× se upar jaayenge.

Recompute karo. Kyun? Data movement eliminate karne ki value isolate karo. $S = \frac{1}{0.05 + \frac{0.95}{50} + 0} = \frac{1}{0.069} \approx 14.49 \times .$
Ex. 4 se compare karo. Kyun? Jeet quantify karne ke liye. $14.49$ vs $11.24$ — sirf unified memory se 29% improvement.

Verify: $1/0.069 = 14.49$ ; ratio $14.49/11.24 = 1.289$ . ✓ Directly Memory Hierarchy and Caching aur DMA and I/O Controllers se juda hai — DMA/unified memory ka poora point hi hai woh $2 D / B$ term ko chhota karna.

Example 8 — Cell G: balanced pipeline

Forecast: teen equal stages → speedup 3 ke paas jaayega.

Sequential time. Kyun? Koi overlap nahi wala baseline. $T_{se q} = n \sum t_{i} = 1000 (12) = 12000 ms .$
Pipelined time. Kyun? Pehla item full latency pay karta hai, phir hum slowest stage ki rate par sustain karte hain. $T_{p i p e} = \sum t_{i} + (n - 1) max t_{i} = 12 + 999 (4) = 4008 ms .$
Speedup. $S = \frac{12000}{4008} \approx 2.994 \times$ , aur $\frac{\sum t _{i}}{m a x t _{i}} = \frac{12}{4} = 3$ jab $n \to \infty$ .

Verify: $12000/4008 = 2.9940 \dots \approx 3$ . ✓ Figure ka staircase dikhata hai ki stages fully overlap kar rahi hain — pipe full hone ke baad har 4 ms mein ek nayi image start hoti hai.

Example 9 — Cell H: ek bottleneck stage

Forecast: compute baaki se 5× hai — throughput 10 ms se limit hoga, toh speedup ≈ $14/10 = 1.4$ , 3 nahi.

Sequential. $T_{se q} = 1000 (2 + 10 + 2) = 14000$ ms. Kyun? Baseline.
Pipelined. $max t_{i} = 10$ . Kyun? Pipe fill hone ke baad har 10 ms mein ek result deta hai. $T_{p i p e} = 14 + 999 (10) = 10004 ms .$
Speedup. $S = \frac{14000}{10004} \approx 1.399$ , limit $\frac{14}{10} = 1.4$ .

Verify: $14000/10004 = 1.3994 \dots$ ✓ Lesson: pipeline utni hi fast hoti hai jitna uska slowest station — stages balance karo (relates to load balancing in Parallel Programming Models).

Example 10 — Cell I: real-world word problem

Forecast: 4 GB par 8 TFLOP work → intensity $\approx 2000$ FLOP/byte, bahut zyada. Guess: strongly offload.

Break-even threshold. Kyun? Decision test. $W_{min} = \frac{2 ( 4 ) ( 0.5 ) ( 8 )}{16 ( 8 - 0.5 )} = \frac{32}{120} \approx 0.267 TFLOP = 267 GFLOP .$
Compare karo. Actual $W = 8000$ GFLOP $≫ 267$ GFLOP $\Rightarrow$ offload karo. Kyun? Work threshold se 30× zyada hai.
Jeet quantify karo. Kyun? Managers ko number chahiye. $T_{C P U} = \frac{8}{0.5} = 16 s, T_{h e t er o} = \frac{2 ( 4 )}{16} + \frac{8}{8} = 0.5 + 1 = 1.5 s, S = \frac{16}{1.5} \approx 10.67 \times .$

Verify: $16/1.5 = 10.667$ ; threshold $32/120 = 0.2667$ TFLOP. ✓ Units check: $\frac{GB \cdot ( TFLOP/s ) ^{2}}{( GB/s ) ( TFLOP/s )} = TFLOP$ . ✓

Recall Self-test — answers chhupa lo

Infinite GPU ke saath bhi speedup kahan cap hota hai? ::: Cell E — $1/ (f_{s} + t_{x f er})$ par cap hota hai. Vector add vs matrix multiply: Cell B (offload mat karo) kaun sa hai? ::: Vector add (low arithmetic intensity, $O (n)$ work / $O (n)$ data). Balanced 3-stage pipeline mein speedup ___ ke paas jaata hai? ::: 3, yaani $\sum t_{i} / max t_{i}$ . Unified memory speedup improve karta hai kaunsa term zero set karke? ::: $t_{x f er}$ (Cell J). Break-even threshold kis quantity ke saath badhta hai, offload ko hurt karta hai? ::: Data size $D$ (bade transfers ko justify karne ke liye zyada work chahiye).