A histogram looks like the simplest kernel there is. Read a key, add one to its bin. On a GPU, that simple update can become the slowest line in a program.
This post walks through the four methods recorded on the MI300X study. The workload is a skewed integer histogram on an AMD Instinct MI300X VF under ROCm 7.2.4.
The workload
The input holds 67,108,864 keys. The output holds 4,096 bins. The keys are skewed, so many of them map to the same few bins.
Skew is what makes this workload hard. With uniform keys, updates spread across all 4,096 bins. With skewed keys, thousands of threads try to update the same memory location at the same moment.
Why global atomics stall
The baseline made one global atomic update per key. An atomic add is safe because the hardware applies each update in turn. That same rule is the cost. When many threads target one address, the hardware must apply their updates one after another.
So the kernel does not run at the speed of the GPU. It runs at the speed of the busiest bin. The recorded baseline took 86.3898 ms.
Two methods that did not move the bottleneck
The study recorded two attempts that aimed at other costs.
Larger blocks and vector loads recorded 86.3963 ms. Wider loads help when a kernel waits on memory bandwidth. This kernel waited on atomic contention, so the time stayed the same.
Wave aggregated atomics recorded 73.2241 ms. Here, threads in one wavefront that share a bin combine their counts first, then one thread issues the atomic. That cuts the number of atomics on hot bins, and the time dropped by about 13 ms. Contention across wavefronts and blocks remained.
Both results are useful. They show where the time was not going, and they rule out bandwidth as the main cost.
The method that worked
The revised kernel counted within each block and then merged those counts. Each block keeps its own private copy of the 4,096 bins. Threads update that local copy first. At the end, each block adds its local counts into the global histogram once.
This changes the shape of the contention. Hot bins are still hot, but each block competes only with its own threads. Global updates happen once per block at the merge, instead of once per key.
The recorded time for block local counts and merge was 0.1015 ms. The baseline of 86.3898 ms ran on the same card, workload and ROCm 7.2.4 stack.
The ratio of the two recorded times is about 851. The speedup compares these two implementations on this workload, as the study states.
How the result was checked
Speed only counts once the answer holds. The revised kernel matched the CPU reference across five rounds with fresh inputs and a prefilled output buffer.
Fresh inputs stop a kernel from passing on a cached answer. A prefilled output buffer catches a kernel that skips writes. Any bin left unwritten keeps the fill value and fails the comparison. The poison buffer post covers this gate in more depth.
A histogram of integer counts has an exact answer, so the CPU reference can be matched exactly. Floating point histograms need a calibrated bound instead, as the tolerance post explains.
The full timing table
All four methods sit in one table on the MI300X study. Global atomic baseline 86.3898 ms. Larger block and vector loads 86.3963 ms. Wave aggregated atomics 73.2241 ms. Block local counts and merge 0.1015 ms.
The raw CSV archive is hosted as a dataset linked from the same page.
What carries over to your kernels
When a kernel uses atomics on skewed data, measure contention before tuning memory access. If wider loads do not change the time, bandwidth is not the limit.
Try keeping the hot state private to each block, then merge once. Check the result against a reference on fresh inputs with a prefilled output buffer before you trust the speedup.
The right block size and merge strategy depend on the chip and the ROCm version. A change in either one is a reason to measure again.
Run your workload
Bring the kernel or solver run that costs you the most time. Run a workload with Computelab.co.