liveBook · Manning

Privatization

As explained in Grokking GPU Programming

A technique that gives each parallel worker or group of workers a private copy of data, which can be merged after processing.

When many workers update the same histogram bin, atomic operations keep the count correct, but the updates must take turns. Privatization reduces that contention by giving each worker or group of workers a private copy to update, then combining the copies into the final result. section 8.8 section 8.4

A sequential histogram makes one pass over the input and updates a single set of bins. A CUDA histogram can instead give each block its own bins in shared memory. Threads in a block tally locally, and each block adds its partial counts to the global histogram. section 8.8

The CUDA pattern has three steps:

  • Initialize: divide the local bins among the block’s threads and set every bin to zero. Synchronize the block before tallying. section 8.8 section 8.12
  • Tally: read input elements and use shared-memory atomic adds to update the block’s bins. Synchronize again before merging. section 8.8 section 8.12
  • Merge: add each nonzero local count to its global bin with an atomic add, since blocks can merge concurrently. section 8.8
Figure 8.4 The three-step shared memory histogram pipeline, with time flowing top to bottom. Step 1 (setup): each of the m blocks zeros its own 256-bin localHist in shared memory in parallel. Step 2 (compute): each block i reads its k-element slice of the input from global memory and atomically increments the matching bins of its own localHist. Step 3 (merge): each block adds the values in its localHist into the single global hist array. Only Step 2 reads global input and only Step 3 writes global output; the heavy traffic between them, the tallying, stays in fast shared memory.

Follow the input from each block’s private histogram to the combined global histogram. section 8.8

Two partial histograms

Suppose two blocks process [1, 1] and [1, 2]. Their local counts for bins 1 and 2 are [2, 0] and [1, 1]. Merging them gives global counts [3, 1]. Each block contributes at most one global atomic update per bin, rather than one for every input element. section 8.8 section 8.12

Initialize the global histogram on the device before launch, too. Both block barriers must be reached by every thread: otherwise, tallying could begin before initialization is complete, or merging before tallying is complete. Private copies do not eliminate all contention: threads within a block can still compete on shared-memory atomics, including through memory-bank conflicts. section 8.12 section 8.8

The same local-then-global idea appears in reduction, where blocks produce partial sums. On a CPU, OpenMP can give each thread private histogram bins and sum them at the end. Performance depends on the hardware, bin count, and distribution of values; privatization reduces global contention but does not guarantee a particular speedup. section 8.8

How Grokking GPU Programming covers it

How deep it goes
Walks through initialization, atomic local tallying, synchronization, and global merging, including remaining shared-memory contention.
Examples
Uses a 256-bin CUDA histogram, a pixel-intensity histogram, and per-thread OpenMP bins.
What you can do after
Build a privatized CUDA histogram from scratch using shared-memory atomics, block barriers, and a global merge.
How it connects
Connects privatization to histograms, atomic operations, shared memory, reduction, and synchronization.

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.