Histograms, atomics, and skew
Predict atomic contention from a key distribution and choose a privatization scope
Before you begin
Follow a linked prerequisite when you cannot explain it from memory. Background skills without links are stated as abilities rather than hidden terminology.
- Atomics
- Shared memory
- Input distributions
A mixture-of-experts layer assigns each token to an expert and counts how many tokens each expert will receive. A simple CUDA histogram kernel lets one thread process each token and atomically increment the selected expert counter. With 65,536 tokens and 64 experts, a nearly uniform routing result spreads updates across many addresses. If half the tokens choose expert 0, Nsight Compute reports the same number of atomic instructions but the kernel time grows because many updates target one counter.
Run the histogram twice with the same array length and different key distributions. The output counters confirm correctness in both runs. The timeline and atomic-throughput counters reveal a performance difference caused by destination conflicts rather than by additional arithmetic. Engineers call simultaneous updates to the same memory location contention.
Atomics make a conflicting update correct by giving it a serialization point. They do not make the conflict disappear. If millions of threads increment one counter, the hardware must establish an order for those updates, and parallel execution collapses around a hot address. Contention is therefore a property of the input distribution as much as the code.
The standard remedy is privatization: create more counters at a narrow scope, aggregate there, and merge compact results later. Privatization spends memory and merge work to reduce simultaneous access to global state. The ideal scope depends on the number of bins, skew, shared-memory capacity, and whether per-warp or per-block working sets remain practical.
The word atomic describes correctness of one update. The word does not predict update throughput. Updates to unrelated addresses can proceed with substantial parallelism, while updates to one address must be ordered. A histogram design therefore begins with the distribution of destination addresses, not only with the instruction used to update them.
Contention comes from the key distribution
Suppose 32 lanes each issue one atomic increment. If they target 32 independent counters, the memory system can service several operations concurrently. If all 32 target counter 0, the updates to that address require one legal order. The second case has the same instruction count, but a much longer dependency chain at the hot location.
Use at least three distributions when evaluating a histogram: approximately uniform keys, a skewed distribution such as Zipf, and a single-hot case. The three inputs expose different limits. The uniform case tests general atomic throughput and memory locality. The skewed case tests realistic heavy hitters. The single-hot case shows the maximum serialization pressure and often motivates a dedicated path.
Warp aggregation and privatization
Warp aggregation detects lanes that target the same bin, elects one lane, counts the matching lanes, and issues one atomic update for the group. In the single-hot case, 32 atomics become one atomic with increment 32. In a uniform case, few lanes match, so grouping work may add overhead without reducing many atomics.
Block privatization allocates a histogram for each block, normally in shared memory. Threads update the private bins, and the block later merges its results into the global histogram. Privatization changes the number and scope of conflicts. Global contention falls because each block emits at most one update per nonzero private bin, but shared-memory capacity, local contention, initialization, and the merge pass become new costs.
When the bin set does not fit on chip
A 50,000-bin histogram with 32-bit counters needs about 200 KiB for one copy, which may exceed the shared-memory capacity available to one block. Allocating a private copy per warp is even less practical. The implementation can process subsets of bins in separate passes, use a smaller cache for frequently used bins, or handle identified heavy hitters separately from the long tail.
Each alternative changes traffic. Tiling the bin range rereads inputs unless keys are first partitioned. Hashing uses less storage but introduces collisions and a later merge. A heavy-hitter path requires a method to identify or assume the hot keys. There is no distribution-independent winner, so the benchmark must cover the declared production distribution and include every extra pass.
Counter lifecycle and numerical limits
Private counters must begin in a known state. Clearing a dense private histogram can dominate work when each block touches only a few bins. A touched-bin list can clear or merge only active bins, but maintaining that list adds bookkeeping. A generation-tag design stores an epoch beside each counter. A bin whose tag does not match the current epoch is treated as zero and initialized on first use, which avoids a dense clear but adds tag storage and synchronization on first access.
Select counter width from the maximum possible count, not from the input datatype. One hundred million records can overflow narrow counters even when each key is a 16-bit token identifier. Test initialization, overflow behavior, and merge correctness separately from throughput. Race detectors and exact CPU references can expose failures that aggregate performance measurements cannot.
Worked example: A skewed token-frequency histogram
A batch contains 100 million token IDs over a vocabulary of 50,000, but one padding token accounts for 45% of inputs.
- A direct global atomic places 45 million updates on one counter. Uniform-vocabulary benchmarks dramatically underestimate this contention.
- Estimate the reduction available from local aggregation. If each of 256 threads counts many tokens before updating, one block can replace thousands of padding-token atomics with one block partial.
- Detect or special-case the padding token. Each thread accumulates local occurrences, then warp or block reductions produce far fewer global updates for the hot bin.
- For remaining bins, use a privatization strategy sized to available shared memory or partition the vocabulary. Include initialization and merge passes in timing.
- Validate counts in 64-bit space and sweep skew from uniform to 90% hot. Plot the point at which each strategy overtakes direct atomics.
- Include the cost of clearing private bins and merging them. Report separate timings so the selected strategy can be explained rather than chosen from one total number.
Conclusion: Histogram performance depends on the destination distribution. The padding-token frequency determines the load on the hottest counter and can require a different aggregation method.
Common errors
- Calling atomics slow without measuring contention. Distributed atomics can be efficient; one hot location cannot.
- Privatizing blindly. Large private histograms consume capacity and expensive initialization or merge work.
- Benchmarking only a uniform distribution. Real routing, padding, and categorical workloads often contain severe skew.
- Using 32-bit counters because token IDs are 32-bit. Key width and maximum count are independent requirements.
Reference summary
Histogram-like workloads map many updates into fewer bins. Performance depends on skew: uniform keys spread atomics; hot keys serialize. Privatize bins per warp or block, aggregate repeated keys, then merge. But privatization consumes memory and adds a combine phase, so the best design depends on bin count and distribution.
- Benchmark uniform, Zipf-like, and single-hot distributions.
- On targets with suitable warp match/group operations, combine equal keys before issuing an atomic; retain another path for targets without those operations.
- Keep privatized hot bins on chip when capacity permits.
- Separate common and rare paths if one layout cannot serve both.
- Report performance across the declared input distributions. Do not select only the most favorable distribution.
Knowledge check
Why can a shared-memory histogram be slower for many bins even though shared memory has lower latency than global memory?
Show the answer guide
- Shared memory has lower access latency than global memory, but a shared-memory histogram still uses atomic updates when several threads target the same bin. Lower storage latency does not remove serialization among conflicting updates.
- A histogram with many bins needs a large private table per block. The table can consume most of the shared-memory budget, reduce resident blocks, and lower occupancy.
- Every block must initialize its private bins and later merge them into the global histogram. When the bin count is large or each block processes few inputs, initialization and merge traffic can exceed the global atomics that privatization removed.
- The access pattern can also become irregular and poorly coalesced during the merge. A shared-memory design is beneficial only when contention reduction outweighs table initialization, capacity, occupancy, and merge costs for the measured distribution.
Sweep histogram bin count and input skew
Implement an FP32- or integer-key histogram with direct global atomics and a block-private shared-memory version. Process 16 million keys with 16, 256, 4,096, and 32,768 bins under both a uniform distribution and a distribution in which 90% of keys select one bin. Verify exact bin counts before timing the kernels.
Evidence to keep: Submit both kernels, exact correctness tests, a benchmark matrix for every bin-count and distribution pair, and profiler reports for one winning and one losing shared-memory case that include shared-memory use, occupancy, and atomic activity. Conclude which measured cost causes the crossover.
Reduction, scan, and histogram kernels use hierarchical cooperation. GEMM applies the same structure to staged tiles and partial accumulations across the K dimension.
Sources and further reading
The lesson explanations synthesize primary papers and official references. Follow the originals for proofs, exact APIs, architecture details, and version-sensitive behavior.
- CUDA C++ Programming Guide↗
- CUDA C++ Best Practices Guide↗
- Nsight Compute Profiling Guide↗
- NVIDIA Nsight Systems User Guide↗
Official reference for capturing and reading CPU, CUDA API, GPU workload, and communication timelines.
- NVIDIA CUTLASS↗