Chapter 8: The Histogram pattern
This introduction illustrates lost updates in shared results and contrasts them with earlier patterns that reduce write collisions.
After this chapter you will be able to
- Shared result race conditions. Explain how concurrent updates to a shared result can overwrite work and produce an incorrect count.
- Concurrent increment race. Explain how concurrent increments can lose an update, including why shared memory does not eliminate the race.
- Atomic histogram updates. Explain how an atomic increment prevents the lost-update race and contrast the stated atomic needs of histogram and reduction kernels.
- Shared counter race. Trace how two threads incrementing a shared counter can lose an update, and contrast that with sequential execution.
- Atomic Counter Increment. Explain how atomicAdd replaces the ordinary increment of a shared counter and what arguments it takes.
- Device Counter Initialization. Explain why the device counter must start at zero and how this program initializes it.
- Compare-and-swap behavior. Explain how atomicCAS conditionally replaces a value and how its return value supports retries.
- Floating-point maximum with atomicCAS. Describe how the section builds a floating-point maximum from atomicCAS, including the required initialization and treatment of NaN.
- Atomic contention and cost. Explain why atomic updates to the same address can slow a histogram and how shared-memory cost and contention affect the design goal.
- Histogram counts and bins. Explain how a histogram counts occurrences using one bin per possible value, including the section’s 0–255 example.
- Single thread histogram construction. Describe how the single CPU thread builds the histogram and why its updates do not collide.
- Concurrent histogram bin conflicts. Explain why parallel histogram updates can lose counts when threads encounter the same pixel value.
- Atomic histogram bin updates. Explain how atomicAdd updates a global histogram bin and why the bin's address is passed to it.
- Bin contention and throughput. Explain how the distribution of values across histogram bins affects the performance of global atomics.
- Privatized histogram pipeline. Trace how each block initializes a private histogram, tallies input, and merges its counts into the global histogram. Describe how threads divide the bins and why both local and global updates use atomics.
- Barriers between histogram phases. Explain why the kernel synchronizes after initialization and after local tallying, and where those barriers must be placed.
- Per-bin contention and performance. Explain why privatization can improve histogram performance even when the total number of merge atomics is similar to the original number of global atomics.
- Grid-stride histogram extension. Describe how a grid-stride loop lets each thread tally multiple input elements and how launching fewer blocks can reduce merge contention.
- Shared update safety failures. Distinguish the consequences of omitting an atomic increment from those of placing a barrier where only part of a block reaches it.
- Shared Bin Update Race. Explain why plain increments of a shared histogram bin can lose counts and how atomicAdd fixes the race.
- Privatized Histogram Update Sites. Describe the two places in a privatized histogram kernel that need atomicAdd and why each can have competing updates.
- Block Barrier Participation. Explain why placing __syncthreads() on a path reached by only some block threads is unsafe and how to fix it.
- Histogram Counting and Conflicts. Describe the histogram input and output, why bin updates can conflict, and the two remedies summarized here.
What it builds on
- Putting it all together: the complete kernel (chapter 5) · The reduction kernel combines block partial sums into a global result.
- The shared-variable trap: many threads, one counter (chapter 5) · The shared-variable trap when many threads update one counter.
- The last piece: atomic operations (chapter 5) · Atomic operations used to combine reduction results.
- Step 2: Copy host to device (carry the exams to the students) (chapter 2) · Copying data from host to device.
- Beyond addition: max, min, and more (chapter 5) · Maximum as a reduction operation.
- The barrier: __syncthreads() (chapter 5) · The block-wide barrier and shared-memory visibility provided by __syncthreads().
- The global index formula (chapter 3) · The global thread index used as the starting input position.
- Mistake 3: Regular add instead of atomic (chapter 5) · The same race and atomic fix for a single shared result
Section by section
Introduction
This introduction illustrates lost updates in shared results and contrasts them with earlier patterns that reduce write collisions.
- Shared result race conditions: Explain how concurrent updates to a shared result can overwrite work and produce an incorrect count.
Why it matters: This explains why a parallel count can be wrong even when each individual addition is correct. - Collisions across parallel patterns: Distinguish independent per-thread work and the earlier reduction approach from the shared-write problem motivating histograms.
Why it matters: The contrast shows why independent work or a reduction tree does not describe every shared-update problem.
Key terms: race condition, shared result, histogram pattern, reduction, partial sums, collisions
8.1 The conflict problem
This section recaps why concurrent histogram updates can lose counts and how atomic operations prevent that race.
- Concurrent increment race: Explain how concurrent increments can lose an update, including why shared memory does not eliminate the race.
Why it matters: This explains why a histogram can produce incorrect counts even when each thread processes its own element. - Atomic histogram updates: Explain how an atomic increment prevents the lost-update race and contrast the stated atomic needs of histogram and reduction kernels.
Why it matters: Atomic updates protect histogram counts where many threads may increment the same bin.
Key terms: race condition, shared memory, global memory, bin, atomic operation, atomic, histogram, reduction
8.2 One counter, a thousand threads
This section explains how concurrent increments of a shared counter can lose updates and produce an unpredictable count.
- Shared counter race: Trace how two threads incrementing a shared counter can lose an update, and contrast that with sequential execution.
Why it matters: This explains why a seemingly simple parallel counter can give the wrong answer. - Racing counter outcome range: Describe the simple interleaving picture for 1,000 threads incrementing a zeroed counter, including its limits.
Why it matters: The scaled example shows that a race can lose many updates, not just one.
Key terms: read-modify-write, interleave, race condition, shared counter, interleaving, race, counter
8.3 Making read-modify-write indivisible
This section fixes a shared counter with atomic addition and explains how to initialize it on the device.
- Atomic Counter Increment: Explain how atomicAdd replaces the ordinary increment of a shared counter and what arguments it takes.
Why it matters: Atomic addition fixes the shared-counter update while specifying which location to change and by how much. - Atomic Addition Return Value: Explain what atomicAdd returns and how threads incrementing a shared counter can use those return values.
Why it matters: The returned old value can give each thread its own output position. - Device Counter Initialization: Explain why the device counter must start at zero and how this program initializes it.
Why it matters: An atomic increment cannot produce the intended count if the counter starts from garbage.
Key terms: atomic operation, atomicAdd, pointer, old value, output array, hostCount, device, counter
8.4 The CUDA atomic toolkit
This section explains CUDA compare-and-swap, its use in a floating-point maximum, and the performance cost of atomic contention.
- Compare-and-swap behavior: Explain how atomicCAS conditionally replaces a value and how its return value supports retries.
Why it matters: Compare-and-swap lets a thread attempt an update without silently overwriting a concurrent change. - Floating-point maximum with atomicCAS: Describe how the section builds a floating-point maximum from atomicCAS, including the required initialization and treatment of NaN.
Why it matters: This shows how a conditional atomic update can implement a maximum for floats when the built-in operation is unavailable. - Atomic contention and cost: Explain why atomic updates to the same address can slow a histogram and how shared-memory cost and contention affect the design goal.
Why it matters: Correct atomic updates can still become a performance bottleneck when many threads compete for one location. - Integer maximum setup: State the exercise's correct setup for finding an integer array maximum with atomicMax.
Why it matters: A suitable initial value and the right atomic operation are both needed for the maximum exercise.
Key terms: atomicCAS, compare-and-swap, atomicMax, unsigned int, -FLT_MAX, -INFINITY, NaN, atomics, serialize, shared memory
8.5 From one counter to 256 bins
This section defines histogram bins and shows how a single CPU thread counts values without update conflicts.
- Histogram counts and bins: Explain how a histogram counts occurrences using one bin per possible value, including the section’s 0–255 example.
Why it matters: This gives you the basic counting problem that the parallel histogram must solve. - Single thread histogram construction: Describe how the single CPU thread builds the histogram and why its updates do not collide.
Why it matters: The sequential version provides a baseline for understanding the conflicts introduced by parallel updates.
Key terms: histogram, bins, single CPU thread, bin, updates
8.6 Why parallel histograms are hard
This section explains how concurrent updates to the same histogram bin can cause lost counts.
- Concurrent histogram bin conflicts: Explain why parallel histogram updates can lose counts when threads encounter the same pixel value.
Why it matters: This conflict explains why parallel histogram counts can be incorrect.
Key terms: histogram, bins, lost-update problem
8.7 A first fix: global atomics
This section applies global atomic additions to histogram bins and explains how bin contention affects performance.
- Atomic histogram bin updates: Explain how atomicAdd updates a global histogram bin and why the bin's address is passed to it.
Why it matters: Passing the bin's address lets the atomic operation update the intended counter. - Histogram initialization before launch: Describe how to prepare the global histogram before launching the kernel.
Why it matters: Starting the counters at zero ensures they represent counts from the current run. - Bin contention and throughput: Explain how the distribution of values across histogram bins affects the performance of global atomics.
Why it matters: The same correct histogram approach can perform very differently depending on the input distribution.
Key terms: atomicAdd, hist[bin], &hist[bin], cudaMemset, d_hist, global histogram, contention, bin, throughput, global atomics
8.8 A faster fix: privatization in shared memory
This section builds a shared-memory privatized histogram and explains its synchronization, contention benefits, and grid-stride extension.
- Privatized histogram pipeline: Trace how each block initializes a private histogram, tallies input, and merges its counts into the global histogram. Describe how threads divide the bins and why both local and global updates use atomics.
Why it matters: This pipeline turns many competing global updates into block-local counts that can be combined safely. - Barriers between histogram phases: Explain why the kernel synchronizes after initialization and after local tallying, and where those barriers must be placed.
Why it matters: Correct atomic increments alone cannot protect one phase from starting before the previous phase is complete. - Per-bin contention and performance: Explain why privatization can improve histogram performance even when the total number of merge atomics is similar to the original number of global atomics.
Why it matters: The important bottleneck is contention on each bin, not just the total count of atomic operations. - Grid-stride histogram extension: Describe how a grid-stride loop lets each thread tally multiple input elements and how launching fewer blocks can reduce merge contention.
Why it matters: A grid-stride loop handles more inputs than launched threads while allowing fewer block-level merges. - PyTorch histogram operations: Distinguish the section's two PyTorch histogram operations and describe the CUDA ideas they share with the kernel.
Why it matters: These operations connect the histogram pattern to familiar high-level GPU tools.
Key terms: privatization, localHist, shared memory, stride loop, atomicAdd, __syncthreads(), barrier, contention, global atomics, shared memory atomics
8.9 Common mistakes
This section links two shared-update mistakes to missing or unreachable safety guarantees.
- Shared update safety failures: Distinguish the consequences of omitting an atomic increment from those of placing a barrier where only part of a block reaches it.
Why it matters: Recognizing these distinct failures helps you diagnose incorrect counts and hanging kernels.
Key terms: atomic, indivisible, barrier, block
8.10 Mistake 1: Forgetting atomics
This section explains how unprotected histogram updates lose counts and where atomic operations are needed in a privatized kernel.
- Shared Bin Update Race: Explain why plain increments of a shared histogram bin can lose counts and how atomicAdd fixes the race.
Why it matters: This explains why a histogram can produce incorrect, inconsistent counts even when each thread processes its own input. - Privatized Histogram Update Sites: Describe the two places in a privatized histogram kernel that need atomicAdd and why each can have competing updates.
Why it matters: Privatizing the histogram does not eliminate all competing writes, so both stages must protect their updates. - Shared Update Race Detection: Describe how to spot an unprotected shared update and name the forms of protection the section suggests.
Why it matters: This gives you a practical way to recognize similar races beyond the histogram example.
Key terms: read-modify-write, race condition, atomicAdd, bin, privatized kernel, localHist, hist, tally, merge, atomic
8.11 Mistake 2: Conditional __syncthreads() (the deadlock trap)
This section explains conditional barrier failures, offers histogram debugging clues, and recaps how histogram threads cooperate to count values.
- Block Barrier Participation: Explain why placing __syncthreads() on a path reached by only some block threads is unsafe and how to fix it.
Why it matters: Checking barrier participation helps prevent kernels from hanging or producing unpredictable results. - Histogram Debugging Clues: Describe how symptoms suggest missing atomics, a partially reached barrier, or missing initialization, and explain the limits of repeated tests.
Why it matters: Symptoms can narrow down a bug, but a repeatable result does not prove a parallel kernel is race-free. - Histogram Counting and Conflicts: Describe the histogram input and output, why bin updates can conflict, and the two remedies summarized here.
Why it matters: The histogram’s shared counters determine both its correctness challenge and its choice of update strategy.
Key terms: __syncthreads(), barrier, common path, undefined behavior, deadlock, missing atomic, race, initialization, swforces, histogram
8.12 Summary
Where this is used later
- (chapter intro) (chapter 9) · The histogram's potential for write conflicts.
- Where you’ll use the Histogram and Stencil patterns (chapter 9) · A histogram uses bins to count values
- (chapter intro) (chapter 11) · Histogram counts can be accumulated in shared memory.
- Applying the 3-Step Recipe (chapter 11) · Privatization of histogram bins in shared memory.
- Step 2: Synchronize (chapter 12) · The tiled kernel synchronizes its threads after loading tiles.
- Producers and consumers (chapter 11) · The deadlock trap from conditional synchronization.
Concepts explained in this chapter
- histogram patternThe histogram pattern counts input values into corresponding categories or bins, combining contributions that may come from multiple threads.
- privatizationA technique that gives each parallel worker or group of workers a private copy of data, which can be merged after processing.
- atomic operationAn atomic operation performs a read-modify-write or similar memory update as an indivisible action with respect to other threads.
- resource contentionContention occurs when multiple threads compete to access or update the same resource, potentially limiting parallel performance.
- race conditionA race condition is a concurrency error in which unsynchronized reads and writes let one thread overwrite a value before another thread reads it.
- atomicAddatomicAdd is a CUDA atomic operation that adds a value to a memory location without allowing concurrent updates to interfere.
- histogramA histogram is a collection of counts recording how many values fall into each category or bin.
- barrierA barrier is a synchronization mechanism that makes participating threads wait until the required threads reach a specified point.
- __syncthreads()__syncthreads is a CUDA barrier operation that makes threads in one block wait until all threads in that block reach the barrier.
- read-modify-write operationA read-modify-write is an operation sequence that reads a value, computes an update, and writes the result back.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
