Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

A pyramid of crabs on a sandy shore at dusk. 4 crabs on the sand hold up the products 2, 6, 3 and 4. On a rock above them, 2 crabs hold the sums of pairs, 8 and 7. On the highest rock, 1 crab holds the total, 15. A tag reads: pairs, then pairs of pairs.

Chapter 15: Reduction and the Dot Product

The dot product of 2 vectors multiplies the vectors element by element and adds up the products. It is the inner loop of a matrix-vector product, it gives the length of a vector and the angle between 2 vectors, and every iterative solver computes several dot products in each step to decide how far it is from convergence. The multiplications form a map, the pattern of Chapter 14, and they can run in parallel in the same way. The additions cannot be treated in this way. All products must flow into a single number, and the obvious loop adds them one after another, each addition waiting for the one before it. A computation that combines many values into 1 value in this way is called a reduction, and it is the second basic pattern of parallel programming.

In this chapter, we develop the parallel reduction on the dot product of 2 vectors of 16 small integers. We first write the sequential loop and examine its chain of dependent additions. We then use the associativity of addition to regroup the additions into a tree, in which many additions can be performed at the same time. The tree becomes a kernel in which the threads of a block add their values in shared memory, step by step, with a barrier between consecutive steps. We remove a barrier to see the wrong sum that results, and we prove with a loop invariant that the tree is correct when all barriers are present. After that, we replace most of the barriers by warp shuffles, and we compare two ways of combining the sums of different blocks, a second launch and atomic additions. Finally, we implement all designs in Rust with cuda-oxide and in CUDA C++. From the measurements, we explain why the fused kernel runs more than twice as fast as a map followed by a separate reduction, and why atomic additions change the last bits of the result from run to run.

This chapter covers

  • the dot product as a map followed by a reduction, worked by hand on 16 elements
  • the sequential sum and its chain of dependent additions
  • associativity, commutativity and the reduction tree
  • the tree in shared memory: strides, active threads and barriers, step by step
  • a missing barrier and the wrong sum it produces
  • a loop-invariant proof that the tree computes the sum
  • warp shuffles and a block sum with 1 barrier
  • combining the block sums with a second launch or with atomic additions
  • why the order of float additions changes the result
  • measured rates in Rust and C++ against the memory bandwidth

The code of the chapter is in code/oxide/ch15_dot_product/ (Rust) and code/cuda/ch15_dot_product/ (C++). The Rust crate uses the same Cargo.toml and rust-toolchain.toml as Chapter 13.

15.1 The problem

15.1.1 A worked example

We use the same pair of vectors throughout the chapter, so that every number can be checked by hand. Each vector holds 16 small integers.

\[ \begin{aligned} a &= (1, 2, 3, 1, 5, 1, 2, 3,\ 3, 1, 2, 3, 1, 3, 2, 1),\\ b &= (2, 3, 1, 4, 1, 1, 4, 1,\ 1, 2, 2, 2, 1, 3, 1, 4). \end{aligned} \]

As in Chapter 14, we number the positions from 0 and write \(a_i\) for the element of \(a\) at position \(i\), so that \(a_0 = 1\) and \(b_0 = 2\). We multiply the 2 vectors position by position. The first 8 products are \(a_0 b_0 = 1 \cdot 2 = 2\), \(a_1 b_1 = 2 \cdot 3 = 6\), 3, 4, 5, 1, 8 and 3, and they add up to 32. The last 8 products are 3, 2, 4, 6, 1, 9, 2 and 4, and they add up to 31. The dot product is therefore \(32 + 31 = 63\), as shown in Figure 15.1.

The worked example: vectors a = 1, 2, 3, 1, 5, 1, 2, 3, 3, 1, 2, 3, 1, 3, 2, 1 and b = 2, 3, 1, 4, 1, 1, 4, 1, 1, 2, 2, 2, 1, 3, 1, 4. Their products are 2, 6, 3, 4, 5, 1, 8, 3 (sum 32) and 3, 2, 4, 6, 1, 9, 2, 4 (sum 31). The dot product is 63.
Figure 15.1 The worked example. The 16 products add up to \(32 + 31 = 63\).

The example contains 3 numbers that appear again and again in the chapter. The first 8 products add up to 32, the last 8 products add up to 31, and all 16 products add up to 63. Later in the chapter, the GPU splits the work exactly along this line, with one block for each half of the vectors. The faulty kernels of Sections 15.4 and 15.6 then produce 24 instead of 32, and 31 instead of 63.

15.1.2 Definitions

Definition 15.1 Dot product. The dot product of 2 vectors \(a\) and \(b\) of \(n\) elements is

\[ a \cdot b = \sum_{i \in [0, n)} a_i\, b_i . \]

Example. For the vectors above, \(a \cdot b = 2 + 6 + 3 + \cdots + 4 = 63\).

SymbolMeaningIn the example
\(n\)number of elements in each vector16
\(i\)position, from 0 to \(n - 1\)0 to 15
\(a_i, b_i\)elements of \(a\) and \(b\) at position \(i\)\(a_1 = 2\), \(b_1 = 3\)
\(a_i\, b_i\)product at position \(i\)\(a_1 b_1 = 6\)
\(\sum_{i \in [0, n)}\)sum over all positions \(i\) from 0 to \(n - 1\)\(2 + 6 + \cdots + 4\)
\(a \cdot b\)the dot product63

The dot product consists of two parts. The first part computes the products, which we call \(p_i = a_i b_i\), so that \(p_0 = 2\) and \(p_1 = 6\) in our example. The products form a map in the sense of Definition 14.2, since each of them depends only on the elements at position \(i\). The second part, the sum, then combines all \(n\) products into 1 number. A computation of this second kind has a name of its own.

Definition 15.2 Reduction. A reduction combines the \(n\) elements of an array into 1 value with a binary operator \(\oplus\), as \(p_0 \oplus p_1 \oplus \cdots \oplus p_{n-1}\). The identity of the operator is the value \(e\) with \(e \oplus v = v\) for every \(v\).

Example. The sum is a reduction with \(\oplus = +\) and identity 0. The maximum is a reduction with \(\oplus = \max\) and identity \(-\infty\).

The symbol \(\oplus\) stands for any operator that takes 2 values and returns 1 value. For the dot product, \(\oplus\) is ordinary addition, so the reduction is \(p_0 + p_1 + \cdots + p_{15} = 2 + 6 + \cdots + 4 = 63\). The identity is the value that changes nothing when it is combined with another value. For addition, the identity is 0, since \(0 + 6 = 6\). We need the identity later, when a thread that has no value of its own must still contribute something to a reduction.

Exercises

15.1 Compute the dot product of \((1, 0, 2, 3)\) and \((4, 5, 1, 2)\).
15.2 What are the operator and the identity of a reduction that counts the elements of an array that are larger than 10?
15.3 In the worked example, which position contributes the largest product, and how much does it contribute?

15.2 The sequential algorithm

15.2.1 The loop and its chain

On a CPU, Definition 15.1 becomes a single loop that keeps a running sum \(\mathsf{sum}\) and adds 1 product to it in each iteration.

Dot(\(a, b, n\))

  1. \(\mathsf{sum} = 0\)
  2. for \(i \in [0, n)\) {
  3. \(\mathsf{sum} = \mathsf{sum} + a_i \cdot b_i\) // 2 reads, 2 FLOP
  4. }
  5. return \(\mathsf{sum}\)

Line 3 executes \(n\) times. Each time, it reads 2 floats, which is 8 bytes, and performs 2 FLOP, 1 multiplication and 1 addition. Our example therefore performs 32 FLOP on 128 bytes. The vectors that we measure at the end of the chapter have \(n = 2^{24}\) elements, and for them the loop performs 33.6 million FLOP on 134.2 MB.

Recall that in the loop of SAXPY in Chapter 14, the iterations shared nothing. This loop is different. Iteration \(i\) reads \(\mathsf{sum}\), which iteration \(i - 1\) wrote, so it cannot start before iteration \(i - 1\) has finished. In our example, the running sum takes the values 2, 8, 11, 15, 20, 21, 29, 32, 35, 37, 41, 47, 48, 57, 59 and 63, and each of these values is obtained from the one before it, as shown in Figure 15.2. For example, the value 11 after iteration 2 is \(8 + 3\), and it could not be computed before the 8 was known. The 16 multiplications are independent of each other, but the 16 additions form a chain of 16 steps. As long as the additions are performed in this order, no number of threads can shorten the chain.

The sequential sum of the 16 products. The running sums are 2, 8, 11, 15, 20, 21, 29, 32, 35, 37, 41, 47, 48, 57, 59, 63, each joined to the next: 16 additions in a chain of 16 steps.
Figure 15.2 The running sum of Dot: each addition needs the result of the one before, a chain of 16 steps.

15.2.2 Regrouping the additions

Note, however, that the order of the chain is a choice that the loop makes, not a property of the sum. The sum \(2 + 6 + 3 + 4\) can also be computed as \((2 + 6) + (3 + 4) = 8 + 7 = 15\), and in this form the 2 additions inside the parentheses do not depend on each other. Addition has 2 properties that allow this and any other order.

Definition 15.3 Associative and commutative operators. An operator \(\oplus\) is associative if \((u \oplus v) \oplus w = u \oplus (v \oplus w)\) for all values, so that the parentheses of a long expression may be placed anywhere. It is commutative if \(u \oplus v = v \oplus u\), so that the operands may be reordered.

Example. Integer addition is both: \((2 + 6) + 3 = 2 + (6 + 3) = 11\) and \(2 + 6 = 6 + 2\). Subtraction is neither: \((2 - 6) - 3 = -7\), but \(2 - (6 - 3) = -1\).

Associativity lets us add the 16 products in pairs, then add the sums of the pairs in pairs, and continue in this way until 1 value remains, as shown in Figure 15.3. The first step adds 8 independent pairs, from \(2 + 6 = 8\) and \(3 + 4 = 7\) to \(2 + 4 = 6\). The second step adds 4 pairs of these sums, the third step adds 2 pairs, and the fourth step adds \(32 + 31 = 63\). The tree performs \(8 + 4 + 2 + 1 = 15\) additions, which is as many as the chain needs after its first addition to 0. It performs them, however, in 4 steps instead of 16, because the additions within each step are independent of each other.

The 16 products regrouped in pairs. Step 1 makes 8, 7, 6, 11, 5, 10, 10, 6; step 2 makes 15, 17, 15, 16; step 3 makes 32 and 31; step 4 makes 63. 15 additions in 4 steps.
Figure 15.3 The 16 products added in pairs: 15 additions in 4 steps.

In general, a tree reduces \(n\) values with \(n - 1\) operations. Every step halves the number of values, so the number of steps is the number of times that \(n\) can be halved before 1 value remains. This number is \(\log_2 n\), rounded up when \(n\) is not a power of 2, which we write \(\lceil \log_2 n \rceil\). For our 16 products, \(\log_2 16 = 4\), since 16 halves to 8, 4, 2 and 1 in 4 steps. For \(n = 2^{24}\), the chain is 16,777,216 steps long, while the tree is only 24 steps deep.

Key observation Because addition is associative and commutative, the 16 products may be added in any grouping. Added in pairs, then in pairs of pairs, they need 4 steps instead of 16, and the additions within each step are independent, so a different thread can perform each of them.

Floating-point addition is associative only approximately, because every addition rounds its result. In Section 15.6.3, we show what this changes. Until then, we work with the exact integers of the example.

Exercises

15.4 Draw the tree for the 8 values \(4, 1, 3, 5, 2, 2, 6, 1\). How many additions and how many steps does it take?
15.5 How many steps does a tree need for \(n = 1{,}000\) values? Explain the rounding up.
15.6 The maximum is associative and commutative. Run the tree of Figure 15.3 with \(\max\) in place of \(+\).

15.3 A tree in shared memory

15.3.1 What the threads of a block need

Suppose that we give each addition of the tree to its own thread. In the second step, for example, some thread must add the sums 8 and 7, which were computed in the first step by 2 other threads. Each addition therefore combines 2 values that 2 different threads produced in the step before. The threads must exchange values, and a thread must know when the value that it needs is ready. Recall from Definition 14.4 that a block provides both: a memory that all of its threads can read and write, and a way for its threads to wait for one another.

Definition 15.4 Shared memory. Shared memory is a small memory on each SM, typically 48 KB to 228 KB, that the threads of 1 block can all read and write and no other thread can access. It responds within a few cycles. Each block receives its own copy of every shared array, which exists from the start of the block to its end and starts with undefined contents.

Example. Block 0 of our example holds its 8 products in a shared array cells of 8 floats; block 1 has its own cells.

Definition 15.5 Barrier. A barrier is a point in a kernel that no thread of a block may pass until every thread of the block has reached it. All writes to shared memory made before the barrier are visible to every thread of the block after it. In CUDA C++, the barrier is __syncthreads(), and in cuda-oxide, it is thread::sync_threads().

Example. After a barrier, thread 0 of block 0 can read the product that thread 4 stored before the barrier.

15.3.2 Which cells a thread adds

We now place the values of a block in a shared array, 1 value per thread, and call the elements of this array cells. In block 0 of our example, cell \(k\) holds the product \(p_k\), so the 8 cells hold 2, 6, 3, 4, 5, 1, 8 and 3. The tree of Figure 15.3 adds neighboring cells: cells 0 and 1, cells 2 and 3, cells 4 and 5, and cells 6 and 7. On a GPU, we prefer a different pairing, in which the 2 cells of a pair lie a fixed distance apart. We call this distance the stride. Recall that \(\mathsf{threadIdx{.}x}\) is the position of a thread in its block. In a step with a given \(\mathsf{stride}\), we let every thread whose \(\mathsf{threadIdx{.}x}\) is smaller than \(\mathsf{stride}\) add cell \(\mathsf{threadIdx{.}x} + \mathsf{stride}\) into its own cell, \(\mathsf{threadIdx{.}x}\). With 8 cells, the strides are 4, 2 and 1. In the first step, with \(\mathsf{stride} = 4\), threads 0 to 3 add cells 4 to 7 into cells 0 to 3. For example, thread 2 adds cell \(2 + 4 = 6\) into cell 2. In the second step, with \(\mathsf{stride} = 2\), threads 0 and 1 add cells 2 and 3 into cells 0 and 1. In the third step, with \(\mathsf{stride} = 1\), thread 0 adds cell 1 into cell 0.

SymbolMeaningThread 2, first step of block 0
\(\mathsf{stride}\)stride: distance between the 2 cells of a pair, and number of working threads4
\(\mathsf{threadIdx{.}x}\)index of the thread in its block, which works only if \(\mathsf{threadIdx{.}x} < \mathsf{stride}\)2
\(\mathsf{threadIdx{.}x} + \mathsf{stride}\)cell that the thread reads and adds into its own cell6

The stride pairing adds \(p_0 + p_4\) where Figure 15.3 added \(p_0 + p_1\), so it relies on commutativity as well as on associativity. In return, the threads that work in each step are always the lowest \(\mathsf{stride}\) threads, 0 to \(\mathsf{stride} - 1\), and they read the neighboring cells \(\mathsf{stride}\) to \(2\,\mathsf{stride} - 1\). This has 2 advantages in a block of 256 threads. In the first steps, whole warps are busy and whole warps are idle, instead of half the threads of every warp being idle, and the cells that a warp reads at once are neighbors in memory.

In Figure 15.4, we run this pairing in block 0 of the example. The 8 cells start with the products 2, 6, 3, 4, 5, 1, 8 and 3. With \(\mathsf{stride} = 4\), threads 0 to 3 compute \(2 + 5 = 7\), \(6 + 1 = 7\), \(3 + 8 = 11\) and \(4 + 3 = 7\). With \(\mathsf{stride} = 2\), threads 0 and 1 compute \(7 + 11 = 18\) and \(7 + 7 = 14\). With \(\mathsf{stride} = 1\), thread 0 computes \(18 + 14 = 32\). In the same way, block 1 computes 4, 11, 6 and 10 in the first step, 10 and 21 in the second, and 31 in the third.

The tree in the shared memory of block 0. The 8 cells start as 2, 6, 3, 4, 5, 1, 8, 3. With s = 4, threads 0 to 3 add cell t + 4 into cell t, giving 7, 7, 11, 7. With s = 2, threads 0 and 1 give 18 and 14. With s = 1, thread 0 gives 32. A barrier separates the steps; cells no longer read are gray.
Figure 15.4 The tree in the shared memory of block 0. Each color is 1 thread; a barrier separates the steps.

15.3.3 The algorithm

In our example, each block has 8 threads, and each thread holds exactly 1 product. A real block, however, has \(\mathsf{blockDim{.}x} = 256\) threads, and a real vector has millions of elements, many more than the threads of the grid. Each thread therefore begins with the grid-stride loop of Chapter 14. It multiplies the elements \(\mathsf{index}, \mathsf{index} + \mathsf{gridSize}, \mathsf{index} + 2\,\mathsf{gridSize}, \ldots\) of the 2 vectors and adds the products in a register, where \(\mathsf{index}\) starts at the thread’s global index and \(\mathsf{gridSize}\) is the number of threads in the grid. The products are never stored in memory. The tree then combines the \(\mathsf{blockDim{.}x}\) register sums of the block, and thread 0 writes the block’s sum to a partial sum array, which holds one element per block. Every thread executes the following procedure, in which cells is a shared array of \(\mathsf{blockDim{.}x}\) floats and \(\mathsf{mySum}\) is the thread’s register sum.

Dot-Block(\(a, b, \mathsf{partial}, n\))

  1. \(\mathsf{index} = \mathsf{blockIdx{.}x} \times \mathsf{blockDim{.}x} + \mathsf{threadIdx{.}x}\) // first element
  2. \(\mathsf{gridSize} = \mathsf{gridDim{.}x} \times \mathsf{blockDim{.}x}\) // threads in the grid
  3. \(\mathsf{mySum} = 0\)
  4. while \(\mathsf{index} \lt n\) { // the grid-stride loop of Chapter 14
  5. \(\mathsf{mySum} = \mathsf{mySum} + a_{\mathsf{index}} \times b_{\mathsf{index}}\)
  6. \(\mathsf{index} = \mathsf{index} + \mathsf{gridSize}\)
  7. }
  8. \(\mathsf{cells}[\mathsf{threadIdx{.}x}] = \mathsf{mySum}\)
  9. Barrier() // every cell holds its value
  10. for \(\mathsf{stride} = \mathsf{blockDim{.}x}/2, \mathsf{blockDim{.}x}/4, \ldots, 1\) {
  11. if \(\mathsf{threadIdx{.}x} \lt \mathsf{stride}\) {
  12. \(\mathsf{cells}[\mathsf{threadIdx{.}x}] = \mathsf{cells}[\mathsf{threadIdx{.}x}] + \mathsf{cells}[\mathsf{threadIdx{.}x} + \mathsf{stride}]\)
  13. }
  14. Barrier() // this step is complete
  15. }
  16. if \(\mathsf{threadIdx{.}x} = 0\) {
  17. \(\mathsf{partial}[\mathsf{blockIdx{.}x}] = \mathsf{cells}[0]\)
  18. }
SymbolMeaningThread 2 of block 0, example
\(\mathsf{blockDim{.}x}\)number of threads in a block8 (256 in the measured program)
\(\mathsf{threadIdx{.}x}\)index of the thread in its block (threadIdx.x)2
\(\mathsf{index}\)element the thread processes next; starts at its global index2
\(\mathsf{gridSize}\)number of threads in the grid, and the distance from one of the thread’s elements to the next\(2 \cdot 8 = 16\)
\(\mathsf{mySum}\)the thread’s register sum\(a_2 b_2 = 3\)
\(\mathsf{stride}\)stride of the current step of the tree4, 2, 1

Lines 1 to 7 compute the thread’s register sum. On the example, launched with 2 blocks of 8 threads, \(\mathsf{gridSize} = 16 = n\), so the loop runs once, and \(\mathsf{mySum}\) is the thread’s single product. For instance, thread 2 of block 0 sets \(\mathsf{mySum} = a_2 b_2 = 3 \cdot 1 = 3\) and then leaves the loop, since \(2 + 16 = 18 \ge 16\). Line 8 stores the sum in the thread’s own cell, and the barrier of line 9 waits until all \(\mathsf{blockDim{.}x}\) cells are filled. Lines 10 to 15 are the tree of Figure 15.4, with a barrier after every step, and lines 16 to 18 write the block’s sum. On the example, block 0 writes 32 into partial[0], and block 1 writes 31 into partial[1]. In Section 15.6, we add the partial sums.

Note that lines 9 and 14 lie outside every if. The barrier of line 14 is therefore executed by all \(\mathsf{blockDim{.}x}\) threads in every step, including the threads with \(\mathsf{threadIdx{.}x} \ge \mathsf{stride}\), which have nothing to add.

15.3.4 Counting

Let us count the work of the tree. A block of \(\mathsf{blockDim{.}x}\) threads performs \(\mathsf{blockDim{.}x} - 1\) additions in its tree, in \(\log_2 \mathsf{blockDim{.}x}\) steps, with \(\log_2 \mathsf{blockDim{.}x} + 1\) barriers: 1 barrier in line 9 and 1 barrier after each step. For our block of 8 threads, this is 7 additions in 3 steps, with 4 barriers. For \(\mathsf{blockDim{.}x} = 256\), it is 255 additions in 8 steps, with 9 barriers. The number of working threads halves in every step, from 128 through 64, 32, 16, 8, 4 and 2 to 1. In the last 5 steps, at most 16 threads work, all of them in warp 0, and the other 7 warps wait at the barrier.

The cost of the tree is paid once per block, not once per element. With a grid of 1,024 blocks of 256 threads, \(\mathsf{gridSize} = 262{,}144\), and each thread adds \(2^{24} / 262{,}144 = 64\) products in lines 4 to 7 before the tree begins. The kernel reads every element of \(a\) and \(b\) exactly once, which is 8 bytes per element, and it performs 2 FLOP per element. Its arithmetic intensity is therefore \(2 / 8 = 0.25\) FLOP/B, far below the ridge point of any GPU (Section 14.6). Like SAXPY, the dot product is memory-bound.

Exercises

15.7 Run Figure 15.4 for block 1, whose cells start with 3, 2, 4, 6, 1, 9, 2, 4. Which threads work in each step, and what does each compute?
15.8 For \(\mathsf{blockDim{.}x} = 512\), how many steps, additions and barriers does the tree take?
15.9 With 1,024 blocks of 256 threads and \(n = 10^6\), how many products does thread 0 add in lines 4 to 7, and how many does thread 262,143 add?

15.4 Correctness

The threads of a block run at different speeds, and they read cells that other threads write. As a result, 2 things can go wrong. A thread can read a cell before the thread responsible for it has written the value of the current step, and a thread can overwrite a cell that another thread has not yet read. The 2 barriers prevent both errors. In this section, we remove the barrier of line 14 and follow the effect on the example, and we then prove that the kernel with both barriers is correct.

15.4.1 Without the barrier between the steps

Suppose that line 14 is deleted, and that in block 0, thread 2 runs late. Thread 0 finishes its addition for \(\mathsf{stride} = 4\), which is \(2 + 5 = 7\), and moves on to \(\mathsf{stride} = 2\), where it needs cell 2. Thread 2 should have stored \(3 + 8 = 11\) there, but it has not yet done so, and cell 2 still holds the product 3, as shown in Figure 15.5. Thread 0 therefore computes \(7 + 3 = 10\) instead of 18, and in the last step, it computes \(10 + 14 = 24\) instead of 32.

Without the barrier after step s = 4. Thread 0 finishes s = 4 early and in step s = 2 reads cell 2 while it still holds 3, because thread 2 has not yet stored 3 + 8 = 11. Cell 0 becomes 7 + 3 = 10 in place of 18, and the block sum 10 + 14 = 24 in place of 32.
Figure 15.5 Without the barrier of line 14, thread 0 reads cell 2 before thread 2 has updated it. Block 0 sums to 24 in place of 32.

We deleted the barrier from both programs and ran them. The C++ build also contained the faulty plain addition of Section 15.6.2, which affects only the last column of the output. The C++ program printed the following lines.

exact tests                   map+red      tree   shuffle    atomic
  worked example, 16 pairs          63        26        63        63   expected 63
  0s and 1s, 16777216 pairs    2796203    760424   2796203    338598   expected 2796203

The column tree holds the results of the kernel without the barrier, 26 instead of 63 for the worked example. The Rust program returned 36 for the worked example and 778,180 for the second test. On \(2^{24}\) floats in \([0, 1)\), the tree returned 920,497.0 (C++) and 1,159,452.9 (Rust) instead of 4,195,680.0, and a second run gave different wrong values, 756,503 and 778,042, for the second test. The program runs the example on the real block of 256 threads, so the precise wrong value differs from the 24 of Figure 15.5. Without the barrier, nothing orders the store of 1 step before the loads of the next step. The warps of a block reach each step at different times, and the compiler may also load a cell earlier than the program text suggests, because it assumes that no other thread changes the cell in between. Every wrong value has the same cause as the wrong value in Figure 15.5.

The barrier of line 9 protects the first step in the same way. Without it, thread 0 could add cell 4 before thread 4 has stored its sum there, and it would then add whatever the undefined shared memory held.

15.4.2 A proof that the tree is correct

With both barriers in place, the tree computes the block’s sum. To prove this, we follow which products each cell holds at the start of every step, as shown in Figure 15.6. At the start of the step with stride \(\mathsf{stride} = 4\), cell 0 holds \(p_0\). At the start of the step with \(\mathsf{stride} = 2\), it holds \(p_0 + p_4\), and at the start of the step with \(\mathsf{stride} = 1\), it holds \(p_0 + p_2 + p_4 + p_6\). After the last step, it holds all 8 products. We can describe this pattern with remainders. At the start of the step with stride \(\mathsf{stride}\), cell \(k\) holds the products whose index \(j\) leaves the remainder \(k\) when divided by \(2\,\mathsf{stride}\). For example, at the start of the step with \(\mathsf{stride} = 2\), we have \(2\,\mathsf{stride} = 4\), and the indices 0 and 4 are exactly the indices below 8 that leave the remainder 0 when divided by 4, so cell 0 holds \(p_0 + p_4 = 2 + 5 = 7\).

The loop invariant for cell 0 of block 0. At the start of step s = 4 it holds p0 = 2; of s = 2, p0 + p4 = 7; of s = 1, p0 + p2 + p4 + p6 = 18; after s = 1, all 8 products, 32.
Figure 15.6 The loop invariant for cell 0 of block 0: at the start of the step with stride \(\mathsf{stride}\), it holds the products with index \(j \equiv 0 \pmod{2\,\mathsf{stride}}\).

We write \(j \equiv k \pmod{2\,\mathsf{stride}}\), read “\(j\) is congruent to \(k\) modulo \(2\,\mathsf{stride}\)”, when \(j\) and \(k\) leave the same remainder when divided by \(2\,\mathsf{stride}\). For example, \(6 \equiv 2 \pmod{4}\), since both 6 and 2 leave the remainder 2 when divided by 4. The theorem and its proof use this notation.

Theorem 15.1 Let \(\mathsf{blockDim{.}x}\) be a power of 2 and let \(v_j\) be the value that thread \(j\) of a block stores in line 8 of Dot-Block. When the loop of lines 10 to 15 finishes, \(\mathsf{cells}[0] = \sum_{j \in [0, \mathsf{blockDim{.}x})} v_j\).

Proof. We show that the loop maintains the following invariant: at the start of the iteration with stride \(\mathsf{stride}\), for every \(k \in [0, 2\,\mathsf{stride})\),

\[ \mathsf{cells}[k] = \sum_{j \in [0, B),\ j \equiv k \ (\mathrm{mod}\ 2s)} v_j . \]

SymbolMeaningBlock 0 of the example, \(\mathsf{stride} = 2\), \(k = 1\)
\(\mathsf{blockDim{.}x}\)number of threads, and cells, in the block8
\(v_j\)value stored by thread \(j\) in line 8\(v_1 = 6\), \(v_5 = 1\)
\(\mathsf{stride}\)stride of the current iteration2
\(k\)a cell that is still read, \(k < 2\,\mathsf{stride}\)1
\(j \equiv k \pmod{2\,\mathsf{stride}}\)\(j\) leaves the remainder \(k\) when divided by \(2\,\mathsf{stride}\)\(j = 1, 5\)
\(\mathsf{cells}[k]\)content of cell \(k\) at the start of the iteration\(6 + 1 = 7\)

In words, at the start of each iteration, the first \(2\,\mathsf{stride}\) cells together hold all \(\mathsf{blockDim{.}x}\) values, and cell \(k\) holds those values whose index leaves the remainder \(k\). In Figure 15.4, at the start of the step with \(\mathsf{stride} = 2\), cell 1 indeed holds \(6 + 1 = 7\), the sum of \(v_1\) and \(v_5\).

Initialization. The first iteration has \(\mathsf{stride} = \mathsf{blockDim{.}x}/2\), so \(2\,\mathsf{stride} = \mathsf{blockDim{.}x}\), and the only \(j \in [0, \mathsf{blockDim{.}x})\) with \(j \equiv k \pmod{\mathsf{blockDim{.}x}}\) is \(k\) itself. The sum in the invariant therefore consists of the single value \(v_k\). Line 8 stored \(v_k\) in \(\mathsf{cells}[k]\), and the barrier of line 9 makes every one of these stores complete before any thread reads a cell in line 12. The invariant therefore holds.

Maintenance. Assume that the invariant holds at the start of the iteration with stride \(\mathsf{stride}\). In line 12, each thread \(\mathsf{threadIdx{.}x} < \mathsf{stride}\) reads cells \(\mathsf{threadIdx{.}x}\) and \(\mathsf{threadIdx{.}x} + \mathsf{stride}\) and writes cell \(\mathsf{threadIdx{.}x}\). The cells written, \([0, \mathsf{stride})\), and the cells that are only read, \([\mathsf{stride}, 2\,\mathsf{stride})\), do not overlap, and each cell of \([0, \mathsf{stride})\) is written by exactly 1 thread. Hence, no read in this iteration sees a write of this iteration, except the thread’s own. After line 12, for \(\mathsf{threadIdx{.}x} < \mathsf{stride}\), cell \(\mathsf{threadIdx{.}x}\) holds the sum over \(j \equiv \mathsf{threadIdx{.}x} \pmod{2\,\mathsf{stride}}\) plus the sum over \(j \equiv \mathsf{threadIdx{.}x} + \mathsf{stride} \pmod{2\,\mathsf{stride}}\). An index \(j\) belongs to one of these 2 groups exactly when it leaves the remainder \(\mathsf{threadIdx{.}x}\) when divided by \(\mathsf{stride}\), so the 2 sums together are the sum over \(j \equiv \mathsf{threadIdx{.}x} \pmod{\mathsf{stride}}\). For example, with \(\mathsf{stride} = 2\) and \(\mathsf{threadIdx{.}x} = 1\), cell 1 holds \(v_1 + v_5\) and cell 3 holds \(v_3 + v_7\), and their sum is the sum over the odd \(j\), that is, over \(j \equiv 1 \pmod{2}\). The barrier of line 14 makes these writes complete before any thread starts the next iteration. That iteration has the stride \(\mathsf{stride}/2\), and \(2 \cdot (\mathsf{stride}/2) = \mathsf{stride}\), so the invariant holds for the next iteration.

Termination. After the iteration with \(\mathsf{stride} = 1\), the maintenance step shows that cell 0 holds the sum over \(j \equiv 0 \pmod{1}\). Every integer leaves the remainder 0 when divided by 1, so this is the sum over all \(j \in [0, \mathsf{blockDim{.}x})\).

The proof uses each barrier once, the barrier of line 9 in the initialization and the barrier of line 14 in the maintenance. Removing either barrier breaks exactly the step of the proof that uses it, and in Section 15.4.1, we saw the wrong value that follows.

Rule Every thread of a block must reach every barrier. Never place a barrier inside a branch that only some threads of the block take, such as the if of line 11.

A barrier inside if t < s would be reached by \(\mathsf{stride}\) threads but awaited by all \(\mathsf{blockDim{.}x}\) threads. The behavior of such a kernel is undefined, and in practice, it hangs or returns wrong values.

15.4.3 Shared memory in Rust

In cuda-oxide, a shared array is a static mut of type SharedArray<f32, 256> declared inside the kernel. Rust requires an unsafe block for every access to a static mut, because the compiler cannot prove that 2 threads do not access it at the same time. If we write the store of line 8 without the block, the build stops with the following error.

$ cargo oxide build
error[E0133]: use of mutable static is unsafe and requires unsafe block
   --> src/main.rs:117:9
    |
117 |         CELLS[t] = products(a, b);
    |         ^^^^^ use of mutable static
    |
    = note: mutable statics can be mutated by multiple threads: aliasing violations or data races will cause undefined behavior

The program’s // SAFETY: comments state the two facts that the proof of Theorem 15.1 uses. The first is that each thread writes only its own cell before the barrier of line 9. The second is that in each step, each working thread alone writes its own cell and reads cell \(\mathsf{threadIdx{.}x} + \mathsf{stride}\), which no thread writes in that step. The compiler accepts the program without the barrier as well, because the unsafe blocks are still there, and only the argument in their comments is then false.

Exercises

15.10 Without the barrier of line 14, suppose thread 1 of block 1 runs late in step \(\mathsf{stride} = 4\). Which cell does thread 0 read too early in step \(\mathsf{stride} = 2\), and what block sum results?
15.11 In the proof of Theorem 15.1, where is it used that \(\mathsf{blockDim{.}x}\) is a power of 2? What goes wrong for \(\mathsf{blockDim{.}x} = 6\)?
15.12 Explain why moving the barrier of line 14 inside the if of line 11 can make the kernel hang.

15.5 Warp shuffles

15.5.1 Exchanging registers within a warp

Recall from Section 15.3.4 that the last 5 steps of the tree in a block of 256 threads run with 16, 8, 4, 2 and 1 working threads, all of them in warp 0. Each of these steps nevertheless ends with a barrier for the whole block, at which 7 idle warps wait. The threads of 1 warp, however, can exchange values without shared memory and without a barrier.

Definition 15.6 Warp shuffle. A warp shuffle is an instruction with which every lane of a warp (Definition 14.6) reads a register of another lane of the same warp. In the form shuffle down with offset \(\mathsf{distance}\), lane \(k\) receives the value that lane \(k + \mathsf{distance}\) holds; a lane with \(k + \mathsf{distance} \ge 32\) receives its own value. All lanes named in the instruction’s mask execute it together, so the values are exchanged without a barrier.

Example. With offset 4, lane 0 receives the value of lane 4, and lane 3 the value of lane 7.

A shuffle closely resembles a step of the tree. In a tree step, each working thread adds cell \(\mathsf{threadIdx{.}x} + \mathsf{stride}\) into its own cell. A shuffle-down by \(\mathsf{distance}\), followed by an addition, lets each lane add the register of the lane \(\mathsf{distance}\) places to its right into its own register, which is the same step with registers in place of cells and \(\mathsf{distance}\) in place of \(\mathsf{stride}\). A sequence of shuffles with offsets 16, 8, 4, 2 and 1, each followed by an addition, is therefore the tree of Section 15.3 inside 1 warp. In Figure 15.7, we draw it on 8 lanes with the products of block 0, so that only the last 3 of the 5 steps, with offsets 4, 2 and 1, are needed. The registers take the same values as the cells of Figure 15.4: 7, 7, 11 and 7 after offset 4, then 18 and 14, and finally 32.

A warp sum by shuffles, drawn on 8 lanes. The registers start as 2, 6, 3, 4, 5, 1, 8, 3. With offset 4, lanes 0 to 3 add the values of lanes 4 to 7: 7, 7, 11, 7. With offset 2: 18, 14. With offset 1: lane 0 holds 32. The same numbers as the tree in shared memory, with no shared memory and no barrier.
Figure 15.7 A warp sum by shuffles, drawn on 8 lanes with the products of block 0. The values are those of Figure 15.4.

Warp-Sum(\(\mathsf{value}\))

  1. for \(\mathsf{distance} = 16, 8, 4, 2, 1\) {
  2. \(\mathsf{value} = \mathsf{value} + \) Shuffle-Down\((\mathsf{value}, \mathsf{distance})\) // lane k adds lane k + distance
  3. }
  4. return \(\mathsf{value}\) // the sum of the warp, in lane 0

15.5.2 A block sum with 1 barrier

A shuffle reaches only the lanes of its own warp, so Warp-Sum alone cannot add the values of a whole block. A block of 256 threads consists of 8 warps. Each warp first reduces its 32 values with Warp-Sum, and lane 0 of each warp stores the warp’s sum in 1 of 8 shared slots, called \(\mathsf{warps}[0]\) to \(\mathsf{warps}[7]\). A single barrier makes the 8 sums visible to all threads, and warp 0 then reduces them with a second Warp-Sum, as shown in Figure 15.8. In the procedure below, \(\mathsf{lane}\) is the position of the thread within its warp and \(\mathsf{warpIndex}\) is the number of its warp. For example, thread 70 of the block has \(\mathsf{lane} = 70 \bmod 32 = 6\) and \(w = \lfloor 70 / 32 \rfloor = 2\), where \(\lfloor \cdot \rfloor\) rounds down.

Block-Sum(\(\mathsf{mySum}\))

  1. \(\mathsf{lane} = \mathsf{threadIdx{.}x} \bmod 32\) // position in the warp
  2. \(\mathsf{warpIndex} = \lfloor \mathsf{threadIdx{.}x} / 32 \rfloor\) // warp number in the block
  3. \(\mathsf{warpTotal} = \) Warp-Sum\((\mathsf{mySum})\)
  4. if \(\mathsf{lane} = 0\) {
  5. \(\mathsf{warpSums}[\mathsf{warpIndex}] = \mathsf{warpTotal}\)
  6. }
  7. Barrier()
  8. if \(\mathsf{warpIndex} \ne 0\) {
  9. return 0 // only warp 0 finishes the sum
  10. }
  11. \(\mathsf{value} = \mathsf{warpSums}[\mathsf{lane}]\) if \(\mathsf{lane} \lt 8\), else 0
  12. return Warp-Sum\((\mathsf{value})\) // the block sum, in thread 0
The block sum with shuffles. Each of the 8 warps of a 256-thread block sums its 32 values with 5 shuffles, and lane 0 stores the warp sum in w[0] to w[7] in shared memory. After 1 barrier, warp 0 reads the 8 values and sums them with 5 more shuffles; thread 0 holds the block sum.
Figure 15.8 The block sum: 5 shuffles in every warp, 1 barrier, 5 shuffles in warp 0.

In line 11, lanes 8 to 31 of warp 0 contribute 0, the identity of addition, so the second Warp-Sum adds exactly the 8 warp sums. Only warp 0 calls Warp-Sum the second time, and all 32 of its lanes do so, as the shuffle requires. Compared with the tree of Section 15.3, Block-Sum uses 1 barrier instead of 9, and 8 floats of shared memory instead of 256. A fused kernel with shuffles computes the register sum \(\mathsf{mySum}\) with lines 1 to 7 of Dot-Block, and it replaces lines 8 to 15 by \(\mathsf{mySum} = \) Block-Sum\((\mathsf{mySum})\).

Exercises

15.13 In Warp-Sum on 32 lanes holding the values 0 to 31, what does lane 0 hold after each of the 5 steps?
15.14 Why may lines 11 and 12 of Block-Sum not read warpSums before the barrier of line 7?

15.6 Combining the block results

15.6.1 A second launch

After Dot-Block has run on the example, partial[0] = 32 and partial[1] = 31. The 2 numbers were computed by different blocks, and the threads of different blocks can share neither a barrier nor shared memory. In fact, the blocks of a large grid do not even run at the same time. The end of a kernel, however, is a point that every block has passed. A second kernel launched on the same stream starts only after the first kernel has finished, so it sees every partial sum. We therefore launch a sum kernel with 1 block, which adds the partial sums with the same grid-stride loop and block sum. On the example, it computes \(32 + 31 = 63\), as shown on the left of Figure 15.9.

15.6.2 Atomic additions

The second launch can be avoided if every block adds its sum directly into the result. This requires an addition that no other thread can interrupt.

Definition 15.7 Atomic operation. An atomic operation is a read-modify-write of 1 memory location that executes as 1 indivisible step. No other thread can access the location between the read and the write. atomicAdd(p, v) in C++ and fetch_add(v, ...) on a DeviceAtomicF32 in Rust add \(\mathsf{mySum}\) to the value at \(p\) atomically.

Example. If block 1 finishes first, it atomically changes the result from 0 to 31, and block 0 then changes it from 31 to 63.

Figure 15.9 compares the two methods. With the second launch, the 2 partial sums are added in an order that the program fixes. With atomic additions, they are added in the order in which the blocks finish, and this order changes from run to run.

2 ways to combine the block sums 32 and 31. Left: each block writes its partial sum, and a second kernel, which starts after every block of the first is done, adds them in a fixed order: 63. Right: each block adds its sum into result with an atomic addition, in the order the blocks finish, here block 1 then block 0: 0, 31, 63.
Figure 15.9 Left: a second launch adds the partial sums in a fixed order. Right: atomic additions add them in the order the blocks finish.

The addition must be atomic. With an ordinary *result += total, a block reads the result, adds its sum and writes the result back, in 3 separate steps. Suppose that block 0 and block 1 both read 0 before either of them writes. Block 0 then writes \(0 + 32 = 32\), block 1 writes \(0 + 31 = 31\), and the later write wins, so the result is 31 instead of 63, as shown in Figure 15.10.

A plain addition in place of an atomic one. Block 0 reads result = 0, then block 1 reads 0. Block 0 writes 32, and block 1 later writes 0 + 31. The result is 31 in place of 63.
Figure 15.10 With a plain addition, both blocks read 0 and the later write wins: 31 in place of 63.

We replaced atomicAdd(result, total) by *result += total in the C++ program. The 0-and-1 test returned 338,598 instead of 2,796,203, and the dot product of the random floats returned 100 different values in 100 runs, from 479,931.1 to 528,424.6, which is about 12% of the correct 4,195,680. The worked example was launched with 1,024 blocks, of which only block 0 has a nonzero sum. It returned the correct 63 in 1 run and 0 in another run, because a block with the sum 0 read the result before block 0 wrote 63, and it wrote its 0 afterward.

15.6.3 The order of float additions

The 2 correct methods add the same numbers in different orders. For integers, the order does not matter. For floats, it does, because every addition rounds its result to the nearest float.

A float has 24 significant bits. Every integer up to \(2^{24} = 16{,}777{,}216\) can therefore be represented as a float, but beyond \(2^{24}\), the floats are 2 apart, so only the even integers are floats. In Figure 15.11, we add 16,777,216, 1 and 1 in 2 orders. From left to right, the first addition gives \(16{,}777{,}216 + 1 = 16{,}777{,}217\), which is not a float and rounds back to 16,777,216, and the second \(+ 1\) is lost in the same way. With the small values first, \(1 + 1 = 2\), and \(16{,}777{,}216 + 2 = 16{,}777{,}218\) is exact.

The same 3 floats, 16,777,216, 1 and 1, added in 2 orders. Left to right, each + 1 gives 16,777,217, which is not a float and rounds back to 16,777,216. With the small values first, 1 + 1 = 2 and 16,777,216 + 2 = 16,777,218 exactly.
Figure 15.11 The same 3 floats added in 2 orders give 2 different sums.

With a second launch, the order of every addition is fixed. We let each thread add its elements in the order of its loop, the shuffles combine fixed pairs of lanes, and the last block adds the partial sums in a fixed pattern. The result is therefore the same, bit for bit, in every run with the same grid. With atomic additions, the 1,024 block sums arrive in an order that depends on timing, and the last bits of the result can change from run to run. Both results are correct to the precision of a float.

The program uses this observation to verify itself exactly, in the same way as the paper on tiled matrix multiplication does with small integers. Its second test fills \(a\) with 1 at every position divisible by 3 and \(b\) with 1 at every position divisible by 2, and with 0 elsewhere. Every product, every partial sum and the total are then integers no larger than \(2^{24}\), and all of them are floats. No addition rounds, every order gives the same result, and every method must return exactly 2,796,203, the number of positions below \(2^{24}\) that are divisible by 6.

Exercises

15.15 With 4 blocks whose sums are 10, 20, 30 and 40, list 2 orders of atomic additions and the intermediate values of the result for each.
15.16 Why does the 0-and-1 test stay exact with \(n = 2^{24}\), but not necessarily with \(n = 2^{25}\)?
15.17 In the faulty plain addition, what is the smallest wrong result the worked example can produce, and what is the largest?

15.7 Implementation

15.7.1 The register sum

We implement the grid-stride loop of lines 1 to 7 as a device function, that is, a function that runs on the GPU and is called from kernels rather than launched by the host. In C++, a device function is marked __device__, and in Rust, it is marked #[device]. The following code computes the register sum of 1 thread.

Listing 15.1 The register sum of 1 thread: lines 1 to 7 of Dot-Block.

mod kernels {
    // ...
    /// The sum of a[index] * b[index] over this thread's elements, a grid apart.
    #[device]
    fn products(a: &[f32], b: &[f32]) -> f32 {
        let grid_size = (thread::gridDim_x() * BLOCK) as usize;
        let mut index = thread::index_1d().get();

        let mut sum = 0.0;
        while index < a.len() {
            sum += a[index] * b[index];
            index += grid_size;
        }
        sum
    }
    // ...
}
// The sum of a[index] * b[index] over this thread's elements, a grid apart.
__device__ float products(const float* a, const float* b, int n)
{
    int gridSize = gridDim.x * blockDim.x;
    float sum = 0.0f;

    for (int index = blockIdx.x * blockDim.x + threadIdx.x; index < n; index += gridSize) {
        sum += a[index] * b[index];
    }
    return sum;
}

The loop reads a[i] and b[i] and adds their product to sum without storing the product. In Rust, the slices are indexed with an ordinary usize. The loop condition i < a.len() lets the compiler drop the bounds check on a, and the check on b costs 1 comparison per 8 bytes loaded, which does not change the speed of a memory-bound loop. The Rust function computes \(\mathsf{gridSize}\) from the constant BLOCK, which the launch contract of every kernel that calls the function fixes at 256.

15.7.2 The tree kernel

Listing 15.2 shows the complete fused kernel with the tree in shared memory, which is Dot-Block in both languages.

Listing 15.2 The fused kernel with the tree in shared memory: Dot-Block.

mod kernels {
    // ...
    /// Fused: products and a tree in shared memory, 1 partial sum per block.
    #[kernel]
    #[launch_contract(domain = 1, block = (256, 1, 1))]
    pub fn dot_tree(a: &[f32], b: &[f32], mut partial: DisjointSlice<f32>) {
        static mut CELLS: SharedArray<f32, 256> = SharedArray::UNINIT;
        let thread_idx = thread::threadIdx_x() as usize;

        // SAFETY: each thread writes only its own cell, before the barrier.
        unsafe { CELLS[thread_idx] = products(a, b) };
        thread::sync_threads();

        let mut step: usize = 0;
        #[unroll]
        while step < 8 {
            let stride: usize = 128 >> step;
            if thread_idx < stride {
                // SAFETY: in this step, this thread alone writes its cell and reads cell
                // thread_idx + stride, which no thread writes in this step.
                unsafe { CELLS[thread_idx] += CELLS[thread_idx + stride] };
            }
            thread::sync_threads();
            step += 1;
        }

        if thread_idx == 0 {
            // SAFETY: only thread 0 of each block writes, at its own block number.
            unsafe { *partial.get_unchecked_mut(thread::blockIdx_x() as usize) = CELLS[0] };
        }
    }
    // ...
}
// Fused: products and a tree in shared memory, 1 partial sum per block.
__global__ void dotTree(const float* a, const float* b, float* partial, int n)
{
    __shared__ float cells[BLOCK];

    cells[threadIdx.x] = products(a, b, n);
    __syncthreads();

    for (int stride = BLOCK / 2; stride > 0; stride /= 2) {
        if (threadIdx.x < stride) {
            cells[threadIdx.x] += cells[threadIdx.x + stride];
        }
        __syncthreads();
    }

    if (threadIdx.x == 0) {
        partial[blockIdx.x] = cells[0];
    }
}

The call products(a, b) performs lines 1 to 7, the store into cells[t] or CELLS[t] is line 8, and the first barrier is line 9. The loop performs lines 10 to 15, with the barrier of line 14 after the if, and the final if t == 0 performs lines 16 to 18.

The two languages differ in 3 places. First, C++ declares the shared array with __shared__, while Rust declares a static mut SharedArray<f32, 256>. The length of the Rust array is part of its type, and this is why the Rust kernel’s launch contract fixes the block at exactly 256 threads. Every access to the array is in an unsafe block with its argument (Section 15.4.3). Second, the C++ loop halves stride directly, whereas the Rust loop counts step from 0 to 7 and computes stride = 128 >> step, which is 128, 64, 32 and so on down to 1. The reason is that cuda-oxide unrolls a loop marked #[unroll] only when the loop has an integer counter that is compared with a constant and increased by a constant. With s /= 2, the compiler reports that the loop was not unrolled. Third, thread 0 writes partial[blockIdx.x], at an index that is not its own global index, so Rust uses get_unchecked_mut, with the argument that only thread 0 of each block writes, and only at its own block number.

15.7.3 The warp and block sums

Listing 15.3 shows Warp-Sum and Block-Sum as device functions.

Listing 15.3 Warp-Sum and Block-Sum.

mod kernels {
    // ...
    /// The sum of `value` over the 32 lanes of a warp, left in lane 0.
    #[device]
    fn warp_sum(mut value: f32) -> f32 {
        let mut step: u32 = 0;

        #[unroll]
        while step < 5 {
            value += warp::shuffle_down_f32(value, 16u32 >> step);
            step += 1;
        }
        value
    }

    /// The sum of `value` over the 256 threads of a block, returned to thread 0.
    #[device]
    fn block_sum(value: f32) -> f32 {
        static mut WARP_SUMS: SharedArray<f32, 8> = SharedArray::UNINIT;
        let lane = warp::lane_id() as usize;
        let warp_index = thread::threadIdx_x() as usize / 32;

        let value = warp_sum(value);
        if lane == 0 {
            // SAFETY: lane 0 of each warp writes its own slot, before the barrier.
            unsafe { WARP_SUMS[warp_index] = value };
        }
        thread::sync_threads();

        // SAFETY: after the barrier the slots are only read.
        let warp_total = if lane < 8 { unsafe { WARP_SUMS[lane] } } else { 0.0 };
        if warp_index == 0 { warp_sum(warp_total) } else { 0.0 }
    }
    // ...
}
// The sum of value over the 32 lanes of a warp, left in lane 0.
__device__ float warpSum(float value)
{
    for (int distance = 16; distance > 0; distance /= 2) {
        value += __shfl_down_sync(0xffffffff, value, distance);
    }
    return value;
}

// The sum of value over the 256 threads of a block, returned to thread 0.
__device__ float blockSum(float value)
{
    __shared__ float warpSums[8];
    int lane = threadIdx.x % 32;
    int warpIndex = threadIdx.x / 32;

    value = warpSum(value);
    if (lane == 0) {
        warpSums[warpIndex] = value;
    }
    __syncthreads();

    float warpTotal = lane < 8 ? warpSums[lane] : 0.0f;
    return warpIndex == 0 ? warpSum(warpTotal) : 0.0f;
}

The calls __shfl_down_sync(0xffffffff, v, offset) and warp::shuffle_down_f32(v, offset) are the shuffle of Definition 15.6. The mask 0xffffffff has all 32 bits set and therefore names all 32 lanes, and the Rust function applies the same mask. In Rust, the offset is computed as 16u32 >> step, which gives 16, 8, 4, 2 and 1 for step from 0 to 4. The counter is declared u32, and the shifted constant is written 16u32, because with both types left to inference, the GPU backend of cuda-oxide stopped with an internal error about a shift of a 64-bit value by a 32-bit amount. The shared array WARP_SUMS is declared inside the device function, and every block that calls block_sum still receives its own 8 slots.

15.7.4 Combining the block sums

Listing 15.4 shows the fused kernel that combines the block sums with 1 atomic addition per block.

Listing 15.4 The fused kernel with an atomic addition per block.

mod kernels {
    // ...
    /// Fused: products, warp shuffles, and 1 atomic addition per block.
    #[kernel]
    #[launch_contract(domain = 1, block = (256, 1, 1))]
    pub fn dot_atomic(a: &[f32], b: &[f32], result: &[DeviceAtomicF32]) {
        let total = block_sum(products(a, b));

        if thread::threadIdx_x() == 0 {
            result[0].fetch_add(total, AtomicOrdering::Relaxed);
        }
    }
}
// Fused: products, warp shuffles, and 1 atomic addition per block.
__global__ void dotAtomic(const float* a, const float* b, float* result, int n)
{
    float total = blockSum(products(a, b, n));

    if (threadIdx.x == 0) {
        atomicAdd(result, total);
    }
}

In Rust, the result is a slice of DeviceAtomicF32, received as a shared reference &[...] rather than a mutable one. Like the atomic types of the Rust standard library, the atomic type permits modification through a shared reference, because each modification is 1 indivisible operation. The kernel therefore needs no unsafe. AtomicOrdering::Relaxed asks for atomicity and nothing more, which suffices here, because the host reads the result only after the kernel has finished. A device buffer of DeviceAtomicF32 cannot be copied with to_host_vec, so the Rust program uses 2 small kernels, clear and publish. The first sets the result to 0 before the launch, and the second copies it into an ordinary float afterward. In C++, the program sets the result to 0 with cudaMemsetAsync.

The host prepares every launch once, and it runs the 4 designs with 1 closure in Rust and 1 function in C++. Listing 15.5 shows the launches. The map followed by a reduction needs 3 launches, each fused kernel with a second launch needs 2, and the atomic design needs 3 in Rust and 2 in C++.

Listing 15.5 The launches of the 4 designs.

fn main() -> Result<(), Error> {
    // ...
    let grid = LaunchConfig1D::new(GRID, BLOCK, 0);
    let one = LaunchConfig1D::new(1, BLOCK, 0);
    let map = LaunchConfig1D::new(N as u32 / BLOCK, BLOCK, 0);

    let multiply = module.prepare_multiply(map)?;
    let reduce = module.prepare_sum(grid)?;
    let last = module.prepare_sum(one)?;
    let tree = module.prepare_dot_tree(grid)?;
    let shuffle = module.prepare_dot_shuffle(grid)?;
    let clear = module.prepare_clear(one)?;
    let atomic = module.prepare_dot_atomic(grid)?;
    let publish = module.prepare_publish(one)?;

    // Launches 1 dot product; the result ends in `buf.total`.
    let run = |method: Method, buf: &mut Buffers| -> Result<(), Error> {
        let (a, b, stream) = (&buf.a, &buf.b, &stream);
        match method {
            Method::MapReduce => {
                module.multiply(stream, &multiply, a, b, &mut buf.products)?;
                module.sum(stream, &reduce, &buf.products, &mut buf.partial)?;
                module.sum(stream, &last, &buf.partial, &mut buf.total)?;
            }
            Method::Tree => {
                module.dot_tree(stream, &tree, a, b, &mut buf.partial)?;
                module.sum(stream, &last, &buf.partial, &mut buf.total)?;
            }
            Method::Shuffle => {
                module.dot_shuffle(stream, &shuffle, a, b, &mut buf.partial)?;
                module.sum(stream, &last, &buf.partial, &mut buf.total)?;
            }
            Method::Atomic => {
                module.clear(stream, &clear, &buf.atomic)?;
                module.dot_atomic(stream, &atomic, a, b, &buf.atomic)?;
                module.publish(stream, &publish, &buf.atomic, &mut buf.total)?;
            }
        }
        Ok(())
    };
    // ...
}
// Launches 1 dot product; the result ends in buf.total.
void run(Method method, const Buffers& buf)
{
    int n = buf.n;
    int mapBlocks = (n + BLOCK - 1) / BLOCK;

    switch (method) {
    case MAP_REDUCE:
        multiply<<<mapBlocks, BLOCK>>>(buf.a, buf.b, buf.products, n);
        sum<<<GRID, BLOCK>>>(buf.products, buf.partial, n);
        sum<<<1, BLOCK>>>(buf.partial, buf.total, GRID);
        break;
    case TREE:
        dotTree<<<GRID, BLOCK>>>(buf.a, buf.b, buf.partial, n);
        sum<<<1, BLOCK>>>(buf.partial, buf.total, GRID);
        break;
    case SHUFFLE:
        dotShuffle<<<GRID, BLOCK>>>(buf.a, buf.b, buf.partial, n);
        sum<<<1, BLOCK>>>(buf.partial, buf.total, GRID);
        break;
    case ATOMIC:
        check(cudaMemsetAsync(buf.total, 0, sizeof(float)));
        dotAtomic<<<GRID, BLOCK>>>(buf.a, buf.b, buf.total, n);
        break;
    }
    check(cudaGetLastError());
}

Exercises

15.18 Write a fused kernel that combines 1 atomic addition per warp instead of per block. How many atomic operations does 1 run perform with 1,024 blocks of 256 threads?
15.19 Reuse block_sum to compute \(\sum a_i^2\), the squared length of a vector. How many bytes per element does it read?

15.8 Measurements

15.8.1 Platform and method

The measurements come from an integrated GPU, a Jetson Orin NX 16 GB, with 8 SMs and a memory bandwidth of 102 GB/s. Each program first runs the 2 exact tests of Section 15.6.3. It then computes the dot product of \(2^{24}\) pairs of floats in \([0, 1)\), drawn from a fixed generator, with each of the 4 designs, which is 64 MiB per vector. Every design runs 10 times as a warm-up and 20 times under CUDA events. The rate is the number of bytes that the design must move, 16 or 8 per pair, divided by its time. The program then runs the second-launch and atomic designs 100 times each and counts the distinct results. Repeated runs differed by up to 9%.

15.8.2 Results

The Rust program printed the following lines.

$ cargo oxide run
GPU: Orin, 8 SMs
exact tests                   map+red      tree   shuffle    atomic
  worked example, 16 pairs          63        63        63        63   expected 63
  0s and 1s, 16777216 pairs    2796203   2796203   2796203   2796203   expected 2796203
16777216 pairs of floats in [0, 1), 20 runs
  method                    time   bytes/pair      rate      result
  map, then reduce        3.334 ms       16 B    80.5 GB/s  4195680.0
  fused, shared tree      1.409 ms        8 B    95.2 GB/s  4195680.0
  fused, shuffles         1.405 ms        8 B    95.5 GB/s  4195680.0
  fused, atomic combine   1.405 ms        8 B    95.5 GB/s  4195681.0
  exact, in double precision                             4195680.2
distinct results in 100 runs
  second launch    1  from 4195680.0 to 4195680.0
  atomic           3  from 4195680.5 to 4195681.5
largest relative error 3.20e-7
PASSED

Every design returns 63 for the worked example and exactly 2,796,203 for the 0-and-1 test. In the table of floats, the column bytes/pair gives the bytes that each design moves per pair of elements, and the line exact, in double precision gives the exact result for comparison. Table 15.1 collects the times of both languages.

DesignBytes per pairRust timeRust rateC++ timeC++ rate
map, then reduce163.334 ms80.5 GB/s3.096 ms86.7 GB/s
fused, tree in shared memory81.409 ms95.2 GB/s1.412 ms95.1 GB/s
fused, warp shuffles81.405 ms95.5 GB/s1.456 ms92.2 GB/s
fused, atomic combine81.405 ms95.5 GB/s1.389 ms96.6 GB/s

Table 15.1 The dot product of \(2^{24}\) pairs on the measured GPU. Least times at 102 GB/s: 2.63 ms for 16 bytes per pair, 1.32 ms for 8.

Measured rates of the 4 designs on the measured GPU, Rust and C++, against 102 GB/s.
Figure 15.12 Measured rates of the 4 designs against the memory bandwidth of 102 GB/s.

15.8.3 Why the fused kernel is more than twice as fast

We first count the bytes. The design that stores the products reads \(a_i\) and \(b_i\), writes \(p_i\), and reads \(p_i\) back in the reduction. These are 4 accesses of 4 bytes each, so the design moves 16 bytes per pair, or 268 MB for \(2^{24}\) pairs. The fused kernels read only \(a_i\) and \(b_i\), which is 8 bytes per pair, or 134 MB, as shown in Figure 15.13. At 102 GB/s, these amounts take at least 2.63 ms and 1.32 ms, a ratio of 2.

Bytes moved per pair. Map then reduce reads a[i] and b[i], writes p[i] and reads it back: 16 bytes. The fused kernel reads a[i] and b[i] and adds the product to a register: 8 bytes. For 16,777,216 pairs, 268 MB against 134 MB, 2.63 ms against 1.32 ms at 102 GB/s.
Figure 15.13 Bytes moved per pair: 16 when the products are stored, 8 when they stay in registers.

The measured ratio is \(3.334 / 1.405 = 2.4\) in Rust and \(3.096 / 1.412 = 2.2\) in C++. Halving the bytes accounts for a factor of 2. The rest comes from the lower rate of the first design, 80.5 GB/s and 86.7 GB/s against 95 GB/s. Its multiplication kernel writes one value for every 2 values that it reads, as SAXPY does, and recall from Chapter 14 that SAXPY reached at most 93 GB/s, for the reasons given in Section 14.8.3. The fused kernels only read, and they reach 92 GB/s to 97 GB/s, which is 90% to 95% of the pin rate of the memory. The Rust map-then-reduce design ran 8% to 11% slower than the C++ design in every run, while the fused kernels ran at the same speed in both languages.

15.8.4 Barriers, shuffles and atomics

The tree with 9 barriers and the warp shuffles with 1 barrier run at the same speed, 1.409 ms and 1.405 ms in Rust. We let each thread add 64 products in its register before the block sum begins, so the 9 barriers of a block cost time only once per \(64 \cdot 256 = 16{,}384\) products, which is a small part of its time. In Chapter 8, we found the same for the plain sum. After coarsening, its tree and its shuffle sum ran at 64.1 GB/s and 64.4 GB/s. Shuffles matter where combinations are frequent, as in the many short reductions of a softmax over the rows of a matrix (Chapter 23).

The atomic design is as fast as the others, because its 1,024 atomic additions are few, and its extra launches, clear and publish, each run only 1 block. Its results, however, differ. The exact dot product, computed in double precision on the CPU, is 4,195,680.2. Between \(2^{22} = 4{,}194{,}304\) and \(2^{23}\), the floats are 0.5 apart, so the nearest float is 4,195,680.0. The second-launch designs return exactly this value, and the 100 runs of the shuffle design returned the same bits every time. The atomic design returned 3 different values in 100 runs, 4,195,680.5, 4,195,681.0 and 4,195,681.5, which lie 1 to 3 float steps above the nearest float, and in other runs, it also returned 4,195,680.0. All of these values are correct to a relative error of \(3.2 \cdot 10^{-7}\), which is about the precision of a float. A program that must reproduce its results bit for bit, for example to compare two versions of a simulation, needs the second launch.

Exercises

15.20 From Table 15.1, compute the fraction of the 102 GB/s that each fused design reaches in each language.
15.21 Predict the time of the fused dot product of \(2^{26}\) pairs on the measured GPU, and on a GPU with 3,350 GB/s.

15.9 The complete programs

Listing 15.6 gives the complete programs, from which every excerpt of this chapter was taken.

Listing 15.6 The complete programs. code/oxide/ch15_dot_product/src/main.rs code/cuda/ch15_dot_product/dot.cu

//! Chapter 15: the dot product of 2 vectors as a reduction, 4 ways: map then reduce,
//! a fused kernel with a tree in shared memory, a fused kernel with warp shuffles, and
//! a fused kernel that combines its block results with atomic additions.
//!
//!     cargo oxide run

use std::collections::BTreeSet;
use std::sync::Arc;

use cuda_core::sys::CUevent_flags_enum_CU_EVENT_DEFAULT as TIMING;
use cuda_core::{CudaContext, CudaStream, DeviceBuffer, LaunchConfig1D};
use cuda_device::atomic::{AtomicOrdering, DeviceAtomicF32};
use cuda_device::{DisjointSlice, SharedArray, cuda_module, device, kernel, launch_contract};
use cuda_device::{thread, warp};

const BLOCK: u32 = 256;
const GRID: u32 = 1024;
const N: usize = 1 << 24;
const RUNS: u32 = 20;

/// The worked example of the chapter: 16 pairs whose products add up to 63.
const A16: [f32; 16] = [1., 2., 3., 1., 5., 1., 2., 3., 3., 1., 2., 3., 1., 3., 2., 1.];
const B16: [f32; 16] = [2., 3., 1., 4., 1., 1., 4., 1., 1., 2., 2., 2., 1., 3., 1., 4.];

type Error = Box<dyn std::error::Error>;

#[cuda_module]
mod kernels {
    use super::*;

    /// The sum of `value` over the 32 lanes of a warp, left in lane 0.
    #[device]
    fn warp_sum(mut value: f32) -> f32 {
        let mut step: u32 = 0;

        #[unroll]
        while step < 5 {
            value += warp::shuffle_down_f32(value, 16u32 >> step);
            step += 1;
        }
        value
    }

    /// The sum of `value` over the 256 threads of a block, returned to thread 0.
    #[device]
    fn block_sum(value: f32) -> f32 {
        static mut WARP_SUMS: SharedArray<f32, 8> = SharedArray::UNINIT;
        let lane = warp::lane_id() as usize;
        let warp_index = thread::threadIdx_x() as usize / 32;

        let value = warp_sum(value);
        if lane == 0 {
            // SAFETY: lane 0 of each warp writes its own slot, before the barrier.
            unsafe { WARP_SUMS[warp_index] = value };
        }
        thread::sync_threads();

        // SAFETY: after the barrier the slots are only read.
        let warp_total = if lane < 8 { unsafe { WARP_SUMS[lane] } } else { 0.0 };
        if warp_index == 0 { warp_sum(warp_total) } else { 0.0 }
    }

    /// The sum of a[index] * b[index] over this thread's elements, a grid apart.
    #[device]
    fn products(a: &[f32], b: &[f32]) -> f32 {
        let grid_size = (thread::gridDim_x() * BLOCK) as usize;
        let mut index = thread::index_1d().get();

        let mut sum = 0.0;
        while index < a.len() {
            sum += a[index] * b[index];
            index += grid_size;
        }
        sum
    }

    /// Map: products[index] = a[index] * b[index], one element per thread.
    #[kernel]
    #[launch_contract(domain = 1, block = (256, 1, 1))]
    pub fn multiply(a: &[f32], b: &[f32], mut element_products: DisjointSlice<f32>) {
        let thread_id = thread::index_1d();
        let index = thread_id.get();

        if let Some(out) = element_products.get_mut(thread_id) {
            *out = a[index] * b[index];
        }
    }

    /// Reduce: 1 partial sum of `input` per block.
    #[kernel]
    #[launch_contract(domain = 1, block = (256, 1, 1))]
    pub fn sum(input: &[f32], mut partial: DisjointSlice<f32>) {
        let grid_size = (thread::gridDim_x() * BLOCK) as usize;
        let mut index = thread::index_1d().get();

        let mut my_sum = 0.0;
        while index < input.len() {
            my_sum += input[index];
            index += grid_size;
        }

        let total = block_sum(my_sum);
        if thread::threadIdx_x() == 0 {
            // SAFETY: only thread 0 of each block writes, at its own block number.
            unsafe { *partial.get_unchecked_mut(thread::blockIdx_x() as usize) = total };
        }
    }

    /// Fused: products and a tree in shared memory, 1 partial sum per block.
    #[kernel]
    #[launch_contract(domain = 1, block = (256, 1, 1))]
    pub fn dot_tree(a: &[f32], b: &[f32], mut partial: DisjointSlice<f32>) {
        static mut CELLS: SharedArray<f32, 256> = SharedArray::UNINIT;
        let thread_idx = thread::threadIdx_x() as usize;

        // SAFETY: each thread writes only its own cell, before the barrier.
        unsafe { CELLS[thread_idx] = products(a, b) };
        thread::sync_threads();

        let mut step: usize = 0;
        #[unroll]
        while step < 8 {
            let stride: usize = 128 >> step;
            if thread_idx < stride {
                // SAFETY: in this step, this thread alone writes its cell and reads cell
                // thread_idx + stride, which no thread writes in this step.
                unsafe { CELLS[thread_idx] += CELLS[thread_idx + stride] };
            }
            thread::sync_threads();
            step += 1;
        }

        if thread_idx == 0 {
            // SAFETY: only thread 0 of each block writes, at its own block number.
            unsafe { *partial.get_unchecked_mut(thread::blockIdx_x() as usize) = CELLS[0] };
        }
    }

    /// Fused: products and warp shuffles, 1 partial sum per block.
    #[kernel]
    #[launch_contract(domain = 1, block = (256, 1, 1))]
    pub fn dot_shuffle(a: &[f32], b: &[f32], mut partial: DisjointSlice<f32>) {
        let total = block_sum(products(a, b));

        if thread::threadIdx_x() == 0 {
            // SAFETY: only thread 0 of each block writes, at its own block number.
            unsafe { *partial.get_unchecked_mut(thread::blockIdx_x() as usize) = total };
        }
    }

    /// Sets the atomic result to 0 before a run of `dot_atomic`.
    #[kernel]
    #[launch_contract(domain = 1, block = (256, 1, 1))]
    pub fn clear(result: &[DeviceAtomicF32]) {
        if thread::index_1d().get() == 0 {
            result[0].store(0.0, AtomicOrdering::Relaxed);
        }
    }

    /// Copies the atomic result into an ordinary float that the host can read.
    #[kernel]
    #[launch_contract(domain = 1, block = (256, 1, 1))]
    pub fn publish(result: &[DeviceAtomicF32], mut out: DisjointSlice<f32>) {
        if let Some(value) = out.get_mut(thread::index_1d()) {
            *value = result[0].load(AtomicOrdering::Relaxed);
        }
    }

    /// Fused: products, warp shuffles, and 1 atomic addition per block.
    #[kernel]
    #[launch_contract(domain = 1, block = (256, 1, 1))]
    pub fn dot_atomic(a: &[f32], b: &[f32], result: &[DeviceAtomicF32]) {
        let total = block_sum(products(a, b));

        if thread::threadIdx_x() == 0 {
            result[0].fetch_add(total, AtomicOrdering::Relaxed);
        }
    }
}

/// The 4 ways of computing the dot product that the program compares.
#[derive(Clone, Copy)]
enum Method {
    MapReduce,
    Tree,
    Shuffle,
    Atomic,
}

const METHODS: [(&str, Method, usize); 4] = [
    ("map, then reduce", Method::MapReduce, 16),
    ("fused, shared tree", Method::Tree, 8),
    ("fused, shuffles", Method::Shuffle, 8),
    ("fused, atomic combine", Method::Atomic, 8),
];

/// The device memory of 1 problem.
struct Buffers {
    a: DeviceBuffer<f32>,
    b: DeviceBuffer<f32>,
    products: DeviceBuffer<f32>,
    partial: DeviceBuffer<f32>,
    total: DeviceBuffer<f32>,
    atomic: DeviceBuffer<DeviceAtomicF32>,
}

impl Buffers {
    fn new(stream: &Arc<CudaStream>, a: &[f32], b: &[f32]) -> Result<Self, Error> {
        Ok(Buffers {
            a: DeviceBuffer::from_host(stream, a)?,
            b: DeviceBuffer::from_host(stream, b)?,
            products: DeviceBuffer::zeroed(stream, a.len())?,
            partial: DeviceBuffer::zeroed(stream, GRID as usize)?,
            total: DeviceBuffer::zeroed(stream, 1)?,
            atomic: DeviceBuffer::<f32>::zeroed(stream, 1)?.cast_elem(),
        })
    }
}

/// Runs 1 method once and returns its result.
fn result<R>(
    run: &R,
    method: Method,
    buf: &mut Buffers,
    stream: &CudaStream,
) -> Result<f32, Error>
where
    R: Fn(Method, &mut Buffers) -> Result<(), Error>,
{
    run(method, buf)?;
    Ok(buf.total.to_host_vec(stream)?[0])
}

/// Milliseconds per run of 1 method: 10 warm-up runs, then RUNS runs timed with events.
fn time_ms<R>(
    run: &R,
    method: Method,
    buf: &mut Buffers,
    stream: &CudaStream,
) -> Result<f64, Error>
where
    R: Fn(Method, &mut Buffers) -> Result<(), Error>,
{
    for _ in 0..10 {
        run(method, buf)?;
    }

    let start = stream.record_event(Some(TIMING))?;
    for _ in 0..RUNS {
        run(method, buf)?;
    }
    let stop = stream.record_event(Some(TIMING))?;
    stop.synchronize()?;

    Ok(start.elapsed_ms(&stop)? as f64 / RUNS as f64)
}

/// Floats in [0, 1) from a small linear congruential generator.
fn random(n: usize, seed: u32) -> Vec<f32> {
    let mut state = seed;

    (0..n)
        .map(|_| {
            state = state.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
            (state >> 8) as f32 / 16_777_216.0
        })
        .collect()
}

/// Every method on 1 input whose dot product is an integer that a float holds exactly.
/// Returns the number of methods whose result differs from `expect`.
fn exact_test<R>(
    run: &R,
    stream: &Arc<CudaStream>,
    label: &str,
    a: &[f32],
    b: &[f32],
) -> Result<usize, Error>
where
    R: Fn(Method, &mut Buffers) -> Result<(), Error>,
{
    let expect: f32 = a.iter().zip(b).map(|(x, y)| x * y).sum();
    let mut buf = Buffers::new(stream, a, b)?;
    let mut bad = 0;

    print!("  {label:<26}");
    for (_, method, _) in METHODS {
        let got = result(run, method, &mut buf, stream)?;
        print!(" {got:>9}");
        bad += usize::from(got != expect);
    }
    println!("   expected {expect}");
    Ok(bad)
}

fn main() -> Result<(), Error> {
    let ctx = CudaContext::new(0)?;
    let stream = ctx.default_stream();
    // SAFETY: the loaded code was compiled from the `kernels` module above.
    let module = unsafe { kernels::load(&ctx)? };

    let name = ctx.device_name()?;
    let sms = ctx.multiprocessor_count()?;
    println!("GPU: {name}, {sms} SMs");

    let grid = LaunchConfig1D::new(GRID, BLOCK, 0);
    let one = LaunchConfig1D::new(1, BLOCK, 0);
    let map = LaunchConfig1D::new(N as u32 / BLOCK, BLOCK, 0);

    let multiply = module.prepare_multiply(map)?;
    let reduce = module.prepare_sum(grid)?;
    let last = module.prepare_sum(one)?;
    let tree = module.prepare_dot_tree(grid)?;
    let shuffle = module.prepare_dot_shuffle(grid)?;
    let clear = module.prepare_clear(one)?;
    let atomic = module.prepare_dot_atomic(grid)?;
    let publish = module.prepare_publish(one)?;

    // Launches 1 dot product; the result ends in `buf.total`.
    let run = |method: Method, buf: &mut Buffers| -> Result<(), Error> {
        let (a, b, stream) = (&buf.a, &buf.b, &stream);
        match method {
            Method::MapReduce => {
                module.multiply(stream, &multiply, a, b, &mut buf.products)?;
                module.sum(stream, &reduce, &buf.products, &mut buf.partial)?;
                module.sum(stream, &last, &buf.partial, &mut buf.total)?;
            }
            Method::Tree => {
                module.dot_tree(stream, &tree, a, b, &mut buf.partial)?;
                module.sum(stream, &last, &buf.partial, &mut buf.total)?;
            }
            Method::Shuffle => {
                module.dot_shuffle(stream, &shuffle, a, b, &mut buf.partial)?;
                module.sum(stream, &last, &buf.partial, &mut buf.total)?;
            }
            Method::Atomic => {
                module.clear(stream, &clear, &buf.atomic)?;
                module.dot_atomic(stream, &atomic, a, b, &buf.atomic)?;
                module.publish(stream, &publish, &buf.atomic, &mut buf.total)?;
            }
        }
        Ok(())
    };

    println!("exact tests                   map+red      tree   shuffle    atomic");
    let mut failed = exact_test(&run, &stream, "worked example, 16 pairs", &A16, &B16)?;

    let ones_a: Vec<f32> = (0..N).map(|index| f32::from(index % 3 == 0)).collect();
    let ones_b: Vec<f32> = (0..N).map(|index| f32::from(index % 2 == 0)).collect();
    failed += exact_test(&run, &stream, "0s and 1s, 16777216 pairs", &ones_a, &ones_b)?;

    let a = random(N, 1);
    let b = random(N, 2);
    let exact: f64 = a.iter().zip(&b).map(|(&x, &y)| x as f64 * y as f64).sum();
    let mut buf = Buffers::new(&stream, &a, &b)?;
    let error = |r: f32| ((r as f64 - exact) / exact).abs();
    let mut worst = 0.0f64;

    println!("{N} pairs of floats in [0, 1), {RUNS} runs");
    println!("  method                    time   bytes/pair      rate      result");
    for (name, method, per_pair) in METHODS {
        let ms = time_ms(&run, method, &mut buf, &stream)?;
        let got = result(&run, method, &mut buf, &stream)?;
        worst = worst.max(error(got));

        let gbs = (N * per_pair) as f64 / ms / 1e6;
        print!("  {name:<22} {ms:6.3} ms {per_pair:>8} B");
        println!("  {gbs:6.1} GB/s  {got:.1}");
    }
    println!("  {:<54} {exact:.1}", "exact, in double precision");

    println!("distinct results in 100 runs");
    for (name, method) in [("second launch", Method::Shuffle), ("atomic", Method::Atomic)] {
        let mut seen = BTreeSet::new();
        for _ in 0..100 {
            seen.insert(result(&run, method, &mut buf, &stream)?.to_bits());
        }

        let low = f32::from_bits(*seen.first().ok_or("no result")?);
        let high = f32::from_bits(*seen.last().ok_or("no result")?);
        println!("  {name:<14} {:3}  from {low:.1} to {high:.1}", seen.len());
        worst = worst.max(error(low)).max(error(high));
    }

    println!("largest relative error {worst:.2e}");
    if failed == 0 && worst < 1e-5 {
        println!("PASSED");
    } else {
        println!("FAILED");
    }
    Ok(())
}
// Chapter 15: the dot product of 2 vectors as a reduction, 4 ways: map then reduce,
// a fused kernel with a tree in shared memory, a fused kernel with warp shuffles, and
// a fused kernel that combines its block results with atomic additions.
// Build: nvcc -O3 -arch=native dot.cu -o dot

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <set>
#include <vector>
#include <cuda_runtime.h>

const int BLOCK = 256;
const int GRID = 1024;
const int N = 1 << 24;
const int RUNS = 20;

// The worked example of the chapter: 16 pairs whose products add up to 63.
const float A16[16] = {1, 2, 3, 1, 5, 1, 2, 3, 3, 1, 2, 3, 1, 3, 2, 1};
const float B16[16] = {2, 3, 1, 4, 1, 1, 4, 1, 1, 2, 2, 2, 1, 3, 1, 4};

void check(cudaError_t err)
{
    if (err != cudaSuccess) {
        std::fprintf(stderr, "CUDA error: %s\n", cudaGetErrorString(err));
        std::exit(1);
    }
}

// The sum of value over the 32 lanes of a warp, left in lane 0.
__device__ float warpSum(float value)
{
    for (int distance = 16; distance > 0; distance /= 2) {
        value += __shfl_down_sync(0xffffffff, value, distance);
    }
    return value;
}

// The sum of value over the 256 threads of a block, returned to thread 0.
__device__ float blockSum(float value)
{
    __shared__ float warpSums[8];
    int lane = threadIdx.x % 32;
    int warpIndex = threadIdx.x / 32;

    value = warpSum(value);
    if (lane == 0) {
        warpSums[warpIndex] = value;
    }
    __syncthreads();

    float warpTotal = lane < 8 ? warpSums[lane] : 0.0f;
    return warpIndex == 0 ? warpSum(warpTotal) : 0.0f;
}

// The sum of a[index] * b[index] over this thread's elements, a grid apart.
__device__ float products(const float* a, const float* b, int n)
{
    int gridSize = gridDim.x * blockDim.x;
    float sum = 0.0f;

    for (int index = blockIdx.x * blockDim.x + threadIdx.x; index < n; index += gridSize) {
        sum += a[index] * b[index];
    }
    return sum;
}

// Map: elementProducts[index] = a[index] * b[index], one element per thread.
__global__ void multiply(const float* a, const float* b, float* elementProducts, int n)
{
    int index = blockIdx.x * blockDim.x + threadIdx.x;

    if (index < n) {
        elementProducts[index] = a[index] * b[index];
    }
}

// Reduce: 1 partial sum of input per block.
__global__ void sum(const float* input, float* partial, int n)
{
    int gridSize = gridDim.x * blockDim.x;
    float mySum = 0.0f;

    for (int index = blockIdx.x * blockDim.x + threadIdx.x; index < n; index += gridSize) {
        mySum += input[index];
    }

    float total = blockSum(mySum);
    if (threadIdx.x == 0) {
        partial[blockIdx.x] = total;
    }
}

// Fused: products and a tree in shared memory, 1 partial sum per block.
__global__ void dotTree(const float* a, const float* b, float* partial, int n)
{
    __shared__ float cells[BLOCK];

    cells[threadIdx.x] = products(a, b, n);
    __syncthreads();

    for (int stride = BLOCK / 2; stride > 0; stride /= 2) {
        if (threadIdx.x < stride) {
            cells[threadIdx.x] += cells[threadIdx.x + stride];
        }
        __syncthreads();
    }

    if (threadIdx.x == 0) {
        partial[blockIdx.x] = cells[0];
    }
}

// Fused: products and warp shuffles, 1 partial sum per block.
__global__ void dotShuffle(const float* a, const float* b, float* partial, int n)
{
    float total = blockSum(products(a, b, n));

    if (threadIdx.x == 0) {
        partial[blockIdx.x] = total;
    }
}

// Fused: products, warp shuffles, and 1 atomic addition per block.
__global__ void dotAtomic(const float* a, const float* b, float* result, int n)
{
    float total = blockSum(products(a, b, n));

    if (threadIdx.x == 0) {
        atomicAdd(result, total);
    }
}

enum Method { MAP_REDUCE, TREE, SHUFFLE, ATOMIC };

struct MethodInfo {
    const char* name;
    Method method;
    int bytesPerPair;
};

const MethodInfo METHODS[4] = {
    {"map, then reduce", MAP_REDUCE, 16},
    {"fused, shared tree", TREE, 8},
    {"fused, shuffles", SHUFFLE, 8},
    {"fused, atomic combine", ATOMIC, 8},
};

// The device memory of 1 problem.
struct Buffers {
    int n;
    float *a, *b, *products, *partial, *total;
};

Buffers upload(const std::vector<float>& a, const std::vector<float>& b)
{
    Buffers buf;
    buf.n = a.size();
    size_t bytes = buf.n * sizeof(float);

    check(cudaMalloc(&buf.a, bytes));
    check(cudaMalloc(&buf.b, bytes));
    check(cudaMalloc(&buf.products, bytes));
    check(cudaMalloc(&buf.partial, GRID * sizeof(float)));
    check(cudaMalloc(&buf.total, sizeof(float)));

    check(cudaMemcpy(buf.a, a.data(), bytes, cudaMemcpyHostToDevice));
    check(cudaMemcpy(buf.b, b.data(), bytes, cudaMemcpyHostToDevice));
    return buf;
}

void release(Buffers& buf)
{
    check(cudaFree(buf.a));
    check(cudaFree(buf.b));
    check(cudaFree(buf.products));
    check(cudaFree(buf.partial));
    check(cudaFree(buf.total));
}

// Launches 1 dot product; the result ends in buf.total.
void run(Method method, const Buffers& buf)
{
    int n = buf.n;
    int mapBlocks = (n + BLOCK - 1) / BLOCK;

    switch (method) {
    case MAP_REDUCE:
        multiply<<<mapBlocks, BLOCK>>>(buf.a, buf.b, buf.products, n);
        sum<<<GRID, BLOCK>>>(buf.products, buf.partial, n);
        sum<<<1, BLOCK>>>(buf.partial, buf.total, GRID);
        break;
    case TREE:
        dotTree<<<GRID, BLOCK>>>(buf.a, buf.b, buf.partial, n);
        sum<<<1, BLOCK>>>(buf.partial, buf.total, GRID);
        break;
    case SHUFFLE:
        dotShuffle<<<GRID, BLOCK>>>(buf.a, buf.b, buf.partial, n);
        sum<<<1, BLOCK>>>(buf.partial, buf.total, GRID);
        break;
    case ATOMIC:
        check(cudaMemsetAsync(buf.total, 0, sizeof(float)));
        dotAtomic<<<GRID, BLOCK>>>(buf.a, buf.b, buf.total, n);
        break;
    }
    check(cudaGetLastError());
}

// Runs method once and returns its result.
float result(Method method, const Buffers& buf)
{
    float value;
    run(method, buf);
    check(cudaMemcpy(&value, buf.total, sizeof(float), cudaMemcpyDeviceToHost));
    return value;
}

// Milliseconds per run of method: 10 warm-up runs, then RUNS runs timed with events.
float timeMs(Method method, const Buffers& buf)
{
    for (int warmup = 0; warmup < 10; ++warmup) {
        run(method, buf);
    }

    cudaEvent_t start, stop;
    check(cudaEventCreate(&start));
    check(cudaEventCreate(&stop));

    check(cudaEventRecord(start));
    for (int timed = 0; timed < RUNS; ++timed) {
        run(method, buf);
    }
    check(cudaEventRecord(stop));
    check(cudaEventSynchronize(stop));

    float ms = 0;
    check(cudaEventElapsedTime(&ms, start, stop));
    check(cudaEventDestroy(start));
    check(cudaEventDestroy(stop));
    return ms / RUNS;
}

// Floats in [0, 1) from a small linear congruential generator.
std::vector<float> random(int n, unsigned seed)
{
    std::vector<float> v(n);
    unsigned state = seed;

    for (int i = 0; i < n; ++i) {
        state = state * 1664525u + 1013904223u;
        v[i] = (state >> 8) / 16777216.0f;
    }
    return v;
}

// Every method on 1 input whose dot product is an integer that a float holds exactly.
// Returns the number of methods whose result differs from expect.
int exactTest(const char* label, const std::vector<float>& a, const std::vector<float>& b)
{
    float expect = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        expect += a[i] * b[i];
    }

    Buffers buf = upload(a, b);
    int bad = 0;

    std::printf("  %-26s", label);
    for (const MethodInfo& m : METHODS) {
        float got = result(m.method, buf);
        std::printf(" %9.0f", got);
        bad += got != expect;
    }
    std::printf("   expected %.0f\n", expect);

    release(buf);
    return bad;
}

unsigned bits(float f)
{
    unsigned u;
    std::memcpy(&u, &f, sizeof(u));
    return u;
}

float fromBits(unsigned u)
{
    float f;
    std::memcpy(&f, &u, sizeof(f));
    return f;
}

int main()
{
    cudaDeviceProp prop;
    check(cudaGetDeviceProperties(&prop, 0));
    std::printf("GPU: %s, %d SMs\n", prop.name, prop.multiProcessorCount);

    std::printf("exact tests                   map+red      tree   shuffle    atomic\n");
    std::vector<float> a16(A16, A16 + 16), b16(B16, B16 + 16);
    int failed = exactTest("worked example, 16 pairs", a16, b16);

    std::vector<float> onesA(N), onesB(N);
    for (int i = 0; i < N; ++i) {
        onesA[i] = i % 3 == 0;
        onesB[i] = i % 2 == 0;
    }
    failed += exactTest("0s and 1s, 16777216 pairs", onesA, onesB);

    std::vector<float> a = random(N, 1);
    std::vector<float> b = random(N, 2);
    double exact = 0;
    for (int i = 0; i < N; ++i) {
        exact += double(a[i]) * b[i];
    }
    Buffers buf = upload(a, b);
    double worst = 0;

    std::printf("%d pairs of floats in [0, 1), %d runs\n", N, RUNS);
    std::printf("  method                    time   bytes/pair      rate      result\n");
    for (const MethodInfo& m : METHODS) {
        float ms = timeMs(m.method, buf);
        float got = result(m.method, buf);
        worst = std::fmax(worst, std::fabs((got - exact) / exact));

        double gbs = double(N) * m.bytesPerPair / ms / 1e6;
        std::printf("  %-22s %6.3f ms %8d B", m.name, ms, m.bytesPerPair);
        std::printf("  %6.1f GB/s  %.1f\n", gbs, got);
    }
    std::printf("  %-54s %.1f\n", "exact, in double precision", exact);

    std::printf("distinct results in 100 runs\n");
    const MethodInfo combine[2] = {{"second launch", SHUFFLE, 8}, {"atomic", ATOMIC, 8}};
    for (const MethodInfo& m : combine) {
        std::set<unsigned> seen;
        for (int trial = 0; trial < 100; ++trial) {
            seen.insert(bits(result(m.method, buf)));
        }

        float low = fromBits(*seen.begin());
        float high = fromBits(*seen.rbegin());
        std::printf("  %-14s %3zu  from %.1f to %.1f\n", m.name, seen.size(), low, high);
        worst = std::fmax(worst, std::fabs((low - exact) / exact));
        worst = std::fmax(worst, std::fabs((high - exact) / exact));
    }
    release(buf);

    std::printf("largest relative error %.2e\n", worst);
    if (failed == 0 && worst < 1e-5) {
        std::printf("PASSED\n");
    } else {
        std::printf("FAILED\n");
    }
    return 0;
}

Common mistakes

Storing the products of a map that a reduction consumes. The array of products doubles the memory traffic of a memory-bound computation. The map should instead be fused into the reduction, so that the products stay in a register.

A missing barrier between the steps of the tree. The kernel compiles in both languages and returns a wrong sum that changes from run to run (Section 15.4.1).

A barrier inside a branch that only some threads take. Every thread of the block must reach every __syncthreads() or thread::sync_threads().

A plain addition where an atomic one is needed. *result += total from many blocks loses most of the additions (Section 15.6.2).

Expecting identical bits from atomic float additions. The order of the additions changes from run to run, and so can the last bits of the result. When results must repeat exactly, the block sums should be combined with a second launch.

An unsafe block without its argument. Each access to a shared array needs a stated reason why no other thread writes the same element at the same time, and this reason usually names a barrier.

Summary

  • The dot product is a map, \(p_i = a_i b_i\), followed by a reduction, the sum. On the example, the 16 products add up to \(32 + 31 = 63\).
  • The sequential sum is a chain of \(n\) dependent additions. Because addition is associative and commutative, the additions can be regrouped into a tree of \(\log_2 n\) steps, 4 for the example.
  • In shared memory, each step lets the threads with \(\mathsf{threadIdx{.}x} < \mathsf{stride}\) add cell \(\mathsf{threadIdx{.}x} + \mathsf{stride}\) into their own cell; block 0 of the example computes 7, 7, 11, 7, then 18, 14, then 32. A barrier must follow every step: without it, the example’s block summed to 24 instead of 32, and the real programs returned 26 and 36 instead of 63.
  • Theorem 15.1 proves the tree correct with the invariant that, at the start of the step with stride \(\mathsf{stride}\), cell \(k\) holds the values whose index \(j\) leaves the remainder \(k\) when divided by \(2\,\mathsf{stride}\).
  • Warp shuffles exchange registers within a warp without a barrier; a block sum with shuffles needs 1 barrier and 8 shared floats instead of 9 and 256.
  • Block sums are combined by a second launch, in a fixed order, or by atomic additions, in the order the blocks finish. A plain addition loses sums. Atomic float additions gave 3 different last bits in 100 runs; the second launch gave the same bits every time.
  • The fused kernels read 8 bytes per pair and ran at 92 GB/s to 97 GB/s on the measured GPU, 2.2 to 2.4 times as fast as a map followed by a reduction, which moves 16.

Exercises

  1. Compute the least time of the fused dot product of \(2^{26}\) pairs on your GPU from its memory bandwidth. Change N in both programs and compare.
  2. Change both programs to f64. The fused kernel then reads 16 bytes per pair. Is its time twice that of the f32 version?
  3. Change GRID from 1,024 to 64 and to 8,192. How many products does each thread add in each case, and how do the times of the tree and shuffle kernels change?
  4. In Listing 15.2, which cells does thread 5 read and write in each of the 8 steps? In which steps is it idle?
  5. Write the maximum of an array as a reduction, reusing the tree of Dot-Block with \(\max\) in place of \(+\). What must the threads with no element store in line 8?
  6. Prove that Block-Sum returns the sum of the 256 values to thread 0, using Theorem 15.1 for each warp.
  7. The exact dot product of the measured vectors is 4,195,680.2. Explain why no float program can return it, and which float is the best possible answer.

Sources and further reading

  • A. Pathak, An Introduction to Tiled Parallel Programming, Simplified, 2026. The style of worked example, broken variants and loop-invariant proof used here, and the exact verification with small integers.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022. Pseudocode conventions and loop invariants.
  • M. Harris, “Optimizing Parallel Reduction in CUDA”, NVIDIA, 2007.
  • J. Luitjens, “Faster Parallel Reductions on Kepler”, NVIDIA Technical Blog, 2014.
  • D. Goldberg, “What Every Computer Scientist Should Know About Floating-Point Arithmetic”, ACM Computing Surveys 23(1), 1991.
  • NVIDIA, CUDA C++ Programming Guide, sections “Warp Shuffle Functions”, “Atomic Functions” and “Synchronization Functions”.
  • The Rust Reference, “Static items” and “Unsafety”; the cuda-oxide repository, https://github.com/NVlabs/cuda-oxide.