Heterogeneous computing concepts: Exercises — Hardware deep dive

Throughout, we reuse the parent note's symbols. To keep the contract, here they are in one place, in plain words:

Definition Symbol glossary (each defined in words)

$B$ = bandwidth of the link between processors, in gigabytes per second (GB/s). "How many GB can cross the wire each second."
$D$ = data size that must cross that wire, in gigabytes (GB).
$W$ = work, the total count of floating-point operations (adds, multiplies) the task needs, in FLOPs.
$F_{C P U}, F_{GP U}$ = compute rate of each chip, in FLOPs per second (FLOP/s). A TFLOP/s is $1 0^{12}$ FLOP/s.
$f_{s}, f_{p}$ = fraction serial and fraction parallel of a program. They are pure numbers between 0 and 1 with $f_{s} + f_{p} = 1$ .
$S$ = speedup = (old time) ÷ (new time). "How many times faster."
$t_{x f er}$ = transfer tax, the data-movement overhead expressed as a fraction of the original CPU-only time (a pure number, e.g. $0.02$ = 2%). It is the fixed toll you pay for copying data between processors each launch.
Arithmetic intensity = $W / D$ , FLOPs done per byte moved. High = worth the trip; low = the wire is the bottleneck.

Classify each chip as CPU-like (latency-optimised) or GPU-like (throughput-optimised): (a) 8 powerful cores with megabytes of cache and branch prediction; (b) 2048 tiny ALUs sharing a small cache, running one instruction across many threads; (c) a fixed-function block that only does AES encryption.

Recall Solution

(a) CPU-like — few strong cores + big caches + branch prediction all serve latency of one task.
(b) GPU-like — thousands of simple lanes running SIMT (Single Instruction, Multiple Threads) serve throughput of many tasks. See SIMD and Vector Processing.
(c) Neither general type — it is a specialized accelerator (fixed-function). Narrow domain, so hardwired logic wins on energy.

L1.2

A system has 4 identical ARM cores. Is it heterogeneous? Now it adds 1 GPU and 1 NPU. Now?

Recall Solution

4 identical cores = homogeneous (same instruction set, same strengths).
Adding a GPU + NPU = heterogeneous — two or more different processor types with distinct computational models.

Level 2 — Application

L2.1

PCIe link with $B = 32$ GB/s. You must move $D = 1$ GB to the GPU and the result back. How long does the round-trip transfer take?

Recall Solution

Round-trip means data crosses twice, so the moved amount is $2 D$ . $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. Your GPU runs at $F_{GP U} = 10$ TFLOP/s; your CPU at $F_{C P U} = 1$ TFLOP/s. Using the parent's break-even formula, what is the minimum work $W$ that makes the GPU worthwhile for that 1 GB?

Recall Solution

Plug in $D = 1$ , $F_{C P U} = 1$ , $F_{GP U} = 10$ , $B = 32$ (all in matching TFLOP/s and GB/s units, giving TFLOP): $W > \frac{2 \cdot 1 \cdot 1 \cdot 10}{32 ( 10 - 1 )} = \frac{20}{288} \approx 0.0694 TFLOP = 69.4 GFLOP .$ What it means: unless the task needs at least ~69 billion operations, the 62.5 ms trip costs more than it saves. The arithmetic intensity floor is $69.4 GFLOP /1 GB \approx 69$ FLOP/byte.

L2.3

Matrix–matrix multiply of two $n \times n$ matrices needs $W \approx 2 n^{3}$ FLOPs and moves $D \approx 3 n^{2} \times 4$ bytes (three float32 matrices). Compute arithmetic intensity for $n = 1024$ . Is it above the 69 FLOP/byte floor?

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 clears the floor comfortably. This is why GEMM loves GPUs. Contrast — vector add. Adding two length- $N$ float32 arrays does $W = N$ FLOPs (one add per element) but moves $D = 3 N \times 4 = 12 N$ bytes (read two operands, write one result, 4 bytes each). So intensity $= W / D = \frac{N}{12 N} = \frac{1}{12} \approx 0.083$ FLOP/byte — one measly add per 12 bytes moved, hopeless for a GPU. See Roofline Performance Model.

Level 3 — Analysis

L3.1

Heterogeneous Amdahl's Law. A program is $f_{p} = 0.90$ parallel, $f_{s} = 0.10$ serial, GPU speedup $S_{GP U} = 20$ , transfer tax $t_{x f er} = 0.05$ (5% of original time). Find overall speedup.

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 .$ Even with a 20× engine, we get ~5×. The $0.10$ serial floor plus $0.05$ tax cap us. See Amdahl's Law and Scalability.

L3.2

Take L3.1 and set $S_{GP U} \to \infty$ (infinitely fast GPU). What is the hard ceiling on speedup? What single change would raise that ceiling the most?

Recall Solution

As $S_{GP U} \to \infty$ , the $\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 .$ The ceiling is set entirely by serial fraction + transfer tax, not by GPU speed. The biggest lever: cut $f_{s}$ (parallelise more code) or $t_{x f er}$ (unified memory removes copies — see Memory Hierarchy and Caching). Buying a faster GPU past this point is wasted money.

L3.3

Pipeline. Four stages take $t_{1} = 2, t_{2} = 5, t_{3} = 3, t_{4} = 1$ ms per image. Process $n = 1000$ images. Compare sequential vs pipelined time and give the speedup.

Figure below (alt: a Gantt-style timeline). The top strip shows the sequential schedule — every stage of every image laid end-to-end, so time just adds up. The bottom strip shows the pipelined schedule — each new image starts one bottleneck-length ( $= 5$ ms) after the previous, so all four stages run concurrently and the tallest bar ( $t_{2} = 5$ ) sets the rhythm. The horizontal axis is time in ms; each colour is one stage.

Figure — Heterogeneous computing concepts

Recall Solution

Sum of stages $\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$ . As $n \to \infty$ the limit is $\sum t_{i} / max t_{i} = 11/5 = 2.2 \times$ . The slow 5 ms stage is the bottleneck — speeding any other stage does nothing. See Parallel Programming Models.

Level 4 — Synthesis

L4.1

You must decide CPU-only vs heterogeneous for a task with $W = 40$ GFLOP and $D = 1$ GB, on the L2 machine ( $B = 32$ , $F_{C P U} = 1$ , $F_{GP U} = 10$ TFLOP/s). Compute both times and decide.

Recall Solution

CPU alone: $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$ , so CPU wins. Makes sense: $W = 40$ GFLOP is below the L2.2 floor of 69.4 GFLOP. Not enough work to pay the transfer toll.

L4.2

Redesign: keep $D = 1$ GB but raise the work to $W = 500$ GFLOP (denser algorithm). Recompute both. Now who wins, and by how much?

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 now wins clearly — same data, more work per byte crossed the break-even line. Lesson: raising arithmetic intensity, not just chip speed, unlocks the GPU.

L4.3

Given a 3-stage pipeline (read on CPU, compute on GPU, write on CPU) with 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, and $n = 200$ images — pick which stage to optimise if you can halve exactly one stage. Compute pipelined time for each choice and justify.

Recall Solution

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

Halve read (4→2): $\sum t_{i} = 2 + 10 + 3 = 15$ , $max$ still 10 → $15 + 199 \times 10 = 2005$ ms. Barely moves.
Halve compute (10→5): $\sum t_{i} = 4 + 5 + 3 = 12$ , new $max = 5$ → $12 + 199 \times 5 = 1007$ ms. Huge.
Halve write (3→1.5): $\sum t_{i} = 4 + 10 + 1.5 = 15.5$ , $max$ still 10 → $15.5 + 199 \times 10 = 2005.5$ ms. Negligible. Pick compute — it is the bottleneck ( $max t_{i}$ ). Only shrinking the tallest stage lowers sustained throughput.

Level 5 — Mastery

L5.1

Full system design. A 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) Find current speedup. (b) You buy unified memory that drops $t_{x f er}$ to $0.005$ . New speedup? (c) What is the absolute ceiling ( $S_{GP U} \to \infty$ ) with the new tax, and what should you attack next?

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) Replace $0.02 \to 0.005$ : $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 .$ Since GPU speed is nearly maxed (the $\frac{0.95}{50} = 0.019$ term is small), the next target is the serial fraction $f_{s} = 0.05$ — parallelise data loading / loss / parameter updates. Also relevant: Power and Energy Optimization and DMA and I/O Controllers to overlap those transfers.

L5.2

Cost-effectiveness ranking. For the L5.1 baseline ( $f_{s} = 0.05, f_{p} = 0.95, t_{x f er} = 0.02, S_{GP U} = 50$ ), rank three upgrades by resulting speedup: (i) double GPU speed $S_{GP U} \to 100$ ; (ii) halve serial fraction $f_{s} \to 0.025$ (moving that 2.5% into $f_{p}$ , so $f_{p} \to 0.975$ ); (iii) halve transfer tax $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×. Attacking the serial fraction wins by a mile — because at $S_{GP U} = 50$ the parallel term is already tiny, so doubling the GPU barely helps. Amdahl's ceiling is the boss.

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