Building a Histogram

A histogram counts how many inputs fall into each bin. Many threads will want to increment the same bin, so this is an atomics problem. 📊

Each thread reads one element, finds its bin, and increments that bin. Without protection, popular bins lose counts to races.

The simplest correct fix is one atomicAdd per element straight into global memory. It works, but hot bins serialize threads.

When data clusters into a few bins, thousands of threads pile onto the same address. That contention can make global atomics painfully slow.

Privatization gives each block its own private histogram in fast shared memory. Threads collide only inside their block, not across the whole grid.

Each block declares a shared array sized to the number of bins. It lives on-chip, so atomics there are far cheaper than global ones.

Threads cooperatively zero the shared histogram, then call __syncthreads so no one counts before clearing is done.

Now each thread atomically bumps its bin in shared memory. Same atomicAdd, but on the fast on-chip copy instead of global.

After a barrier, threads add each shared bin into the global histogram with one atomicAdd per bin. Far fewer global atomics than before.

Shared-memory atomics are quick, and the costly global atomics now fire once per bin per block instead of once per element.

The private histogram must fit in shared memory. With too many bins, split them into passes or fall back to global atomics.

One question on the histogram strategy.

You built a histogram with global atomics, then sped it up using shared-memory privatization: clear, count locally, merge. ✅