Heterogeneous computing concepts: Worked examples — Hardware deep dive

Intuition What this page is for

The parent note gave you the formulas for heterogeneous computing: the data-movement break-even, the pipeline speedup, and heterogeneous Amdahl's Law. This page does the opposite of hand-waving. We enumerate every kind of situation those formulas can face — big work, tiny work, zero serial fraction, infinite GPU, a pipeline with a bottleneck stage — and we grind each one to a number. If you meet any of these on an exam, you have already seen it here.

You do not need to memorise anything new. You need three quantities and one habit:

Work $W$ = how many floating-point operations the task needs (unit: FLOP).
Data $D$ = how many bytes must be shipped between processors (unit: byte).
Bandwidth $B$ = how fast the link ships bytes (unit: byte/second).
Habit: before every example, Forecast the answer. Guessing first is what turns a formula into intuition. Related ideas live in Rofline Performance Model, Amdahl's Law and Scalability, and Memory Hierarchy and Caching.

Back to the parent topic.

The scenario matrix

Every problem in this topic is one of a small number of shapes. The table below is the full menu. Each of the worked examples underneath is tagged with the cell it covers, and together they touch every row.

Cell	Scenario class	The question it tests	Degenerate / limiting edge
A	High arithmetic intensity	Is $W$ big enough to beat transfer?	$W \to \infty$ : GPU always wins
B	Low arithmetic intensity	Same, but the task is data-heavy	$W \to 0$ : never offload
C	Exact break-even	Where does hetero = CPU-only?	$T_{h e t er o} = T_{C P U}$
D	Amdahl with serial floor	How much serial fraction kills speedup?	$f_{s} = 0$ : pure parallel
E	Amdahl, infinite GPU	The ceiling nobody can pass	$S_{GP U} \to \infty$
F	Transfer-tax dominance	When the PCIe tax, not compute, rules	$t_{x f er}$ large
G	Pipeline, balanced stages	Speedup as $n \to \infty$	all $t_{i}$ equal
H	Pipeline, one bottleneck	Slowest stage caps throughput	one $t_{i} ≫$ rest
I	Real-world word problem	Translate English → symbols	—
J	Exam twist (unified memory)	Removing $t_{x f er}$ entirely	$t_{x f er} = 0$

We keep re-using these master formulas from the parent, restated once so every symbol is earned:

Example 1 — Cell A: high arithmetic intensity (GPU wins big)

Forecast: matrix multiply is the poster child for GPUs ( $O (n^{3})$ work, $O (n^{2})$ data). Guess: yes, easily.

Compute the break-even work threshold. Why this step? The formula tells us the minimum $W$ that makes offloading pay; we then check our real $W$ against it. $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. Why? Offload is worth it exactly when actual work exceeds the threshold. Actual $W \approx 1.72 \times 1 0^{10}$ FLOP $= 17.2$ GFLOP. $17.2 GFLOP ≫ 3.49 GFLOP \Rightarrow offload.$

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 is $3.5 \times$ faster — consistent with "offload." ✓

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

Forecast: one add per three memory touches — this is the "terrible for GPUs" case the parent warned about. Guess: don't offload.

Break-even threshold. Why? Same test as before, now with a data-heavy task. $W_{min} = \frac{2 ( 1.2 ) ( 1 ) ( 10 )}{32 ( 9 )} = \frac{24}{288} \approx 0.0833 TFLOP = 83.3 GFLOP .$
Compare. Why? Actual $W = 0.1$ GFLOP. $0.1 GFLOP ⋘ 83.3 GFLOP \Rightarrow do NOT offload.$

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 is 750× slower — the transfer tax buried a trivial compute. ✓ (Arithmetic intensity $= \frac{1 0 ^{8} FLOP}{1.2 \times 1 0 ^{9} B} \approx 0.083$ FLOP/byte, far below the $\sim$ 70 FLOP/byte crossover.)

Example 3 — Cell C: the exact break-even point

Forecast: the parent worked this and got $\approx 69$ GFLOP. Let's confirm and see it.

Figure — Heterogeneous computing concepts

Set the two times equal. Why? Break-even is by definition $T_{h e t er o} = T_{C P U}$ . $\frac{2 ( 1 )}{32} + \frac{W}{10} = \frac{W}{1} .$
Solve for $W$ . Why? We want the crossover work. $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: at $W = 0.0694$ TFLOP, hetero $= 0.0625 + 0.00694 = 0.0694$ s and CPU $= 0.0694$ s — equal. ✓ Look at the figure: to the right of the amber line GPU wins (Cell A), to the left CPU wins (Cell B). One line splits the whole world.

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

Forecast: GPU is 50× but serial + tax will crush it — guess low double digits.

Plug into heterogeneous Amdahl. Why? It's the master speedup formula. $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 .$
Attribute the loss. Why? To see which term hurts. Serial contributes $0.05$ , tax $0.02$ , parallel only $0.019$ to the denominator. The two fixed costs ( $0.07$ ) dwarf the compute term.

Verify: $\frac{1}{0.089} = 11.236 \dots$ — matches parent's $\approx 11.2 \times$ . ✓

Example 5 — Cell E: infinite GPU (the ceiling)

Forecast: the $f_{p} / S_{GP U}$ term vanishes, leaving only fixed costs. Guess: around 14×.

Take the limit. Why? To find the hard ceiling no hardware can beat. $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$ ✓ The curve in the figure rises then flattens at 14.29 — proof that after some point, buying a faster GPU buys you nothing. This is exactly Amdahl's Law and Scalability in heterogeneous clothing.

Example 6 — Cell D edge: zero serial fraction

Forecast: no serial floor — should be much closer to 50×.

Substitute. Why? To see the degenerate best case. $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: even with zero serial code the answer is 25, not 50 — the transfer tax alone halves it. The tax is a serial cost in disguise.

Example 7 — Cell J: unified memory removes the tax

Forecast: removing 0.02 from the denominator should push us above 14×.

Recompute. Why? Isolate the value of eliminating data movement. $S = \frac{1}{0.05 + \frac{0.95}{50} + 0} = \frac{1}{0.069} \approx 14.49 \times .$
Compare to Ex. 4. Why? To quantify the win. $14.49$ vs $11.24$ — a 29% improvement just from unified memory.

Verify: $1/0.069 = 14.49$ ; ratio $14.49/11.24 = 1.289$ . ✓ Ties directly to Memory Hierarchy and Caching and DMA and I/O Controllers — the whole point of DMA/unified memory is shrinking that $2 D / B$ term.

Example 8 — Cell G: balanced pipeline

Forecast: three equal stages → speedup approaches 3.

Sequential time. Why? Baseline with no overlap. $T_{se q} = n \sum t_{i} = 1000 (12) = 12000 ms .$
Pipelined time. Why? First item pays full latency, then we sustain at the slowest stage's rate. $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$ , and $\frac{\sum t _{i}}{m a x t _{i}} = \frac{12}{4} = 3$ as $n \to \infty$ .

Verify: $12000/4008 = 2.9940 \dots \approx 3$ . ✓ The figure's staircase shows stages fully overlapping — a new image starts every 4 ms once the pipe is full.

Example 9 — Cell H: one bottleneck stage

Forecast: compute is 5× the others — throughput is limited by 10 ms, so speedup ≈ $14/10 = 1.4$ , not 3.

Sequential. $T_{se q} = 1000 (2 + 10 + 2) = 14000$ ms. Why? Baseline.
Pipelined. $max t_{i} = 10$ . Why? The pipe drips out one result every 10 ms after fill. $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: a pipeline is only as fast as its slowest station — balance the stages (relates to load balancing in Parallel Programming Models).

Example 10 — Cell I: real-world word problem

Forecast: 8 TFLOP of work over 4 GB → intensity $\approx 2000$ FLOP/byte, sky-high. Guess: strongly offload.

Break-even threshold. Why? Decision test. $W_{min} = \frac{2 ( 4 ) ( 0.5 ) ( 8 )}{16 ( 8 - 0.5 )} = \frac{32}{120} \approx 0.267 TFLOP = 267 GFLOP .$
Compare. Actual $W = 8000$ GFLOP $≫ 267$ GFLOP $\Rightarrow$ offload. Why? Work is 30× the threshold.
Quantify the win. Why? Managers want a number. $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 — cover the answers

Which cell has speedup capped even with an infinite GPU? ::: Cell E — capped at $1/ (f_{s} + t_{x f er})$ . Vector add vs matrix multiply: which is Cell B (don't offload)? ::: Vector add (low arithmetic intensity, $O (n)$ work / $O (n)$ data). In a balanced 3-stage pipeline the speedup approaches ___ ? ::: 3, i.e. $\sum t_{i} / max t_{i}$ . Unified memory improves speedup by setting which term to zero? ::: $t_{x f er}$ (Cell J). The break-even threshold grows with which quantity, hurting offload? ::: Data size $D$ (bigger transfers need more work to justify).