Privatization is an item on GPU performance checklists. Threads that all update the same location in global memory have to take turns, so each thread works on its own block's private copy instead and the copies are combined once at the end. A histogram shows both the gain and the price, and this page calculates them.
The problem: one address, many updates
A histogram kernel can launch one thread for each input value. Each thread adds 1 to the bin its value belongs to, with atomicAdd on a counter in global memory. An atomic update reads, changes and writes the counter as one indivisible step, so the result is correct. Updates to the same address are applied one at a time. When there are few bins and many values, a long queue forms on each bin's address.
// One thread per value. Every thread updates the one global histogram.
__global__ void histogram_basic(const unsigned int *bin_of, unsigned int n,
unsigned int *hist) {
unsigned int i = blockIdx.x * blockDim.x + threadIdx.x;
if (i < n) {
atomicAdd(&hist[bin_of[i]], 1u);
}
}
Private copies
The privatized kernel launches G blocks of 256 threads. Block g takes a contiguous slice of n / G input values, and its threads stride through the slice, so each thread handles n / (256 G) values. Each block keeps its own copy of the histogram in shared memory. It zeroes the copy, updates it with shared-memory atomics, synchronizes with __syncthreads(), and then adds each bin of its copy to the global histogram.
// Each block counts its slice into a private copy in shared memory,
// then adds the whole copy to the global histogram once.
__global__ void histogram_privatized(const unsigned int *bin_of, unsigned int n,
unsigned int bins, unsigned int *hist) {
extern __shared__ unsigned int copy[];
// Zero the block's copy, with threads striding over the bins.
for (unsigned int b = threadIdx.x; b < bins; b += blockDim.x) {
copy[b] = 0;
}
__syncthreads();
// This block's contiguous slice of the input. gridDim.x must divide n,
// or the n % gridDim.x leftover values would be skipped.
unsigned int slice = n / gridDim.x;
unsigned int start = blockIdx.x * slice;
for (unsigned int i = threadIdx.x; i < slice; i += blockDim.x) {
atomicAdd(©[bin_of[start + i]], 1u);
}
__syncthreads();
// Merge: every bin of the copy, empty ones included.
for (unsigned int b = threadIdx.x; b < bins; b += blockDim.x) {
atomicAdd(&hist[b], copy[b]);
}
}
The kernels on this page are in histogram.cu; its README gives the build command, the inputs checked and the recorded run. They were compiled and checked for correct output against a CPU reference on an RTX A6000, and they were not timed.
The kernel above already gives each thread several values: with 256 blocks, each thread handles 16. Giving each thread still more values, so that fewer blocks are launched, is thread coarsening, which the next page in this chapter covers. A common refinement of the merge is to skip bins whose count is zero, which the kernel above does not do.
The kernel needs gridDim.x to divide n, because each block takes a slice of n / gridDim.x values. The figure offers only block counts that do, so every block receives an equal slice.
Calculating the queues
The figure counts updates for n = 1,048,576 input values. The histogram has B bins. In the even input, value i goes to bin i mod B. In the skewed input, every even i goes to bin 0 and every odd i is spread over the B bins, so bin 0 receives half of all updates plus its share of the other half: 599,187 of the 1,048,576 with 7 bins. Start at 7 bins, the even input and 256 blocks, then switch to the skewed input.
No private copies
Global memory. Longest queue 149,797.
One block's copy
Shared memory, block 0. Longest queue 586.
Merge to global
Global memory. 256 updates per bin.
One linear scale for all three charts, 0 to 149,797 updates.
Calculated counts, not times. The input is split evenly across the blocks, and the merge adds every bin of every copy. In the readout, A → B is without copies → with copies. A nonzero bar is drawn at least 3% of the chart height so that it stays visible. A shorter queue is not a measured speedup.
With 7 bins and 256 blocks, the even input puts 149,797 updates on the busiest global address without copies. With copies, the busiest global address receives 256 updates, one from each block, during the merge. The skewed input raises the first number to 599,187 and leaves the second at 256. The merge makes 256 x 7 = 1,792 global updates instead of 1,048,576.
The queues do not disappear. They move into shared memory, where the busiest bin of one copy holds 586 updates for the even input and 2,341 for the skewed one. Shared-memory atomics are a different mechanism from global ones. NVIDIA's post on fast histograms with shared atomics reports that on a GeForce GTX TITAN X (Maxwell) the shared-atomics histogram was almost twice as fast as the global-atomics version, while on a GeForce GTX TITAN (Kepler), which handles shared-memory atomics in software, global atomics generally won. That is a measured claim about those GPUs, not something the figure shows.
Costs and limits
- Shared memory. Each copy takes bins x 4 bytes with 32-bit counters: 28 bytes for 7 bins and 1,024 bytes for 256. Shared memory is divided among the blocks on an SM, so a larger copy can lower how many blocks fit, one of the knobs in the occupancy section of the SM page. A very large bin count may not fit at all.
- The merge. It adds blocks x bins global updates. With 256 bins and 1,024 blocks that is 262,144 updates, and with 4,096 blocks it is 1,048,576, as many as the input has values. At that point the merge removes the update saving, and the merge queue on one address is then 4,096, the same as without copies for the even input.
- The gain depends on contention. With 7 bins, every copy removes a long queue. With 256 bins and the even input the busiest address has 4,096 updates without copies and 1,024 with 1,024 blocks, a smaller change. The skewed input keeps the gain large, because one hot bin receives more than half of all updates.
These are calculated counts, so they show where the cost moves, not how long the kernel takes. The parallel histogram chapter of Programming Massively Parallel Processors discusses when privatization pays. Fewer blocks, each processing more input, mean fewer merges. That is the link to thread coarsening: it reduces the number of copies to merge.
The same pattern elsewhere
- Reductions. Each block reduces its slice to one partial sum, and the partial sums are combined afterwards.
- A split inner dimension. Kernel 7 of the eight-kernels article has each block add its partial sums straight into
YwithatomicAdd. A private alternative is a buffer per split followed by a reduction. This page makes no claim about what any library does.
Further reading
- Programming Massively Parallel Processors, 4th edition (Hwu, Kirk and El Hajj, 2022): the parallel histogram chapter, on atomic operations, privatization, coarsening and aggregation, and the chapter on performance considerations.
- NVIDIA, GPU Pro Tip: Fast Histograms Using Shared Atomics on Maxwell, NVIDIA Technical Blog.
- One multiply, one RTX 5090, eight kernels, for Kernel 7's
atomicAddinto the output.
Related concepts
A tiled matrix multiply repeats global loads across neighboring blocks. Let one block compute several output tiles, then calculate the loads it saves and the SM slots it leaves idle.
A fine kernel can still profile poorly: warp divergence taxes throughput ~1/N; alone on a long scoreboard wait, SM issue util can hit 0%. Interactive demos.
Master GPU memory hierarchy from registers to global memory, understand coalescing patterns, bank conflicts, and optimization strategies for maximum performance
A matrix multiply is cut into thread-block tiles, and the tiles run in waves across the SMs. Calculate both rounding losses and read the steps in a throughput sweep.
How page-locked memory changes CPU-to-GPU transfers, the extra staging in pageable paths, and the conditions needed to overlap copies with GPU work.
Deep dive into the CUDA context object: control vs data plane, inventory (memory, modules, streams, events, graphs), push/pop/setCurrent stacks, primary retain/release, flags and limits, isolation, cost, and traps.
