Heterogeneous computing concepts: Visual walkthrough

Step 1 — Draw the whole job as a bar of time

WHAT. Imagine the entire program running on the CPU alone. We do not care yet what it does — we only care how long it takes. Draw that total time as one long bar.

WHY. Before we can talk about "speeding things up", we need one honest baseline: how long the slow, ordinary way takes. Everything else will be measured against this bar, so we give it the friendly value $1$ — one "whole job's worth of time".

PICTURE. The bar below is the whole job; its length is exactly $1$ . The horizontal axis is time as a fraction of the whole job (dimensionless, $0$ to $1$ ); there is no vertical scale — the bar's height is only for visibility.

Figure — Heterogeneous computing concepts

Step 2 — Split the bar into what CAN and CAN'T go to the GPU

WHAT. Cut the bar into two coloured pieces. One piece is work that must stay on the CPU (reading files, awkward if/else logic, glue code). The other piece is work that is the same operation repeated over millions of numbers — the piece a GPU loves.

WHY. A GPU cannot speed up everything. Only the repetitive, parallel part benefits. So the very first move in any real analysis is to ask "how much of my job is even eligible for the accelerator?" That question splits the bar.

Every term here is a length along the bar. If $f_{p} = 0.95$ then $95%$ of the bar is coloured "GPU-eligible" and only $5%$ stays "CPU-only".

PICTURE. Same bar and same horizontal axis as Step 1 (time as a fraction of the whole job, $0$ to $1$ ), now split into two colours whose lengths add back to the full $1$ . The tick at $f_{s}$ marks where serial ends and parallel begins.

Step 3 — Shrink only the parallel slice

WHAT. Send the parallel slice to the GPU. The GPU chews through it faster, so that coloured slice gets shorter. The serial slice does not move — it keeps its full length.

WHY. This is the heart of the whole idea. Speedup is not magic that shortens the whole bar; it only shrinks the part that ran on the faster machine. We need one number that says "how much faster is the GPU on this slice?"

So the parallel slice, originally length $f_{p}$ , becomes: $\frac{f _{p}}{S _{GP U}}$

PICTURE. Two bars stacked, sharing the same time axis (fraction of the whole job, $0$ to $1$ ): the "before" bar on top, the "after" bar below. Watch the pink slice collapse while the yellow serial slice stubbornly stays the same length.

Step 4 — Add the tax nobody talks about: moving the data

WHAT. The GPU has its own memory (VRAM). To use it, the CPU must copy the data in, and later copy the result back. That copying takes time — and it happens no matter how fast the GPU computes.

WHY. In Step 3 we quietly assumed the GPU slice was "free to hand over". It is not. This is the piece that turns a beautiful theory into engineering reality — and it is the piece that will build the wall. We name this cost.

First, name the two ingredients of any copy. Copying takes longer when there are more bytes to copy, and shorter when the pipe is fatter. So we need exactly two named quantities:

How much data is there? It depends on how big the parallel slice is. A bigger parallel slice ( $f_{p}$ closer to $1$ ) usually means more numbers to ship, so $D$ is really a function of $f_{p}$ . We write that dependence explicitly as $D (f_{p})$ — read it " $D$ as a function of $f_{p}$ ", i.e. "the number of bytes we must move when the parallel fraction is $f_{p}$ ". The key facts we need are only these two: $D (f_{p})$ grows as $f_{p}$ grows, and $D (0) = 0$ (no parallel slice ⇒ no bytes to move).

Definition The transfer overhead

$t_{x f er} (f_{p})$ Now build the tax. Take the seconds a round-trip copy costs, $\frac{2 D ( f _{p} )}{B}$ , and divide by $T_{0}$ so it is expressed as a fraction of the original job (matching $f_{s}$ and $f_{p}$ , which are also fractions of the job): $t_{x f er} (f_{p}) = \frac{1}{T _{0}} \cdot \frac{2 D ( f _{p} )}{B}$

the $2$ = "copy in and copy back" (two one-way trips),
$D (f_{p})$ = bytes to move, which grows with the parallel slice,
$B$ = pipe width (bytes per second),
dividing by $T_{0}$ turns seconds into a fraction of the whole job.

We write $t_{x f er} (f_{p})$ with the $(f_{p})$ shown precisely so nobody mistakes it for a constant. If copying costs $2%$ of the original job time, then $t_{x f er} (f_{p}) = 0.02$ for that particular $f_{p}$ . Crucial consequence: if $f_{p} = 0$ then $D (0) = 0$ , so $t_{x f er} (0) = 0$ — no parallel work means nothing to ship, hence no tax.

Now stack the three pieces to get the new total time: $T_{h e t er o} = serial slice (unchanged) f_{s} + parallel slice (shrunk) \frac{f _{p}}{S _{GP U}} + data-move tax (grows with f_{p}) t_{x f er} (f_{p})$

The subscript hetero means "on the heterogeneous CPU+GPU system". Read the equation left to right and you are literally reading the new bar left to right.

PICTURE. The new bar on the same time axis (fraction of the whole job): full yellow serial slice + tiny pink shrunk slice + a grey tax block whose length is $t_{x f er} (f_{p})$ , i.e. it depends on how much parallel data we shipped.

Step 5 — Compare old bar to new bar → the speedup formula

WHAT. Speedup is just "how many times shorter did the bar get?" Old bar over new bar.

WHY. We want a single number to report to a boss: "we made it $X$ times faster." That number is a ratio of the two bar lengths we just drew.

Plug in the parent note's numbers ( $f_{s} = 0.05$ , $f_{p} = 0.95$ , $S_{GP U} = 50$ , and for this workload $t_{x f er} (0.95) = 0.02$ ): $S_{o v er a l l} = \frac{1}{0.05 + \frac{0.95}{50} + 0.02} = \frac{1}{0.05 + 0.019 + 0.02} = \frac{1}{0.089} \approx 11.2 \times$

Fifty-times-faster hardware, eleven-times-faster program. The two little constants $0.05$ and $0.02$ ate most of it.

PICTURE. Old bar on top, new bar below, both on the same time axis (fraction of the old job, $0$ to $1$ ), with a bracket showing "≈ 11× shorter, not 50×".

Step 6 — The wall: push the GPU to infinity

WHAT. Now do a thought experiment. Suppose the GPU became infinitely fast — the shrunk slice vanishes entirely, $f_{p} / S_{GP U} \to 0$ .

WHY. This is the classic move to find the ceiling. If even a perfect GPU can't remove the serial slice and the tax, then those two together are a hard limit no hardware can beat. We use a limit because it answers the exact question: "what is the best possible outcome?"

So even a magical GPU caps out around $14.3 \times$ for this workload. The $11.2 \times$ we already got is startlingly close to the ceiling — buying faster hardware would barely help. The serial slice and the transfer tax are the wall.

PICTURE. Horizontal axis: $S_{GP U}$ (how many times faster the GPU is, dimensionless). Vertical axis: $S_{o v er a l l}$ (overall program speedup, dimensionless). The blue curve climbs as $S_{GP U}$ grows, then flattens against a dashed pink ceiling line at $1/ (f_{s} + t_{x f er} (f_{p}))$ .

Step 7 — Edge & degenerate cases (never leave a gap)

WHAT. Every case a reader could hit. We test the formula at its extremes so nothing surprises you.

WHY. A formula you trust only in the "nice" middle is a trap. Push it to $0$ , to $1$ , to no-tax, and check it says something sensible. Crucially, we now respect that $t_{x f er} (f_{p})$ depends on $f_{p}$ : no parallel work ⇒ no data moved ⇒ no tax.

Worked example Five corners of the formula

Using $S_{o v er a l l} = \frac{1}{f _{s} + f _{p} / S _{GP U} + t _{x f er} ( f _{p} )}$ with $f_{s} + f_{p} = 1$ , $f_{s}, f_{p} \geq 0$ :

(a) Nothing is parallel, $f_{p} = 0$ (so $f_{s} = 1$ ). There is no data to ship, so $t_{x f er} (0) = 0$ automatically. Denominator $= 1 + 0 + 0 = 1$ . Speedup $= 1$ — exactly the same as the CPU, no better, no worse. You correctly gained nothing and, honestly modelled, lost nothing either. Lesson: don't even set up the GPU path.

(b) Everything is parallel, $f_{s} = 0$ so $f_{p} = 1$ , and (idealised) no tax $t_{x f er} (1) = 0$ . Denominator $= 0 + f_{p} / S_{GP U} + 0 = 1/ S_{GP U}$ (since $f_{p} = 1$ ). Speedup $= S_{GP U}$ . The formula correctly collapses to the raw GPU speedup — the ideal.

(c) Fully parallel but the tax is REAL, $f_{s} = 0$ so $f_{p} = 1$ , and $t_{x f er} (1) > 0$ . Denominator $= 0 + 1/ S_{GP U} + t_{x f er} (1)$ . Speedup $= \frac{1}{1/ S _{GP U} + t _{x f er} ( 1 )} < S_{GP U}$ . Even with zero serial work, the transfer tax alone drags you below the raw GPU speedup — the wall exists even when nothing is serial. This is the honest version of case (b).

(d) Free transfers, $t_{x f er} (f_{p}) = 0$ (unified memory, no copies). Speedup $= \frac{1}{f _{s} + f _{p} / S _{GP U}}$ — this is classic Amdahl's Law. Our formula is Amdahl plus a data-movement tax; remove the tax and Amdahl reappears. See Amdahl's Law and Scalability.

(e) Tiny GPU speedup, $S_{GP U} = 1$ (GPU no faster), with real parallel work $f_{p} > 0$ so $t_{x f er} (f_{p}) > 0$ . Denominator $= f_{s} + f_{p} + t_{x f er} (f_{p}) = 1 + t_{x f er} (f_{p})$ . Speedup $= \frac{1}{1 + t _{x f er} ( f _{p} )} < 1$ — you slowed down by exactly the tax, because you paid to move data for zero compute benefit.

PICTURE. Five mini-bars stacked, all on the same time axis (fraction of the old job): a dotted vertical line marks the old baseline length $1$ , and each case's new bar is drawn to true length so you can see it land at, below, or past the baseline.

The one-picture summary

Everything above, compressed: start with a bar of length $1$ , split it into serial (yellow, immovable) and parallel (pink, shrinkable) with $f_{s} + f_{p} = 1$ , collapse the pink by $S_{GP U}$ , glue on the grey transfer tax $t_{x f er} (f_{p})$ (which is only there because there is pink to move), then read the speedup as old length ÷ new length — bounded forever by the yellow+grey stub.

Recall Feynman retelling — say it back in plain words

Picture your whole program as one chocolate bar, and its length is how long it takes.

Some squares of the bar are "boring glue work" (reading files, weird logic) — those have to stay on the CPU, and they never get shorter. The rest of the bar is "the same math a million times" — those squares can go to the GPU. The two kinds of squares always add up to the whole bar, and you can't have negative squares or more than a full bar.

The GPU is fast, so it shrinks only those math squares, dividing their length by how many times faster it is. But there's a catch: you have to carry the data over to the GPU and carry the answer back, and that carrying costs a grey chunk. How big is that grey chunk? It's the number of bytes you move ( $D$ ) divided by how fast the wire is ( $B$ ), times two for the round trip. And the number of bytes only exists because there are math squares to feed — if none of the bar can go to the GPU, there's nothing to carry and no grey chunk at all.

So the new bar = the immovable glue squares + the tiny shrunken math squares + the grey carrying chunk. Your speedup is just how many times shorter the new bar is than the old one.

The punchline: as long as there is real GPU work, even an infinitely fast GPU still leaves the glue squares and the grey carrying chunk. They set a wall you can never break through. That's why a 50×-faster GPU only gave an 11× program — we were already almost touching the wall.

See also: Parallel Programming Models · Memory Hierarchy and Caching · Power and Energy Optimization · SIMD and Vector Processing · Amdahl's Law and Scalability