Reduction is a class of parallel algorithms that pass over O(N) input data and generate an O(1) result computed with a binary associative operator ⊕. The example used in this chapter is summation, with addition serving as the operator, but minimum, maximum, sum of squares, logical AND, logical OR, and the dot product of two vectors are reductions as well. Reduction is also an important primitive used as a subroutine in other operations, such as Scan (Chapter 13).
Since ⊕ is associative, the O(N) operations that compute a reduction may be performed in any order.
\[\sum_{i}^{}a_{i} = a_{0} \oplus a_{1} \oplus a_{2} \oplus a_{3} \oplus a_{4} \oplus a_{5} \oplus a_{6} \oplus a_{7}\]
Figure 12-1 shows some of the ways to reduce an 8-element array.
Figure 12-1. Reduction of 8 elements.
The serial implementation is included for contrast: only one execution unit that can perform ⊕ is needed, but performance is poor because the 7 operations are performed one after another. The parallel implementations perform some of the operations concurrently – 4, then 2, then 1 in this example – and finish in O(lgN) steps, the pattern known as a log-step reduction. As the reduction proceeds, fewer operations can run in parallel, so the algorithm becomes progressively less work-efficient. When ⊕ is addition, the intermediate results are called partial sums, or just partials.
The order in which a thread combines its elements affects performance. Performing ⊕ on adjacent elements, as in the center of Figure 12-1, causes bank conflicts when the partials are held in shared memory, because adjacent threads address the same shared memory banks. Interleaving the accesses – having each thread combine elements a multiple of the block size apart – keeps adjacent threads on different banks and avoids the conflicts.
Modern reductions in CUDA are built from the bottom up: a warp reduces its 32 values with shuffle instructions, a thread block combines its warps’ results through a small amount of shared memory, and a grid combines its blocks’ results with either a second kernel launch or a single global atomic. This chapter follows that progression – warp, then block, then grid – and then optimizes the grid-level reduction until it saturates memory bandwidth, matching the throughput of the reductions in CUB and Thrust.