liveBook · Manning

Histogram pattern

As explained in Grokking GPU Programming

The histogram pattern counts input values into corresponding categories or bins, combining contributions that may come from multiple threads.

Imagine counting pixel values: each value goes into a matching bin, and each bin records how many times that value appeared. The histogram pattern turns an array of N inputs into an array of B counts, one per bin. section 8.11 section 8.6

Counting repeated values

For inputs [42, 7, 42], increment bin 42, then bin 7, then bin 42 again. The result is 2 in bin 42 and 1 in bin 7; all other bins remain zero. section 8.11 section 8.6

Sequentially, one worker can increment each bin in turn. In parallel, two threads may read the same bin before either writes its increment. One update can overwrite the other, leaving a count that is too small. This is a race condition. section 8.6

A simple CUDA fix is to zero the global histogram on the device before launch and use atomicAdd(&hist[bin], 1) for each input. The atomic operation protects each increment, but threads targeting the same bin must take turns. A popular, or hot, bin can therefore become a bottleneck. section 8.12 section 8.11

Privatization reduces pressure on the global bins. Each CUDA block builds its own histogram in shared memory, like a group of ballot counters keeping local totals before adding them to a master tally. section 8.8

A privatized histogram has three stages:

  • Initialize: threads zero the block’s local bins. A stride loop lets each thread clear more than one bin when needed. All block threads then meet at a __syncthreads() barrier. section 8.8
  • Tally: threads read inputs and use shared-memory atomicAdd to increment local bins. A second barrier ensures the tally is complete before merging. section 8.8 section 8.12
  • Merge: threads add local counts to the global histogram with atomicAdd, because different blocks can still update the same global bin simultaneously. section 8.8
__global__ void histogramShared(int* data, int* hist, int n) {
    __shared__ int localHist[256];
    int tid = threadIdx.x;
    int idx = blockIdx.x * blockDim.x + threadIdx.x;
 
    // Step 1: Initialize
    for (int i = tid; i < 256; i += blockDim.x) {
        localHist[i] = 0;
    }
    __syncthreads();
 
    // Step 2: Build local histogram
    if (idx < n) {
        int bin = data[idx];
        atomicAdd(&localHist[bin], 1);
    }
    __syncthreads();
 
    // Step 3: Merge to global
    for (int i = tid; i < 256; i += blockDim.x) {
        if (localHist[i] > 0) atomicAdd(&hist[i], localHist[i]);
    }
}

This complete kernel puts the initialization, local tally, and global merge together for 256 bins. section 8.8

Keep both barriers where every thread in the block reaches them, even when some threads have no input to process. Otherwise, conditional synchronization can deadlock. Also check initialization: counts that carry over between runs can mean the device histogram was not zeroed. Different results on repeated runs suggest a race, but a race can also repeat the same answer. section 8.11 section 8.12

Privatization replaces up to one global atomic increment per input with at most one global atomic addition per bin per block. It does not remove local contention, but it confines the frequent tally updates to shared memory. For inputs larger than the thread count, a grid-stride loop lets each thread process multiple elements. section 8.12 section 8.8

How Grokking GPU Programming covers it

How deep it goes
Works through atomic increments, contention, shared-memory privatization, barriers, and the global merge.
Examples
Uses pixel-value bins, an election-night tally, and exercises counting survey answers, letters, and concurrent meetings.
What you can do after
Build from scratch a CUDA histogram using atomics and a shared-memory privatized merge.
How it connects
Connects race conditions, atomic operations, synchronization barriers, privatization, reduction, and grid-stride loops.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Grokking GPU Programming. The section links point to the parts of the book it draws on.