Heterogeneous computing concepts: Exercises — Hinglish deep dive

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

Poore note mein, hum parent note ke symbols reuse karte hain. Contract maintain karne ke liye, yahan sabhi ek jagah plain words mein hain:

Definition Symbol glossary (har ek words mein define kiya hua)

$B$ = processors ke beech link ki bandwidth, gigabytes per second (GB/s) mein. "Har second mein kitne GB wire cross kar sakte hain."
$D$ = data size jo us wire ko cross karna hai, gigabytes (GB) mein.
$W$ = work, yaani task ko kitne floating-point operations (adds, multiplies) chahiye, FLOPs mein.
$F_{C P U}, F_{GP U}$ = har chip ki compute rate, FLOPs per second (FLOP/s) mein. Ek TFLOP/s hota hai $1 0^{12}$ FLOP/s.
$f_{s}, f_{p}$ = program ka serial fraction aur parallel fraction. Ye pure numbers hain 0 aur 1 ke beech, jahan $f_{s} + f_{p} = 1$ .
$S$ = speedup = (purana time) ÷ (naya time). "Kitne guna fast."
$t_{x f er}$ = transfer tax, yaani data-movement overhead jo original CPU-only time ke fraction ke roop mein express hota hai (ek pure number, jaise $0.02$ = 2%). Ye woh fixed toll hai jo aap har launch mein processors ke beech data copy karne ke liye dete ho.
Arithmetic intensity = $W / D$ , FLOPs done per byte moved. High = trip worth hai; low = wire bottleneck hai.

Har chip ko CPU-like (latency-optimised) ya GPU-like (throughput-optimised) classify karo: (a) 8 powerful cores with megabytes of cache aur branch prediction; (b) 2048 tiny ALUs ek small cache share karte hue, many threads mein ek instruction run karte hue; (c) ek fixed-function block jo sirf AES encryption karta hai.

Recall Solution

(a) CPU-like — kuch strong cores + bade caches + branch prediction sab ek task ki latency serve karte hain.
(b) GPU-like — hazaron simple lanes SIMT (Single Instruction, Multiple Threads) run karte hue many tasks ka throughput serve karte hain. Dekho SIMD and Vector Processing.
(c) Koi bhi general type nahi — ye ek specialized accelerator hai (fixed-function). Narrow domain hai, isliye hardwired logic energy mein jeet jaata hai.

L1.2

Ek system mein 4 identical ARM cores hain. Kya ye heterogeneous hai? Ab usme 1 GPU aur 1 NPU add hote hain. Ab?

Recall Solution

4 identical cores = homogeneous (same instruction set, same strengths).
GPU + NPU add karna = heterogeneous — do ya zyada different processor types jinke distinct computational models hain.

Level 2 — Application

L2.1

PCIe link jahan $B = 32$ GB/s hai. Aapko $D = 1$ GB GPU ko move karna hai aur result wapas lana hai. Round-trip transfer mein kitna time lagega?

Recall Solution

Round-trip ka matlab hai data do baar cross karta hai, isliye moved amount $2 D$ hai. $T_{t r an s f er} = \frac{2 D}{B} = \frac{2 \times 1}{32} = 0.0625 s = 62.5 ms .$

L2.2

Same link. Aapka GPU $F_{GP U} = 10$ TFLOP/s pe run karta hai; aapka CPU $F_{C P U} = 1$ TFLOP/s pe. Parent ki break-even formula use karke, us 1 GB ke liye minimum work $W$ kya hai jo GPU ko worthwhile banata hai?

Recall Solution

$D = 1$ , $F_{C P U} = 1$ , $F_{GP U} = 10$ , $B = 32$ plug in karo (sab matching TFLOP/s aur GB/s units mein, TFLOP deta hai): $W > \frac{2 \cdot 1 \cdot 1 \cdot 10}{32 ( 10 - 1 )} = \frac{20}{288} \approx 0.0694 TFLOP = 69.4 GFLOP .$ Iska matlab: jab tak task ko kam se kam ~69 billion operations nahi chahiye, 62.5 ms ki trip jo bachat ho sakti thi usse zyada cost karta hai. Arithmetic intensity floor hai $69.4 GFLOP /1 GB \approx 69$ FLOP/byte.

L2.3

Do $n \times n$ matrices ka matrix–matrix multiply $W \approx 2 n^{3}$ FLOPs leta hai aur $D \approx 3 n^{2} \times 4$ bytes move karta hai (teen float32 matrices). $n = 1024$ ke liye arithmetic intensity compute karo. Kya ye 69 FLOP/byte floor se upar hai?

Recall Solution

$W = 2 \cdot 102 4^{3} = 2147483648 \approx 2.147 \times 1 0^{9}$ FLOP. $D = 3 \cdot 102 4^{2} \cdot 4 = 12582912$ bytes $\approx 12.58$ MB. Intensity $= W / D = 2.147 \times 1 0^{9} /1.258 \times 1 0^{7} \approx 170.7$ FLOP/byte. $170.7 > 69$ ✓ — matrix multiply floor aaram se clear karta hai. Yahi wajah hai ki GEMM GPUs ko love karta hai. Contrast — vector add. Do length- $N$ float32 arrays add karne mein $W = N$ FLOPs lagte hain (ek add per element) lekin $D = 3 N \times 4 = 12 N$ bytes move hote hain (do operands read, ek result write, 4 bytes each). Toh intensity $= W / D = \frac{N}{12 N} = \frac{1}{12} \approx 0.083$ FLOP/byte — ek akeela add per 12 bytes moved, GPU ke liye bilkul bekar. Dekho Roofline Performance Model.

Level 3 — Analysis

L3.1

Heterogeneous Amdahl's Law. Ek program $f_{p} = 0.90$ parallel, $f_{s} = 0.10$ serial hai, GPU speedup $S_{GP U} = 20$ , transfer tax $t_{x f er} = 0.05$ (original time ka 5%) hai. Overall speedup nikalo.

Recall Solution

$S_{o v er a l l} = \frac{1}{0.10 + \frac{0.90}{20} + 0.05} = \frac{1}{0.10 + 0.045 + 0.05} = \frac{1}{0.195} \approx 5.13 \times .$ 20× engine ke bawajood, hum ~5× milta hai. $0.10$ serial floor plus $0.05$ tax hume cap karta hai. Dekho Amdahl's Law and Scalability.

L3.2

L3.1 lo aur $S_{GP U} \to \infty$ set karo (infinitely fast GPU). Speedup ki hard ceiling kya hai? Kaun sa ek change us ceiling ko sabse zyada raise karega?

Recall Solution

Jab $S_{GP U} \to \infty$ , toh $\frac{f _{p}}{S _{GP U}}$ term $\to 0$ : $S_{m a x} = \frac{1}{f _{s} + t _{x f er}} = \frac{1}{0.10 + 0.05} = \frac{1}{0.15} \approx 6.67 \times .$ Ceiling poori tarah serial fraction + transfer tax se set hoti hai, GPU speed se nahi. Sabse bada lever: $f_{s}$ kam karo (zyada code parallelize karo) ya $t_{x f er}$ (unified memory copies remove karta hai — dekho Memory Hierarchy and Caching). Is point ke baad faster GPU kharidna paisa barbad karna hai.

L3.3

Pipeline. Chaar stages $t_{1} = 2, t_{2} = 5, t_{3} = 3, t_{4} = 1$ ms per image lete hain. $n = 1000$ images process karo. Sequential vs pipelined time compare karo aur speedup do.

Neeche figure (alt: ek Gantt-style timeline). Top strip sequential schedule dikhata hai — har image ki har stage end-to-end laid out hai, isliye time bas add hota jaata hai. Bottom strip pipelined schedule dikhata hai — har naya image ek bottleneck-length ( $= 5$ ms) baad shuru hota hai, isliye sab chaar stages concurrently run karti hain aur sabse lamba bar ( $t_{2} = 5$ ) rhythm set karta hai. Horizontal axis time in ms hai; har colour ek stage hai.

Figure — Heterogeneous computing concepts

Recall Solution

Stages ka sum $\sum t_{i} = 2 + 5 + 3 + 1 = 11$ ms. Slowest stage $max t_{i} = 5$ ms. Sequential: $n \sum t_{i} = 1000 \times 11 = 11000$ ms. Pipelined: $\sum t_{i} + (n - 1) max t_{i} = 11 + 999 \times 5 = 11 + 4995 = 5006$ ms. Speedup: $11000/5006 \approx 2.198 \times$ . Jab $n \to \infty$ tab limit hai $\sum t_{i} / max t_{i} = 11/5 = 2.2 \times$ . 5 ms wali slow stage bottleneck hai — kisi bhi doosri stage ko fast karna kuch nahi karta. Dekho Parallel Programming Models.

Level 4 — Synthesis

L4.1

Aapko CPU-only vs heterogeneous decide karna hai ek task ke liye jisme $W = 40$ GFLOP aur $D = 1$ GB hai, L2 machine pe ( $B = 32$ , $F_{C P U} = 1$ , $F_{GP U} = 10$ TFLOP/s). Dono times compute karo aur decide karo.

Recall Solution

CPU akela: $T_{C P U} = W / F_{C P U} = \frac{40 \times 1 0 ^{9}}{1 \times 1 0 ^{12}} = 0.040$ s. Heterogeneous: $T_{h e t er o} = \frac{2 D}{B} + \frac{W}{F _{GP U}} = \frac{2}{32} + \frac{40 \times 1 0 ^{9}}{10 \times 1 0 ^{12}} = 0.0625 + 0.004 = 0.0665$ s. $0.0665 > 0.040$ , isliye CPU jeeetta hai. Samajh aata hai: $W = 40$ GFLOP L2.2 ke 69.4 GFLOP floor se neeche hai. Transfer toll pay karne ke liye kaafi kaam nahi hai.

L4.2

Redesign: $D = 1$ GB rakho lekin work $W = 500$ GFLOP tak badhao (denser algorithm). Dono recompute karo. Ab kaun jeeeta hai, aur kitne se?

Recall Solution

CPU: $T_{C P U} = \frac{500 \times 1 0 ^{9}}{1 0 ^{12}} = 0.500$ s. Hetero: $\frac{2}{32} + \frac{500 \times 1 0 ^{9}}{10 \times 1 0 ^{12}} = 0.0625 + 0.050 = 0.1125$ s. Speedup: $0.500/0.1125 \approx 4.44 \times$ . GPU ab clearly jeetta hai — same data, zyada kaam per byte ne break-even line cross ki. Lesson: arithmetic intensity badhana, sirf chip speed nahi, GPU ko unlock karta hai.

L4.3

Ek 3-stage pipeline di gayi hai (CPU pe read, GPU pe compute, CPU pe write) per-image times $t_{r e a d} = 4, t_{co m p u t e} = 10, t_{w r i t e} = 3$ ms ke saath, aur $n = 200$ images — choose karo ki kaun sa stage optimize karein agar aap exactly ek stage ko aadha kar sakte ho. Har choice ke liye pipelined time compute karo aur justify karo.

Recall Solution

Baseline pipelined: $\sum t_{i} + (n - 1) max t_{i} = 17 + 199 \times 10 = 17 + 1990 = 2007$ ms.

Read aadha karo (4→2): $\sum t_{i} = 2 + 10 + 3 = 15$ , $max$ still 10 → $15 + 199 \times 10 = 2005$ ms. Barely hilta hai.
Compute aadha karo (10→5): $\sum t_{i} = 4 + 5 + 3 = 12$ , new $max = 5$ → $12 + 199 \times 5 = 1007$ ms. Bahut bada.
Write aadha karo (3→1.5): $\sum t_{i} = 4 + 10 + 1.5 = 15.5$ , $max$ still 10 → $15.5 + 199 \times 10 = 2005.5$ ms. Negligible. Compute choose karo — ye bottleneck hai ( $max t_{i}$ ). Sirf sabse lamba stage chhota karne se sustained throughput girta hai.

Level 5 — Mastery

L5.1

Full system design. Ek neural-net training step: $f_{p} = 0.95$ (matrix ops), $f_{s} = 0.05$ , $S_{GP U} = 50$ , current $t_{x f er} = 0.02$ . (a) Current speedup nikalo. (b) Aap unified memory kharidite ho jo $t_{x f er}$ $0.005$ tak drop karta hai. Naya speedup? (c) Absolute ceiling ( $S_{GP U} \to \infty$ ) naye tax ke saath kya hai, aur aapko aage kya attack karna chahiye?

Recall Solution

(a) $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 .$ (b) $0.02 \to 0.005$ replace karo: $S = \frac{1}{0.05 + 0.019 + 0.005} = \frac{1}{0.074} \approx 13.51 \times .$ (c) Ceiling: $S_{m a x} = \frac{1}{f _{s} + t _{x f er}} = \frac{1}{0.05 + 0.005} = \frac{1}{0.055} \approx 18.18 \times .$ Kyunki GPU speed almost maxed hai ( $\frac{0.95}{50} = 0.019$ term chhota hai), agla target hai serial fraction $f_{s} = 0.05$ — data loading / loss / parameter updates parallelize karo. Bhi relevant hai: Power and Energy Optimization aur DMA and I/O Controllers un transfers ko overlap karne ke liye.

L5.2

Cost-effectiveness ranking. L5.1 baseline ke liye ( $f_{s} = 0.05, f_{p} = 0.95, t_{x f er} = 0.02, S_{GP U} = 50$ ), teen upgrades ko resulting speedup se rank karo: (i) GPU speed double karo $S_{GP U} \to 100$ ; (ii) serial fraction aadhi karo $f_{s} \to 0.025$ (us 2.5% ko $f_{p}$ mein move karo, toh $f_{p} \to 0.975$ ); (iii) transfer tax aadhi karo $t_{x f er} \to 0.01$ .

Recall Solution

(i) $\frac{1}{0.05 + \frac{0.95}{100} + 0.02} = \frac{1}{0.05 + 0.0095 + 0.02} = \frac{1}{0.0795} \approx 12.58 \times .$
(ii) $\frac{1}{0.025 + \frac{0.975}{50} + 0.02} = \frac{1}{0.025 + 0.0195 + 0.02} = \frac{1}{0.0645} \approx 15.50 \times .$
(iii) $\frac{1}{0.05 + \frac{0.95}{50} + 0.01} = \frac{1}{0.05 + 0.019 + 0.01} = \frac{1}{0.079} \approx 12.66 \times .$ Ranking: (ii) 15.50× > (iii) 12.66× > (i) 12.58×. Serial fraction attack karna badi jeet se jeetta hai — kyunki $S_{GP U} = 50$ pe parallel term already tiny hai, isliye GPU double karna barely help karta hai. Amdahl's ceiling boss hai.

Exercises — Heterogeneous computing concepts

Level 1 — Recognition

L1.1

L1.2

Level 2 — Application

L2.1

L2.2

L2.3

Level 3 — Analysis

L3.1

L3.2

L3.3

Level 4 — Synthesis

L4.1

L4.2

L4.3

Level 5 — Mastery

L5.1

L5.2