Chapter 21: Scan and Stream Compaction
A scan turns a list of numbers into the list of its running totals. It is one of the most widely used building blocks of parallel programs, because a running total answers the question “how many elements come before this one?”, and the answer to that question decides where each element is written when a program packs, sorts or distributes data. The sequential algorithm for a scan is a single loop, and every iteration of that loop needs the result of the iteration before it. At first sight, therefore, a scan looks like the opposite of a parallel computation.
In this chapter, we derive 2 parallel scans from the sequential loop, using one example of 8 small integers throughout, so that every number can be checked by hand. The first, the Hillis-Steele scan, takes the fewest steps. The second, the Blelloch scan, performs no more additions than necessary, up to a factor of 2. We then show why each barrier of these algorithms is needed, by removing it and following the wrong values that appear, and we prove 1 of the 2 scans correct. After that, we extend both scans to arrays of any length, and we use the scan for stream compaction, the removal of unwanted elements from an array. Finally, we implement every algorithm in Rust with cuda-oxide and in CUDA C++, and we measure it.
This chapter covers
- inclusive and exclusive scans, worked by hand on 8 values
- the dependence chain of the sequential scan, and how associativity breaks it
- the Hillis-Steele and Blelloch scans, their work and their steps
- the barrier and the second buffer of a scan, broken one at a time, and a proof of correctness
- the scan of an array of many blocks
- stream compaction with a scan, and with warp votes
- measured times on 16,777,216 values, and why they differ
The code of the chapter is in
code/oxide/ch21_scan_compaction/
for Rust and in
code/cuda/ch21_scan_compaction/
for C++. In Section 8.7, we already built a fast scan from warp shuffles. In this chapter, we
derive the scan from the beginning, and we reuse the kernel of Chapter 8 as the third of our
measured methods.
21.1 The problem
21.1.1 A worked example
Throughout the chapter, we use the same 8 values, which we call \(x\):
\[ x = (3,\ 1,\ 7,\ 0,\ 4,\ 1,\ 6,\ 3). \]
We number the positions from 0, so that \(x_0 = 3\) is the first value, \(x_1 = 1\) the second, and \(x_7 = 3\) the last. The running totals of these values are found by walking along the list and adding each value to the total so far. The first total is 3. Adding 1 gives 4, adding 7 gives 11, and adding 0 leaves the total at 11. In the same way, the remaining 4 values give the totals 15, 16, 22 and 25. The last total, 25, is the sum of all 8 values.
There are two ways to line up these totals with the input. In the first, the total at position \(i\) includes the value \(x_i\) itself, so that position 4 holds \(3 + 1 + 7 + 0 + 4 = 15\). In the second, the total at position \(i\) stops just before \(x_i\), so that position 4 holds \(3 + 1 + 7 + 0 = 11\). In the second form, position 0 has no values before it and holds the empty sum, 0. Figure 21.1 shows both forms.
We will return to 2 of these totals several times, \(y_2 = 11\) at position 2 and \(y_6 = 22\) at position 6. In particular, in Section 21.6, we will see 2 faulty kernels that produce 8 and 14 in place of \(y_2 = 11\).
21.1.2 Definitions
We write ranges of integers as in the rest of the book: \([a, b)\) is the set of integers
\(a, a + 1, \ldots, b - 1\), like a..b in Rust. For example, \([0, 8)\) is the set of the 8
positions 0 to 7 of our example. Indices start at 0.
Definition 21.1 Inclusive scan. The inclusive scan of an array \(x\) of \(n\) values is the array \(y\) of \(n\) values with
\[ y_i = x_0 + x_1 + \cdots + x_i, \qquad i \in [0, n). \]
Example. For our 8 values, \(y = (3, 4, 11, 11, 15, 16, 22, 25)\).
| Symbol | Meaning | In the example |
|---|---|---|
| \(n\) | number of values in the array | 8 |
| \(i\) | a position in the array, from 0 to \(n - 1\) | 4 |
| \(x_i\) | the input value at position \(i\) | \(x_4 = 4\) |
| \(y_i\) | the sum of the inputs at positions 0 to \(i\), \(x_i\) included | \(y_4 = 15\) |
Definition 21.2 Exclusive scan. The exclusive scan of \(x\) is the array \(e\) with \(e_0 = 0\) and
\[ e_i = x_0 + x_1 + \cdots + x_{i-1}, \qquad i \in [1, n). \]
Example. For our 8 values, \(e = (0, 3, 4, 11, 11, 15, 16, 22)\).
The value \(e_i\) is the sum of the inputs that come strictly before position \(i\). In our example, \(e_4 = x_0 + x_1 + x_2 + x_3 = 3 + 1 + 7 + 0 = 11\), and \(e_0 = 0\), because no input comes before position 0.
The 2 scans differ by exactly 1 term at every position, namely \(x_i\), so each of them is obtained from the other with 1 operation per element:
\[ e_i = y_i - x_i, \qquad y_i = e_i + x_i. \]
At position 4, for example, \(e_4 = 15 - 4 = 11\) and \(y_4 = 11 + 4 = 15\). Scans are also called prefix sums, because \(y_i\) is the sum of the prefix of the array that ends at position \(i\). The same definitions apply to operators other than addition, such as the maximum. In this chapter, we use addition throughout, as do the applications of this chapter and of Chapter 22.
The exclusive scan has a direct use, which motivates much of this part of the book. Suppose that some of the values are to be copied, in their original order, to the front of another array. We write 1 for every value that is copied and 0 for every other value. The exclusive scan of these 1s and 0s at position \(i\) is then the number of copied values before position \(i\), and that number is exactly the position in the output array to which value \(i\) must be copied. In Section 21.8, we build stream compaction on this fact, and in Chapter 22, we build a radix sort on it.
Exercises
21.1 Compute the inclusive and the exclusive scan of \((2, 0, 5, 1, 1, 3, 0, 4)\).
21.2 The maximum is also an operator for a scan. Compute the inclusive max-scan of our 8 values.
What does \(y_i\) mean for this operator?
21.3 Show that the last value of the inclusive scan equals the last value of the exclusive scan
plus the last input. Which value of our example does this give?
21.2 The sequential algorithm
21.2.1 The loop
On a CPU, Definition 21.1 becomes a single loop. The first total is the first input, and each iteration of the loop adds the next input to the previous total.
Sequential-Scan(\(x, y, n\))
- \(y_0 = x_0\)
- for \(i \in [1, n)\) {
- \(y_i = y_{i-1} + x_i\) // 1 addition, needs line 3 of the previous iteration
- }
In our example, the iteration with \(i = 4\) computes \(y_4 = y_3 + x_4 = 11 + 4 = 15\). Line 3 executes once for each \(i\) from 1 to \(n - 1\), that is, \(n - 1\) times, so the loop performs \(n - 1\) additions, 7 for our example. No algorithm can do with fewer additions, because each of the inputs \(x_1\) to \(x_7\) has to enter the final total through at least 1 addition.
21.2.2 The dependence chain
On a parallel machine, the number of additions is not the main cost. The main cost is the order in which the additions must happen. Consider the iteration that computes \(y_4 = 15\). It adds \(x_4 = 4\) to \(y_3 = 11\), and so it cannot start until \(y_3\) is known. The value \(y_3\), in turn, needs \(y_2\), which needs \(y_1\). Figure 21.2 draws these dependences. Every addition waits for the one before it, and the 7 additions form a single chain.
To compare algorithms by both of these costs, we give them names.
Definition 21.3 Work and steps. The work of an algorithm is the number of operations it performs. Its steps are the length of its longest chain of operations in which each needs the result of the one before. A machine with enough processors can execute an algorithm in as many rounds as it has steps, but not in fewer.
Example. Sequential-Scan of our 8 values does a work of 7 additions in 7 steps.
A GPU executes thousands of threads at once, and it is fast only when it has work for all of them. Sequential-Scan, however, offers only 1 addition per step. For an array of 1,024 values, it needs 1,023 steps, each of which waits for the one before, and during each step every other thread of the GPU is idle. To make use of the GPU, we therefore need an algorithm whose number of steps grows much more slowly than \(n\).
Exercises
21.4 How many additions and how many steps does Sequential-Scan need for \(n = 2^{20}\)?
21.5 The sum of all \(n\) values is the last output of the scan. In Chapter 15, we computed a sum in
\(\log_2 n\) steps. Why does the tree of a sum not give all \(n\) outputs of a scan?
21.3 Breaking the chain
21.3.1 1 thread per output
Recall that a kernel is a function that the GPU runs many times at once, and that each of these runs is a thread, with its own index and its own variables. The most direct parallel scan gives each output its own thread, and lets thread \(i\) add up the inputs \(x_0\) to \(x_i\) on its own.
Direct-Scan(\(x, y, n\))
- \(i\) = the index of this thread // 1 thread per output
- \(sum = 0\)
- for \(j \in [0, i]\) {
- \(sum = sum + x_j\) // \(i + 1\) reads of \(x\)
- }
- \(y_i = sum\)
In this kernel, no thread waits for another, so the threads may run in any order. Consider, however, thread 7. It reads all 8 values and performs 8 additions in a chain, which is exactly the chain of Sequential-Scan, so the number of steps has not changed. The work, on the other hand, has grown. Thread \(i\) reads \(i + 1\) values, so the 8 threads together read \(1 + 2 + \cdots + 8 = 36\) values. For \(n\) values, the kernel reads \(n(n + 1)/2\) of them, which for 1,024 values amounts to 524,800 reads of only 1,024 different numbers.
The waste is easy to see in the example. Thread 3 computes the sum \(3 + 1 + 7 + 0 = 11\) of the first 4 values, and threads 4, 5, 6 and 7 each compute the same sum again from the beginning. In general, each thread rebuilds a total that another thread already holds.
21.3.2 Regrouping a sum
Thread 7 needs \(y_7 = 3 + 1 + 7 + 0 + 4 + 1 + 6 + 3\). Since the result of an addition does not depend on how its terms are grouped, we may write
\[ y_7 = \underbrace{(3 + 1 + 7 + 0)}_{11} + \underbrace{(4 + 1 + 6 + 3)}_{14} = 25. \]
The left group is the sum of the values at positions 0 to 3, and the right group is the sum of the values at positions 4 to 7. Each group can itself be split into 2 pairs, which gives the 4 pair sums \(3 + 1 = 4\), \(7 + 0 = 7\), \(4 + 1 = 5\) and \(6 + 3 = 9\). These 4 additions do not depend on one another, so they can be performed at the same time. Figure 21.3 draws the result. It contains the same 7 additions as the chain of Figure 21.2, arranged as a tree of 3 levels instead of a chain of 7.
The property of addition that allows this regrouping has a name, and we will use it repeatedly.
Definition 21.4 Associative operator. An operator \(\oplus\) is associative if \((a \oplus b) \oplus c = a \oplus (b \oplus c)\) for all \(a\), \(b\), \(c\). The result of combining a list with an associative operator then depends only on the order of the list, not on how its terms are grouped.
Example. Integer addition is associative: \((3 + 1) + 7 = 3 + (1 + 7) = 11\).
Each node of the tree in Figure 21.3 holds the sum of the inputs over a range of consecutive positions. We need a short name for such a sum.
Definition 21.5 Range sum. For \(a \le b\), the range sum \(S[a..b]\) is \(x_a + x_{a+1} + \cdots + x_b\), the sum of the inputs at positions \(a\) to \(b\), both included. Because addition is associative, for every \(m\) with \(a \le m < b\),
\[ S[a..b] = S[a..m] + S[m+1..b]. \]
Example. \(S[0..7] = S[0..3] + S[4..7] = 11 + 14 = 25\), and \(y_i = S[0..i]\).
| Symbol | Meaning | In the example |
|---|---|---|
| \(a\) | first position of the range | 0 |
| \(b\) | last position of the range, included | 7 |
| \(m\) | last position of the left part; the right part begins at \(m + 1\) | 3 |
| \(S[a..m]\) | sum of the left part, positions \(a\) to \(m\) | \(S[0..3] = 11\) |
| \(S[m+1..b]\) | sum of the right part, positions \(m + 1\) to \(b\) | \(S[4..7] = 14\) |
In words, the sum over a range is the sum over its left part plus the sum over its right part, wherever we cut the range. Note also that the inclusive scan is a range sum that always starts at position 0: \(y_i = S[0..i]\), so that, for example, \(y_4 = S[0..4] = 15\).
Integer addition is exactly associative, which is why every program of this chapter can check its result against the CPU value by value. Floating-point addition is associative only approximately, because every addition rounds its result. In Section 8.2, we measured how much a regrouped float sum changes.
We can now state the idea on which the first parallel scan is built.
Key observation A thread that knows the range sums of 2 adjacent ranges obtains the range sum of their union with 1 addition. If, at every step, every thread doubles the length of the range it knows by adding the range sum held by another thread, then after \(\log_2 n\) steps every thread \(i\) holds \(S[0..i] = y_i\).
For our 8 values, \(\log_2 8 = 3\), so 3 steps suffice: the ranges grow from length 1 to length 2, then 4, then 8.
Exercises
21.6 Draw the tree of Figure 21.3 for \(y_5\). Which range sums of the figure can it reuse?
21.7 How many reads does Direct-Scan perform for \(n = 4{,}096\)? How many steps does it need?
21.4 The Hillis-Steele scan
21.4.1 Doubling the ranges
We now turn the key observation into an algorithm. Each position \(i\) keeps 1 value. At the start, this value is the input \(x_i\), which is the range sum \(S[i..i]\) of the range of length 1 that ends at \(i\).
In the first step, every position \(i \ge 1\) adds the value of position \(i - 1\), its left neighbor. For example, position 7 adds \(S[6..6] = 6\) to its own \(S[7..7] = 3\), and then holds \(S[6..7] = 9\). After this step, every position holds the sum of a range of length 2 that ends at it.
In the second step, every position \(i \ge 2\) adds the value of position \(i - 2\), which is the sum of the 2 values just before its own pair. Position 7 adds \(S[4..5] = 5\) and then holds \(S[4..7] = 14\), the sum of a range of length 4.
In the third step, every position \(i \ge 4\) adds the value of position \(i - 4\). Position 7 adds \(S[0..3] = 11\) and then holds \(S[0..7] = 25\), which is \(y_7\).
We call the distance between a position and the position whose value it adds the offset of the step, and write it \(\mathsf{distance}\). In our example, the offsets are \(\mathsf{distance} = 1\), 2 and 4. A position whose index is smaller than the offset has no partner, because position \(i - \mathsf{distance}\) would be negative. Such a position already holds the sum of a range that starts at position 0, so its value is final, and it keeps it. Figure 21.4 shows all 3 steps on our values, with the range that each cell sums written under the cell.
After the step with offset 4, the range of every cell in the last row starts at position 0, so the last row is the inclusive scan. This algorithm is due to Hillis and Steele, and it is called the Hillis-Steele scan.
21.4.2 Blocks, shared memory and the barrier
Every step reads the values that the previous step wrote, and those values were written by other threads. The threads therefore need a memory that all of them can read and write, and a way to wait for each other between steps. The GPU provides both, but only among the threads of 1 block.
Definition 21.6 Block and shared memory. A block is a group of up to 1,024 threads that run on the same streaming multiprocessor (SM) of the GPU. Shared memory is a small memory of each SM, a few cycles away, that every thread of a block can read and write and that no thread of another block can access.
Example. We scan our 8 values with 1 block of 8 threads, thread \(i\) for position \(i\), and keep the values in shared memory.
Definition 21.7 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. In cuda-oxide, a
barrier is written thread::sync_threads(), and in CUDA C++, __syncthreads().
Example. With a barrier at the end of each step, no thread starts the step with offset 2 until all 8 threads have finished the step with offset 1.
A second difficulty remains. A step reads the values of the previous step and writes new ones. If the new values overwrite the old ones in the same array, a thread may read a value that its neighbor has already replaced with the new value of the current step. We avoid this with 2 arrays. Every step reads 1 array and writes the other, and the next step exchanges their roles.
Definition 21.8 Double buffer. A double buffer is a pair of arrays \(\mathsf{current}\) and \(\mathsf{next}\) in which each step of an algorithm reads only \(\mathsf{current}\) and writes only \(\mathsf{next}\), after which the 2 names are exchanged.
Example. In the step with offset 1, thread 2 reads \(\mathsf{current}[2] = 7\) and \(\mathsf{current}[1] = 1\) and writes \(\mathsf{next}[2] = 8\); \(\mathsf{current}[1]\) keeps the value 1 until the step is over, whatever thread 1 does.
21.4.3 The algorithm
Every thread of the block executes the following procedure. The arrays \(\mathsf{current}\) and \(\mathsf{next}\) are stored in shared memory, and \(\mathsf{distance}\) is the offset of the current step.
Hillis-Steele-Scan(\(x, y, n\))
- \(i\) = the index of this thread in the block // 1 thread per value, \(n\) threads
- \(\mathsf{current}[i] = x_i\)
- Barrier() // every value is in \(\mathsf{current}\)
- for \(\mathsf{distance} = 1, 2, 4, \ldots\) while \(\mathsf{distance} < n\) {
- if \(i \ge \mathsf{distance}\): \(\mathsf{next}[i] = \mathsf{current}[i] + \mathsf{current}[i - \mathsf{distance}]\) // reads only \(\mathsf{current}\), writes only \(\mathsf{next}\)
- else: \(\mathsf{next}[i] = \mathsf{current}[i]\)
- Barrier() // the step is complete
- exchange the names \(\mathsf{current}\) and \(\mathsf{next}\)
- }
- \(y_i = \mathsf{current}[i]\)
Line 2 copies the input into shared memory, and the barrier in line 3 makes sure that every value is there before any thread reads the value of a neighbor. Lines 5 and 6 perform 1 step of Figure 21.4. For example, in the step with \(\mathsf{distance} = 2\), thread 6 executes line 5 and computes \(\mathsf{next}[6] = \mathsf{current}[6] + \mathsf{current}[4] = 7 + 4 = 11\), while thread 1 has \(i < \mathsf{distance}\) and executes line 6, which copies \(\mathsf{current}[1] = 4\) unchanged. Line 7 is the barrier that ends the step, and line 8 makes the array written in this step the input of the next step. In Section 21.6, we remove line 7 and then line 8, and we show the wrong values that each removal produces.
21.4.4 Counting the work
In the step with offset \(\mathsf{distance}\), the threads with \(i \ge \mathsf{distance}\) perform 1 addition each, and there are \(n - \mathsf{distance}\) such threads. In our example, the 3 steps therefore perform \(8 - 1 = 7\), \(8 - 2 = 6\) and \(8 - 4 = 4\) additions, \(7 + 6 + 4 = 17\) in all, in 3 steps, whereas the sequential loop performs 7 additions in 7 steps. In general, when \(n\) is a power of 2, the offsets are \(\mathsf{distance} = 2^k\) for \(k = 0, 1, \ldots, \log_2 n - 1\), that is, \(1, 2, \ldots, n/2\). There are \(\log_2 n\) steps, and the work is
\[ \sum_{k=0}^{\log_2 n - 1} (n - 2^k) = n \log_2 n - (n - 1). \]
| Symbol | Meaning | In the example |
|---|---|---|
| \(k\) | number of the step, starting from 0 | 0, 1 or 2 |
| \(2^k\) | the offset \(\mathsf{distance}\) of step \(k\) | 1, 2 or 4 |
| \(n - 2^k\) | additions in step \(k\), 1 per thread with \(i \ge \mathsf{distance}\) | 7, 6 or 4 |
| \(\log_2 n\) | number of steps | \(\log_2 8 = 3\) |
The right-hand side follows because the \(\log_2 n\) terms \(n\) add up to \(n \log_2 n\), and the offsets \(1 + 2 + \cdots + n/2\) add up to \(n - 1\). For our example, this gives \(8 \cdot 3 - 7 = 17\), as counted above. For a block of 1,024 values, the scan takes 10 steps and 11 barriers, and it performs \(1{,}024 \cdot 10 - 1{,}023 = 9{,}217\) additions, where the sequential loop performs 1,023. The Hillis-Steele scan thus pays for its small number of steps with about \(\log_2 n\) times the work of the sequential loop.
Exercises
21.8 Carry out Hillis-Steele-Scan on \((2, 0, 5, 1, 1, 3, 0, 4)\) and write the range under
each cell, as in Figure 21.4.
21.9 How many additions does Hillis-Steele-Scan perform for \(n = 16\), and how many of them
does the sequential loop need?
21.10 In which step does position 5 reach its final value? What does it do in the remaining
steps?
21.5 The Blelloch scan
21.5.1 Work efficiency
An algorithm is work-efficient if it performs, up to a constant factor, no more operations than the best sequential algorithm. The Hillis-Steele scan is not work-efficient: on 1,024 values, it performs 9,217 additions, 9 times the 1,023 additions of the sequential loop. A GPU block can absorb some extra work, since many of its threads would otherwise wait. The extra additions, however, still occupy the arithmetic units and, more importantly, shared memory, which line 5 reads twice and writes once for every addition. In 1990, Blelloch described a scan that performs \(2(n - 1)\) additions in \(2 \log_2 n\) steps. For our 8 values, these are 14 additions in 6 steps. The scan works in 2 phases on a single array, which we now describe in turn.
21.5.2 The up-sweep
The first phase builds the tree of Figure 21.3 in place, in the array itself. As before, we call the distance between the 2 positions that are added \(\mathsf{distance}\). At distance 1, every odd position \(\mathsf{right}\) adds the value of position \(\mathsf{right} - 1\), so that positions 1, 3, 5 and 7 receive the pair sums 4, 7, 5 and 9. At distance 2, positions 3 and 7 add the values of positions 1 and 5, and receive \(7 + 4 = 11\) and \(9 + 5 = 14\). At distance 4, position 7 adds the value of position 3 and receives \(14 + 11 = 25\). Figure 21.5 shows the 3 levels.
At each level, the number of additions halves. The up-sweep performs \(4 + 2 + 1 = 7\) additions, and \(n - 1\) in general, the same number as the sequential loop. It leaves the array holding a mixture of results, however. Position 7 holds the total, 25, and position 3 holds \(S[0..3] = 11\), which is \(y_3\). Position 5, on the other hand, holds \(S[4..5] = 5\), which is neither \(y_5 = 16\) nor \(e_5 = 15\). The second phase must complete such totals.
Key observation After the up-sweep, every position in the right half of the array needs, to complete its total, the sum of the whole left half, and that sum, \(S[0..3] = 11\), already sits at position 3. The same holds inside each half and each quarter. Every node of the tree needs the sum of everything to its left. For a left child that sum is its parent’s, and for a right child it is its parent’s plus the total of its left sibling. Passing these sums down the tree takes 1 addition per node, \(n - 1\) in all.
For example, position 5 holds \(S[4..5] = 5\) and lies in the right half. To obtain its exclusive total \(e_5 = S[0..4]\), it lacks the sum of the left half, 11, which sits at position 3, and the value \(x_4 = 4\), which sits at position 4: \(e_5 = 11 + 4 = 15\).
21.5.3 The down-sweep
The second phase starts by setting the last position, the root of the tree, to 0, since nothing lies to the left of the whole array. Then, from the root downwards, the down-sweep visits every pair \((\mathsf{right} - \mathsf{distance}, \mathsf{right})\) of the up-sweep again, in the reverse order of the levels. At each pair, the left position receives the value of the right position, which is the sum of everything to the left of the pair. The right position receives that same value plus the old value of the left position, which is the total of its left sibling. Figure 21.6 shows the 3 levels on our values.
Let us follow position 5 through the down-sweep. At distance 2, the pair (5, 7) holds the values (5, 11). Position 5 receives 11, the sum of everything to the left of the pair, and position 7 receives \(11 + 5 = 16\). At distance 1, the pair (4, 5) holds (4, 11). Position 4 receives 11, and position 5 receives \(11 + 4 = 15\), which is \(e_5\). The last row is the exclusive scan \((0, 3, 4, 11, 11, 15, 16, 22)\), and adding \(x_i\) to each position gives the inclusive scan.
21.5.4 The algorithm
A block of \(n/2\) threads scans \(n\) values, 2 per thread, in 1 array \(\mathsf{cells}\) in shared memory. At each level, every pair is handled by 1 thread. At a given distance, thread \(\mathsf{threadIdx{.}x}\) handles the pair whose right position is
\[ \mathsf{right} = (2 \cdot \mathsf{threadIdx{.}x} + 2) \cdot \mathsf{distance} - 1, \]
and only the first \(n/(2 \cdot \mathsf{distance})\) threads have a pair.
| Symbol | Meaning | In the example, \(\mathsf{distance} = 2\) |
|---|---|---|
| \(\mathsf{threadIdx{.}x}\) | index of the thread in the block, from 0 to \(n/2 - 1\) | 0 to 3 |
| \(\mathsf{distance}\) | distance between the 2 positions of a pair | 2 |
| \(\mathsf{right}\) | right position of the pair of thread \(\mathsf{threadIdx{.}x}\) | 3 for \(\mathsf{threadIdx{.}x} = 0\), 7 for \(\mathsf{threadIdx{.}x} = 1\) |
| \(\mathsf{right} - \mathsf{distance}\) | left position of the pair | 1 for \(\mathsf{threadIdx{.}x} = 0\), 5 for \(\mathsf{threadIdx{.}x} = 1\) |
| \(n/(2 \cdot \mathsf{distance})\) | number of pairs, and of threads with a pair | \(8/4 = 2\) |
The right positions of the pairs at a given distance are spaced \(2 \cdot \mathsf{distance}\) apart, starting at \(2 \cdot \mathsf{distance} - 1\), and the formula numbers them in that order. At distance 2, for instance, thread 0 handles the pair (1, 3) and thread 1 the pair (5, 7), while threads 2 and 3 have no pair, since \(n/(2 \cdot \mathsf{distance}) = 2\).
Blelloch-Scan(\(x, y, n\))
- \(\mathsf{first} = 2 \cdot \mathsf{threadIdx{.}x}\) // this thread owns positions first and first + 1; \(n/2\) threads
- \(\mathsf{cells}[\mathsf{first}] = x_{\mathsf{first}}\), \(\mathsf{cells}[\mathsf{first} + 1] = x_{\mathsf{first}+1}\)
- for \(\mathsf{distance} = 1, 2, 4, \ldots\) while \(\mathsf{distance} < n\) { // up-sweep
- Barrier()
- if \(\mathsf{threadIdx{.}x} < n/(2 \cdot \mathsf{distance})\) {
- \(\mathsf{right} = (2 \cdot \mathsf{threadIdx{.}x} + 2) \cdot \mathsf{distance} - 1\)
- \(\mathsf{cells}[\mathsf{right}] = \mathsf{cells}[\mathsf{right}] + \mathsf{cells}[\mathsf{right} - \mathsf{distance}]\)
- }
- }
- Barrier()
- if \(\mathsf{threadIdx{.}x} = 0\): \(\mathsf{cells}[n - 1] = 0\) // the root: nothing to its left
- for \(\mathsf{distance} = n/2, n/4, \ldots, 1\) { // down-sweep
- Barrier()
- if \(\mathsf{threadIdx{.}x} < n/(2 \cdot \mathsf{distance})\) {
- \(\mathsf{right} = (2 \cdot \mathsf{threadIdx{.}x} + 2) \cdot \mathsf{distance} - 1\)
- \(\mathsf{left} = \mathsf{right} - \mathsf{distance}\)
- \((\mathsf{cells}[\mathsf{left}],\ \mathsf{cells}[\mathsf{right}]) = (\mathsf{cells}[\mathsf{right}],\ \mathsf{cells}[\mathsf{right}] + \mathsf{cells}[\mathsf{left}])\) // swap and add
- }
- }
- Barrier()
- \(y_{\mathsf{first}} = \mathsf{cells}[\mathsf{first}]\), \(y_{\mathsf{first}+1} = \mathsf{cells}[\mathsf{first}+1]\) // the exclusive scan
Lines 3 to 9 are the up-sweep of Figure 21.5, and lines 12 to 19 are the down-sweep of Figure 21.6. Within 1 level, the pairs of different threads do not overlap, so no 2 threads touch the same position between 2 barriers. Line 17 assigns both positions at once from their old values. In code, this means that the old left value must be kept in a register before the left position is overwritten.
21.5.5 Comparing the 3 scans
The up-sweep performs \(n - 1\) additions, and so does the down-sweep, so the Blelloch scan performs \(2(n - 1)\) additions in total. This is 14 for our example and 2,046 for 1,024 values, twice the work of the sequential loop and about 1/4.5 of the work of the Hillis-Steele scan. The Blelloch scan pays for this saving with steps. It has \(2 \log_2 n\) levels, 20 for 1,024 values, and 21 barriers. Figure 21.7 compares the three algorithms.
Figure 21.7 alone does not tell us which of the 2 parallel scans is faster on a GPU. The answer depends on what a step, an addition and a barrier cost on the hardware, and we measure both scans in Section 21.11.
Exercises
21.11 Carry out the up-sweep and the down-sweep on \((2, 0, 5, 1, 1, 3, 0, 4)\).
21.12 At distance 2 of the up-sweep, which threads have a pair, and which positions
do they read and write?
21.13 Why must line 11 set \(\mathsf{cells}[n-1]\) to 0 rather than leave the total there? What would the
last row of Figure 21.6 be without it?
21.6 Correctness
The threads of a block run at different speeds, and they read and write the same slots of shared memory. Without coordination, 2 things can go wrong. A thread can read a slot before the step that fills it is over, or it can read a slot that the current step has already changed. In this section, we remove line 7 of Hillis-Steele-Scan, and then line 8, and we follow each error as it happens on our example.
21.6.1 The barrier at the end of a step
Suppose that we delete line 7, the barrier that ends each step. In the step with offset 1, thread 2 computes \(\mathsf{next}[2] = \mathsf{current}[2] + \mathsf{current}[1] = 7 + 1 = 8\) and moves on to the step with offset 2. In that step, the names have been exchanged, so thread 2 reads the array that was \(\mathsf{next}\) in the previous step, and it needs the value at position 0. Thread 0, however, is running late and has not yet written \(\mathsf{next}[0] = \mathsf{current}[0] = 3\), as Figure 21.8 shows.
The slot still holds whatever it held before the kernel started, and thread 2 computes its new value as \(8 + \mathsf{next}[0]\) from that content. On the GPU we measured, the slot held 0, so the result is \(y_2 = 8\) instead of 11. We removed the barrier from the C++ program and ran it, and it printed the following lines.
$ ./nobarrier # line 7 deleted
scans of 3 1 7 0 4 1 6 3
Hillis-Steele 3 4 8 7 7 6 14 9
Position 2 holds 8, the value predicted by Figure 21.8. The 5 positions after it are wrong as well, because each of them read at least 1 slot too early. The output was the same in 3 runs, and the program reported FAILED for the array of 16,777,216 values. Line 7 prevents this error, since no thread may start a step until every thread has finished the previous one.
21.6.2 The second buffer
Now we restore line 7 and delete line 8 instead, so that every step reads and writes the same array, and line 5 becomes \(\mathsf{current}[i] = \mathsf{current}[i] + \mathsf{current}[i - \mathsf{distance}]\). In the step with offset 1, thread 1 computes \(\mathsf{current}[1] = \mathsf{current}[1] + \mathsf{current}[0] = 1 + 3 = 4\). Thread 2 is late, and when it reads \(\mathsf{current}[1]\), it finds the new value 4 instead of the old value 1, as Figure 21.9 shows.
Thread 2 therefore computes \(\mathsf{current}[2] = 7 + 4 = 11\) instead of 8, and its range now counts \(x_0\) twice. After the step with offset 2, it holds \(11 + 3 = 14\), and we get \(y_2 = 14\) instead of 11. We deleted line 8 from the C++ program and ran it 3 times. The 8 values came out right every time, as in the following output.
$ ./inplace # line 8 deleted
scans of 3 1 7 0 4 1 6 3
Hillis-Steele 3 4 11 11 15 16 22 25
The scan of 16,777,216 values, however, failed in all 3 runs. We added to the program a count of the wrong values and the position of the first one, and the 3 runs printed the following lines.
Hillis-Steele: 16768480 of 16777216 values wrong, first at 8288 (tile 8, position 96)
Hillis-Steele: 16766720 of 16777216 values wrong, first at 6848 (tile 6, position 704)
Hillis-Steele: 16764032 of 16777216 values wrong, first at 6848 (tile 6, position 704)
In almost every tile, every thread read \(\mathsf{current}[i - \mathsf{distance}]\) before the thread that owns that slot had updated it, and the tile was scanned correctly. A single block, scanned on its own 1,000 times in a separate test, never went wrong. In a few of the 16,384 tiles, however, 1 warp updated its values before another warp had read them, as in Figure 21.9, and the wrong total of that tile reached every later value through the tile offsets of Section 21.7. Nothing in the hardware or in CUDA fixes the order of 2 warps inside a step, so a test on a small input cannot show that this kernel is correct. Only an argument about every possible order can, and for the in-place kernel, that argument fails at Figure 21.9.
21.6.3 A proof of correctness
With lines 7 and 8 in place, we can prove that Hillis-Steele-Scan computes the inclusive scan. The idea is to watch the value \(\mathsf{current}[i]\) of 1 thread grow step by step, as in Figure 21.10. At the start of the step with offset \(\mathsf{distance}\), this value is the sum of the last \(\mathsf{distance}\) inputs up to and including position \(i\), or of all inputs from position 0 if there are fewer than \(\mathsf{distance}\) of them. We call this range of inputs the window of thread \(i\). For thread 6, the window has length 1, 2 and 4 at the start of the 3 steps, and it then covers all 7 inputs \(x_0\) to \(x_6\).
The window of \(\mathsf{distance}\) inputs that ends at position \(i\) begins at position \(i - \mathsf{distance} + 1\), but never before position 0. We write its first position as
\[ \ell(i, \mathsf{distance}) = \max(0,\ i - \mathsf{distance} + 1). \]
| Symbol | Meaning | Thread 6 |
|---|---|---|
| \(i\) | position of the thread, and last position of its window | 6 |
| \(\mathsf{distance}\) | offset of the step, and length of the window when it fits | 1, 2, 4, then 8 |
| \(\ell(i, \mathsf{distance})\) | first position of the window | 6, 5, 3, then \(\max(0, -1) = 0\) |
For example, at the start of the step with offset 4, thread 6 holds \(S[\ell(6, 4)..6] = S[3..6] = 0 + 4 + 1 + 6 = 11\), as in Figure 21.10.
Theorem 21.1 When Hillis-Steele-Scan finishes, \(y_i = S[0..i]\) for every \(i \in [0, n)\).
Proof. Write \(\ell(i, \mathsf{distance}) = \max(0, i - \mathsf{distance} + 1)\) for the first position of the window. We show that the loop of lines 4 to 9 maintains the invariant
\[ \mathsf{current}[i] = S[\ell(i, \mathsf{distance})\,..\,i] \quad \text{for every } i \in [0, n), \text{ at the start of the iteration with offset } d. \]
Initialization. Before the first iteration, \(\mathsf{distance} = 1\), and line 2 stored \(\mathsf{current}[i] = x_i = S[i..i]\). The barrier in line 3 makes all \(n\) stores complete before any thread reads \(\mathsf{current}\).
Maintenance. Assume that the invariant holds at the start of the iteration with offset \(\mathsf{distance}\). In lines 5 and 6, each thread reads only \(\mathsf{current}\) and writes only its own slot of \(\mathsf{next}\), so every value it reads is a value from the start of the iteration; this excludes the error of Section 21.6.2. If \(i \ge \mathsf{distance}\), thread \(i\) writes \(S[\ell(i, \mathsf{distance})..i] + S[\ell(i - \mathsf{distance}, \mathsf{distance})..i - \mathsf{distance}]\). The second range ends at \(i - \mathsf{distance}\), 1 position before the first range begins, and it starts at \(\ell(i, 2 \cdot \mathsf{distance})\), so by Definition 21.5 the sum is \(S[\ell(i, 2 \cdot \mathsf{distance})..i]\). If \(i < \mathsf{distance}\), then \(\ell(i, \mathsf{distance}) = \ell(i, 2 \cdot \mathsf{distance}) = 0\), and thread \(i\) copies \(S[0..i]\) unchanged. The barrier in line 7 completes every write to \(\mathsf{next}\) before any thread passes it; this excludes the error of Section 21.6.1. After line 8 exchanges the names, \(\mathsf{current}[i] = S[\ell(i, 2 \cdot \mathsf{distance})..i]\) at the start of the iteration with offset \(2 \cdot \mathsf{distance}\).
Termination. The loop ends with the first offset \(\mathsf{distance} \ge n\). Then \(i - \mathsf{distance} + 1 \le 0\) for every \(i < n\), so \(\ell(i, \mathsf{distance}) = 0\) and \(\mathsf{current}[i] = S[0..i]\), and line 10 stores this value.
The maintenance step can be checked on thread 6 in the step with offset 2. At the start of the step, thread 6 holds \(S[5..6] = 7\), and thread 4 holds \(S[3..4] = 4\). The second range ends at position 4, just before the first begins, so thread 6 writes \(S[3..6] = 7 + 4 = 11\), which is the window of length 4 that the invariant requires at the start of the step with offset 4.
The proof uses each of the 3 barriers and the double buffer exactly once, and it uses no fact about the speed of the threads. The same argument, applied level by level, shows that the Blelloch scan is correct; Exercise 21.16 asks for its invariant. Note, finally, that a barrier works only if every thread of the block reaches it. In both scans, the threads without a partner in a step do not leave the loop. They copy their value, or do nothing, and then wait at the barrier with the others.
Rule Every thread of a block must reach every barrier. Never place a barrier where some threads of the block can skip it, and never let a step read a slot that the same step writes.
Exercises
21.14 Without line 7, could thread 7 read a wrong value in the step with offset 4? Give a
schedule in which it does, and the value of \(y_7\) it produces.
21.15 Explain why the proof of Theorem 21.1 breaks if a thread with \(i < \mathsf{distance}\) leaves the loop
early, even though its value no longer changes.
21.16 State an invariant for the up-sweep of Blelloch-Scan: what does \(s[i]\) hold after the
level with distance \(\mathsf{distance}\)?
21.7 Scanning more than 1 block
21.7.1 Tiles
A block holds at most 1,024 threads, and its threads cooperate only through its own shared memory and its own barriers. The arrays that we want to scan, on the other hand, hold millions of values. We therefore cut the array into tiles of 1,024 values, 1 tile per block, and every block scans its tile on its own. The result is correct inside each tile, but every tile has started its totals from 0, whereas the true total at the first value of a tile must include every value of the earlier tiles.
Figure 21.11 shows how this is repaired, on our 8 values cut into 2 tiles of 4. Tile 0, \((3, 1, 7, 0)\), scans to \((3, 4, 11, 11)\), and tile 1, \((4, 1, 6, 3)\), scans to \((4, 5, 11, 14)\). The last value of each tile scan is the total of the tile, 11 and 14. The inclusive scan of these totals, \((11, 25)\), says that the values before tile 1 add up to 11. Adding 11 to every value of tile 1 gives \((15, 16, 22, 25)\), and the whole scan is then correct.
21.7.2 The algorithm
The scan of the tile totals is itself a scan, of an array 1,024 times shorter than the input, so the procedure can call itself. For example, 16,777,216 values form 16,384 tiles, whose 16,384 totals form 16 tiles, whose 16 totals fit in a single tile. In the following procedure, \(\mathsf{tiles}\) is the number of tiles, \(\mathsf{totals}_{\mathsf{tile}}\) is the total of tile \(\mathsf{tile}\), and \(\mathsf{offsets}\) is the inclusive scan of the totals, so that \(\mathsf{offsets}_{\mathsf{tile}-1}\) is the sum of all values before tile \(\mathsf{tile}\). In our example, \(\mathsf{tiles} = 2\), \(\mathsf{totals} = (11, 14)\), \(\mathsf{offsets} = (11, 25)\), and tile 1 receives \(\mathsf{offsets}_0 = 11\).
Scan(\(x, y, n\))
- \(\mathsf{tiles} = \lceil n / 1024 \rceil\) // the number of tiles
- launch 1 block per tile: scan the tile of \(x\) into \(y\), write its total to \(\mathsf{totals}_{\mathsf{tile}}\)
- if \(\mathsf{tiles} > 1\) {
- Scan(\(\mathsf{totals}, \mathsf{offsets}, \mathsf{tiles}\)) // the tile totals, recursively
- launch 1 block per tile: add \(\mathsf{offsets}_{\mathsf{tile}-1}\) to every value of tile \(\mathsf{tile} \ge 1\)
- }
The 2 launches of lines 2 and 5 take the place of a barrier across blocks, which the GPU does not provide. A kernel launch starts only after the previous launch on the same stream has finished, so line 5 reads totals that are complete.
21.7.3 Counting the traffic
Any scan must read every input value once and write every output once. For values of 4 bytes, this is 8 bytes per value, if nothing else is stored. Scan moves more than this. Line 2 reads the input and writes the tile scans, and line 5 reads the tile scans again and writes them again, so Scan moves 16 bytes per value, plus 1 total per 1,024 values. On 16,777,216 values, the minimum is 134 MB, and Scan moves 268 MB. A scan that passes the total of each tile directly to the next block while the kernel runs, called a single-pass scan, avoids the second pass; in Chapter 11, we measured one from the CUB library.
Exercises
21.17 Carry out Figure 21.11 with 4 tiles of 2 values. What are the tile totals, their scan, and
the offsets?
21.18 How many levels of recursion does Scan need for \(n = 2^{30}\), and how many tiles does
each level have?
21.8 Stream compaction
21.8.1 The problem
Stream compaction takes an array and a condition, and writes the values that satisfy the condition to the front of an output array, in their input order. It appears wherever a computation produces many candidates and keeps a few of them, for example particles that are still inside a simulation, rays that hit a surface, or detections above a threshold. In our example, we keep the values with \(x \ge 3\). These are 3, 7, 4, 6 and 3, at positions 0, 2, 4, 6 and 7, and the output is \((3, 7, 4, 6, 3)\).
On a CPU, compaction is a single loop with a counter \(\mathsf{count}\) of the values written so far.
Sequential-Compact(\(x, \mathsf{out}, n\))
- \(\mathsf{count} = 0\) // values written so far
- for \(i \in [0, n)\) {
- if \(x_i \ge 3\) {
- \(\mathsf{out}_{\mathsf{count}} = x_i\)
- \(\mathsf{count} = \mathsf{count} + 1\)
- }
- }
- return \(\mathsf{count}\) // the number of kept values
The counter \(\mathsf{count}\) forms a chain like the one of Figure 21.2, because the position of a kept value depends on every earlier decision. For example, when line 4 writes \(x_4 = 4\), the counter holds \(\mathsf{count} = 2\), because 2 values, at positions 0 and 2, were kept before it.
Key observation When line 4 writes \(x_i\), the counter \(\mathsf{count}\) equals the number of kept values before position \(i\). With a flag \(f_i\) that is 1 for a kept value and 0 otherwise, that number is the exclusive scan of the flags at \(i\). A parallel scan gives every kept value its output position at once.
Definition 21.9 Flags and scatter. The flag of a value is 1 if the value is kept and 0 if it is removed. A scatter is a write in which each thread writes its value to a position computed from data, rather than to its own index.
Example. The flags of our values for \(x \ge 3\) are \((1, 0, 1, 0, 1, 0, 1, 1)\); their exclusive scan is \((0, 1, 1, 2, 2, 3, 3, 4)\), and \(x_4 = 4\) is scattered to position 2.
21.8.2 The algorithm
The parallel algorithm computes the flags, scans them, and scatters every kept value to its position. In the following procedure, \(f_i\) is the flag of value \(i\) and \(s_i\) is the inclusive scan of the flags, the number of kept values at positions 0 to \(i\).
Parallel-Compact(\(x, \mathsf{out}, n\))
- for every \(i \in [0, n)\) in parallel: \(f_i = 1\) if \(x_i \ge 3\), else 0 // kernel 1
- \(s\) = the inclusive scan of \(f\) // Scan of Section 21.7
- for every \(i \in [0, n)\) in parallel: if \(f_i = 1\): \(\mathsf{out}_{s_i - 1} = x_i\) // kernel 2, a scatter
- return \(s_{n-1}\)
Line 3 uses \(s_i - 1\), the inclusive scan minus the flag 1 of a kept value, which is the exclusive scan at \(i\). For example, \(x_4 = 4\) has \(f_4 = 1\) and \(s_4 = 3\), since 3 values among positions 0 to 4 are kept, and it is written to position \(3 - 1 = 2\). Figure 21.12 follows the algorithm on our values. The 5 kept values read their positions 0, 1, 2, 3 and 4 from the exclusive scan, and the count of kept values is the last inclusive value, \(s_7 = 5\).
Theorem 21.2 Parallel-Compact writes every kept value exactly once, to a distinct position in \([0, c)\), where \(c\) is the number of kept values, and the output keeps the input order.
Proof. Let \(e_i = s_i - f_i\) be the exclusive scan. Take 2 kept values at positions \(i < j\). The kept values before \(j\) include those before \(i\) and \(i\) itself, so \(e_j \ge e_i + 1\): the positions are distinct and increase with the input position, which is the input order. The first kept value has \(e = 0\), and the last has \(e = c - 1\), since \(c - 1\) kept values precede it. Every position therefore lies in \([0, c)\).
In our example, \(c = 5\), and the kept values at positions 2 and 4 receive \(e_2 = 1\) and \(e_4 = 2\). Since the value at position 2 is itself kept, \(e_4\) is at least \(e_2 + 1\).
The proof also describes the mistake to avoid. If line 3 used the inclusive scan \(s_i\) as the position, every value would land 1 position too far to the right. We made this change in the C++ program, and it printed the following lines.
$ ./inclusive # out[s_i] in place of out[s_i - 1]
compaction of 3 1 7 0 4 1 6 3, keep x >= 3
flags 1 0 1 0 1 0 1 1
exclusive 0 1 1 2 2 3 3 4
output 0 3 7 4 6
Position 0 keeps whatever the output buffer held, and the last kept value, 3, goes to position 5, which the program does not read. No error is reported, because position 5 lies inside the buffer of 8 values, and the writes are distinct and in bounds, only wrong. Only the comparison with the CPU result detects the mistake.
Exercises
21.19 Compact \((2, 0, 5, 1, 1, 3, 0, 4)\) with the condition \(x \ge 1\): give the flags,
their exclusive scan and the output.
21.20 Change Parallel-Compact so that it writes the removed values, in order, after the kept
ones. Which position does a removed value at index \(i\) receive?
21.9 Compaction with warp votes
21.9.1 Bytes moved per value
Compaction performs almost no arithmetic, so its time is set by the bytes that it moves between the SMs and global memory. We count them per input value of 4 bytes, when half of the values are kept. Kernel 1 reads the value and writes the flag, which is 8 bytes. The scan reads and writes the flags twice, which is 16 bytes, as we counted in Section 21.7.3. Kernel 2 reads the flag, the scan and the value, which is 12 bytes, and writes half a value on average, 2 bytes, for 14 bytes in all. In total, Parallel-Compact moves \(8 + 16 + 14 = 38\) bytes per value. The least that any compaction must move is 1 read of each value and 1 write of each kept value, which is \(4 + 2 = 6\) bytes, as Figure 21.13 shows.
Most of the 38 bytes are spent on storing the flags and their scan and on reading them back. A method that computes the flags and the positions inside each block, while it reads the values, never has to store them in global memory. The tool for this is the warp vote, which we now introduce.
21.9.2 Warps and ballots
Definition 21.10 Warp and lane. A warp is a group of 32 threads of a block that the SM executes together, 1 instruction for all 32 at a time. Threads \(32 \cdot \mathsf{warp}\) to \(32 \cdot \mathsf{warp} + 31\) of a block form warp \(\mathsf{warp}\). The position of a thread inside its warp, 0 to 31, is its lane.
Example. A block of 256 threads has 8 warps; thread 70 is lane 6 of warp 2.
In the example of Definition 21.10, warp 2 consists of threads \(32 \cdot 2 = 64\) to \(64 + 31 = 95\), and thread 70 lies \(70 - 64 = 6\) places after the first of them. In general, thread \(\mathsf{threadIdx{.}x}\) belongs to warp \(\lfloor \mathsf{threadIdx{.}x} / 32 \rfloor\), and its lane is \(\mathsf{threadIdx{.}x} \bmod 32\).
Definition 21.11 Ballot and population count. A ballot is an instruction that all 32 lanes of a warp execute together, each with a condition; it returns to every lane the same 32-bit word, whose bit \(\mathsf{step}\) is 1 if the condition of lane \(\mathsf{step}\) is true. The population count of a word, popcount for short, is the number of its bits that are 1.
Example. For 8 lanes holding our values, the ballot of \(x \ge 3\) has the bits \((1, 0, 1, 0, 1, 0, 1, 1)\) for lanes 0 to 7, and its popcount is 5.
A ballot thus hands every lane the flags of the whole warp in 1 instruction, and every lane can compute its own exclusive scan from it. Lane \(\mathsf{step}\) needs the number of kept values in the lanes below it, that is, the number of 1 bits among bits 0 to \(\mathsf{step} - 1\) of the ballot. The word \(2^\mathsf{step} - 1\) has exactly these \(\mathsf{step}\) bits set to 1 and all others set to 0. For \(\mathsf{step} = 4\), for example, \(2^4 - 1 = 15\), which is 1111 in binary. Combining the ballot with this mask by a bitwise AND keeps only the bits of the lanes below lane \(\mathsf{step}\), and the popcount of the result is the exclusive scan of lane \(\mathsf{step}\). Figure 21.14 does this for lane 4 of a warp drawn with 8 lanes. The bits of lanes 0 to 3 are \((1, 0, 1, 0)\), their popcount is 2, and \(x_4 = 4\) therefore goes to position 2, as in Figure 21.12.
21.9.3 The algorithm
The method runs two kernels on tiles of 1,024 values, with 1 block of 256 threads per tile, and each thread handles 4 values. The first kernel counts the kept values of every tile. Scan then turns the 16,384 counts into the position of the first kept value of each tile. The second kernel reads the values again and places every kept value after the kept values of the earlier tiles, of the earlier steps of its own tile, of the earlier warps of the step, and of the earlier lanes of its warp.
In the following procedure, \(\mathsf{blockIdx{.}x}\) is the number of the block, which is also the number of its tile, \(\mathsf{threadIdx{.}x}\) is the index of the thread in the block, \(\mathsf{warp}\) is its warp, and \(\mathsf{lane}\) is its lane. The block processes its tile in 4 steps \(\mathsf{step} = 0, 1, 2, 3\) of 256 values each. The shared array \(\mathsf{counts}\) holds the count of kept values of each of the 8 warps in the current step, and \(\mathsf{next}\) is the output position at which the kept values of the current step begin.
Compact-Votes(\(x, \mathsf{out}, n\))
- \(\mathsf{next}\) = the scanned count of tiles \(0\) to \(\mathsf{blockIdx{.}x} - 1\) // 0 for \(\mathsf{blockIdx{.}x} = 0\)
- for \(\mathsf{step} \in [0, 4)\) {
- \(i = 1024 \cdot \mathsf{blockIdx{.}x} + 256 \cdot \mathsf{step} + \mathsf{threadIdx{.}x}\), \(\mathsf{keep} = (i < n\) and \(x_i \ge 3)\)
- \(\mathsf{votes}\) = Ballot(\(\mathsf{keep}\))
- lane 0 of warp \(\mathsf{warp}\): \(\mathsf{counts}[\mathsf{warp}]\) = Popc(\(\mathsf{votes}\)) // \(\mathsf{counts}\) in shared memory
- Barrier()
- \(\mathsf{before} = \mathsf{counts}[0] + \cdots + \mathsf{counts}[\mathsf{warp} - 1]\), \(\mathsf{total} = \mathsf{counts}[0] + \cdots + \mathsf{counts}[7]\)
- if \(\mathsf{keep}\): \(\mathsf{out}[\mathsf{next} + \mathsf{before} + \)Popc\((\mathsf{votes} \wedge (2^{lane} - 1))] = x_i\)
- \(\mathsf{next} = \mathsf{next} + \mathsf{total}\)
- Barrier() // \(\mathsf{counts}\) is read before the next step writes it
- }
| Symbol | Meaning | Thread 70 of block 1, step 2 |
|---|---|---|
| \(\mathsf{blockIdx{.}x}\) | number of the block and of its tile | 1 |
| \(\mathsf{step}\) | step within the tile, 256 values per step | 2 |
| \(\mathsf{threadIdx{.}x}\) | index of the thread in the block | 70 |
| \(i = 1024 \cdot \mathsf{blockIdx{.}x} + 256 \cdot \mathsf{step} + \mathsf{threadIdx{.}x}\) | index of the value the thread handles | \(1{,}024 + 512 + 70 = 1{,}606\) |
| \(\mathsf{warp}\), \(\mathsf{lane}\) | warp of the thread and its lane in the warp | 2 and 6 |
| \(\mathsf{before}\) | kept values in warps 0 to \(\mathsf{warp} - 1\) of this step | \(\mathsf{counts}[0] + \mathsf{counts}[1]\) |
| \(\mathsf{total}\) | kept values in all 8 warps of this step | \(\mathsf{counts}[0] + \cdots + \mathsf{counts}[7]\) |
The index \(i\) in line 3 is built from three parts. The tile of block \(\mathsf{blockIdx{.}x}\) begins at value \(1024 \cdot \mathsf{blockIdx{.}x}\), step \(\mathsf{step}\) begins \(256 \cdot \mathsf{step}\) values later, and thread \(\mathsf{threadIdx{.}x}\) takes the value \(\mathsf{threadIdx{.}x}\) places after that. Line 8 then adds 4 counts to find the output position of a kept value: the kept values of the earlier tiles and earlier steps, which are in \(\mathsf{next}\), those of the earlier warps of the step, which are in \(\mathsf{before}\), and those of the earlier lanes of the warp, which are the popcount of the ballot under the mask \(2^{lane} - 1\).
The order of the positions is therefore the order of the input. Value \(1024 \cdot \mathsf{blockIdx{.}x} + 256 \cdot \mathsf{step} + \mathsf{threadIdx{.}x}\) is processed in step \(\mathsf{step}\), by warp \(\lfloor \mathsf{threadIdx{.}x} / 32 \rfloor\), in lane \(\mathsf{threadIdx{.}x} \bmod 32\). Line 8 orders the kept values first by tile, then by step, then by warp, and then by lane, which is the order of their indices. The argument of Theorem 21.2 then applies unchanged. The first kernel, Count-Kept, consists of lines 2 to 6, with \(\mathsf{next}\) replaced by a running count, followed by the sum of the 8 warp counts.
With half of the values kept, this method reads the values twice and writes the kept values once, which is \(4 + 4 + 2 = 10\) bytes per value, and the scan of 1 count per 1,024 values adds almost nothing. Figure 21.13 compares the two methods.
Exercises
21.21 For a warp of 32 lanes in which lanes 3, 4, 10 and 31 keep their values, give the ballot
as a binary number and the position of lane 10.
21.22 Why does line 3 compute the condition \(i < n\) instead of skipping line 4 for the lanes
beyond the end of the array?
21.10 Implementation
21.10.1 The Hillis-Steele kernel
We now turn the algorithms into code. The following listing implements Hillis-Steele-Scan for tiles of 1,024 values and blocks of 1,024 threads; each block scans 1 tile and writes the total of its tile.
Listing 21.1 The Hillis-Steele scan of 1 tile.
mod kernels {
// ...
/// Hillis-Steele: 1,024 threads, 1 element each, 2 buffers in shared memory.
#[kernel]
#[launch_contract(domain = 1, block = (1024, 1, 1))]
pub fn scan_hillis_steele(
x: &[u32],
mut y: DisjointSlice<u32>,
mut sums: DisjointSlice<u32>,
) {
static mut BUF: SharedArray<u32, 2048> = SharedArray::UNINIT;
let idx = thread::index_1d();
let index = idx.get();
let thread_idx = thread::threadIdx_x() as usize;
// SAFETY: each thread writes only its own slot thread_idx, before the barrier.
unsafe { BUF[thread_idx] = if index < x.len() { x[index] } else { 0 } };
thread::sync_threads();
let mut src = 0;
let mut step = 0usize;
#[unroll]
while step < 10 {
let distance = 1 << step; // 1, 2, 4, ..., 512
let dst = TILE - src;
// SAFETY: a step reads only buffer src and writes only this thread's slot of
// buffer dst; the barrier ends the step before the next one reads buffer dst.
unsafe {
let mut value = BUF[src + thread_idx];
if thread_idx >= distance {
value += BUF[src + thread_idx - distance];
}
BUF[dst + thread_idx] = value;
}
thread::sync_threads();
src = dst;
step += 1;
}
// SAFETY: after the last barrier the buffers are only read.
let total = unsafe { BUF[src + thread_idx] };
if let Some(out) = y.get_mut(idx) {
*out = total;
}
if thread_idx == TILE - 1 {
let block = thread::blockIdx_x() as usize;
// SAFETY: only the last thread of each block writes, at its own block number.
unsafe { *sums.get_unchecked_mut(block) = total };
}
}
// ...
}
// Hillis-Steele: 1,024 threads, 1 element each, 2 buffers in shared memory.
__global__ void scanHillisSteele(const unsigned* x, unsigned* y, unsigned* sums, int n)
{
__shared__ unsigned buf[2 * TILE];
int index = blockIdx.x * TILE + threadIdx.x;
buf[threadIdx.x] = index < n ? x[index] : 0;
__syncthreads();
int src = 0;
for (int distance = 1; distance < TILE; distance *= 2) {
int dst = TILE - src;
unsigned value = buf[src + threadIdx.x];
if (threadIdx.x >= distance) {
value += buf[src + threadIdx.x - distance];
}
buf[dst + threadIdx.x] = value;
__syncthreads(); // the step is complete before any read
src = dst;
}
if (index < n) {
y[index] = buf[src + threadIdx.x];
}
if (threadIdx.x == TILE - 1) {
sums[blockIdx.x] = buf[src + threadIdx.x];
}
}
The load into the first buffer is line 2 of the pseudocode, and the first barrier is line 3. The
loop over step is lines 4 to 9, with \(\mathsf{distance} = 2^{\mathsf{step}}\), so that steps 0, 1
and 2 have the distances 1, 2 and 4. The 2 buffers \(\mathsf{current}\) and \(\mathsf{next}\) are the two halves of 1 shared array of 2,048
values, and src and dst are the offsets of these halves, 0 or 1,024. The assignment
src = dst at the end of the loop is line 8, the exchange of the names. The barrier inside the
loop is line 7, and it stands outside every if, so every thread reaches it. Finally, the last
thread of the block also writes the total of the tile to sums, for line 2 of Scan.
The two languages differ in 3 places. First, shared memory in cuda-oxide is a static mut of type
SharedArray<u32, 2048>, whose length is part of its type, whereas C++ declares a __shared__
array. Every access to the shared array is unsafe in Rust, because the compiler cannot see the
barriers that make the accesses safe, so each unsafe block carries a // SAFETY: comment that
states the argument of Section 21.6.3. Second, the output y has the type DisjointSlice<u32>,
which can be written only through get_mut(idx), with the index that thread::index_1d() returned
to this thread. With one thread per value, the type itself proves that no 2 threads write the same
element, and the write needs no unsafe. The total, which is written at the block number rather
than at the thread index, uses get_unchecked_mut with its own safety comment. Third, the loop
runs over a counter step rather than over distance. For a loop that doubles distance, the cuda-oxide
compiler did not unroll the loop and reported “no recognized induction variable”. A counter that
grows by 1 is recognized, and distance is computed from it.
21.10.2 The Blelloch kernel
The following listing implements Blelloch-Scan for blocks of 512 threads, each of which handles 2 of the 1,024 values of a tile. The kernel converts the exclusive result of line 21 into the inclusive scan by adding the 2 inputs, which each thread kept in registers. Thread 0 also saves the total from \(\mathsf{cells}[1023]\) before line 11 replaces it with 0.
Listing 21.2 The Blelloch scan of 1 tile.
mod kernels {
// ...
/// Blelloch: 512 threads, 2 elements each, 1 buffer; an up-sweep, then a down-sweep.
#[kernel]
#[launch_contract(domain = 1, block = (512, 1, 1))]
pub fn scan_blelloch(
x: &[u32],
mut y: DisjointSlice<u32>,
mut sums: DisjointSlice<u32>,
) {
static mut CELLS: SharedArray<u32, 1024> = SharedArray::UNINIT;
let thread_idx = thread::threadIdx_x() as usize;
let block = thread::blockIdx_x() as usize;
let index = block * TILE + 2 * thread_idx;
let first = if index < x.len() { x[index] } else { 0 };
let second = if index + 1 < x.len() { x[index + 1] } else { 0 };
// SAFETY: each thread writes only its own 2 slots, before a barrier.
unsafe {
CELLS[2 * thread_idx] = first;
CELLS[2 * thread_idx + 1] = second;
}
let mut step = 0usize;
#[unroll]
while step < 10 {
let distance = 1 << step; // up-sweep: 1, 2, 4, ..., 512
thread::sync_threads();
if thread_idx < TILE / (2 * distance) {
let right = (2 * thread_idx + 2) * distance - 1;
// SAFETY: at each distance, the pairs (right - distance, right) of
// different threads are disjoint, and the barriers separate the levels.
unsafe { CELLS[right] += CELLS[right - distance] };
}
step += 1;
}
thread::sync_threads();
if thread_idx == 0 {
// SAFETY: thread 0 alone touches slot TILE - 1 between 2 barriers.
unsafe {
*sums.get_unchecked_mut(block) = CELLS[TILE - 1];
CELLS[TILE - 1] = 0;
}
}
let mut step = 0usize;
#[unroll]
while step < 10 {
let distance = 512 >> step; // down-sweep: 512, 256, ..., 1
thread::sync_threads();
if thread_idx < TILE / (2 * distance) {
let right = (2 * thread_idx + 2) * distance - 1;
// SAFETY: as in the up-sweep, each pair belongs to 1 thread per level.
unsafe {
let left = CELLS[right - distance];
CELLS[right - distance] = CELLS[right];
CELLS[right] += left;
}
}
step += 1;
}
thread::sync_threads();
// SAFETY: after the last barrier CELLS is only read; each thread alone writes its 2
// elements of y, and both lie below y.len() when the test passes.
unsafe {
if index < y.len() {
*y.get_unchecked_mut(index) = CELLS[2 * thread_idx] + first;
}
if index + 1 < y.len() {
*y.get_unchecked_mut(index + 1) = CELLS[2 * thread_idx + 1] + second;
}
}
}
// ...
}
// Blelloch: 512 threads, 2 elements each, 1 buffer; an up-sweep, then a down-sweep.
__global__ void scanBlelloch(const unsigned* x, unsigned* y, unsigned* sums, int n)
{
__shared__ unsigned cells[TILE];
int index = blockIdx.x * TILE + 2 * threadIdx.x;
unsigned first = index < n ? x[index] : 0;
unsigned second = index + 1 < n ? x[index + 1] : 0;
cells[2 * threadIdx.x] = first;
cells[2 * threadIdx.x + 1] = second;
for (int distance = 1; distance < TILE; distance *= 2) {
__syncthreads();
if (threadIdx.x < TILE / (2 * distance)) {
int right = (2 * threadIdx.x + 2) * distance - 1;
cells[right] += cells[right - distance];
}
}
__syncthreads();
if (threadIdx.x == 0) {
sums[blockIdx.x] = cells[TILE - 1];
cells[TILE - 1] = 0;
}
for (int distance = TILE / 2; distance >= 1; distance /= 2) {
__syncthreads();
if (threadIdx.x < TILE / (2 * distance)) {
int right = (2 * threadIdx.x + 2) * distance - 1;
unsigned left = cells[right - distance];
cells[right - distance] = cells[right];
cells[right] += left;
}
}
__syncthreads();
if (index < n) {
y[index] = cells[2 * threadIdx.x] + first; // exclusive plus own: inclusive
}
if (index + 1 < n) {
y[index + 1] = cells[2 * threadIdx.x + 1] + second;
}
}
The loops of the up-sweep and the down-sweep are lines 3 to 9 and lines 12 to 19 of the
pseudocode, with right = (2 * thread_idx + 2) * distance - 1 as in line 6. The swap-and-add of line 17 keeps the old
left value in the register left before it overwrites the left position. We let each thread write 2
elements of y, at \(\mathsf{first}\) and \(\mathsf{first} + 1\), which are not the index of the
thread, so the Rust kernel writes them through get_unchecked_mut, and the safety comment states
that the 2 positions belong to that thread alone.
21.10.3 The scan of many tiles
The following listing implements Scan of Section 21.7.2 on the host. The first function launches the kernel that scans every tile, and the second function is the recursive procedure itself. The 3 tile kernels have the same interface, so the functions take the method as a parameter.
Listing 21.3 The scan of an array of any length.
/// Scans every tile of 1,024 elements on its own and writes the tile totals.
fn scan_tiles(
module: &Module,
stream: &Arc<CudaStream>,
method: Method,
x: &DeviceBuffer<u32>,
y: &mut DeviceBuffer<u32>,
sums: &mut DeviceBuffer<u32>,
) -> Result<(), Error> {
let tiles = x.len().div_ceil(TILE) as u32;
match method {
Method::HillisSteele => {
let grid = LaunchConfig1D::new(tiles, 1024, 0);
let config = module.prepare_scan_hillis_steele(grid)?;
module.scan_hillis_steele(stream, &config, x, y, sums)?;
}
Method::Blelloch => {
let grid = LaunchConfig1D::new(tiles, 512, 0);
let config = module.prepare_scan_blelloch(grid)?;
module.scan_blelloch(stream, &config, x, y, sums)?;
}
Method::Warps => {
let grid = LaunchConfig1D::new(tiles, 256, 0);
let config = module.prepare_scan_warps(grid)?;
module.scan_warps(stream, &config, x, y, sums)?;
}
}
Ok(())
}
/// Inclusive scan: the tiles, then the tile totals (by the same function), then offsets.
fn scan(
module: &Module,
stream: &Arc<CudaStream>,
method: Method,
x: &DeviceBuffer<u32>,
y: &mut DeviceBuffer<u32>,
levels: &mut [(DeviceBuffer<u32>, DeviceBuffer<u32>)],
) -> Result<(), Error> {
let tiles = x.len().div_ceil(TILE) as u32;
let ((totals, scanned), rest) = levels.split_first_mut().ok_or("no level left")?;
scan_tiles(module, stream, method, x, y, totals)?;
if tiles > 1 {
scan(module, stream, method, totals, scanned, rest)?;
let config = module.prepare_add_offsets(LaunchConfig1D::new(tiles, 256, 0))?;
module.add_offsets(stream, &config, y, scanned)?;
}
Ok(())
}
// Scans every tile of 1,024 elements on its own and writes the tile totals.
void scanTiles(Method method, const unsigned* x, unsigned* y, unsigned* sums, int n)
{
int tiles = (n + TILE - 1) / TILE;
if (method == HILLIS_STEELE) {
scanHillisSteele<<<tiles, TILE>>>(x, y, sums, n);
} else if (method == BLELLOCH) {
scanBlelloch<<<tiles, TILE / 2>>>(x, y, sums, n);
} else {
scanWarps<<<tiles, 256>>>(x, y, sums, n);
}
}
// Inclusive scan of n elements: the tiles, then the tile totals (in place), then offsets.
void scan(Method method, const unsigned* x, unsigned* y, int n, unsigned* scratch)
{
int tiles = (n + TILE - 1) / TILE;
scanTiles(method, x, y, scratch, n);
if (tiles > 1) {
scan(method, scratch, scratch, tiles, scratch + tiles);
addOffsets<<<tiles, 256>>>(y, scratch, n);
}
}
The C++ function scans the tile totals in place, in scratch, which holds every level of the
recursion one after another. A Rust function, however, cannot borrow 1 buffer as both its input
&[u32] and its output DisjointSlice<u32>. The Rust version therefore gives each level its own
pair of buffers, totals and scanned, which scan_levels allocates once before any timing
starts, and it hands the remaining levels to the recursive call with split_first_mut. Both
versions launch the three kernels on 1 stream, so each launch starts after the previous one has
finished.
21.10.4 The compaction kernels
The following listing implements line 3 of Parallel-Compact, the scatter, in which every thread whose flag is 1 writes its value to the position given by the scan.
Listing 21.4 The scatter of a compaction.
mod kernels {
// ...
/// Writes each kept element at its exclusive scan: the inclusive scan minus its flag 1.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn scatter_kept(
x: &[u32],
flags: &[u32],
scanned: &[u32],
mut out: DisjointSlice<u32>,
) {
let index = thread::index_1d().get();
if index < x.len() && flags[index] == 1 {
let at = (scanned[index] - 1) as usize;
// SAFETY: the kept elements receive the distinct positions 0 to count - 1,
// and out holds x.len() >= count elements.
unsafe { *out.get_unchecked_mut(at) = x[index] };
}
}
// ...
}
// Writes each kept element at its exclusive scan, the inclusive scan minus its flag of 1.
__global__ void scatterKept(const unsigned* x, const unsigned* flags,
const unsigned* scanned, unsigned* out, int n)
{
int index = blockIdx.x * blockDim.x + threadIdx.x;
if (index < n && flags[index] == 1) {
out[scanned[index] - 1] = x[index];
}
}
Thread \(i\) writes element \(s_i - 1\) of the output, a position computed from the contents of
the scan buffer. No type can express a property of the contents of a buffer, so DisjointSlice
cannot prove that the positions are distinct, and the write uses get_unchecked_mut. Its safety
comment is Theorem 21.2: the kept values receive the distinct positions 0 to \(c - 1\), and the
output holds \(n \ge c\) elements. This argument depends on the scan being complete when the
scatter runs, which the single stream guarantees.
The next listing implements Compact-Votes. Each block processes its tile in 4 steps, and in each step, it computes the output positions with a ballot and the counts of its 8 warps.
Listing 21.5 Compaction with warp votes.
mod kernels {
// ...
/// Writes the kept elements of each tile in order, after those of the earlier tiles.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn compact_votes(
x: &[u32],
threshold: u32,
scanned: &[u32],
mut out: DisjointSlice<u32>,
) {
static mut WARPS: SharedArray<u32, 8> = SharedArray::UNINIT;
let tid = thread::threadIdx_x() as usize;
let lane = warp::lane_id();
let warp = tid / 32;
let block = thread::blockIdx_x() as usize;
let below = (1u32 << lane) - 1; // the lanes to the left of this one
let mut next = if block > 0 { scanned[block - 1] } else { 0 };
let mut step = 0;
#[unroll]
while step < 4 {
let index = block * TILE + step * 256 + tid;
let keep = index < x.len() && x[index] >= threshold;
let votes = warp::ballot(keep);
if lane == 0 {
// SAFETY: lane 0 of each warp writes its own slot, before the barrier.
unsafe { WARPS[warp] = votes.count_ones() };
}
thread::sync_threads();
let mut before = 0;
let mut total = 0;
let mut other = 0;
#[unroll]
while other < 8 {
// SAFETY: between the 2 barriers the slots are only read.
let count = unsafe { WARPS[other] };
before += if other < warp { count } else { 0 };
total += count;
other += 1;
}
if keep {
let at = (next + before + (votes & below).count_ones()) as usize;
// SAFETY: the kept elements receive the distinct positions 0 to count - 1,
// in input order, and out holds x.len() >= count elements.
unsafe { *out.get_unchecked_mut(at) = x[index] };
}
next += total;
thread::sync_threads();
step += 1;
}
}
}
// Writes the kept elements of each tile in order, after those of the earlier tiles.
__global__ void compactVotes(const unsigned* x, unsigned threshold,
const unsigned* scanned, unsigned* out, int n)
{
__shared__ unsigned warps[8];
int lane = threadIdx.x % 32;
int warp = threadIdx.x / 32;
unsigned below = (1u << lane) - 1; // the lanes to the left of this one
unsigned next = blockIdx.x > 0 ? scanned[blockIdx.x - 1] : 0;
for (int step = 0; step < 4; ++step) {
int index = blockIdx.x * TILE + step * 256 + threadIdx.x;
bool keep = index < n && x[index] >= threshold;
unsigned votes = __ballot_sync(0xffffffff, keep);
if (lane == 0) {
warps[warp] = __popc(votes);
}
__syncthreads();
unsigned before = 0;
unsigned total = 0;
for (int other = 0; other < 8; ++other) {
before += other < warp ? warps[other] : 0;
total += warps[other];
}
if (keep) {
out[next + before + __popc(votes & below)] = x[index];
}
next += total;
__syncthreads();
}
}
The call warp::ballot(keep) in Rust and the call __ballot_sync(0xffffffff, keep) in C++ are
line 4 of Compact-Votes, and count_ones() and __popc compute the popcount. The variable
below is the mask \(2^{lane} - 1\) of line 8. Every lane calls the ballot, including the lanes
whose index lies beyond the end of the array, because a ballot needs all 32 lanes of the warp;
those lanes vote false. The shared array \(\mathsf{counts}\) is named WARPS in Rust and warps in C++, and
the 2 barriers that protect it are lines 6 and 10.
Exercises
21.23 In Listing 21.1, y.get_mut(idx) returns None for some threads of the last block.
Which threads, for \(n = 3{,}000\)?
21.24 Rewrite the Blelloch kernel for blocks of 1,024 threads and tiles of 2,048 values. What
must change in scan_tiles?
21.11 Measurements
21.11.1 Platform and method
The measurements come from a Jetson Orin NX 16 GB, an integrated GPU with 8 SMs (sm_87) and 102 GB/s of memory bandwidth. The programs scan 16,777,216 values of 4 bytes, 64 MiB in all, drawn from \([0, 4)\), and they compact 16,777,216 values drawn from \([0, 100)\) at 3 thresholds. Every result is compared value by value with the result computed on the CPU. Each time is the average of 20 runs after 0.4 s of warm-up; between runs of the same program, times varied by up to 10%.
21.11.2 Results
The C++ program printed the following output.
$ ./scan_compaction
...
inclusive scans of 16777216 values, average of 20 runs
method blocks/SM tiles ms GB/s whole ms GB/s
Hillis-Steele 1 5.540 24.2 7.118 18.9
Blelloch 3 4.722 28.4 6.328 21.2
warp shuffles 6 1.750 76.7 3.404 39.4
compaction of 16777216 values in [0, 100), average of 20 runs
keep x >= kept 3 passes ms GB/s warp votes ms GB/s
90 1676698 7.74 9.5 2.28 32.3
50 8387729 8.05 12.5 2.41 41.8
10 15100473 8.46 15.1 2.66 47.9
PASSED
The column “tiles” times line 2 of Scan alone, in which every block scans its tile of 1,024 values and writes its total. The column “whole” times the complete scan of Section 21.7. The GB/s columns divide the bytes that the job needs by the time. These bytes are 1 read of every input and 1 write of every output, which for the scans is \(2 \times 4 \times 16{,}777{,}216 = 134.2\) MB. The column “blocks/SM” gives the number of blocks of each kernel that fit on 1 SM at the same time; the program asks the CUDA runtime for it. The Rust program measured 5.65, 4.74 and 1.76 ms for the tiles and 7.23, 6.35 and 3.46 ms for the whole scans, within 3% of the C++ times, and compaction times within 2% of the C++ times. Figure 21.15 draws the C++ times.
21.11.3 Why the work-efficient scan is not 4.5 times faster
The Blelloch scan performs 2,046 additions per tile and the Hillis-Steele scan 9,217, yet the Blelloch scan is only 1.17 times as fast, 4.72 ms against 5.54 ms. Both take 2.7 to 3.2 times as long as the scan of Chapter 8, which runs at 76.7 GB/s, 75% of the 102 GB/s of the memory. All 3 kernels read and write the same 134.2 MB, so the difference must lie inside the SMs. The difference is explained by three costs, which we take in turn.
The first cost is the barrier. Removing line 7 from the Hillis-Steele kernel, as in Section 21.6.1, gives wrong results, but it lets us measure what the 10 barriers of the loop cost. The broken kernel scanned the tiles in 4.03 ms instead of 5.54 ms, so 27% of the time of the Hillis-Steele scan is spent waiting at barriers.
The second cost is the small number of blocks on an SM. A thread that waits, at a barrier or for a value from global memory, does no work, and the SM hides that wait only if other threads are ready to run in the meantime. The following definition gives this quantity a name.
Definition 21.12 Occupancy. The occupancy of a kernel is the number of its threads, or warps, that an SM holds at the same time, often given as a fraction of the most the SM can hold.
Example. An SM of the measured GPU holds at most 1,536 threads. A block of 1,024 threads leaves room for no second block: one block per SM, 2/3 of the maximum.
The Hillis-Steele kernel runs one block per SM. While that block waits at one of its 11 barriers, or for its tile to arrive from global memory, the SM has nothing else to run. The Blelloch kernel uses blocks of 512 threads and runs 3 of them per SM. Its 22 barriers are twice as many, but while 1 block waits, the 2 others can work. The warp-shuffle kernel runs 6 blocks of 256 threads per SM and waits at only 2 barriers per tile.
The third cost is shared memory. The Hillis-Steele kernel reads 2 values and writes 1 in each of its 10 steps, about 31 accesses to shared memory per value. The Blelloch kernel reads 2 values and writes 1 for every pair of the up-sweep, and writes 2 for every pair of the down-sweep, about 9 accesses per value in all. The warp-shuffle kernel scans 4 values per thread in registers and exchanges values between the lanes of a warp with shuffles, which do not use shared memory at all; it writes only 1 total per warp to shared memory.
We can now see why Figure 21.7 does not predict the measured times. The work in that figure counts additions, and in a GPU block, an addition is the cheapest part of a step. What a step costs is set by its barrier, its accesses to shared memory, and the occupancy that decides whether those waits overlap with other work. The scan of Chapter 8 was designed around these three costs, and it is the scan that the compaction uses.
The whole scan adds 1.58 to 1.65 ms to each tile scan. This is the second pass of Section 21.7.3, which reads and writes all 16,777,216 values again: 134.2 MB in 1.65 ms is 81 GB/s.
21.11.4 Why the warp votes are 3.3 times faster, not 3.8
With half of the values kept, the 3-pass compaction took 8.05 ms and the warp votes took 2.41 ms, a ratio of 3.3. In Section 21.9.1, we predicted the ratio of the bytes moved, \(38 / 10 = 3.8\). Dividing the bytes that each method moves by its time gives the rate at which it used the memory. For the 3 passes, this is \(38 \times 16{,}777{,}216 = 637.5\) MB in 8.05 ms, or 79.2 GB/s, and for the warp votes, it is \(10 \times 16{,}777{,}216 = 167.8\) MB in 2.41 ms, or 69.6 GB/s. Both methods therefore run close to the rate of the memory, and the warp votes are faster because they move fewer bytes. They run at a slightly lower rate because each tile waits at 8 barriers and reads its values twice, in 2 separate kernels, so each kernel has less work with which to overlap its waits.
The time of the 3-pass method hardly changes with the fraction of kept values, from 7.74 to 8.46 ms, because 24 of its 38 bytes, those of the flags and the scan, do not depend on that fraction. The warp votes write more as more values are kept, and their time grows from 2.28 to 2.66 ms.
Exercises
21.25 Compute, from the table, the time per tile of the Blelloch kernel on 1 SM, and the number
of cycles per barrier at a clock of 1 GHz.
21.26 Predict the time of the 3-pass compaction with 90% of the values kept from the byte count,
and compare with the measured value.
21.12 The complete programs
The following listing contains the complete programs of this chapter, in Rust and in CUDA C++. Each program runs the small example, scans and compacts 16,777,216 values with every method, checks every result against the CPU, and prints the times.
Listing 21.6 The complete programs. code/oxide/ch21_scan_compaction/src/main.rs and code/cuda/ch21_scan_compaction/scan_compaction.cu
//! Chapter 21: 3 inclusive scans of a tile (Hillis-Steele, Blelloch, warp shuffles),
//! the scan of a long array, and stream compaction by a scan and by warp votes.
//!
//! cargo oxide run
use std::sync::Arc;
use std::time::{Duration, Instant};
use cuda_core::{CudaContext, CudaStream, DeviceBuffer, LaunchConfig1D};
use cuda_device::{DisjointSlice, SharedArray, cuda_module, device, kernel, launch_contract};
use cuda_device::{thread, warp};
const TILE: usize = 1024; // elements scanned by 1 block
const N: usize = 16 << 20; // elements in the measured runs
type Error = Box<dyn std::error::Error>;
type Levels = Vec<(DeviceBuffer<u32>, DeviceBuffer<u32>)>;
type Module = kernels::LoadedModule;
#[derive(Clone, Copy)]
enum Method {
HillisSteele,
Blelloch,
Warps,
}
const METHODS: [(Method, &str); 3] = [
(Method::HillisSteele, "Hillis-Steele"),
(Method::Blelloch, "Blelloch"),
(Method::Warps, "warp shuffles"),
];
#[cuda_module]
mod kernels {
use super::*;
/// Hillis-Steele: 1,024 threads, 1 element each, 2 buffers in shared memory.
#[kernel]
#[launch_contract(domain = 1, block = (1024, 1, 1))]
pub fn scan_hillis_steele(
x: &[u32],
mut y: DisjointSlice<u32>,
mut sums: DisjointSlice<u32>,
) {
static mut BUF: SharedArray<u32, 2048> = SharedArray::UNINIT;
let idx = thread::index_1d();
let index = idx.get();
let thread_idx = thread::threadIdx_x() as usize;
// SAFETY: each thread writes only its own slot thread_idx, before the barrier.
unsafe { BUF[thread_idx] = if index < x.len() { x[index] } else { 0 } };
thread::sync_threads();
let mut src = 0;
let mut step = 0usize;
#[unroll]
while step < 10 {
let distance = 1 << step; // 1, 2, 4, ..., 512
let dst = TILE - src;
// SAFETY: a step reads only buffer src and writes only this thread's slot of
// buffer dst; the barrier ends the step before the next one reads buffer dst.
unsafe {
let mut value = BUF[src + thread_idx];
if thread_idx >= distance {
value += BUF[src + thread_idx - distance];
}
BUF[dst + thread_idx] = value;
}
thread::sync_threads();
src = dst;
step += 1;
}
// SAFETY: after the last barrier the buffers are only read.
let total = unsafe { BUF[src + thread_idx] };
if let Some(out) = y.get_mut(idx) {
*out = total;
}
if thread_idx == TILE - 1 {
let block = thread::blockIdx_x() as usize;
// SAFETY: only the last thread of each block writes, at its own block number.
unsafe { *sums.get_unchecked_mut(block) = total };
}
}
/// Blelloch: 512 threads, 2 elements each, 1 buffer; an up-sweep, then a down-sweep.
#[kernel]
#[launch_contract(domain = 1, block = (512, 1, 1))]
pub fn scan_blelloch(
x: &[u32],
mut y: DisjointSlice<u32>,
mut sums: DisjointSlice<u32>,
) {
static mut CELLS: SharedArray<u32, 1024> = SharedArray::UNINIT;
let thread_idx = thread::threadIdx_x() as usize;
let block = thread::blockIdx_x() as usize;
let index = block * TILE + 2 * thread_idx;
let first = if index < x.len() { x[index] } else { 0 };
let second = if index + 1 < x.len() { x[index + 1] } else { 0 };
// SAFETY: each thread writes only its own 2 slots, before a barrier.
unsafe {
CELLS[2 * thread_idx] = first;
CELLS[2 * thread_idx + 1] = second;
}
let mut step = 0usize;
#[unroll]
while step < 10 {
let distance = 1 << step; // up-sweep: 1, 2, 4, ..., 512
thread::sync_threads();
if thread_idx < TILE / (2 * distance) {
let right = (2 * thread_idx + 2) * distance - 1;
// SAFETY: at each distance, the pairs (right - distance, right) of
// different threads are disjoint, and the barriers separate the levels.
unsafe { CELLS[right] += CELLS[right - distance] };
}
step += 1;
}
thread::sync_threads();
if thread_idx == 0 {
// SAFETY: thread 0 alone touches slot TILE - 1 between 2 barriers.
unsafe {
*sums.get_unchecked_mut(block) = CELLS[TILE - 1];
CELLS[TILE - 1] = 0;
}
}
let mut step = 0usize;
#[unroll]
while step < 10 {
let distance = 512 >> step; // down-sweep: 512, 256, ..., 1
thread::sync_threads();
if thread_idx < TILE / (2 * distance) {
let right = (2 * thread_idx + 2) * distance - 1;
// SAFETY: as in the up-sweep, each pair belongs to 1 thread per level.
unsafe {
let left = CELLS[right - distance];
CELLS[right - distance] = CELLS[right];
CELLS[right] += left;
}
}
step += 1;
}
thread::sync_threads();
// SAFETY: after the last barrier CELLS is only read; each thread alone writes its 2
// elements of y, and both lie below y.len() when the test passes.
unsafe {
if index < y.len() {
*y.get_unchecked_mut(index) = CELLS[2 * thread_idx] + first;
}
if index + 1 < y.len() {
*y.get_unchecked_mut(index + 1) = CELLS[2 * thread_idx + 1] + second;
}
}
}
/// The inclusive scan of 1 value per lane across a warp (Section 8.7.2).
#[device]
fn warp_scan(mut value: u32) -> u32 {
let lane = warp::lane_id();
let mut step = 0u32;
#[unroll]
while step < 5 {
let offset = 1 << step; // 1, 2, 4, 8, 16
let left = warp::shuffle_up_sync(u32::MAX, value, offset);
if lane >= offset {
value += left;
}
step += 1;
}
value
}
/// The scan of Chapter 8: 256 threads, 4 elements each, warp shuffles and 2 barriers.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn scan_warps(
x: &[u32],
mut y: DisjointSlice<u32>,
mut sums: DisjointSlice<u32>,
) {
static mut WARPS: SharedArray<u32, 8> = SharedArray::UNINIT;
let first = thread::index_1d().get() * 4;
let lane = warp::lane_id() as usize;
let warp = thread::threadIdx_x() as usize / 32;
let mut prefix = [0u32; 4];
let mut own = 0;
let mut element = 0;
#[unroll]
while element < 4 {
if first + element < x.len() {
own += x[first + element];
}
prefix[element] = own;
element += 1;
}
let warp_prefix = warp_scan(own);
if lane == 31 {
// SAFETY: lane 31 of each warp writes its own slot, before the barrier.
unsafe { WARPS[warp] = warp_prefix };
}
thread::sync_threads();
if warp == 0 {
// SAFETY: only warp 0 touches the slots between the 2 barriers.
let warp_total = if lane < 8 { unsafe { WARPS[lane] } } else { 0 };
let scanned_total = warp_scan(warp_total);
if lane < 8 {
unsafe { WARPS[lane] = scanned_total };
}
}
thread::sync_threads();
// SAFETY: after the second barrier the slots are only read.
let earlier_warps = if warp > 0 { unsafe { WARPS[warp - 1] } } else { 0 };
let before = warp_prefix - own + earlier_warps;
let mut element = 0;
#[unroll]
while element < 4 {
if first + element < y.len() {
// SAFETY: each thread alone writes its own 4 elements.
unsafe { *y.get_unchecked_mut(first + element) = before + prefix[element] };
}
element += 1;
}
if thread::threadIdx_x() == 255 {
let block = thread::blockIdx_x() as usize;
// SAFETY: only the last thread of each block writes, at its own block number.
unsafe { *sums.get_unchecked_mut(block) = before + prefix[3] };
}
}
/// Adds to every element of tile b the total of tiles 0 to b - 1.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn add_offsets(mut y: DisjointSlice<u32>, scanned: &[u32]) {
let block = thread::blockIdx_x() as usize;
let tid = thread::threadIdx_x() as usize;
if block > 0 {
let offset = scanned[block - 1];
let mut step = 0;
#[unroll]
while step < 4 {
let index = block * TILE + step * 256 + tid;
if index < y.len() {
// SAFETY: element g is this thread's alone and lies below y.len().
unsafe { *y.get_unchecked_mut(index) += offset };
}
step += 1;
}
}
}
/// flags[i] = 1 if x[i] is kept, 0 if it is removed.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn keep_flags(x: &[u32], threshold: u32, mut flags: DisjointSlice<u32>) {
let idx = thread::index_1d();
let index = idx.get();
if let Some(flag) = flags.get_mut(idx) {
*flag = (x[index] >= threshold) as u32;
}
}
/// Writes each kept element at its exclusive scan: the inclusive scan minus its flag 1.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn scatter_kept(
x: &[u32],
flags: &[u32],
scanned: &[u32],
mut out: DisjointSlice<u32>,
) {
let index = thread::index_1d().get();
if index < x.len() && flags[index] == 1 {
let at = (scanned[index] - 1) as usize;
// SAFETY: the kept elements receive the distinct positions 0 to count - 1,
// and out holds x.len() >= count elements.
unsafe { *out.get_unchecked_mut(at) = x[index] };
}
}
/// The number of kept elements in each tile of 1,024, counted with warp votes.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn count_kept(x: &[u32], threshold: u32, mut counts: DisjointSlice<u32>) {
static mut WARPS: SharedArray<u32, 8> = SharedArray::UNINIT;
let tid = thread::threadIdx_x() as usize;
let base = thread::blockIdx_x() as usize * TILE;
let mut count = 0;
let mut step = 0;
#[unroll]
while step < 4 {
let index = base + step * 256 + tid;
let keep = index < x.len() && x[index] >= threshold;
count += warp::ballot(keep).count_ones();
step += 1;
}
if warp::lane_id() == 0 {
// SAFETY: lane 0 of each warp writes its own slot, before the barrier.
unsafe { WARPS[tid / 32] = count };
}
thread::sync_threads();
if tid == 0 {
let mut total = 0;
let mut other = 0;
#[unroll]
while other < 8 {
// SAFETY: after the barrier the slots are only read.
total += unsafe { WARPS[other] };
other += 1;
}
let block = thread::blockIdx_x() as usize;
// SAFETY: only thread 0 of each block writes, at its own block number.
unsafe { *counts.get_unchecked_mut(block) = total };
}
}
/// Writes the kept elements of each tile in order, after those of the earlier tiles.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn compact_votes(
x: &[u32],
threshold: u32,
scanned: &[u32],
mut out: DisjointSlice<u32>,
) {
static mut WARPS: SharedArray<u32, 8> = SharedArray::UNINIT;
let tid = thread::threadIdx_x() as usize;
let lane = warp::lane_id();
let warp = tid / 32;
let block = thread::blockIdx_x() as usize;
let below = (1u32 << lane) - 1; // the lanes to the left of this one
let mut next = if block > 0 { scanned[block - 1] } else { 0 };
let mut step = 0;
#[unroll]
while step < 4 {
let index = block * TILE + step * 256 + tid;
let keep = index < x.len() && x[index] >= threshold;
let votes = warp::ballot(keep);
if lane == 0 {
// SAFETY: lane 0 of each warp writes its own slot, before the barrier.
unsafe { WARPS[warp] = votes.count_ones() };
}
thread::sync_threads();
let mut before = 0;
let mut total = 0;
let mut other = 0;
#[unroll]
while other < 8 {
// SAFETY: between the 2 barriers the slots are only read.
let count = unsafe { WARPS[other] };
before += if other < warp { count } else { 0 };
total += count;
other += 1;
}
if keep {
let at = (next + before + (votes & below).count_ones()) as usize;
// SAFETY: the kept elements receive the distinct positions 0 to count - 1,
// in input order, and out holds x.len() >= count elements.
unsafe { *out.get_unchecked_mut(at) = x[index] };
}
next += total;
thread::sync_threads();
step += 1;
}
}
}
/// Runs `launch` for 0.4 s so that the clocks rise, then averages 20 runs, in ms.
fn time_ms(
stream: &Arc<CudaStream>,
mut launch: impl FnMut() -> Result<(), Error>,
) -> Result<f64, Error> {
let warm = Instant::now();
while warm.elapsed() < Duration::from_millis(400) {
launch()?;
stream.synchronize()?;
}
let start = Instant::now();
for _ in 0..20 {
launch()?;
}
stream.synchronize()?;
Ok(start.elapsed().as_secs_f64() * 1e3 / 20.0)
}
/// Numbers below `limit` from a small linear congruential generator.
fn random_below(n: usize, limit: u32, seed: u32) -> Vec<u32> {
let mut state = seed;
(0..n)
.map(|_| {
state = state.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
(state >> 8) % limit
})
.collect()
}
/// Buffers for the tile totals and their scan, per level: n / 1,024, / 1,024 again, ... 1.
fn scan_levels(stream: &Arc<CudaStream>, mut n: usize) -> Result<Levels, Error> {
let mut levels = Vec::new();
while n > 1 {
n = n.div_ceil(TILE);
let totals = DeviceBuffer::<u32>::zeroed(stream, n)?;
let scanned = DeviceBuffer::<u32>::zeroed(stream, n)?;
levels.push((totals, scanned));
}
Ok(levels)
}
/// Scans every tile of 1,024 elements on its own and writes the tile totals.
fn scan_tiles(
module: &Module,
stream: &Arc<CudaStream>,
method: Method,
x: &DeviceBuffer<u32>,
y: &mut DeviceBuffer<u32>,
sums: &mut DeviceBuffer<u32>,
) -> Result<(), Error> {
let tiles = x.len().div_ceil(TILE) as u32;
match method {
Method::HillisSteele => {
let grid = LaunchConfig1D::new(tiles, 1024, 0);
let config = module.prepare_scan_hillis_steele(grid)?;
module.scan_hillis_steele(stream, &config, x, y, sums)?;
}
Method::Blelloch => {
let grid = LaunchConfig1D::new(tiles, 512, 0);
let config = module.prepare_scan_blelloch(grid)?;
module.scan_blelloch(stream, &config, x, y, sums)?;
}
Method::Warps => {
let grid = LaunchConfig1D::new(tiles, 256, 0);
let config = module.prepare_scan_warps(grid)?;
module.scan_warps(stream, &config, x, y, sums)?;
}
}
Ok(())
}
/// Inclusive scan: the tiles, then the tile totals (by the same function), then offsets.
fn scan(
module: &Module,
stream: &Arc<CudaStream>,
method: Method,
x: &DeviceBuffer<u32>,
y: &mut DeviceBuffer<u32>,
levels: &mut [(DeviceBuffer<u32>, DeviceBuffer<u32>)],
) -> Result<(), Error> {
let tiles = x.len().div_ceil(TILE) as u32;
let ((totals, scanned), rest) = levels.split_first_mut().ok_or("no level left")?;
scan_tiles(module, stream, method, x, y, totals)?;
if tiles > 1 {
scan(module, stream, method, totals, scanned, rest)?;
let config = module.prepare_add_offsets(LaunchConfig1D::new(tiles, 256, 0))?;
module.add_offsets(stream, &config, y, scanned)?;
}
Ok(())
}
fn print(name: &str, values: &[u32]) {
let cells: Vec<String> = values.iter().map(|v| v.to_string()).collect();
println!(" {name:13} {}", cells.join(" "));
}
/// The worked example of the chapter: 8 values, 3 scans and 1 compaction.
fn small_example(module: &Module, stream: &Arc<CudaStream>) -> Result<bool, Error> {
let values = [3u32, 1, 7, 0, 4, 1, 6, 3];
let x = DeviceBuffer::from_host(stream, &values)?;
let mut y = DeviceBuffer::<u32>::zeroed(stream, 8)?;
let mut levels = scan_levels(stream, 8)?;
let mut ok = true;
println!("scans of 3 1 7 0 4 1 6 3");
for (method, name) in METHODS {
scan(module, stream, method, &x, &mut y, &mut levels)?;
let result = y.to_host_vec(stream)?;
print(name, &result);
ok &= result == [3, 4, 11, 11, 15, 16, 22, 25];
}
let one = LaunchConfig1D::new(1, 256, 0);
let mut flags = DeviceBuffer::<u32>::zeroed(stream, 8)?;
let mut out = DeviceBuffer::<u32>::zeroed(stream, 8)?;
module.keep_flags(stream, &module.prepare_keep_flags(one)?, &x, 3, &mut flags)?;
scan(module, stream, Method::HillisSteele, &flags, &mut y, &mut levels)?;
let scatter = module.prepare_scatter_kept(one)?;
module.scatter_kept(stream, &scatter, &x, &flags, &y, &mut out)?;
let f = flags.to_host_vec(stream)?;
let s = y.to_host_vec(stream)?;
let exclusive: Vec<u32> = s.iter().zip(&f).map(|(s, f)| s - f).collect();
let kept = out.to_host_vec(stream)?[..s[7] as usize].to_vec();
println!("compaction of 3 1 7 0 4 1 6 3, keep x >= 3");
print("flags", &f);
print("exclusive", &exclusive);
print("output", &kept);
Ok(ok && kept == [3, 7, 4, 6, 3])
}
/// The 3 scans of N values: tiles alone, and the whole array, checked against the CPU.
fn scans(module: &Module, stream: &Arc<CudaStream>) -> Result<bool, Error> {
let host = random_below(N, 4, 1);
let expected: Vec<u32> = host
.iter()
.scan(0u32, |run, &v| {
*run += v;
Some(*run)
})
.collect();
let x = DeviceBuffer::from_host(stream, &host)?;
let mut y = DeviceBuffer::<u32>::zeroed(stream, N)?;
let mut levels = scan_levels(stream, N)?;
let gb = 2.0 * N as f64 * 4.0 / 1e9;
let mut ok = true;
println!("inclusive scans of {N} values, average of 20 runs");
println!(" method tiles ms GB/s whole ms GB/s");
for (method, name) in METHODS {
let (totals, _) = levels.first_mut().ok_or("no level")?;
let one_level = || scan_tiles(module, stream, method, &x, &mut y, totals);
let tiles = time_ms(stream, one_level)?;
let all_levels = || scan(module, stream, method, &x, &mut y, &mut levels);
let whole = time_ms(stream, all_levels)?;
ok &= y.to_host_vec(stream)? == expected;
let (tiles_gb, whole_gb) = (gb / (tiles / 1e3), gb / (whole / 1e3));
println!(" {name:14} {tiles:9.3} {tiles_gb:6.1} {whole:10.3} {whole_gb:6.1}");
}
Ok(ok)
}
/// Compaction of N values in [0, 100) at 3 thresholds, by 3 passes and by warp votes.
fn compaction(module: &Module, stream: &Arc<CudaStream>) -> Result<bool, Error> {
let host = random_below(N, 100, 2);
let x = DeviceBuffer::from_host(stream, &host)?;
let mut flags = DeviceBuffer::<u32>::zeroed(stream, N)?;
let mut scanned = DeviceBuffer::<u32>::zeroed(stream, N)?;
let mut levels = scan_levels(stream, N)?;
let tiles = N.div_ceil(TILE);
let mut counts = DeviceBuffer::<u32>::zeroed(stream, tiles)?;
let mut tile_scan = DeviceBuffer::<u32>::zeroed(stream, tiles)?;
let mut tile_levels = scan_levels(stream, tiles)?;
let every = LaunchConfig1D::new(N.div_ceil(256) as u32, 256, 0);
let per_tile = LaunchConfig1D::new(tiles as u32, 256, 0);
let flag_cfg = module.prepare_keep_flags(every)?;
let scatter_cfg = module.prepare_scatter_kept(every)?;
let count_cfg = module.prepare_count_kept(per_tile)?;
let votes_cfg = module.prepare_compact_votes(per_tile)?;
let mut ok = true;
println!("compaction of {N} values in [0, 100), average of 20 runs");
println!(" keep x >= kept 3 passes ms GB/s warp votes ms GB/s");
for threshold in [90u32, 50, 10] {
let expected: Vec<u32> = host.iter().copied().filter(|&v| v >= threshold).collect();
let kept = expected.len();
let gb = (4 * N + 4 * kept) as f64 / 1e9;
let mut out = DeviceBuffer::<u32>::zeroed(stream, N)?;
let three = || -> Result<(), Error> {
module.keep_flags(stream, &flag_cfg, &x, threshold, &mut flags)?;
scan(module, stream, Method::Warps, &flags, &mut scanned, &mut levels)?;
module.scatter_kept(stream, &scatter_cfg, &x, &flags, &scanned, &mut out)?;
Ok(())
};
let three_ms = time_ms(stream, three)?;
ok &= out.to_host_vec(stream)?[..kept] == expected[..];
out = DeviceBuffer::<u32>::zeroed(stream, N)?;
let votes = || -> Result<(), Error> {
module.count_kept(stream, &count_cfg, &x, threshold, &mut counts)?;
scan(module, stream, Method::Warps, &counts, &mut tile_scan, &mut tile_levels)?;
module.compact_votes(stream, &votes_cfg, &x, threshold, &tile_scan, &mut out)?;
Ok(())
};
let votes_ms = time_ms(stream, votes)?;
ok &= out.to_host_vec(stream)?[..kept] == expected[..];
let (three_gb, votes_gb) = (gb / (three_ms / 1e3), gb / (votes_ms / 1e3));
print!(" {threshold:9} {kept:9} {three_ms:13.2} {three_gb:6.1}");
println!(" {votes_ms:15.2} {votes_gb:6.1}");
}
Ok(ok)
}
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 mut passed = small_example(&module, &stream)?;
passed &= scans(&module, &stream)?;
passed &= compaction(&module, &stream)?;
println!("{}", if passed { "PASSED" } else { "FAILED" });
Ok(())
}
// Chapter 21: 3 inclusive scans of a tile (Hillis-Steele, Blelloch, warp shuffles),
// the scan of a long array, and stream compaction by a scan and by warp votes.
// Build: nvcc -O3 -arch=native scan_compaction.cu -o scan_compaction
#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cuda_runtime.h>
const int TILE = 1024; // elements scanned by 1 block
const int N = 16 << 20; // elements in the measured runs
enum Method { HILLIS_STEELE, BLELLOCH, WARPS };
const char* NAMES[] = {"Hillis-Steele", "Blelloch", "warp shuffles"};
void check(cudaError_t err)
{
if (err != cudaSuccess) {
std::fprintf(stderr, "CUDA error: %s\n", cudaGetErrorString(err));
std::exit(1);
}
}
double nowMs()
{
using namespace std::chrono;
return duration<double, std::milli>(steady_clock::now().time_since_epoch()).count();
}
// Runs `launch` for 0.4 s so that the clocks rise, then averages 20 runs, in ms.
template <typename F>
double timeMs(F launch)
{
double warm = nowMs();
while (nowMs() - warm < 400) {
launch();
check(cudaDeviceSynchronize());
}
double t0 = nowMs();
for (int timed = 0; timed < 20; ++timed) {
launch();
}
check(cudaGetLastError());
check(cudaDeviceSynchronize());
return (nowMs() - t0) / 20;
}
// Hillis-Steele: 1,024 threads, 1 element each, 2 buffers in shared memory.
__global__ void scanHillisSteele(const unsigned* x, unsigned* y, unsigned* sums, int n)
{
__shared__ unsigned buf[2 * TILE];
int index = blockIdx.x * TILE + threadIdx.x;
buf[threadIdx.x] = index < n ? x[index] : 0;
__syncthreads();
int src = 0;
for (int distance = 1; distance < TILE; distance *= 2) {
int dst = TILE - src;
unsigned value = buf[src + threadIdx.x];
if (threadIdx.x >= distance) {
value += buf[src + threadIdx.x - distance];
}
buf[dst + threadIdx.x] = value;
__syncthreads(); // the step is complete before any read
src = dst;
}
if (index < n) {
y[index] = buf[src + threadIdx.x];
}
if (threadIdx.x == TILE - 1) {
sums[blockIdx.x] = buf[src + threadIdx.x];
}
}
// Blelloch: 512 threads, 2 elements each, 1 buffer; an up-sweep, then a down-sweep.
__global__ void scanBlelloch(const unsigned* x, unsigned* y, unsigned* sums, int n)
{
__shared__ unsigned cells[TILE];
int index = blockIdx.x * TILE + 2 * threadIdx.x;
unsigned first = index < n ? x[index] : 0;
unsigned second = index + 1 < n ? x[index + 1] : 0;
cells[2 * threadIdx.x] = first;
cells[2 * threadIdx.x + 1] = second;
for (int distance = 1; distance < TILE; distance *= 2) {
__syncthreads();
if (threadIdx.x < TILE / (2 * distance)) {
int right = (2 * threadIdx.x + 2) * distance - 1;
cells[right] += cells[right - distance];
}
}
__syncthreads();
if (threadIdx.x == 0) {
sums[blockIdx.x] = cells[TILE - 1];
cells[TILE - 1] = 0;
}
for (int distance = TILE / 2; distance >= 1; distance /= 2) {
__syncthreads();
if (threadIdx.x < TILE / (2 * distance)) {
int right = (2 * threadIdx.x + 2) * distance - 1;
unsigned left = cells[right - distance];
cells[right - distance] = cells[right];
cells[right] += left;
}
}
__syncthreads();
if (index < n) {
y[index] = cells[2 * threadIdx.x] + first; // exclusive plus own: inclusive
}
if (index + 1 < n) {
y[index + 1] = cells[2 * threadIdx.x + 1] + second;
}
}
// The scan of Chapter 8: 256 threads, 4 elements each, warp shuffles and 2 barriers.
__device__ unsigned warpScan(unsigned value)
{
int lane = threadIdx.x % 32;
for (int offset = 1; offset < 32; offset *= 2) {
unsigned left = __shfl_up_sync(0xffffffff, value, offset);
if (lane >= offset) {
value += left;
}
}
return value;
}
__global__ void scanWarps(const unsigned* x, unsigned* y, unsigned* sums, int n)
{
__shared__ unsigned warps[8];
int first = blockIdx.x * TILE + 4 * threadIdx.x;
int lane = threadIdx.x % 32;
int warp = threadIdx.x / 32;
unsigned prefix[4];
unsigned own = 0;
for (int element = 0; element < 4; ++element) {
own += first + element < n ? x[first + element] : 0;
prefix[element] = own;
}
unsigned warpPrefix = warpScan(own);
if (lane == 31) {
warps[warp] = warpPrefix;
}
__syncthreads();
if (warp == 0) {
unsigned scannedTotal = warpScan(lane < 8 ? warps[lane] : 0);
if (lane < 8) {
warps[lane] = scannedTotal;
}
}
__syncthreads();
unsigned before = warpPrefix - own + (warp > 0 ? warps[warp - 1] : 0);
for (int element = 0; element < 4; ++element) {
if (first + element < n) {
y[first + element] = before + prefix[element];
}
}
if (threadIdx.x == 255) {
sums[blockIdx.x] = before + prefix[3];
}
}
// Adds to every element of a tile the total of the tiles before it.
__global__ void addOffsets(unsigned* y, const unsigned* scanned, int n)
{
if (blockIdx.x == 0) {
return;
}
unsigned offset = scanned[blockIdx.x - 1];
for (int step = 0; step < 4; ++step) {
int index = blockIdx.x * TILE + step * 256 + threadIdx.x;
if (index < n) {
y[index] += offset;
}
}
}
// Scans every tile of 1,024 elements on its own and writes the tile totals.
void scanTiles(Method method, const unsigned* x, unsigned* y, unsigned* sums, int n)
{
int tiles = (n + TILE - 1) / TILE;
if (method == HILLIS_STEELE) {
scanHillisSteele<<<tiles, TILE>>>(x, y, sums, n);
} else if (method == BLELLOCH) {
scanBlelloch<<<tiles, TILE / 2>>>(x, y, sums, n);
} else {
scanWarps<<<tiles, 256>>>(x, y, sums, n);
}
}
// Inclusive scan of n elements: the tiles, then the tile totals (in place), then offsets.
void scan(Method method, const unsigned* x, unsigned* y, int n, unsigned* scratch)
{
int tiles = (n + TILE - 1) / TILE;
scanTiles(method, x, y, scratch, n);
if (tiles > 1) {
scan(method, scratch, scratch, tiles, scratch + tiles);
addOffsets<<<tiles, 256>>>(y, scratch, n);
}
}
// flags[index] = 1 if x[index] is kept.
__global__ void keepFlags(const unsigned* x, unsigned threshold, unsigned* flags, int n)
{
int index = blockIdx.x * blockDim.x + threadIdx.x;
if (index < n) {
flags[index] = x[index] >= threshold;
}
}
// Writes each kept element at its exclusive scan, the inclusive scan minus its flag of 1.
__global__ void scatterKept(const unsigned* x, const unsigned* flags,
const unsigned* scanned, unsigned* out, int n)
{
int index = blockIdx.x * blockDim.x + threadIdx.x;
if (index < n && flags[index] == 1) {
out[scanned[index] - 1] = x[index];
}
}
// The number of kept elements in each tile of 1,024, counted with warp votes.
__global__ void countKept(const unsigned* x, unsigned threshold, unsigned* counts, int n)
{
__shared__ unsigned warps[8];
int base = blockIdx.x * TILE;
unsigned count = 0;
for (int step = 0; step < 4; ++step) {
int index = base + step * 256 + threadIdx.x;
bool keep = index < n && x[index] >= threshold;
count += __popc(__ballot_sync(0xffffffff, keep));
}
if (threadIdx.x % 32 == 0) {
warps[threadIdx.x / 32] = count;
}
__syncthreads();
if (threadIdx.x == 0) {
unsigned total = 0;
for (int other = 0; other < 8; ++other) {
total += warps[other];
}
counts[blockIdx.x] = total;
}
}
// Writes the kept elements of each tile in order, after those of the earlier tiles.
__global__ void compactVotes(const unsigned* x, unsigned threshold,
const unsigned* scanned, unsigned* out, int n)
{
__shared__ unsigned warps[8];
int lane = threadIdx.x % 32;
int warp = threadIdx.x / 32;
unsigned below = (1u << lane) - 1; // the lanes to the left of this one
unsigned next = blockIdx.x > 0 ? scanned[blockIdx.x - 1] : 0;
for (int step = 0; step < 4; ++step) {
int index = blockIdx.x * TILE + step * 256 + threadIdx.x;
bool keep = index < n && x[index] >= threshold;
unsigned votes = __ballot_sync(0xffffffff, keep);
if (lane == 0) {
warps[warp] = __popc(votes);
}
__syncthreads();
unsigned before = 0;
unsigned total = 0;
for (int other = 0; other < 8; ++other) {
before += other < warp ? warps[other] : 0;
total += warps[other];
}
if (keep) {
out[next + before + __popc(votes & below)] = x[index];
}
next += total;
__syncthreads();
}
}
// Numbers from a small linear congruential generator.
std::vector<unsigned> randomBelow(int n, unsigned limit, unsigned seed)
{
std::vector<unsigned> v(n);
unsigned state = seed;
for (int i = 0; i < n; ++i) {
state = state * 1664525u + 1013904223u;
v[i] = (state >> 8) % limit;
}
return v;
}
void print(const char* name, const std::vector<unsigned>& v, int count)
{
std::printf(" %-13s", name);
for (int i = 0; i < count; ++i) {
std::printf(" %u", v[i]);
}
std::printf("\n");
}
std::vector<unsigned> toHost(const unsigned* d, int n)
{
std::vector<unsigned> h(n);
check(cudaMemcpy(h.data(), d, n * sizeof(unsigned), cudaMemcpyDeviceToHost));
return h;
}
// The worked example of the chapter: 8 values, 3 scans and 1 compaction.
bool smallExample(unsigned* scratch)
{
std::vector<unsigned> x = {3, 1, 7, 0, 4, 1, 6, 3};
std::vector<unsigned> inclusive = {3, 4, 11, 11, 15, 16, 22, 25};
unsigned *dx, *dy, *flags, *out;
check(cudaMalloc(&dx, 8 * sizeof(unsigned)));
check(cudaMalloc(&dy, 8 * sizeof(unsigned)));
check(cudaMalloc(&flags, 8 * sizeof(unsigned)));
check(cudaMalloc(&out, 8 * sizeof(unsigned)));
check(cudaMemcpy(dx, x.data(), 8 * sizeof(unsigned), cudaMemcpyHostToDevice));
bool ok = true;
std::printf("scans of 3 1 7 0 4 1 6 3\n");
for (Method m : {HILLIS_STEELE, BLELLOCH, WARPS}) {
scan(m, dx, dy, 8, scratch);
std::vector<unsigned> y = toHost(dy, 8);
print(NAMES[m], y, 8);
ok = ok && y == inclusive;
}
keepFlags<<<1, 256>>>(dx, 3, flags, 8);
scan(HILLIS_STEELE, flags, dy, 8, scratch);
scatterKept<<<1, 256>>>(dx, flags, dy, out, 8);
std::vector<unsigned> f = toHost(flags, 8);
std::vector<unsigned> s = toHost(dy, 8);
std::vector<unsigned> e(8);
for (int i = 0; i < 8; ++i) {
e[i] = s[i] - f[i];
}
std::vector<unsigned> kept = toHost(out, s[7]);
std::printf("compaction of 3 1 7 0 4 1 6 3, keep x >= 3\n");
print("flags", f, 8);
print("exclusive", e, 8);
print("output", kept, s[7]);
ok = ok && kept == std::vector<unsigned>({3, 7, 4, 6, 3});
check(cudaFree(dx));
check(cudaFree(dy));
check(cudaFree(flags));
check(cudaFree(out));
return ok;
}
// The 3 scans of N values: tiles alone, and the whole array, checked against the CPU.
bool scans(const unsigned* dx, unsigned* dy, unsigned* scratch,
const std::vector<unsigned>& x)
{
std::vector<unsigned> expected(N);
unsigned run = 0;
for (int i = 0; i < N; ++i) {
run += x[i];
expected[i] = run;
}
double gb = 2.0 * N * sizeof(unsigned) / 1e9;
int perSm[3]; // blocks that fit on 1 SM at once
auto fit = cudaOccupancyMaxActiveBlocksPerMultiprocessor<decltype(&scanWarps)>;
check(fit(&perSm[HILLIS_STEELE], scanHillisSteele, TILE, 0));
check(fit(&perSm[BLELLOCH], scanBlelloch, TILE / 2, 0));
check(fit(&perSm[WARPS], scanWarps, 256, 0));
bool ok = true;
std::printf("inclusive scans of %d values, average of 20 runs\n", N);
std::printf(" method blocks/SM tiles ms GB/s whole ms GB/s\n");
for (Method m : {HILLIS_STEELE, BLELLOCH, WARPS}) {
double tiles = timeMs([&] { scanTiles(m, dx, dy, scratch, N); });
double whole = timeMs([&] { scan(m, dx, dy, N, scratch); });
ok = ok && toHost(dy, N) == expected;
std::printf(" %-14s %10d %10.3f %6.1f %10.3f %6.1f\n", NAMES[m], perSm[m],
tiles, gb / (tiles / 1e3), whole, gb / (whole / 1e3));
}
return ok;
}
// Compaction of N values in [0, 100) at 3 thresholds, by 3 passes and by warp votes.
bool compaction(const unsigned* dx, unsigned* scratch, const std::vector<unsigned>& x)
{
int tiles = (N + TILE - 1) / TILE;
unsigned *flags, *scanned, *out, *counts;
check(cudaMalloc(&flags, N * sizeof(unsigned)));
check(cudaMalloc(&scanned, N * sizeof(unsigned)));
check(cudaMalloc(&out, N * sizeof(unsigned)));
check(cudaMalloc(&counts, tiles * sizeof(unsigned)));
int blocks = (N + 255) / 256;
bool ok = true;
std::printf("compaction of %d values in [0, 100), average of 20 runs\n", N);
std::printf(" keep x >= kept 3 passes ms GB/s warp votes ms GB/s\n");
for (unsigned threshold : {90u, 50u, 10u}) {
std::vector<unsigned> expected;
for (unsigned v : x) {
if (v >= threshold) {
expected.push_back(v);
}
}
int kept = expected.size();
double gb = (4.0 * N + 4.0 * kept) / 1e9;
auto three = [&] {
keepFlags<<<blocks, 256>>>(dx, threshold, flags, N);
scan(WARPS, flags, scanned, N, scratch);
scatterKept<<<blocks, 256>>>(dx, flags, scanned, out, N);
};
check(cudaMemset(out, 0, N * sizeof(unsigned)));
double threeMs = timeMs(three);
ok = ok && toHost(out, kept) == expected;
auto votes = [&] {
countKept<<<tiles, 256>>>(dx, threshold, counts, N);
scan(WARPS, counts, counts, tiles, scratch);
compactVotes<<<tiles, 256>>>(dx, threshold, counts, out, N);
};
check(cudaMemset(out, 0, N * sizeof(unsigned)));
double votesMs = timeMs(votes);
ok = ok && toHost(out, kept) == expected;
std::printf(" %9u %9d %13.2f %6.1f %15.2f %6.1f\n", threshold, kept,
threeMs, gb / (threeMs / 1e3), votesMs, gb / (votesMs / 1e3));
}
check(cudaFree(flags));
check(cudaFree(scanned));
check(cudaFree(out));
check(cudaFree(counts));
return ok;
}
int main()
{
unsigned *dx, *dy, *scratch;
check(cudaMalloc(&dx, N * sizeof(unsigned)));
check(cudaMalloc(&dy, N * sizeof(unsigned)));
check(cudaMalloc(&scratch, N / 512 * sizeof(unsigned)));
bool ok = smallExample(scratch);
std::vector<unsigned> x = randomBelow(N, 4, 1);
check(cudaMemcpy(dx, x.data(), N * sizeof(unsigned), cudaMemcpyHostToDevice));
ok = scans(dx, dy, scratch, x) && ok;
x = randomBelow(N, 100, 2);
check(cudaMemcpy(dx, x.data(), N * sizeof(unsigned), cudaMemcpyHostToDevice));
ok = compaction(dx, scratch, x) && ok;
check(cudaFree(dx));
check(cudaFree(dy));
check(cudaFree(scratch));
std::printf("%s\n", ok ? "PASSED" : "FAILED");
return ok ? 0 : 1;
}
Common mistakes
- A missing barrier between steps. A thread starts the next step and reads a slot that a slower thread has not written yet (Section 21.6.1). Every step that reads the values of other threads must end with a barrier that every thread reaches.
- Scanning in place. A step that reads and writes the same array lets a thread read a value of the current step. The test passed on 8 values and failed on 16,777,216 (Section 21.6.2). Use 2 buffers, or keep the value to be added in a register and separate the read from the write with a barrier.
- Leaving the loop early. A thread whose value is final must still reach the barriers of the remaining steps, or the block waits for it forever.
- The inclusive scan as an output position. Every kept value lands 1 position too far, in bounds, and no error is reported. The position is the exclusive scan, \(s_i - f_i\).
- A ballot inside a branch. A ballot needs every lane of the warp. Compute the condition for every lane, with the bounds test inside it, and call the ballot unconditionally.
- Assuming that blocks see each other’s results. The blocks of 1 launch cannot wait for each other, so the scan of many tiles crosses blocks only through a second launch.
Summary
- The inclusive scan holds at position \(i\) the sum of the inputs 0 to \(i\), and the exclusive scan stops before \(i\). The sequential scan performs \(n - 1\) additions in a chain of \(n - 1\) steps.
- Because addition is associative, a range sum is the sum of 2 adjacent range sums. Doubling the ranges gives the Hillis-Steele scan, with \(\log_2 n\) steps and \(n \log_2 n - (n - 1)\) additions. Building a tree and then descending it gives the Blelloch scan, with \(2 \log_2 n\) steps and \(2(n - 1)\) additions.
- A step must not start before the previous one has ended, and it must not read what it writes. These two requirements are met by 1 barrier and 1 double buffer, both of which are used in the proof of Theorem 21.1.
- An array of many blocks is scanned in tiles. We scan the tiles, scan their totals, and add the offsets.
- Stream compaction is a scan of flags followed by a scatter to the exclusive scan. Warp votes compute the same positions inside each block and reduce the traffic from 38 to 10 bytes per value.
In Chapter 22, we use the exclusive scan as the core of a radix sort, and we combine it with a histogram.
Exercises
- Run Hillis-Steele-Scan by hand on 16 values \(1, 2, \ldots, 16\), and check the last row against \(y_i = (i + 1)(i + 2)/2\).
- Prove that the up-sweep of Blelloch-Scan leaves \(S[i - 2 \cdot \mathsf{distance} + 1..i]\) at every position \(i = 2 \cdot \mathsf{distance} - 1, 4 \cdot \mathsf{distance} - 1, \ldots\) after the level with distance \(\mathsf{distance}\).
- A segmented scan restarts the running total at every position where a second array holds 1. Write the sequential algorithm, and show how Hillis-Steele-Scan can carry the segment flags.
- Change
scan_hillis_steeleto keep 1 buffer and a register, as suggested in Common mistakes, with 2 barriers per step. Measure it against Listing 21.1. - Estimate the bytes per value of the 3-pass compaction when 10% of the values are kept, taking into account that memory is read in sectors of 32 bytes, and compare with the measured times.
- Write a kernel that removes adjacent duplicates from a sorted array. Which flag does it compute?
Sources and further reading
- W. D. Hillis and G. L. Steele, Jr., “Data Parallel Algorithms”, Communications of the ACM 29(12), 1986.
- G. E. Blelloch, “Prefix Sums and Their Applications”, Technical Report CMU-CS-90-190, Carnegie Mellon University, 1990.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022: loop invariants and the pseudocode conventions of this chapter.
- A. Pathak, “An Introduction to Tiled Parallel Programming, Simplified”, 2026: the worked-example and proof style of this part of the book.
- D. Merrill and M. Garland, “Single-pass Parallel Prefix Scan with Decoupled Look-back”, NVIDIA Technical Report NVR-2016-002, 2016.
- NVIDIA, CUDA C++ Programming Guide, “Warp Vote Functions” and “Synchronization Functions”.
- cuda-oxide, documentation of
DisjointSliceandSharedArray, cratecuda-device, revision b7fe543.