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 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\).
| Symbol | Meaning | In the example |
|---|---|---|
| \(n\) | number of elements in each vector | 16 |
| \(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 product | 63 |
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\))
- \(\mathsf{sum} = 0\)
- for \(i \in [0, n)\) {
- \(\mathsf{sum} = \mathsf{sum} + a_i \cdot b_i\) // 2 reads, 2 FLOP
- }
- 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.
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.
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.
| Symbol | Meaning | Thread 2, first step of block 0 |
|---|---|---|
| \(\mathsf{stride}\) | stride: distance between the 2 cells of a pair, and number of working threads | 4 |
| \(\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 cell | 6 |
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.
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\))
- \(\mathsf{index} = \mathsf{blockIdx{.}x} \times \mathsf{blockDim{.}x} + \mathsf{threadIdx{.}x}\) // first element
- \(\mathsf{gridSize} = \mathsf{gridDim{.}x} \times \mathsf{blockDim{.}x}\) // threads in the grid
- \(\mathsf{mySum} = 0\)
- while \(\mathsf{index} \lt n\) { // the grid-stride loop of Chapter 14
- \(\mathsf{mySum} = \mathsf{mySum} + a_{\mathsf{index}} \times b_{\mathsf{index}}\)
- \(\mathsf{index} = \mathsf{index} + \mathsf{gridSize}\)
- }
- \(\mathsf{cells}[\mathsf{threadIdx{.}x}] = \mathsf{mySum}\)
- Barrier() // every cell holds its value
- for \(\mathsf{stride} = \mathsf{blockDim{.}x}/2, \mathsf{blockDim{.}x}/4, \ldots, 1\) {
- if \(\mathsf{threadIdx{.}x} \lt \mathsf{stride}\) {
- \(\mathsf{cells}[\mathsf{threadIdx{.}x}] = \mathsf{cells}[\mathsf{threadIdx{.}x}] + \mathsf{cells}[\mathsf{threadIdx{.}x} + \mathsf{stride}]\)
- }
- Barrier() // this step is complete
- }
- if \(\mathsf{threadIdx{.}x} = 0\) {
- \(\mathsf{partial}[\mathsf{blockIdx{.}x}] = \mathsf{cells}[0]\)
- }
| Symbol | Meaning | Thread 2 of block 0, example |
|---|---|---|
| \(\mathsf{blockDim{.}x}\) | number of threads in a block | 8 (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 index | 2 |
| \(\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 tree | 4, 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.
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\).
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 . \]
| Symbol | Meaning | Block 0 of the example, \(\mathsf{stride} = 2\), \(k = 1\) |
|---|---|---|
| \(\mathsf{blockDim{.}x}\) | number of threads, and cells, in the block | 8 |
| \(v_j\) | value stored by thread \(j\) in line 8 | \(v_1 = 6\), \(v_5 = 1\) |
| \(\mathsf{stride}\) | stride of the current iteration | 2 |
| \(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.
Warp-Sum(\(\mathsf{value}\))
- for \(\mathsf{distance} = 16, 8, 4, 2, 1\) {
- \(\mathsf{value} = \mathsf{value} + \) Shuffle-Down\((\mathsf{value}, \mathsf{distance})\) // lane k adds lane k + distance
- }
- 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}\))
- \(\mathsf{lane} = \mathsf{threadIdx{.}x} \bmod 32\) // position in the warp
- \(\mathsf{warpIndex} = \lfloor \mathsf{threadIdx{.}x} / 32 \rfloor\) // warp number in the block
- \(\mathsf{warpTotal} = \) Warp-Sum\((\mathsf{mySum})\)
- if \(\mathsf{lane} = 0\) {
- \(\mathsf{warpSums}[\mathsf{warpIndex}] = \mathsf{warpTotal}\)
- }
- Barrier()
- if \(\mathsf{warpIndex} \ne 0\) {
- return 0 // only warp 0 finishes the sum
- }
- \(\mathsf{value} = \mathsf{warpSums}[\mathsf{lane}]\) if \(\mathsf{lane} \lt 8\), else 0
- return Warp-Sum\((\mathsf{value})\) // the block sum, in thread 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.
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.
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.
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.
| Design | Bytes per pair | Rust time | Rust rate | C++ time | C++ rate |
|---|---|---|---|---|---|
| map, then reduce | 16 | 3.334 ms | 80.5 GB/s | 3.096 ms | 86.7 GB/s |
| fused, tree in shared memory | 8 | 1.409 ms | 95.2 GB/s | 1.412 ms | 95.1 GB/s |
| fused, warp shuffles | 8 | 1.405 ms | 95.5 GB/s | 1.456 ms | 92.2 GB/s |
| fused, atomic combine | 8 | 1.405 ms | 95.5 GB/s | 1.389 ms | 96.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.
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.
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
- Compute the least time of the fused dot product of \(2^{26}\) pairs on your GPU from its
memory bandwidth. Change
Nin both programs and compare. - Change both programs to
f64. The fused kernel then reads 16 bytes per pair. Is its time twice that of thef32version? - Change
GRIDfrom 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? - In Listing 15.2, which cells does thread 5 read and write in each of the 8 steps? In which steps is it idle?
- 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?
- Prove that Block-Sum returns the sum of the 256 values to thread 0, using Theorem 15.1 for each warp.
- 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.