Given GPUs’ stellar performance in performing reductions, such as computing the sum of an input array (as described in Chapter 12), one could be forgiven for expecting them to be equally good at computing histograms, which at first blush seems like a similar calculation. When the first edition of this book was written, the data-dependent behavior due to contention was hard to avoid, and strategies to detect degenerate input data reduced average-case performance. The best algorithm therefore depended on the application: applications that required level performance no matter what the input data preferred the per-thread implementations, while applications that were unlikely to encounter degenerate input data preferred the per-block implementations.
The first edition closed by calling for NVIDIA to add hardware
support for atomics in shared memory, which they did. Beginning with
Maxwell (SM 5.0), shared memory has a native atomic unit, and a
shared-memory atomic compiles to a single ATOMS instruction
with the same split between a form that returns the prior value and one
that does not (Section 8.1.5). On a GeForce RTX 3060, the per-block
implementation reading 32 bits at a time sustains about 279 Gpix/s
across the entire sweep, from 256 possible input values down to 1,
varying by less than 2%; it matches NPP on random input and runs twice
as fast on the degenerate input where NPP falls to half its rate. The
privatized per-thread implementations are just as level, but at about 72
Gpix/s they are roughly 4x slower. NVIDIA’s hardware absorbs the
contention: at 279 Gpix/s, our histogram kernel runs at 87% of the GPU’s
318 GB/s pure global read bandwidth, no matter what the data
contains.