What GPU-Friendly Work Has in Common
Dense linear algebra, graphics, model training and inference, image processing, scientific simulation. The list looks unrelated until you notice that every entry is wide, regular and reuses each loaded byte many times — and that the workloads which disappoint share the opposite properties.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
The property behind the list
Dense matrix multiplication is the canonical case because it maximises all three conditions at once. Every element of every tile is reused once per row or column it participates in, so arithmetic intensity grows with tile size; every output is independent; and there is no data-dependent control flow at all. The hardware was shaped around this workload and it shows.
Everything else on the usual list inherits some subset. Graphics is embarrassingly parallel per pixel with largely uniform shading. Convolution reuses each input pixel across every overlapping window. Physical simulation applies the same update to every cell of a grid. What they share is not a domain; it is a shape.
The classification below is the useful artefact. Rather than asking "is this the kind of thing people run on GPUs", ask where the workload sits on width, regularity and intensity — and note that failing any single one is usually enough to sink it.
| Workload | Width | Regularity | Arithmetic intensity | Verdict |
|---|---|---|---|---|
| Dense matrix multiply | High | Uniform | High and tunable via tiling | The shape the hardware was built for |
| Convolution / image filters | High | Uniform | High — each pixel reused across windows | Strong fit |
| Model training and inference | High | Mostly uniform | Varies — high when batched, low when not | Fit depends on batching; see LLM Inference Is a Memory Bandwidth Problem |
| Physical simulation on a grid | High | Uniform | Moderate to high | Strong fit |
| Elementwise array transform | High | Uniform | Very low — one op per element | Bandwidth-bound; the port relocates the bottleneck |
| Graph traversal on a sparse graph | High | Highly divergent | Low, and scattered | Usually a poor fit — see Pointer Chasing: The Address You Do Not Have Yet |
| Sequential state machine | None | Divergent | Irrelevant | No parallelism to exploit at all |
The anti-cases, and why they fail specifically
It is worth being precise about failure rather than saying "not parallel enough", because each anti-case fails for a different reason and the reasons suggest different remedies.
Small inputs fail on fixed cost: the launch and transfer overheads do not shrink with the problem, so below the break-even the device cannot win regardless of the kernel. Sequential dependencies fail on width: there is nothing to run in parallel, and no hardware can manufacture independence that the algorithm does not have. Irregular access — sparse graphs, hash tables, pointer-linked structures — fails on both regularity and intensity: lanes diverge and their scattered addresses defeat coalescing, so traffic multiplies while arithmetic stays flat.
The remedies differ accordingly. Small inputs can sometimes be batched together into one launch until they clear the break-even. Sequential algorithms sometimes have a parallel reformulation — a scan or a reduction where a loop was written — and if they do not, the answer is simply the CPU. Irregular access sometimes yields to reordering or a different data structure, which is the same insight as Data-Oriented Design, Without the Dogma: the layout is part of the algorithm.
1// Each step needs the previous one. One lane could do2// this; ten thousand lanes cannot help, because there is3// no independent work for them to take.4state = initial5for i in 0..n:6 state = step(state, input[i])1// If step is associative, the same result is available2// from a parallel scan in log n dependent rounds, each3// round wide enough to fill the device.4partials = parallel_scan(input, step)5state = partials[n-1]6 7// The change is algorithmic, not a kernel optimisation.8// Associativity is the property that makes it legal.The hardware cannot create parallelism the algorithm does not express. Where a reformulation exists — scan, reduction, divide-and-conquer — it is worth far more than any kernel tuning, and where none exists the honest answer is that this workload belongs on a CPU.
A decision procedure
In order, and stopping at the first failure: is there enough independent work to fill thousands of lanes? Do those units of work mostly follow the same control path? Is each loaded byte used enough times that the kernel will not simply be bandwidth-bound? And does the total work exceed the fixed cost of launching and transferring?
If all four hold, the port is very likely worth it and the remaining question is engineering. If the third fails but the others hold, the GPU may still win by the ratio of memory bandwidths — a real but much smaller prize, and one that has to be weighed against the transfer. If the first or second fails, no amount of kernel work will fix it, because the problem is in the algorithm rather than in the implementation.
This is worth writing down before starting, because the failure modes are all discovered late otherwise. A kernel can be correct, well-written and thoroughly tuned, and still lose to the CPU because the workload never had the shape — and that outcome is indistinguishable from a tuning problem until you check the conditions explicitly.
- Width — thousands of independent elements, not dozens. Fails: sequential dependencies, tiny inputs.
- Regularity — units of work mostly agree on control flow and touch nearby addresses. Fails: sparse graphs, data-dependent branching.
- Intensity — many operations per byte moved. Fails: elementwise transforms, single-pass scans over large arrays.
- Scale — total work large enough to swallow launch and transfer. Fails: small or latency-sensitive calls.
- Pass all four and the port is engineering; fail width or regularity and it is an algorithm problem no kernel can fix.
Key points
- The GPU-friendly list is one property repeated: wide, regular, high-reuse work — not a set of domains to memorise.
- Dense matrix multiplication is canonical because it maximises all three conditions simultaneously.
- Each anti-case fails for a specific reason — fixed cost, missing width, or irregularity — and each has a different remedy.
- A sequential algorithm sometimes has a parallel reformulation; if it does not, the CPU is the right answer.
- Check the four conditions before porting, because a tuned kernel on an unsuitable workload looks exactly like a tuning problem.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Algorithm → independent units: the work is decomposed into elements that can proceed without waiting on each other.
- 2Units → lane groups: elements are grouped, and uniform control flow across a group keeps every lane useful.
- 3Lanes → memory: neighbouring elements touch neighbouring addresses, so requests coalesce into wide transactions.
- 4Loaded bytes → arithmetic: each byte participates in many operations, keeping the compute units rather than the memory system as the constraint.
- 5Total work → fixed cost: the launch and transfer overheads amortise, and the device's advantage survives to the wall clock.
- • "Our workload is in a domain where GPUs are used, so it will benefit" — the domain is a proxy for the property, and proxies fail on new cases.
- • "It is parallel, so it qualifies" — width alone is one condition of four, and it is the one most workloads pass.
- • "The speedup was disappointing, so the kernel needs tuning" — check the conditions first; an unsuitable shape is not a tuning problem.
- • "Sparse means less work, so it should be faster" — less arithmetic with scattered access is exactly the profile a GPU handles worst.
Consequences, controls and cost
- • Workloads matching the shape see speedups large enough to change what is feasible, not merely what is fast.
- • Workloads missing one condition see modest gains that often fail to justify the second toolchain.
- • Workloads missing width or regularity can be slower on the GPU than on a single CPU core.
- • Teams that classify by domain rather than by property port the wrong things and conclude the hardware disappointed.
- • Classify the workload on width, regularity, intensity and scale before writing any kernel.
- • Look for a parallel reformulation — scan, reduction, tiling — before concluding a sequential algorithm cannot move.
- • Batch many small independent problems into a single launch to clear the fixed-cost threshold.
- • Reorder or restructure data to recover regularity when the algorithm permits it.
- • Count independent units of work in the algorithm and compare against the device's lane count — orders of magnitude, not exact numbers.
- • Estimate arithmetic intensity on paper as operations divided by unique bytes touched.
- • Prototype the smallest honest end-to-end version, including transfer, before committing to a full port.
- • Profile achieved arithmetic throughput against achieved memory throughput; whichever is near peak is the constraint.
- • Restructuring an algorithm for width and regularity can make it less clear and harder to maintain than the sequential version.
- • Batching small problems adds latency to each individual one in exchange for throughput across all of them.
- • A parallel reformulation frequently does more total work than the sequential algorithm, and only wins because the work is spread.
Scope
§224 — what these claims are specific to.
- GPU-SPECIFICThe thresholds implied here — thousands of elements, high reuse — scale with the device; a small integrated GPU has a much lower bar than a datacentre part.