liveBook · Manning

Chapter 5: The Reduction pattern

What you will learn in chapter 5 of Grokking GPU Programming

This introduction contrasts reduction with Map and illustrates parallel summation through partial sums and pairing rounds.

After this chapter you will be able to

What it builds on

Section by section

Introduction

This introduction contrasts reduction with Map and illustrates parallel summation through partial sums and pairing rounds.

Key terms: Map, Reduction pattern, cooperation, partial sums, subtotal, chunk, parallel reduction, pairs, rounds, subtotals

5.1 A million values, one answer

This section defines reduction as combining a collection into one value using an associative operation.

Key terms: reduction, addition, max, min, multiplication, associative, subtotals, floating-point addition

5.2 You already know reduction

The section connects familiar reductions to identity elements, safe GPU padding, and counting with a map followed by a sum.

Key terms: sum reduction, max reduction, identity element, padding, spare threads, count, map, sum

5.3 Use cases for reduction

This section identifies uses of reduction in software and parallel algorithms and contrasts reduction with scan.

Key terms: reduction, tensor.sum(), histogram computation, Map pattern, Reduction pattern, MapReduce, Scan pattern, running total

5.4 Why naive parallelism fails

The section previews a comparison between sequential reduction and a naive parallel attempt, without yet explaining why the parallel attempt fails.

5.5 The sequential approach

This section explains sequential array summation and why its loop-carried dependency makes straightforward parallelization difficult.

Key terms: running total, loop-carried dependency, sum, reduction, Scan pattern, intermediate result

5.6 The shared-variable trap: many threads, one counter

This section explains why naive shared-counter reduction races, how atomic addition fixes correctness, and why a single atomic counter remains a bottleneck.

Key terms: race condition, read-modify-write, shared variable, atomic operation, atomicAdd, indivisible, global counter, atomic operations, serializing, private slot

5.7 Tree reduction: from concept to code

This section motivates tree reduction as a way to avoid incorrect concurrent writes and a slow single-counter bottleneck.

Key terms: tree reduction, atomic version, single counter

5.8 The tournament analogy

This section explains tree reduction through a tournament analogy, including stride-based pairing, round coordination, and the difference between fewer rounds and actual speedup.

Key terms: tree reduction, max reduction, sum reduction, binary associative operator, stride, round, active threads, warps, consecutive addresses, block

5.9 Where threads share data: shared memory

This section introduces shared memory as a fast, per-block space that enables threads to exchange data for tree reduction.

Key terms: shared memory, block, tree strategy, registers, global memory, data locality, __shared__, CUDA extension

5.10 Building the kernel step by step

This section previews the three acts of building a tree reduction kernel.

5.11 Act 1: Everyone writes on the whiteboard

This section explains how reduction threads stage input in shared memory, pad incomplete blocks, synchronize, and size the shared array safely.

Key terms: global index, global memory, register, shared memory, sdata, tid, __syncthreads(), barrier, idx < n, identity element

5.12 Act 2: The tournament begins

This section traces a shared-memory tree reduction, explains its synchronization, and identifies the block-size constraint of the simple loop.

Key terms: tree reduction, stride, tid, sdata, __syncthreads(), barrier, blockDim.x, power of 2, identity element

5.13 Act 3: Report the block’s result

This section explains how one thread per block safely adds the block’s reduced sum to the global result.

Key terms: sdata[0], thread 0, global result, tid, atomicAdd, race condition

5.14 The barrier: __syncthreads()

This section explains how __syncthreads() acts as a block-wide barrier and why it cannot coordinate different blocks.

Key terms: __syncthreads(), barrier, block, kernel boundary, atomicAdd

5.15 The last piece: atomic operations

This section explains how atomic operations safely combine block subtotals and why tree reduction avoids the performance cost of an atomic update per element.

Key terms: atomicAdd, read-modify-write, global result, __syncthreads(), tree reduction, block, contention, atomic-per-element, memory bandwidth, end-to-end

5.16 Putting it all together: the complete kernel

This section assembles a multi-block integer sum and explains initialization and floating-point reproducibility concerns.

Key terms: multi-block reduction, atomicAdd, two-pass scheme, per-block partials, cudaMemset, d_result, floating-point reductions, associativity, deterministic modes, bit-for-bit reproducibility

5.17 Beyond addition: max, min, and more

This section shows how to adapt a sum reduction to other operations and determine whether an operation fits the reduction approach.

Key terms: combining operation, identity element, atomicMax, atomicMin, associative, commutative, stride-halving tree, cross-block atomic, atomicAdd, block partials

5.18 Reduction in NumPy and PyTorch

5.20 PyTorch

This section relates PyTorch reductions to the CUDA reduction pattern, explains when a custom kernel may be worthwhile, and connects reduction to MPI and OpenMP.

Key terms: tensor.sum(), tensor.max(), hierarchical reduction, per-block partials, identity, custom CUDA kernel, generic dispatched code, fuse, memory round trips, MPI_Allreduce

5.21 Common mistakes

This section identifies unsafe shared-state handling as the common cause of four reduction mistakes that can produce wrong sums.

Key terms: shared state, sdata, global result, atomicAdd

5.22 Mistake 1: Missing __syncthreads()

This section explains how missing synchronization between reduction steps can produce intermittent wrong sums and how to fix it.

Key terms: __syncthreads(), barrier, reduction step, sdata

5.23 Mistake 2: Forgetting to initialize result

This section explains how an uninitialized result corrupts a reduction sum and how to prevent it.

Key terms: cudaMalloc, cudaMemset, result

5.24 Mistake 3: Regular add instead of atomic

This section explains why ordinary addition can lose block contributions in a reduction and how atomicAdd prevents the error.

Key terms: read-modify-write, atomicAdd, race condition

5.25 Mistake 4: Shared memory size mismatch

This section diagnoses shared-memory sizing mismatches and recaps how reduction combines values across cooperating threads.

Key terms: shared memory, blockDim.x, BLOCK_SIZE, extern __shared__, third launch parameter, reduction, associative operation, sum, max, min

5.26 Summary

Where this is used later

Concepts explained in this chapter

← Chapter 4: The Map pattern Chapter 6: The Scan pattern: Hillis-Steele →

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.