liveBook · Manning

Chapter 8: The Histogram pattern

What you will learn in chapter 8 of Grokking GPU Programming

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

What it builds on

Section by section

Introduction

This introduction illustrates lost updates in shared results and contrasts them with earlier patterns that reduce write collisions.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Key terms: __syncthreads(), barrier, common path, undefined behavior, deadlock, missing atomic, race, initialization, swforces, histogram

8.12 Summary

Where this is used later

Concepts explained in this chapter

← Chapter 7: Work-efficient scan: Blelloch Chapter 9: The Stencil pattern →

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.