Chapter 22: Radix Sort and Histograms
Sorting puts a list of keys in increasing order. Most sorting algorithms compare keys 2 at a time, and the order of the comparisons depends on the keys, which makes these algorithms awkward to run on thousands of threads. A radix sort compares nothing. It sorts integer keys by their digits, 1 digit per pass, and in each pass, every key computes its output position from 2 counts: the number of keys that have a smaller digit, and the number of keys before it that have the same digit. Both counts come from the scan of Chapter 21, and the first one also comes from a histogram, the count of the keys with each digit value.
In this chapter, we derive a radix sort on 8 keys of 3 bits, small enough that every pass can be checked by hand. We start with passes on 1 bit, each of which consists of 2 stream compactions, and we show why every pass must keep keys with equal digits in their input order. We then count keys with atomic operations, measure what happens when many threads count into the same bin, and remove most of that contention with private bins in shared memory. Finally, we use a histogram and an exclusive scan to compute the positions of a pass on a digit of 4 bits, and we measure a sort that runs 6.5 times as fast as the sort by single bits.
This chapter covers
- radix sort, least significant digit first, worked by hand on 8 keys of 3 bits
- a split on 1 bit as 2 compactions, and why each pass must be stable
- a proof that a sort by stable passes is correct
- histograms with atomic operations, contention, private bins and warp aggregation
- a pass on a digit of several bits from a histogram, an exclusive scan and ranks
- measured histograms and sorts of 16,777,216 keys
The code of the chapter is in
code/oxide/ch22_radix_sort_histogram/
for Rust and in
code/cuda/ch22_radix_sort_histogram/
for C++. The programs use the warp-shuffle scan of Chapter 21 (Section 21.10.3) without change. In
Chapters 5 and 8, we measured histograms of bytes in C++ and in Rust, and we cite those results
where we reuse them.
22.1 The problem
22.1.1 A worked example
Throughout the chapter, we sort the same 8 keys, which we call \(K\):
\[ K = (5,\ 2,\ 7,\ 2,\ 0,\ 6,\ 3,\ 5). \]
As in Chapter 21, we number the positions from 0, so that \(K_0 = 5\) is the first key and \(K_7 = 5\) the last. Every key is below 8, so it fits in 3 bits. For example, 5 is 101 in binary, 2 is 010, and 7 is 111. The sorted list is \((0, 2, 2, 3, 5, 5, 6, 7)\). Figure 22.1 shows the keys with their bits, and the sorted keys with the position from which each one came. The key 2 occurs twice, at positions 1 and 3, and so does the key 5, at positions 0 and 7. We follow both pairs through the chapter.
22.1.2 Definitions
A radix sort works on the bits of a key, so we first state precisely how a bit, and a group of bits, is read from a key.
Definition 22.1 Key, bit and digit. A key is an unsigned integer of \(B\) bits. Bit \(b\) of key \(k\) is \(\lfloor k / 2^b \rfloor \bmod 2\), and bit 0 is the least significant. A digit of \(r\) bits at shift \(s\) is \(\lfloor k / 2^s \rfloor \bmod 2^r\), the bits \(s\) to \(s + r - 1\) read as a number.
Example. \(B = 3\). The key 6 = 110 has bit 0 equal to 0 and bit 2 equal to 1; its digit of 2 bits at shift 0 is 10, that is 2.
Dividing a key by \(2^b\) and rounding down removes its lowest \(b\) bits, and taking the remainder modulo 2 then keeps only the lowest of the remaining bits, which is bit \(b\) of the original key. For the key 6 and \(b = 2\), we get \(\lfloor 6 / 4 \rfloor = 1\) and \(1 \bmod 2 = 1\). A digit is read in the same way, except that the remainder modulo \(2^r\) keeps the lowest \(r\) bits instead of 1.
| Symbol | Meaning | Key 6 = 110 |
|---|---|---|
| \(B\) | number of bits of every key | 3 |
| \(b\) | number of a bit, 0 for the least significant | 2 |
| \(\lfloor k / 2^b \rfloor \bmod 2\) | bit \(b\) of key \(k\) | \(\lfloor 6/4 \rfloor \bmod 2 = 1\) |
| \(r\) | number of bits of a digit | 2 |
| \(s\) | shift: the number of the lowest bit of the digit | 0 |
| \(\lfloor k / 2^s \rfloor \bmod 2^r\) | the digit of \(r\) bits at shift \(s\) | \(6 \bmod 4 = 2\) |
The second definition names the property on which the whole chapter depends.
Definition 22.2 Stable. A rearrangement of a list by some property of its keys is stable if any 2 keys with equal property keep the relative order they had in the input.
Example. Sorting \(K\) by value is stable if the 2 from position 1 comes before the 2 from position 3, as in Figure 22.1.
Stability is invisible when the keys are plain numbers, because 2 equal numbers look the same. It becomes visible when each key carries a payload, such as the index of a record. As we show in Section 22.4, stability is also required inside the radix sort itself.
Exercises
22.1 Write the keys \((6, 1, 4, 4, 7, 0, 3, 1)\) in binary, and give their digits of 2 bits at
shift 0.
22.2 How many bits do keys below 1,000 need? How many digits of 4 bits?
22.2 Sorting by 1 bit at a time
22.2.1 The sequential algorithm
A radix sort processes the bits from the least significant to the most significant. In each pass, it reads the keys in their current order and splits them into 2 lists: first the keys whose current bit is 0, and then the keys whose current bit is 1, each list in the order in which the keys were read. In the following procedure, \(\mathsf{zeros}\) is the list of keys whose bit is 0, and \(\mathsf{ones}\) is the list of keys whose bit is 1.
Radix-Sort-Bits(\(K, n, B\))
- for \(\mathsf{bitIndex} \in [0, B)\) { // 1 pass per bit, bit 0 first
- \(\mathsf{zeros}\) = empty list, \(\mathsf{ones}\) = empty list
- for \(i \in [0, n)\) {
- if bit \(\mathsf{bitIndex}\) of \(K_i\) is 0: append \(K_i\) to \(\mathsf{zeros}\)
- else: append \(K_i\) to \(\mathsf{ones}\)
- }
- \(K\) = \(\mathsf{zeros}\) followed by \(\mathsf{ones}\) // the split on bit \(\mathsf{bitIndex}\)
- }
Lines 3 to 7 form 1 pass, which we call the split on bit \(\mathsf{bitIndex}\). Figure 22.2 shows the 3 passes on our keys. After the split on bit 0, the even keys \((2, 2, 0, 6)\) come before the odd keys \((5, 7, 3, 5)\). After the split on bit 1, the keys are ordered by their 2 lowest bits. First comes 0, whose 2 lowest bits are 00, then 5 and 5 (01), then 2, 2 and 6 (10), and finally 7 and 3 (11). After the split on bit 2, the keys are sorted.
Line 4 or line 5 executes once per key and pass, that is, \(nB\) times: \(8 \cdot 3 = 24\) times for our example, and \(32n\) times for keys of 32 bits. The work therefore grows linearly with \(n\), and no 2 keys are ever compared.
22.2.2 Why the least significant bit comes first
The last pass decides the order by the most significant bit, and the order established by every earlier pass must survive it. It survives because each split keeps the order of the keys within each of its 2 lists. Consider the 2 keys 2 and 3 after the pass on bit 1 in Figure 22.2. The key 2 = 010 comes before 3 = 011, because the pass on bit 0 put the even keys first. The pass on bit 2 sees the same bit, 0, in both keys, and so it keeps 2 before 3. The following theorem states this argument in general.
Theorem 22.1 If every pass of Radix-Sort-Bits is a stable split, then after the pass on bit \(\mathsf{bitIndex}\), the keys are in increasing order of \(k \bmod 2^{\mathsf{bitIndex}+1}\), their bits 0 to \(\mathsf{bitIndex}\), and keys with equal bits 0 to \(\mathsf{bitIndex}\) are in input order. In particular, after the pass on bit \(B - 1\) the keys are sorted, and the sort is stable.
The quantity \(k \bmod 2^{\mathsf{bitIndex}+1}\) is the number formed by the lowest \(\mathsf{bitIndex} + 1\) bits of the key, bits 0 to \(\mathsf{bitIndex}\), which are exactly the bits that the passes so far have looked at. After the pass on bit 1, for example, it is \(k \bmod 4\), the 2 lowest bits. In the order of Figure 22.2 after that pass, \((0, 5, 5, 2, 2, 6, 7, 3)\), these values are \((0, 1, 1, 2, 2, 2, 3, 3)\), which are indeed in increasing order.
Proof. We show that the loop of lines 1 to 8 maintains the statement as an invariant, writing \(v_{\mathsf{bitIndex}}(k) = k \bmod 2^{\mathsf{bitIndex}+1}\).
Initialization. Before the first pass, take \(\mathsf{bitIndex} = -1\): \(v_{-1}(k) = 0\) for every key, and the keys are in input order.
Maintenance. Assume the statement holds after the pass on bit \(\mathsf{bitIndex} - 1\), and take 2 keys \(k\) and \(k’\). If their bits \(\mathsf{bitIndex}\) differ, the split on bit \(\mathsf{bitIndex}\) puts the key with bit 0 first. Bit \(\mathsf{bitIndex}\) is the most significant of bits 0 to \(\mathsf{bitIndex}\), so that key has the smaller \(v_{\mathsf{bitIndex}}\), and the order is correct. If their bits \(\mathsf{bitIndex}\) are equal, the split is stable and keeps the order of the previous pass, which is the order of \(v_{\mathsf{bitIndex}-1}\), with input order among equal values. Since \(v_{\mathsf{bitIndex}}(k) - v_{\mathsf{bitIndex}}(k’) = v_{\mathsf{bitIndex}-1}(k) - v_{\mathsf{bitIndex}-1}(k’)\) when bit \(\mathsf{bitIndex}\) is equal, that order is the order of \(v_{\mathsf{bitIndex}}\), with input order among equal values.
Termination. After the pass on bit \(B - 1\), \(v_{B-1}(k) = k\) for every key of \(B\) bits, so the keys are sorted, and equal keys are in input order.
| Symbol | Meaning | Keys 2 and 3, \(\mathsf{bitIndex} = 2\) |
|---|---|---|
| \(v_{\mathsf{bitIndex}}(k)\) | the lowest \(\mathsf{bitIndex} + 1\) bits of \(k\), read as a number | \(v_2(2) = 2\), \(v_2(3) = 3\) |
| \(v_{\mathsf{bitIndex}-1}(k)\) | the same before the pass on bit \(\mathsf{bitIndex}\) | \(v_1(2) = 2\), \(v_1(3) = 3\) |
The case of equal bits can be checked on the keys 2 and 3 in the pass on bit 2. Both have bit 2 equal to 0, so their difference does not change: \(v_2(3) - v_2(2) = 3 - 2 = 1\), which equals \(v_1(3) - v_1(2)\). The order of the previous pass, 2 before 3, is therefore also the correct order after this pass. The proof uses stability in exactly this 1 place, the case of equal bits. In Section 22.4, we show what happens to our keys when that case fails.
Exercises
22.3 Sort \((6, 1, 4, 4, 7, 0, 3, 1)\) with Radix-Sort-Bits, writing the keys after each pass.
22.4 Sort \(K\) with the most significant bit first, by the same splits. Where does the result
differ from the sorted list, and why?
22.3 A split is 2 compactions
22.3.1 Positions from a scan
A split on the GPU cannot append keys to lists, because the threads would have to agree on the order of the appends. Instead, every key computes its own output position, as in the stream compaction of Section 21.8. The keys whose bit \(\mathsf{bitIndex}\) is 0 form 1 compaction. Their flag is \(z_i = 1\) when bit \(\mathsf{bitIndex}\) of key \(i\) is 0, and key \(i\) goes to position \(e_i\), the exclusive scan of these flags. The keys whose bit is 1 form a second compaction, written after the keys of the first one. We write \(\mathsf{zeros}\) for the number of keys whose bit is 0.
The second compaction needs no second scan. Of the \(i\) keys before position \(i\), \(e_i\) have bit 0, so the remaining \(i - e_i\) have bit 1. A key with bit 1 must therefore come after all \(\mathsf{zeros}\) keys with bit 0 and after the \(i - e_i\) keys with bit 1 that precede it, and so it goes to position
\[ \mathsf{zeros} + i - e_i. \]
| Symbol | Meaning | Key 7 at position 2, bit 0 |
|---|---|---|
| \(i\) | input position of the key | 2 |
| \(z_i\) | 1 if bit \(\mathsf{bitIndex}\) of the key is 0, else 0 | 0 |
| \(e_i\) | keys with bit 0 before position \(i\): the exclusive scan of \(z\) | 1 |
| \(i - e_i\) | keys with bit 1 before position \(i\) | 1 |
| \(\mathsf{zeros}\) | number of keys with bit 0 in the whole list | 4 |
Figure 22.3 works out the split on bit 0 of our keys. The flags of the keys with bit 0 are \((0, 1, 0, 1, 1, 1, 0, 0)\), their exclusive scan is \((0, 0, 1, 1, 2, 3, 4, 4)\), and \(\mathsf{zeros} = 4\). The key 5 at position 0 has bit 1 and goes to \(4 + 0 - 0 = 4\). The key 7 at position 2 also has bit 1 and goes to \(4 + 2 - 1 = 5\). The key 2 at position 3 has bit 0 and goes to \(e_3 = 1\).
Key observation 1 exclusive scan of the zero flags places both groups of a split: a key with bit 0 goes to \(e_i\), and a key with bit 1 goes to \(\mathsf{zeros} + i - e_i\), where \(\mathsf{zeros}\) is the number of keys with bit 0. Each group is a stream compaction, so the split inherits the stability of compaction.
22.3.2 The algorithm
In the following procedure, \(s\) is the inclusive scan of the flags, from which line 5 recovers the exclusive scan \(e_i\), and line 3 reads \(\mathsf{zeros}\) as the last inclusive value.
Parallel-Split(\(K, \mathsf{out}, n, \mathsf{bitIndex}\))
- for every \(i \in [0, n)\) in parallel: \(z_i = 1\) if bit \(\mathsf{bitIndex}\) of \(K_i\) is 0, else 0
- \(s\) = the inclusive scan of \(z\) // Scan of Section 21.7
- \(\mathsf{zeros} = s_{n-1}\) // the keys with bit 0
- for every \(i \in [0, n)\) in parallel {
- \(e_i = s_i - z_i\) // the exclusive scan
- if \(z_i = 1\): \(\mathsf{out}_{e_i} = K_i\)
- else: \(\mathsf{out}_{\mathsf{zeros} + i - e_i} = K_i\)
- }
Theorem 22.2 Parallel-Split writes every key exactly once, the positions form a permutation of \([0, n)\), and the split is stable.
Proof. By Theorem 21.2, the keys with bit 0 receive the distinct positions \([0, \mathsf{zeros})\) in input order. A key with bit 1 at position \(i\) receives \(\mathsf{zeros}\) plus the number of keys with bit 1 before it. For 2 such keys at \(i < j\), that number grows by at least 1. These positions are therefore distinct, increase with the input position, and run from \(\mathsf{zeros}\) to \(\mathsf{zeros} + (n - \mathsf{zeros}) - 1 = n - 1\). The 2 ranges \([0, \mathsf{zeros})\) and \([\mathsf{zeros}, n)\) do not overlap and together hold \(n\) positions.
In our example, the 4 keys with bit 1 receive the positions 4, 5, 6 and 7, in the order of their input positions 0, 2, 6 and 7, and the 4 keys with bit 0 receive the positions 0 to 3. A pass of Parallel-Split moves every key once, as the sequential split does. In addition, the parallel split writes the flags, scans them and reads them back, and we count the cost of this extra traffic in Section 22.5.
Exercises
22.5 Carry out Parallel-Split on bit 1 of \((2, 2, 0, 6, 5, 7, 3, 5)\), the output of Figure
22.3, and check the result against Figure 22.2.
22.6 Why does line 7 not need the inclusive scan of the flags of the bit-1 keys?
22.4 Stability
22.4.1 An unstable split
Suppose that a split puts the keys with bit 0 first, as it must, but writes the keys with bit 1 in some other order, for example in reverse. On its own bit, this is still a correct split. We apply it to bit 1 of the keys after the first pass, \((2, 2, 0, 6, 5, 7, 3, 5)\). The keys whose bit 1 is 0 are \((0, 5, 5)\), and they stay in order. The keys whose bit 1 is 1 are \((2, 2, 6, 7, 3)\), and they come out reversed, as \((3, 7, 6, 2, 2)\). The pass on bit 2, which is stable again, then gives \((0, 3, 2, 2, 5, 5, 7, 6)\), as Figure 22.4 shows.
The keys 3 = 011 and 2 = 010 have the same bits 1 and 2, and only bit 0 tells them apart. The first pass had put 2 before 3. The unstable pass reversed them, and the last pass, which saw equal bits, kept the reversed order. As a result, 3 now precedes 2, and 7 precedes 6, which differ in the same way. This is the case of equal bits in the proof of Theorem 22.1, and it is the only place where the proof needs stability.
A split that hands out output positions in the order in which the threads arrive, for example by incrementing a shared counter, produces such an order. We run a split of this kind on the GPU in Section 22.8.
Rule Every pass of a least-significant-digit radix sort must be stable. A pass that places equal digits in any other order than the input order destroys the work of the passes before it.
Exercises
22.7 Which positions of the final result are wrong if the first pass, on bit 0, is the unstable
one and the other 2 are stable?
22.8 Does the last pass of a radix sort need to be stable when the keys carry no payload? Give a
reason.
22.5 The cost of 1-bit passes
A sort of 32-bit keys by Parallel-Split takes 32 passes. Each pass is memory-bound. It performs a few operations per key and moves several bytes per key, so its time is set by the bytes it moves. We count these bytes per key of 4 bytes. Line 1 reads the key and writes the flag, which is 8 bytes. The scan of Section 21.7 reads and writes the flags twice, which is 16 bytes. Lines 4 to 8 read the key, the flag and the scan, and write the key, which is another 16 bytes. A pass therefore moves \(8 + 16 + 16 = 40\) bytes per key, and the sort moves \(32 \times 40 = 1{,}280\) bytes per key, or 21.5 GB to sort 16,777,216 keys of 64 MiB in all.
The way to reduce this traffic is to reduce the number of passes. With a digit of \(r\) bits, a sort of 32-bit keys takes \(32 / r\) passes, so that with \(r = 4\), it needs 8 passes instead of 32. A pass on a digit of \(r\) bits, however, splits the keys into \(2^r\) groups rather than 2, and 1 scan of 1 flag no longer gives every group its start. Every key needs to know how many keys have each smaller digit, so the keys must be counted by digit. That count is a histogram, the subject of the next section.
22.6 Histograms
22.6.1 Counting by value
Definition 22.3 Histogram. The histogram of a list of keys over \(R\) bins is the array \(h\) of \(R\) counts in which \(h_{\mathsf{bin}}\) is the number of keys whose digit, or value, is \(\mathsf{bin}\).
Example. The histogram of \(K\) by value, over 8 bins, is \(h = (1, 0, 2, 1, 0, 2, 1, 1)\): 1 key 0, no key 1, 2 keys 2, and so on.
Each count of a histogram is called a bin. In the example, bin 2 holds \(h_2 = 2\), because the key 2 occurs twice, at positions 1 and 3. The sequential algorithm reads every key once and adds 1 to its bin.
Histogram(\(K, h, n, R\))
- for \(\mathsf{bin} \in [0, R)\): \(h_{\mathsf{bin}} = 0\)
- for \(i \in [0, n)\) {
- \(h_{K_i} = h_{K_i} + 1\) // a read, an addition and a write
- }
In line 3, the key \(K_i\) itself serves as the index of the bin. For \(i = 1\), for example, \(K_1 = 2\), and line 3 adds 1 to \(h_2\).
22.6.2 1 thread per key, and atomic additions
The direct parallel version gives every key its own thread, and each thread executes line 3 for its key. Line 3, however, consists of 3 operations. It reads the bin, adds 1, and writes the bin back. In our example, threads 1 and 3 hold the same key, 2. If both read \(h_2 = 0\) before either of them writes, both write 1, and 1 of the 2 counts is lost. The GPU offers an operation that cannot be split in this way.
Definition 22.4 Atomic operation. An atomic operation reads a
memory location, modifies the value and writes it back as 1 indivisible step. No other thread can
access the location between the read and the write. When several threads apply atomic operations
to the same location, the hardware performs them one after the other, in an order it chooses, and
every one of them takes effect. In CUDA C++, the atomic addition is atomicAdd(&h[v], 1); in
cuda-oxide, it is the method fetch_add of an atomic type such as DeviceAtomicU32.
Example. Threads 1 and 3 each apply an atomic addition of 1 to \(h_2\). Whatever their order, \(h_2\) ends at 2.
Atomic operations make the histogram correct, but they introduce a new cost when many threads update the same bin.
Definition 22.5 Contention. Contention is the waiting that occurs when several threads apply atomic operations to the same location at about the same time: since the operations are performed one after the other, each waits for those before it.
Example. Bins 2 and 5 each receive 2 requests from our 8 threads, and 1 of the 2 requests waits for the other (Figure 22.5).
Atomic operations on global memory are performed in the L2 cache, which all SMs share, and the requests to 1 address are queued there. In Section 5.5.2, we measured this queue. A histogram of 64 MiB of bytes into 256 global bins took 33.40 ms for random bytes and 134.65 ms for bytes that were all 7, 4 times as long, because every request went to the same address. A radix pass with digits of 4 bits has only 16 bins, so even random keys send 1/16 of all requests to each address.
22.6.3 Private bins
The solution is to let fewer threads share a bin. Each block counts its keys into its own copy of the bins in shared memory, where only the threads of that block compete, and where an atomic operation completes within the SM. When the block has counted all of its keys, it adds each of its bins to the corresponding global bin once, as Figure 22.6 shows.
Definition 22.6 Privatization. Privatization gives each block, or each warp, a private copy of a shared result, lets it update only its copy, and merges the copies into the shared result at the end.
Example. Block 0 counts the keys 5, 2, 7, 2 into the private bins \((0, 0, 2, 0, 0, 1, 0, 1)\), block 1 counts 0, 6, 3, 5 into \((1, 0, 0, 1, 0, 1, 1, 0)\), and their sum is the histogram.
In the following procedure, \(\mathsf{privateBins}\) is the array of \(R\) private bins in shared memory.
Histogram-Private(\(K, h, n, R\))
- if \(\mathsf{threadIdx{.}x} < R\): \(\mathsf{privateBins}[\mathsf{threadIdx{.}x}] = 0\) // \(\mathsf{privateBins}\) in shared memory
- Barrier() // every private bin is 0
- for \(i = \mathsf{blockIdx{.}x} \cdot \mathsf{blockDim{.}x} + \mathsf{threadIdx{.}x}\); \(i < n\); \(i = i + \mathsf{gridDim{.}x} \cdot \mathsf{blockDim{.}x}\) {
- Atomic-Add(\(\mathsf{privateBins}[\mathsf{digit}(K_i)]\), 1)
- }
- Barrier() // every key of the block is counted
- if \(\mathsf{threadIdx{.}x} < R\): Atomic-Add(\(h_{\mathsf{threadIdx{.}x}}\), \(\mathsf{privateBins}[\mathsf{threadIdx{.}x}]\)) // the merge
| Symbol | Meaning | Example: \(\mathsf{gridDim{.}x} = 2\), \(\mathsf{blockDim{.}x} = 2\), \(n = 8\) |
|---|---|---|
| \(\mathsf{gridDim{.}x}\), \(\mathsf{blockDim{.}x}\) | number of blocks, and threads per block | 2 and 2 |
| \(\mathsf{gridDim{.}x} \cdot \mathsf{blockDim{.}x}\) | number of threads in the grid, the stride of the loop | 4 |
| \(bT + \mathsf{threadIdx{.}x}\) | the first key of thread \(\mathsf{threadIdx{.}x}\) of block \(\mathsf{blockIdx{.}x}\) | 3 for \(\mathsf{blockIdx{.}x} = 1\), \(\mathsf{threadIdx{.}x} = 1\) |
| \(R\) | number of bins | 8 |
Line 3 is a grid-stride loop. The \(\mathsf{gridDim{.}x} \cdot \mathsf{blockDim{.}x}\) threads of the grid take the keys in rounds, so that in each round, neighboring threads read neighboring keys. In the small grid of the table, thread 1 of block 1 starts at key \(1 \cdot 2 + 1 = 3\) and then moves on to key \(3 + 4 = 7\), while the 4 threads together read keys 0 to 3 in the first round and keys 4 to 7 in the second. The 2 barriers separate 3 phases. Without the first barrier, a thread could count into a bin that another thread has not yet set to 0. Without the second barrier, thread \(\mathsf{threadIdx{.}x}\) could merge bin \(\mathsf{threadIdx{.}x}\) before the other threads have finished counting into it.
With private bins, the number of atomic operations on global memory falls from 1 per key to \(R\) per block. With \(\mathsf{gridDim{.}x} = 1{,}024\) blocks and \(R = 16\) bins, a histogram of 16,777,216 keys makes \(1{,}024 \cdot 16 = 16{,}384\) atomic additions on global memory instead of 16,777,216, which is 1,024 times fewer.
22.6.4 Warp aggregation
Inside a block, some contention remains. When the 32 lanes of a warp hold the same digit, 32 atomic operations on 1 bin in shared memory are performed one after the other. The lanes can, however, combine their counts first, with the following instruction.
Definition 22.7 Match. A match is an instruction that all 32
lanes of a warp execute together, each with a value; it returns to every lane a 32-bit word
whose bit \(k\) is 1 if lane \(k\) holds the same value. In C++, it is
__match_any_sync(mask, v); in cuda-oxide, warp::match_any_sync(mask, v).
Example. For 8 lanes holding the digits \((1, 2, 3, 2, 0, 2, 3, 1)\), lane 5 receives the bits of lanes 1, 3 and 5, the lanes with digit 2.
With a match, the lowest lane of each group of lanes with equal digits adds the popcount of its word, which is the size of the group, with 1 atomic operation, and the other lanes of the group add nothing. In the example of Definition 22.7, lane 1 adds 3 to the bin of digit 2, and lanes 3 and 5 add nothing. A warp then makes at most 1 atomic operation per distinct digit, instead of 32. This technique is called warp aggregation. It costs a match instruction for every key, and in Section 22.10, we measure whether it pays for itself.
Exercises
22.9 Compute the histogram of \((6, 1, 4, 4, 7, 0, 3, 1)\) over 8 bins. Which bins receive more
than 1 request?
22.10 For 16,777,216 keys, 1,024 blocks and 256 bins, how many atomic operations does
Histogram-Private make on global memory, and how many on shared memory?
22.11 What does the merge of line 7 compute if the second barrier is removed and 1 thread of the
block is delayed?
22.7 A pass on a digit of several bits
22.7.1 The positions from a histogram
We now sort by digits of 2 bits. Our keys have 3 bits, so a first pass on the digit at shift 0, the 2 low bits, followed by a second pass on bit 2, sorts them. The digits of the first pass are \((1, 2, 3, 2, 0, 2, 3, 1)\). For example, the key 5 = 101 has the 2 low bits 01, so its digit is 1. The histogram of these digits over 4 bins is \((1, 2, 3, 2)\): 1 key with digit 0, 2 with digit 1, 3 with digit 2 and 2 with digit 3.
In the output of the pass, the key with digit 0 comes first, at position 0. The 2 keys with digit 1 follow at positions 1 and 2, the 3 keys with digit 2 at positions 3, 4 and 5, and the 2 keys with digit 3 at positions 6 and 7. The start of each digit, \((0, 1, 3, 6)\), is therefore the exclusive scan of the histogram. Within a digit, the keys keep their input order. The first key with digit 2, the 2 at position 1, goes to position 3, the second, the 2 at position 3, goes to position 4, and the third, the 6 at position 5, goes to position 5. The number of keys with the same digit that come before a key has its own name.
Definition 22.8 Rank. The rank of a key in a pass is the number of keys before it, in input order, that have the same digit.
Example. In the pass on the 2 low bits, the 6 at position 5 has digit 2, and 2 keys with digit 2 come before it, at positions 1 and 3: its rank is 2.
Key observation The exclusive scan of the digit histogram gives the start of every digit in the output, and a key goes to the start of its digit plus its rank. The split of Section 22.3 is the case of 1 bit: 2 bins, a start of 0 for digit 0 and \(Z\) for digit 1, and ranks \(e_i\) and \(i - e_i\).
For the 6 at position 5, the start of digit 2 is 3 and its rank is 2, so it goes to position \(3 + 2 = 5\). Figure 22.7 carries out the whole pass. The output, \((0, 5, 5, 2, 2, 6, 7, 3)\), is the output of the 2 splits on bits 0 and 1 in Figure 22.2, as it must be, since 1 stable pass on 2 bits sorts by those 2 bits, as 2 stable passes on 1 bit do.
On a CPU, this pass is the counting sort, which consists of 3 loops over the keys and the bins. In the following procedure, \(s\) is the shift and \(r\) the number of bits of the digit, as in Definition 22.1, and \(\mathsf{start}[\mathsf{digit}]\) is the next free output position for a key with digit \(\mathsf{digit}\).
Counting-Pass(\(K, \mathsf{out}, n, s, r\))
- \(h\) = the histogram of the digits \(\lfloor K_i / 2^s \rfloor \bmod 2^r\) over \(2^r\) bins
- \(\mathsf{start}\) = the exclusive scan of \(h\)
- for \(i \in [0, n)\) { // in input order
- \(\mathsf{digit}\) = the digit of \(K_i\)
- \(\mathsf{out}_{start[\mathsf{digit}]} = K_i\)
- \(\mathsf{start}[\mathsf{digit}] = \mathsf{start}[\mathsf{digit}] + 1\) // the next key with digit \(\mathsf{digit}\)
- }
In line 5, \(\mathsf{start}[\mathsf{digit}]\) has grown by 1 for every earlier key with digit \(\mathsf{digit}\), so it equals the start of \(\mathsf{digit}\) plus the rank of the key. For the 6 at position 5, \(\mathsf{start}[2]\) began at 3 and grew by 1 for each of the 2 keys at positions 1 and 3, so it equals 5. Line 6 forms a chain like the counter of Sequential-Compact, because the rank of each key depends on all the keys before it.
22.7.2 Many tiles
On the GPU, the keys are cut into tiles of 1,024 keys, 1 block per tile, as in Section 21.7. A block can count the digits of its own tile and rank its own keys. The position of a key, however, also depends on the keys with smaller digits in every tile, and on the keys with the same digit in earlier tiles. Both of these numbers come from 1 scan, provided that the counts of all tiles are laid out digit by digit. The table holds first the count of digit 0 in tile 0, in tile 1, and so on, then the counts of digit 1 in every tile, and so on. With \(m\) tiles, the count of digit \(\mathsf{digit}\) in tile \(b\) is entry \(dm + b\) of the table. The exclusive scan of this table at entry \((\mathsf{digit}, b)\) is the number of keys with a smaller digit anywhere, plus the number of keys with digit \(\mathsf{digit}\) in the tiles before \(b\), which is exactly the start of digit \(\mathsf{digit}\) in tile \(b\).
Figure 22.8 shows the table for our keys, cut into 2 tiles of 4. Tile 0 holds the digits \((1, 2, 3, 2)\), and tile 1 holds \((0, 2, 3, 1)\). With \(m = 2\), the count of digit 1 in tile 1 is entry \(1 \cdot 2 + 1 = 3\) of the table. The scan of the table places digit 1 of tile 1 at position 2, after the key 0 of tile 1 and the key 5 of tile 0. The keys of tile 1 then land at positions 0, 5, 7 and 2, the same positions as in Figure 22.7.
Inside a tile, the rank of a key is the number of keys with the same digit before it in the tile. A block processes its tile in 4 steps of 256 keys. Within a step, the match of Definition 22.7 gives each lane the lanes of its warp that hold the same digit. Keeping only the bits of the lanes below it, and counting them, gives the rank of the key within the warp, just as the ballot gave the position within the warp in Section 21.9 (Figure 22.9). The counts of the earlier warps of the step, and of the earlier steps of the tile, complete the rank.
22.7.3 The algorithm
A pass on the digit of \(r = 4\) bits at shift \(s\) has three parts. The first kernel counts the digits of every tile with private bins, as in lines 1 to 6 of Histogram-Private but without a grid-stride loop, and writes its 16 counts into column \(\mathsf{blockIdx{.}x}\) of the table \(c\). Scan then computes the inclusive scan of the table, which has \(16 \cdot \mathsf{tiles}\) entries for \(\mathsf{tiles}\) tiles. The second kernel moves the keys.
In the following procedure, \(c\) is the table of counts and \(s\) its inclusive scan, so that \(s_j - c_j\) is the exclusive scan at entry \(j\). In line 1, thread \(\mathsf{threadIdx{.}x} < 16\) stands for digit \(\mathsf{threadIdx{.}x}\), and the entry \(\mathsf{entry} = \mathsf{threadIdx{.}x} \cdot \mathsf{tiles} + \mathsf{blockIdx{.}x}\) is the count of that digit in tile \(\mathsf{blockIdx{.}x}\). The shared array \(\mathsf{start}\) holds, for each digit, the output position of the next key with that digit, and the shared array \(\mathsf{warpCounts}\) holds, for each warp \(\mathsf{warp}\) and digit \(\mathsf{digit}\), the number of keys with digit \(\mathsf{digit}\) in warp \(\mathsf{warp}\) in the current step.
Scatter-Digits(\(K, \mathsf{out}, c, s\))
- if \(\mathsf{threadIdx{.}x} < 16\): \(\mathsf{start}[\mathsf{threadIdx{.}x}] = s_{\mathsf{entry}} - c_{\mathsf{entry}}\) // the exclusive scan of the table
- for \(\mathsf{step} \in [0, 4)\) { // 4 steps of 256 keys, in order
- set \(\mathsf{warpCounts}[\cdot][\cdot]\) to 0; Barrier()
- \(i = 1024 \cdot \mathsf{blockIdx{.}x} + 256 \cdot \mathsf{step} + \mathsf{threadIdx{.}x}\), \(\mathsf{digit}\) = the digit of \(K_i\)
- \(\mathsf{peers}\) = Match(\(\mathsf{digit}\)), \(\mathsf{rank}\) = Popc(\(\mathsf{peers} \wedge (2^{\mathsf{lane}} - 1)\))
- if \(\mathsf{rank} = 0\): \(\mathsf{warpCounts}[\mathsf{warp}][\mathsf{digit}]\) = Popc(\(\mathsf{peers}\)) // 1 lane per digit and warp
- Barrier()
- \(\mathsf{out}[\mathsf{start}[\mathsf{digit}] + \sum_{\mathsf{other} < \mathsf{warp}} \mathsf{warpCounts}[\mathsf{other}][\mathsf{digit}] + \mathsf{rank}] = K_i\)
- Barrier()
- if \(\mathsf{threadIdx{.}x} < 16\): \(\mathsf{start}[\mathsf{threadIdx{.}x}] \mathrel{+}= \sum_{\mathsf{warp}=0}^{7} \mathsf{warpCounts}[\mathsf{warp}][\mathsf{threadIdx{.}x}]\)
- Barrier()
- }
| Symbol | Meaning | Lane 5 in the 8-lane example |
|---|---|---|
| \(\mathsf{digit}\) | digit of the key of this thread | 2 |
| \(\mathsf{peers}\) | lanes of the warp with the same digit, from the match | lanes 1, 3 and 5 |
| \(2^{\mathsf{lane}} - 1\) | mask of the lanes below lane \(\mathsf{lane}\) | lanes 0 to 4 |
| \(\mathsf{rank}\) | lanes below this one with the same digit | 2 (lanes 1 and 3) |
| \(\mathsf{warpCounts}[\mathsf{warp}][\mathsf{digit}]\) | keys with digit \(\mathsf{digit}\) in warp \(\mathsf{warp}\), written by the lane with rank 0 | 3, written by lane 1 |
| \(\mathsf{start}[\mathsf{digit}]\) | output position of the next key with digit \(\mathsf{digit}\) in this tile | 3 in the 1-tile example |
Line 8 corresponds to line 5 of Counting-Pass, with the rank assembled from three parts. The first part is the number of keys with the same digit in the earlier steps of the tile, which line 10 has added to \(\mathsf{start}[\mathsf{digit}]\). The second part is the number of such keys in the earlier warps of the step, and the third part is the number in the earlier lanes of the warp. In the 8-lane example, taken as a single tile and a single warp, lane 5 writes its key 6 to position \(\mathsf{start}[2] + \mathsf{rank} = 3 + 2 = 5\).
Each of the 4 barriers separates a write to the shared arrays from the reads that need it. The barrier of line 3 completes the clearing of \(\mathsf{warpCounts}\) before any lane writes a count, and line 7 completes the counts before any thread sums them. Line 9 completes every read of \(\mathsf{start}\) before line 10 changes it, and line 11 completes the change before the next step reads \(\mathsf{start}\).
22.7.4 Counting the bytes
A pass reads every key twice, once in the counting kernel and once in the scatter, and writes it once, which is 12 bytes per key. The table holds 16 counts per 1,024 keys, so its scan moves less than 1 byte per key. A sort of 32-bit keys by 8 passes of 4 bits therefore moves about \(8 \times 12 = 96\) bytes per key, against 1,280 bytes for 32 passes of 1 bit, which is 13 times less.
Exercises
22.12 Carry out Counting-Pass on the digit of 2 bits at shift 1 of \(K\). What are the
histogram, the starts and the output?
22.13 Build the table of Figure 22.8 for 4 tiles of 2 keys, and give its exclusive scan.
22.14 How many bytes per key does a sort by 4 passes of 8 bits move, if the scan of the table is
counted too? (A tile has 256 counts.)
22.8 Correctness
Theorem 22.3 A pass of Scatter-Digits writes every key of the input exactly once, the positions form a permutation of \([0, n)\), and keys with equal digits keep their input order.
Proof. Let \(c(\mathsf{digit}, \mathsf{blockIdx{.}x})\) be the number of keys with digit \(\mathsf{digit}\) in tile \(\mathsf{blockIdx{.}x}\), and \(S(\mathsf{digit}, \mathsf{blockIdx{.}x})\) the exclusive scan of the table at entry \((\mathsf{digit}, \mathsf{blockIdx{.}x})\): the number of keys with a digit below \(\mathsf{digit}\), plus the keys with digit \(\mathsf{digit}\) in tiles before \(\mathsf{blockIdx{.}x}\). We show that the keys with digit \(\mathsf{digit}\) of tile \(\mathsf{blockIdx{.}x}\) receive the positions \(S(\mathsf{digit}, \mathsf{blockIdx{.}x})\) to \(S(\mathsf{digit}, \mathsf{blockIdx{.}x}) + c(\mathsf{digit}, \mathsf{blockIdx{.}x}) - 1\), in input order. The step \(\mathsf{step}\), the warp \(\mathsf{warp}\) and the lane \(\mathsf{lane}\) of a key order the keys of a tile as their indices do, since the index is \(1024 \cdot \mathsf{blockIdx{.}x} + 256 \cdot \mathsf{step} + 32 \cdot \mathsf{warp} + \mathsf{lane}\). In line 8, the position of a key is \(S(\mathsf{digit}, \mathsf{blockIdx{.}x})\) plus 3 counts of keys with digit \(\mathsf{digit}\): those in the earlier steps (added to \(\mathsf{start}[\mathsf{digit}]\) by line 10 of each earlier step), those in the earlier warps of the step, and those in the earlier lanes of the warp. Together they are exactly the keys with digit \(\mathsf{digit}\) before it in the tile. These numbers are \(0, 1, \ldots, c(\mathsf{digit}, \mathsf{blockIdx{.}x}) - 1\) in input order. The ranges for different \((\mathsf{digit}, \mathsf{blockIdx{.}x})\) follow each other in the order of the table, without gap or overlap, and the last ends at \(n - 1\).
| Symbol | Meaning | Digit 1, tile 1 of Figure 22.8 |
|---|---|---|
| \(c(\mathsf{digit}, \mathsf{blockIdx{.}x})\) | keys with digit \(\mathsf{digit}\) in tile \(\mathsf{blockIdx{.}x}\) | 1 (the key 5) |
| \(S(\mathsf{digit}, \mathsf{blockIdx{.}x})\) | start of digit \(\mathsf{digit}\) in tile \(\mathsf{blockIdx{.}x}\): the exclusive scan of the table | 2 |
| \(S(\mathsf{digit}, \mathsf{blockIdx{.}x})\) to \(S(\mathsf{digit}, \mathsf{blockIdx{.}x}) + c(\mathsf{digit}, \mathsf{blockIdx{.}x}) - 1\) | the positions of these keys | 2 to 2 |
Rank and stability are the same thing here. The rank counts the keys that come before a key in input order, so a pass that places keys by rank is stable by construction, and a pass that places them by any other count is not. To see the difference on the GPU, we replaced the position of line 8 by an atomic increment of \(\mathsf{start}[\mathsf{digit}]\), and removed line 10. The increment hands every key the next free position of its digit, in the order in which the threads arrive. We ran the C++ program with this change, and it printed the following lines.
$ ./unstable # out[atomicAdd(&start[d], 1)] = key
radix sort of 5 2 7 2 0 6 3 5
...
4-bit pass 0 2 2 3 5 5 6 7
...
method 1 run 1: 5618124 neighbours out of order, 15278248 keys misplaced
method 1 run 2: 5627284 neighbours out of order, 15294346 keys misplaced
method 1 run 3: 5638523 neighbours out of order, 15291387 keys misplaced
FAILED
On the 8 keys, the result was correct, because the 8 lanes of 1 warp happened to obtain their positions in lane order. On 16,777,216 keys, 15.3 million keys ended in the wrong place, 5.6 million neighbors were out of order, and the counts differed from run to run. Every pass still grouped the keys correctly by its own digit. Only the order inside the groups was lost, and with it the work of the earlier passes, as in Figure 22.4.
Exercises
22.15 In Scatter-Digits, which wrong position can a key receive if the barrier of line 9 is
removed? Describe a schedule.
22.16 Prove that \(S(\mathsf{digit}, \mathsf{blockIdx{.}x}) + c(\mathsf{digit}, \mathsf{blockIdx{.}x}) = S(\mathsf{digit}, \mathsf{blockIdx{.}x} + 1)\) for \(\mathsf{blockIdx{.}x} < \mathsf{tiles} - 1\), and
\(S(\mathsf{digit}, \mathsf{tiles} - 1) + c(\mathsf{digit}, \mathsf{tiles} - 1) = S(\mathsf{digit} + 1, 0)\).
22.9 Implementation
22.9.1 The histograms
The following listing implements Histogram-Private for digits of 4 bits. Each block clears its 16 private bins, counts its keys into them with a grid-stride loop, and merges them into the global bins.
Listing 22.1 A histogram of 4-bit digits with private bins.
mod kernels {
// ...
/// 2. Each block counts into private bins in shared memory and merges them once.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn hist_shared(keys: &[u32], shift: u32, bins: &[DeviceAtomicU32]) {
static mut LOCAL: SharedArray<u32, RADIX> = SharedArray::UNINIT;
let tid = thread::threadIdx_x() as usize;
if tid < RADIX {
// SAFETY: threads 0 to 15 each zero their own bin, before the barrier.
unsafe { LOCAL[tid] = 0 };
}
thread::sync_threads();
// SAFETY: between the 2 barriers every access to LOCAL is atomic.
let local = unsafe { (*&raw mut LOCAL).as_mut_ptr() };
let stride = (thread::gridDim_x() * 256) as usize;
let mut index = thread::index_1d().get();
while index < keys.len() {
let digit = digit_of(keys[index], shift);
// SAFETY: d < RADIX, and LOCAL holds RADIX bins.
unsafe { shared_bin(local, digit) }.fetch_add(1, AtomicOrdering::Relaxed);
index += stride;
}
thread::sync_threads();
if tid < RADIX {
// SAFETY: after the barrier no thread writes LOCAL again.
let count = unsafe { LOCAL[tid] };
bins[tid].fetch_add(count, AtomicOrdering::Relaxed);
}
}
// ...
}
// 2. Each block counts into private bins in shared memory and merges them once.
__global__ void histShared(const unsigned* keys, int shift, unsigned* bins, int n)
{
__shared__ unsigned local[RADIX];
if (threadIdx.x < RADIX) {
local[threadIdx.x] = 0;
}
__syncthreads();
int stride = gridDim.x * blockDim.x;
for (int index = blockIdx.x * blockDim.x + threadIdx.x; index < n; index += stride) {
atomicAdd(&local[digitOf(keys[index], shift)], 1u);
}
__syncthreads();
if (threadIdx.x < RADIX) {
atomicAdd(&bins[threadIdx.x], local[threadIdx.x]);
}
}
The bins in shared memory are a SharedArray<u32, RADIX> in Rust and a __shared__ array in
C++. CUDA C++ applies atomicAdd to any address. cuda-oxide, on the other hand, gives atomics their
own types, with the scope of the threads that may share them in the name. The type
DeviceAtomicU32 is used for global memory, which every thread of the grid can reach, and
BlockAtomicU32 for shared memory, which only the threads of the block can reach. The global bins
arrive as a slice &[DeviceAtomicU32], which the host creates by reinterpreting a buffer of u32
with cast_elem. A shared bin is viewed as a BlockAtomicU32 with BlockAtomicU32::from_ptr,
which the helper shared_bin wraps. The pointer comes from the SharedArray, so the call is
unsafe, and its safety comment states that the digit is below 16.
The next listing implements the same histogram with warp aggregation. The lanes of a warp that hold the same digit find each other with a match, and only the lowest of them adds the count of the group to the private bin.
Listing 22.2 The same histogram with warp aggregation.
mod kernels {
// ...
/// 3. As 2, but the lanes of a warp with equal digits add their count with 1 atomic.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn hist_aggregated(keys: &[u32], shift: u32, bins: &[DeviceAtomicU32]) {
static mut LOCAL: SharedArray<u32, RADIX> = SharedArray::UNINIT;
let tid = thread::threadIdx_x() as usize;
if tid < RADIX {
// SAFETY: threads 0 to 15 each zero their own bin, before the barrier.
unsafe { LOCAL[tid] = 0 };
}
thread::sync_threads();
// SAFETY: between the 2 barriers every access to LOCAL is atomic.
let local = unsafe { (*&raw mut LOCAL).as_mut_ptr() };
let lane = warp::lane_id();
let stride = (thread::gridDim_x() * 256) as usize;
let mut base = thread::blockIdx_x() as usize * 256;
while base < keys.len() {
let index = base + tid;
let inside = index < keys.len();
let digit = if inside { digit_of(keys[index], shift) } else { RADIX };
let peers = warp::match_any_sync(u32::MAX, digit as u32);
let leader = peers.trailing_zeros();
if lane == leader && digit < RADIX {
// SAFETY: d < RADIX, and LOCAL holds RADIX bins.
let bin = unsafe { shared_bin(local, digit) };
bin.fetch_add(peers.count_ones(), AtomicOrdering::Relaxed);
}
base += stride;
}
thread::sync_threads();
if tid < RADIX {
// SAFETY: after the barrier no thread writes LOCAL again.
let count = unsafe { LOCAL[tid] };
bins[tid].fetch_add(count, AtomicOrdering::Relaxed);
}
}
// ...
}
// 3. As 2, but the lanes of a warp with equal digits add their count with 1 atomic.
__global__ void histAggregated(const unsigned* keys, int shift, unsigned* bins, int n)
{
__shared__ unsigned local[RADIX];
if (threadIdx.x < RADIX) {
local[threadIdx.x] = 0;
}
__syncthreads();
int lane = threadIdx.x % 32;
int stride = gridDim.x * blockDim.x;
for (int base = blockIdx.x * blockDim.x; base < n; base += stride) {
int index = base + threadIdx.x;
unsigned digit = index < n ? digitOf(keys[index], shift) : RADIX;
unsigned peers = __match_any_sync(FULL, digit);
int leader = __ffs(peers) - 1;
if (lane == leader && digit < RADIX) {
atomicAdd(&local[digit], __popc(peers));
}
}
__syncthreads();
if (threadIdx.x < RADIX) {
atomicAdd(&bins[threadIdx.x], local[threadIdx.x]);
}
}
The loop runs over base, the first key of the round of the block, rather than over the key
itself, so that all 32 lanes of every warp execute the match together, including the lanes past
the end of the array. Those lanes match on the value 16, which no digit has, and add nothing. The
variable leader is the lowest lane of the group, the position of the lowest 1 bit of peers.
22.9.2 The split
The following listing implements lines 4 to 8 of Parallel-Split, in which every key computes its position from the scan of the zero flags and writes itself there. The flags and the scan are the kernels of Chapter 21.
Listing 22.3 The scatter of a split on 1 bit.
mod kernels {
// ...
/// Zero-bit keys go to their exclusive scan, one-bit keys after all zero-bit keys.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn split_scatter(
keys: &[u32],
flags: &[u32],
scanned: &[u32],
mut out: DisjointSlice<u32>,
) {
let index = thread::index_1d().get();
if index < keys.len() {
let zeros = scanned[keys.len() - 1] as usize;
let upto = scanned[index] as usize; // zero-bit keys among 0 to i
let at = if flags[index] == 1 { upto - 1 } else { zeros + index - upto };
// SAFETY: zero-bit keys receive 0 to zeros - 1 and one-bit keys zeros to
// n - 1, each position once: a permutation of 0 to n - 1.
unsafe { *out.get_unchecked_mut(at) = keys[index] };
}
}
// ...
}
// Zero-bit keys go to their exclusive scan, one-bit keys after all zero-bit keys.
__global__ void splitScatter(const unsigned* keys, const unsigned* flags,
const unsigned* scanned, unsigned* out, int n)
{
int index = blockIdx.x * blockDim.x + threadIdx.x;
if (index < n) {
unsigned zeros = scanned[n - 1];
unsigned upto = scanned[index]; // zero-bit keys among 0 to index
unsigned at = flags[index] == 1 ? upto - 1 : zeros + index - upto;
out[at] = keys[index];
}
}
The variable zeros is \(Z\), and upto is the inclusive scan \(s_i\), so that upto - 1 is
\(e_i\) for a key with bit 0, and zeros + i - upto is \(Z + i - e_i\) for a key with bit 1,
whose flag is 0. We let every thread read scanned[n - 1], the number of keys with bit 0, and the cache
serves all but the first of these reads. The Rust write uses get_unchecked_mut, and its safety
comment is Theorem 22.2: the positions form a permutation of \([0, n)\).
22.9.3 The pass on a 4-bit digit
A pass on a 4-bit digit takes 3 listings. The following listing implements the first kernel of the pass, which counts the digits of each tile in private bins and writes the 16 counts into the table, digit by digit.
Listing 22.4 The digit counts of every tile, digit by digit.
mod kernels {
// ...
/// The 4-bit pass, step 1: the digit histogram of every tile, stored digit by digit:
/// counts[digit * tiles + tile] is the number of keys with that digit in that tile.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn digit_counts(keys: &[u32], shift: u32, mut counts: DisjointSlice<u32>) {
static mut LOCAL: SharedArray<u32, RADIX> = SharedArray::UNINIT;
let tid = thread::threadIdx_x() as usize;
let block = thread::blockIdx_x() as usize;
if tid < RADIX {
// SAFETY: threads 0 to 15 each zero their own bin, before the barrier.
unsafe { LOCAL[tid] = 0 };
}
thread::sync_threads();
// SAFETY: between the 2 barriers every access to LOCAL is atomic.
let local = unsafe { (*&raw mut LOCAL).as_mut_ptr() };
let mut step = 0;
#[unroll]
while step < 4 {
let index = block * TILE + step * 256 + tid;
if index < keys.len() {
let digit = digit_of(keys[index], shift);
// SAFETY: d < RADIX, and LOCAL holds RADIX bins.
unsafe { shared_bin(local, digit) }.fetch_add(1, AtomicOrdering::Relaxed);
}
step += 1;
}
thread::sync_threads();
if tid < RADIX {
let tiles = thread::gridDim_x() as usize;
// SAFETY: thread d of block b alone writes entry d * tiles + b, and the
// table holds RADIX * tiles entries.
unsafe { *counts.get_unchecked_mut(tid * tiles + block) = LOCAL[tid] };
}
}
// ...
}
// The 4-bit pass, step 1: the digit histogram of every tile, stored digit by digit:
// counts[digit * tiles + tile] is the number of keys with that digit in that tile.
__global__ void digitCounts(const unsigned* keys, int shift, unsigned* counts, int n)
{
__shared__ unsigned local[RADIX];
if (threadIdx.x < RADIX) {
local[threadIdx.x] = 0;
}
__syncthreads();
for (int step = 0; step < 4; ++step) {
int index = blockIdx.x * TILE + step * 256 + threadIdx.x;
if (index < n) {
atomicAdd(&local[digitOf(keys[index], shift)], 1u);
}
}
__syncthreads();
if (threadIdx.x < RADIX) {
counts[threadIdx.x * gridDim.x + blockIdx.x] = local[threadIdx.x];
}
}
The final write stores the count of digit \(d\) of block \(b\) at entry
tid * tiles + block, which is entry \(dm + b\) of the table of Section 22.7.2. The next listing
implements Scatter-Digits, which moves every key to the start of its digit in its tile plus its
rank.
Listing 22.5 The scatter of a pass on a 4-bit digit.
mod kernels {
// ...
/// The 4-bit pass, step 3: every key goes to the start of its digit in its tile, plus
/// the keys with the same digit before it in the tile. 4 steps of 256 keys, in order.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn scatter_digits(
keys: &[u32],
shift: u32,
counts: &[u32],
scanned: &[u32],
mut out: DisjointSlice<u32>,
) {
static mut START: SharedArray<u32, RADIX> = SharedArray::UNINIT;
// The count of digit d in warp w, at slot w * RADIX + d.
static mut WARP_COUNTS: SharedArray<u32, 128> = SharedArray::UNINIT;
let thread_idx = thread::threadIdx_x() as usize;
let block = thread::blockIdx_x() as usize;
let lane = warp::lane_id();
let warp = thread_idx / 32;
let below = (1u32 << lane) - 1;
if thread_idx < RADIX {
let entry = thread_idx * thread::gridDim_x() as usize + block;
// SAFETY: thread t alone writes START[t], before the first barrier.
unsafe { START[thread_idx] = scanned[entry] - counts[entry] };
}
let mut step = 0;
#[unroll]
while step < 4 {
if thread_idx < 8 * RADIX {
// SAFETY: thread t alone writes slot t, between 2 barriers.
unsafe { WARP_COUNTS[thread_idx] = 0 };
}
thread::sync_threads();
let index = block * TILE + step * 256 + thread_idx;
let key = if index < keys.len() { keys[index] } else { 0 };
let digit = if index < keys.len() { digit_of(key, shift) } else { RADIX };
let peers = warp::match_any_sync(u32::MAX, digit as u32);
let rank = (peers & below).count_ones();
if rank == 0 && digit < RADIX {
// SAFETY: 1 lane per digit and warp writes slot warp * 16 + d.
unsafe { WARP_COUNTS[warp * RADIX + digit] = peers.count_ones() };
}
thread::sync_threads();
if digit < RADIX {
let mut before = 0;
let mut other = 0;
while other < warp {
// SAFETY: between the 2 barriers the slots are only read.
before += unsafe { WARP_COUNTS[other * RADIX + digit] };
other += 1;
}
// SAFETY: START is only read between these barriers.
let at = (unsafe { START[digit] } + before + rank) as usize;
// SAFETY: the keys of each digit receive distinct consecutive positions
// after the keys of the smaller digits and of the earlier tiles: the
// positions of all keys form a permutation of 0 to n - 1.
unsafe { *out.get_unchecked_mut(at) = key };
}
thread::sync_threads();
if thread_idx < RADIX {
let mut other = 0;
#[unroll]
while other < 8 {
// SAFETY: thread t alone updates START[t]; the slots are only read.
unsafe { START[thread_idx] += WARP_COUNTS[other * RADIX + thread_idx] };
other += 1;
}
}
thread::sync_threads();
step += 1;
}
}
}
// The 4-bit pass, step 3: every key goes to the start of its digit in its tile, plus
// the keys with the same digit before it in the tile. 4 steps of 256 keys, in order.
__global__ void scatterDigits(const unsigned* keys, int shift, const unsigned* counts,
const unsigned* scanned, unsigned* out, int n)
{
__shared__ unsigned start[RADIX];
__shared__ unsigned warpCounts[8 * RADIX]; // [warp][digit]
int lane = threadIdx.x % 32;
int warp = threadIdx.x / 32;
unsigned below = (1u << lane) - 1;
if (threadIdx.x < RADIX) {
int entry = threadIdx.x * gridDim.x + blockIdx.x;
start[threadIdx.x] = scanned[entry] - counts[entry]; // the exclusive scan
}
for (int step = 0; step < 4; ++step) {
if (threadIdx.x < 8 * RADIX) {
warpCounts[threadIdx.x] = 0;
}
__syncthreads();
int index = blockIdx.x * TILE + step * 256 + threadIdx.x;
unsigned key = index < n ? keys[index] : 0;
unsigned digit = index < n ? digitOf(key, shift) : RADIX;
unsigned peers = __match_any_sync(FULL, digit);
unsigned rank = __popc(peers & below);
if (rank == 0 && digit < RADIX) {
warpCounts[warp * RADIX + digit] = __popc(peers);
}
__syncthreads();
if (digit < RADIX) {
unsigned before = 0;
for (int other = 0; other < warp; ++other) {
before += warpCounts[other * RADIX + digit];
}
out[start[digit] + before + rank] = key;
}
__syncthreads();
if (threadIdx.x < RADIX) {
for (int other = 0; other < 8; ++other) {
start[threadIdx.x] += warpCounts[other * RADIX + threadIdx.x];
}
}
__syncthreads();
}
}
The shared arrays start and warpCounts (START and WARP_COUNTS in Rust) are the arrays
\(\mathsf{start}\) and \(wc\) of the pseudocode, and the 4 calls to the barrier are lines 3, 7, 9 and
11. The rank is popc(peers & below), where below has 1 bits for the lanes below this one. A
lane past the end of the array gets the digit 16, matches only with other such lanes, and writes
nothing, but it still reaches every barrier. The Rust write uses get_unchecked_mut, and its
safety comment is Theorem 22.3.
The last listing runs the 8 passes on the host. Each pass launches the two kernels and the scan of the table between them.
Listing 22.6 8 passes of 4 bits on the host.
/// 1 pass on the 4-bit digit at `shift`, from `keys` into `buffers.spare`.
fn digit_pass(
module: &Module,
stream: &Arc<CudaStream>,
keys: &DeviceBuffer<u32>,
shift: u32,
buffers: &mut SortBuffers,
) -> Result<(), Error> {
let tiles = LaunchConfig1D::new(keys.len().div_ceil(TILE) as u32, 256, 0);
let count = module.prepare_digit_counts(tiles)?;
module.digit_counts(stream, &count, keys, shift, &mut buffers.counts)?;
let levels = &mut buffers.count_levels;
scan(module, stream, &buffers.counts, &mut buffers.positions, levels)?;
let scatter = module.prepare_scatter_digits(tiles)?;
let (counts, positions) = (&buffers.counts, &buffers.positions);
let out = &mut buffers.spare;
module.scatter_digits(stream, &scatter, keys, shift, counts, positions, out)?;
Ok(())
}
/// 8 passes of 4 bits, digit 0 first. The result ends in `keys`.
fn sort_digits(
module: &Module,
stream: &Arc<CudaStream>,
keys: &mut DeviceBuffer<u32>,
buffers: &mut SortBuffers,
) -> Result<(), Error> {
for shift in (0..32).step_by(4) {
digit_pass(module, stream, keys, shift, buffers)?;
std::mem::swap(keys, &mut buffers.spare);
}
Ok(())
}
// 8 passes of 4 bits: digit histograms per tile, 1 scan of the table, a stable scatter.
void sortDigits(unsigned*& keys, Buffers& buffers, int n)
{
int tiles = (n + TILE - 1) / TILE;
unsigned* counts = buffers.flags;
unsigned* scanned = buffers.scanned;
for (int shift = 0; shift < 32; shift += 4) {
digitCounts<<<tiles, 256>>>(keys, shift, counts, n);
scan(counts, scanned, RADIX * tiles, buffers.scratch);
scatterDigits<<<tiles, 256>>>(keys, shift, counts, scanned, buffers.spare, n);
std::swap(keys, buffers.spare);
}
}
The 3 launches of a pass run on 1 stream, so the scatter reads a complete scan. Each pass writes
the keys into a second buffer, and the host then exchanges the 2 buffers, with std::mem::swap of
the 2 DeviceBuffer values in Rust and with std::swap of the 2 pointers in C++, without moving
any data on the GPU. After 8 passes, which is an even number, the sorted keys are back in the first
buffer.
Exercises
22.17 Change digit_counts and scatter_digits for digits of 8 bits. Which shared arrays grow,
and how large is the table for 16,777,216 keys?
22.18 Why does hist_aggregated compare lane with leader instead of testing rank == 0 as
scatter_digits does? Are the 2 tests equivalent?
22.10 Measurements
22.10.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 histograms count the low 4 bits of 16,777,216 keys of 4 bytes, 64 MiB in all, with 1,024 blocks of 256 threads, both on random keys and on keys that are all 7. Each histogram time is the average of 20 runs after 0.4 s of warm-up. The sorts take 16,777,216 random keys of 32 bits, and each sort time is the best of 3 runs after 1 run of warm-up. Every histogram is compared bin by bin, and every sort key by key, with the result computed on the CPU. Between runs, times varied by up to 10%.
The C++ program printed the following output.
$ ./radix_sort_histogram
radix sort of 5 2 7 2 0 6 3 5
split bit 0 2 2 0 6 5 7 3 5
split bit 1 0 5 5 2 2 6 7 3
split bit 2 0 2 2 3 5 5 6 7
histogram 1 0 2 1 0 2 1 1
digit starts 0 1 1 3 4 4 6 7
4-bit pass 0 2 2 3 5 5 6 7
histograms of the low 4 bits of 16777216 keys, average of 20 runs
keys global ms GB/s shared ms GB/s warp-aggregated ms GB/s
random 3.23 20.8 1.02 66.1 1.91 35.1
all 7 15.15 4.4 1.01 66.2 1.31 51.2
radix sorts of 16777216 random 32-bit keys, best of 3 runs
32 passes of 1 bit 262.26 ms 64.0 Mkeys/s
8 passes of 4 bits 40.13 ms 418.1 Mkeys/s
1 pass of 4 bits: counts 1.15 ms, scan 0.04 ms, scatter 3.83 ms
PASSED
The first 4 lines repeat Figure 22.2, and the histogram line is the histogram of Definition 22.3. Because the keys have only 3 bits, 1 pass on the digit of 4 bits at shift 0 sorts them. The digit starts \((0, 1, 1, 3, 4, 4, 6, 7)\) are the exclusive scan of the histogram, and the pass is a counting sort of the whole keys. The Rust program printed the same small example and times within 5% of these: 3.24, 1.00 and 2.00 ms for the random keys, 15.24, 1.01 and 1.28 ms for the keys that are all 7, and 255.32 ms and 39.89 ms for the 2 sorts.
22.10.2 Contention, measured
Figure 22.10 draws the histogram times. With global bins, the keys that are all 7 took 15.15 ms, and the random keys took 3.23 ms, 4.7 times less. In Section 5.5.2, we measured a factor of 4 for bytes in 256 global bins. With all keys equal, every one of the 16,777,216 atomic additions went to 1 address, and the L2 cache performed them one after the other, at a rate of \(16{,}777{,}216 / 15.15\ \text{ms} = 1.11\) billion per second. Spreading them over 16 addresses raised the rate only to 5.19 billion per second.
With private bins, the 2 inputs took the same time, 1.02 and 1.01 ms, and both read the keys at 66 GB/s, 65% of the memory bandwidth. The 1,024 blocks merged 16,384 counts into global memory instead of 16,777,216, and the contention in shared memory, where every key of the second input also went to 1 bin, no longer set the time. In Section 8.8, we found the same for bytes: once the bins were private, the speed of the histogram was set by its loads.
Warp aggregation made the histogram slower, 1.91 ms against 1.02 ms on random keys, and 1.31 ms against 1.01 ms on equal keys. Every key paid for the match instruction, and the atomic operations that it saved were not the limit. On random keys, it saved few of them in any case. The 32 random digits of a warp, drawn from 16 values, take on average \(16 (1 - (15/16)^{32}) = 14.0\) distinct values, because each of the 16 digits is missing from the warp with probability \((15/16)^{32}\). A warp therefore still made about 14 atomic additions instead of 32. Aggregation pays when many lanes of a warp update the same location in global memory, and private bins had already removed that case.
22.10.3 Why the 4-bit sort is 6.5 times faster, not 13
The 32 passes of 1 bit took 262.26 ms. By Section 22.5, they move 1,280 bytes per key, 21.5 GB for 16,777,216 keys, so they used the memory at 81.9 GB/s, 80% of its bandwidth. The sort by single bits is therefore limited by its traffic. The 8 passes of 4 bits move 96 bytes per key, 13.3 times less, but they took 40.13 ms, only 6.5 times less (Figure 22.11), and so they used the memory at only 40.1 GB/s.
The last line of the output locates the difference. In 1 pass, counting the digits took 1.15 ms, reading 67.1 MB at 58.4 GB/s, and the scan of the table of 262,144 counts took 0.04 ms. The scatter took 3.83 ms, reading and writing 134.2 MB at only 35.0 GB/s, so the scatter is the slow part. In a step, the 32 keys of a warp go to about 14 different places, 1 per distinct digit, as computed above. A store instruction of the warp then becomes about 14 separate writes of a few bytes each, whereas the copy of 32 consecutive keys is 4 writes of 32 bytes, and the memory system handles each of those writes as a separate request. The scatter also waits at 16 barriers per tile. The splits of the 1-bit sort scatter too, but every warp writes to at most 2 places, and their writes are nearly as regular as a copy.
The library sort that we measured in Chapter 11, cub::DeviceRadixSort, sorted 16,777,216 keys in
8.96 ms on the same GPU, 4.5 times faster than our 4-bit sort. It uses digits of 8 bits, and
therefore 4 passes instead of 8 (Section 11.2.4). It ranks and reorders the keys of each tile in
shared memory, so that the writes of a warp go to few places, and it computes the digit starts with
a single-pass scan (Adinets and Merrill, 2022). Exercise 5 at the end of the chapter takes the
first of those steps.
22.11 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, measures the 3 histograms and the 2 sorts on 16,777,216 keys, checks every result against the CPU, and prints the times.
Listing 22.7 The complete programs. code/oxide/ch22_radix_sort_histogram/src/main.rs and code/cuda/ch22_radix_sort_histogram/radix_sort_histogram.cu
//! Chapter 22: histograms of 4-bit digits with atomics, a radix sort by 1-bit splits,
//! and a radix sort by 4-bit digits whose offsets come from a histogram and a scan.
//!
//! cargo oxide run
use std::sync::Arc;
use std::time::{Duration, Instant};
use cuda_core::{CudaContext, CudaStream, DeviceBuffer, LaunchConfig1D};
use cuda_device::atomic::{AtomicOrdering, BlockAtomicU32, DeviceAtomicU32};
use cuda_device::{DisjointSlice, SharedArray, cuda_module, device, kernel, launch_contract};
use cuda_device::{thread, warp};
const TILE: usize = 1024; // keys per block in the scan and the sort
const N: usize = 16 << 20; // keys in the measured runs
const RADIX: usize = 16; // digit values of a 4-bit pass
const GRID: u32 = 1024; // blocks of the histogram kernels
type Error = Box<dyn std::error::Error>;
type Levels = Vec<(DeviceBuffer<u32>, DeviceBuffer<u32>)>;
type Bins = DeviceBuffer<DeviceAtomicU32>;
type Module = kernels::LoadedModule;
#[cuda_module]
mod kernels {
use super::*;
#[device]
fn digit_of(key: u32, shift: u32) -> usize {
((key >> shift) as usize) & (RADIX - 1)
}
/// Bin `d` of a block's private bins in shared memory, viewed as an atomic.
///
/// # Safety
/// `local` must point to the block's bins and `d` must be below RADIX.
#[device]
unsafe fn shared_bin<'a>(local: *mut u32, d: usize) -> &'a BlockAtomicU32 {
unsafe { BlockAtomicU32::from_ptr(local.add(d)) }
}
/// 1. Every count is an atomic addition on 1 of 16 bins in global memory.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn hist_global(keys: &[u32], shift: u32, bins: &[DeviceAtomicU32]) {
let stride = (thread::gridDim_x() * 256) as usize;
let mut index = thread::index_1d().get();
while index < keys.len() {
bins[digit_of(keys[index], shift)].fetch_add(1, AtomicOrdering::Relaxed);
index += stride;
}
}
/// 2. Each block counts into private bins in shared memory and merges them once.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn hist_shared(keys: &[u32], shift: u32, bins: &[DeviceAtomicU32]) {
static mut LOCAL: SharedArray<u32, RADIX> = SharedArray::UNINIT;
let tid = thread::threadIdx_x() as usize;
if tid < RADIX {
// SAFETY: threads 0 to 15 each zero their own bin, before the barrier.
unsafe { LOCAL[tid] = 0 };
}
thread::sync_threads();
// SAFETY: between the 2 barriers every access to LOCAL is atomic.
let local = unsafe { (*&raw mut LOCAL).as_mut_ptr() };
let stride = (thread::gridDim_x() * 256) as usize;
let mut index = thread::index_1d().get();
while index < keys.len() {
let digit = digit_of(keys[index], shift);
// SAFETY: d < RADIX, and LOCAL holds RADIX bins.
unsafe { shared_bin(local, digit) }.fetch_add(1, AtomicOrdering::Relaxed);
index += stride;
}
thread::sync_threads();
if tid < RADIX {
// SAFETY: after the barrier no thread writes LOCAL again.
let count = unsafe { LOCAL[tid] };
bins[tid].fetch_add(count, AtomicOrdering::Relaxed);
}
}
/// 3. As 2, but the lanes of a warp with equal digits add their count with 1 atomic.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn hist_aggregated(keys: &[u32], shift: u32, bins: &[DeviceAtomicU32]) {
static mut LOCAL: SharedArray<u32, RADIX> = SharedArray::UNINIT;
let tid = thread::threadIdx_x() as usize;
if tid < RADIX {
// SAFETY: threads 0 to 15 each zero their own bin, before the barrier.
unsafe { LOCAL[tid] = 0 };
}
thread::sync_threads();
// SAFETY: between the 2 barriers every access to LOCAL is atomic.
let local = unsafe { (*&raw mut LOCAL).as_mut_ptr() };
let lane = warp::lane_id();
let stride = (thread::gridDim_x() * 256) as usize;
let mut base = thread::blockIdx_x() as usize * 256;
while base < keys.len() {
let index = base + tid;
let inside = index < keys.len();
let digit = if inside { digit_of(keys[index], shift) } else { RADIX };
let peers = warp::match_any_sync(u32::MAX, digit as u32);
let leader = peers.trailing_zeros();
if lane == leader && digit < RADIX {
// SAFETY: d < RADIX, and LOCAL holds RADIX bins.
let bin = unsafe { shared_bin(local, digit) };
bin.fetch_add(peers.count_ones(), AtomicOrdering::Relaxed);
}
base += stride;
}
thread::sync_threads();
if tid < RADIX {
// SAFETY: after the barrier no thread writes LOCAL again.
let count = unsafe { LOCAL[tid] };
bins[tid].fetch_add(count, AtomicOrdering::Relaxed);
}
}
/// The inclusive scan of 1 value per lane across a warp.
#[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 21: 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: thread t alone writes elements 4t to 4t + 3.
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;
}
}
}
/// The split on 1 bit: flags[i] = 1 if the bit of keys[i] is 0.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn zero_flags(keys: &[u32], bit: u32, mut flags: DisjointSlice<u32>) {
let idx = thread::index_1d();
let index = idx.get();
if let Some(flag) = flags.get_mut(idx) {
*flag = 1 - ((keys[index] >> bit) & 1);
}
}
/// Zero-bit keys go to their exclusive scan, one-bit keys after all zero-bit keys.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn split_scatter(
keys: &[u32],
flags: &[u32],
scanned: &[u32],
mut out: DisjointSlice<u32>,
) {
let index = thread::index_1d().get();
if index < keys.len() {
let zeros = scanned[keys.len() - 1] as usize;
let upto = scanned[index] as usize; // zero-bit keys among 0 to i
let at = if flags[index] == 1 { upto - 1 } else { zeros + index - upto };
// SAFETY: zero-bit keys receive 0 to zeros - 1 and one-bit keys zeros to
// n - 1, each position once: a permutation of 0 to n - 1.
unsafe { *out.get_unchecked_mut(at) = keys[index] };
}
}
/// The 4-bit pass, step 1: the digit histogram of every tile, stored digit by digit:
/// counts[digit * tiles + tile] is the number of keys with that digit in that tile.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn digit_counts(keys: &[u32], shift: u32, mut counts: DisjointSlice<u32>) {
static mut LOCAL: SharedArray<u32, RADIX> = SharedArray::UNINIT;
let tid = thread::threadIdx_x() as usize;
let block = thread::blockIdx_x() as usize;
if tid < RADIX {
// SAFETY: threads 0 to 15 each zero their own bin, before the barrier.
unsafe { LOCAL[tid] = 0 };
}
thread::sync_threads();
// SAFETY: between the 2 barriers every access to LOCAL is atomic.
let local = unsafe { (*&raw mut LOCAL).as_mut_ptr() };
let mut step = 0;
#[unroll]
while step < 4 {
let index = block * TILE + step * 256 + tid;
if index < keys.len() {
let digit = digit_of(keys[index], shift);
// SAFETY: d < RADIX, and LOCAL holds RADIX bins.
unsafe { shared_bin(local, digit) }.fetch_add(1, AtomicOrdering::Relaxed);
}
step += 1;
}
thread::sync_threads();
if tid < RADIX {
let tiles = thread::gridDim_x() as usize;
// SAFETY: thread d of block b alone writes entry d * tiles + b, and the
// table holds RADIX * tiles entries.
unsafe { *counts.get_unchecked_mut(tid * tiles + block) = LOCAL[tid] };
}
}
/// The 4-bit pass, step 3: every key goes to the start of its digit in its tile, plus
/// the keys with the same digit before it in the tile. 4 steps of 256 keys, in order.
#[kernel]
#[launch_contract(domain = 1, block = (256, 1, 1))]
pub fn scatter_digits(
keys: &[u32],
shift: u32,
counts: &[u32],
scanned: &[u32],
mut out: DisjointSlice<u32>,
) {
static mut START: SharedArray<u32, RADIX> = SharedArray::UNINIT;
// The count of digit d in warp w, at slot w * RADIX + d.
static mut WARP_COUNTS: SharedArray<u32, 128> = SharedArray::UNINIT;
let thread_idx = thread::threadIdx_x() as usize;
let block = thread::blockIdx_x() as usize;
let lane = warp::lane_id();
let warp = thread_idx / 32;
let below = (1u32 << lane) - 1;
if thread_idx < RADIX {
let entry = thread_idx * thread::gridDim_x() as usize + block;
// SAFETY: thread t alone writes START[t], before the first barrier.
unsafe { START[thread_idx] = scanned[entry] - counts[entry] };
}
let mut step = 0;
#[unroll]
while step < 4 {
if thread_idx < 8 * RADIX {
// SAFETY: thread t alone writes slot t, between 2 barriers.
unsafe { WARP_COUNTS[thread_idx] = 0 };
}
thread::sync_threads();
let index = block * TILE + step * 256 + thread_idx;
let key = if index < keys.len() { keys[index] } else { 0 };
let digit = if index < keys.len() { digit_of(key, shift) } else { RADIX };
let peers = warp::match_any_sync(u32::MAX, digit as u32);
let rank = (peers & below).count_ones();
if rank == 0 && digit < RADIX {
// SAFETY: 1 lane per digit and warp writes slot warp * 16 + d.
unsafe { WARP_COUNTS[warp * RADIX + digit] = peers.count_ones() };
}
thread::sync_threads();
if digit < RADIX {
let mut before = 0;
let mut other = 0;
while other < warp {
// SAFETY: between the 2 barriers the slots are only read.
before += unsafe { WARP_COUNTS[other * RADIX + digit] };
other += 1;
}
// SAFETY: START is only read between these barriers.
let at = (unsafe { START[digit] } + before + rank) as usize;
// SAFETY: the keys of each digit receive distinct consecutive positions
// after the keys of the smaller digits and of the earlier tiles: the
// positions of all keys form a permutation of 0 to n - 1.
unsafe { *out.get_unchecked_mut(at) = key };
}
thread::sync_threads();
if thread_idx < RADIX {
let mut other = 0;
#[unroll]
while other < 8 {
// SAFETY: thread t alone updates START[t]; the slots are only read.
unsafe { START[thread_idx] += WARP_COUNTS[other * RADIX + thread_idx] };
other += 1;
}
}
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 from a small linear congruential generator.
fn random(n: usize, 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
})
.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)
}
/// Inclusive scan: the tiles, then the tile totals (by the same function), then offsets.
fn scan(
module: &Module,
stream: &Arc<CudaStream>,
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 config = LaunchConfig1D::new(tiles, 256, 0);
let ((totals, scanned), rest) = levels.split_first_mut().ok_or("no level left")?;
module.scan_warps(stream, &module.prepare_scan_warps(config)?, x, y, totals)?;
if tiles > 1 {
scan(module, stream, totals, scanned, rest)?;
module.add_offsets(stream, &module.prepare_add_offsets(config)?, y, scanned)?;
}
Ok(())
}
/// The buffers that a radix sort of n keys needs besides the keys themselves.
struct SortBuffers {
spare: DeviceBuffer<u32>, // the other half of each pass
flags: DeviceBuffer<u32>, // 1 per key
scanned: DeviceBuffer<u32>, // 1 per key
levels: Levels, // the scan of the flags
counts: DeviceBuffer<u32>, // RADIX per tile
positions: DeviceBuffer<u32>, // the scan of the counts
count_levels: Levels,
}
impl SortBuffers {
fn new(stream: &Arc<CudaStream>, n: usize) -> Result<Self, Error> {
let table = RADIX * n.div_ceil(TILE);
Ok(SortBuffers {
spare: DeviceBuffer::<u32>::zeroed(stream, n)?,
flags: DeviceBuffer::<u32>::zeroed(stream, n)?,
scanned: DeviceBuffer::<u32>::zeroed(stream, n)?,
levels: scan_levels(stream, n)?,
counts: DeviceBuffer::<u32>::zeroed(stream, table)?,
positions: DeviceBuffer::<u32>::zeroed(stream, table)?,
count_levels: scan_levels(stream, table)?,
})
}
}
/// 1 stable split on `bit`, from `keys` into `buffers.spare`.
fn split(
module: &Module,
stream: &Arc<CudaStream>,
keys: &DeviceBuffer<u32>,
bit: u32,
buffers: &mut SortBuffers,
) -> Result<(), Error> {
let every = LaunchConfig1D::new(keys.len().div_ceil(256) as u32, 256, 0);
let flag = module.prepare_zero_flags(every)?;
module.zero_flags(stream, &flag, keys, bit, &mut buffers.flags)?;
scan(module, stream, &buffers.flags, &mut buffers.scanned, &mut buffers.levels)?;
let scatter = module.prepare_split_scatter(every)?;
let (flags, scanned, out) = (&buffers.flags, &buffers.scanned, &mut buffers.spare);
module.split_scatter(stream, &scatter, keys, flags, scanned, out)?;
Ok(())
}
/// 1 pass on the 4-bit digit at `shift`, from `keys` into `buffers.spare`.
fn digit_pass(
module: &Module,
stream: &Arc<CudaStream>,
keys: &DeviceBuffer<u32>,
shift: u32,
buffers: &mut SortBuffers,
) -> Result<(), Error> {
let tiles = LaunchConfig1D::new(keys.len().div_ceil(TILE) as u32, 256, 0);
let count = module.prepare_digit_counts(tiles)?;
module.digit_counts(stream, &count, keys, shift, &mut buffers.counts)?;
let levels = &mut buffers.count_levels;
scan(module, stream, &buffers.counts, &mut buffers.positions, levels)?;
let scatter = module.prepare_scatter_digits(tiles)?;
let (counts, positions) = (&buffers.counts, &buffers.positions);
let out = &mut buffers.spare;
module.scatter_digits(stream, &scatter, keys, shift, counts, positions, out)?;
Ok(())
}
/// 32 stable splits of 1 bit, bit 0 first. The result ends in `keys`.
fn sort_bits(
module: &Module,
stream: &Arc<CudaStream>,
keys: &mut DeviceBuffer<u32>,
buffers: &mut SortBuffers,
) -> Result<(), Error> {
for bit in 0..32 {
split(module, stream, keys, bit, buffers)?;
std::mem::swap(keys, &mut buffers.spare);
}
Ok(())
}
/// 8 passes of 4 bits, digit 0 first. The result ends in `keys`.
fn sort_digits(
module: &Module,
stream: &Arc<CudaStream>,
keys: &mut DeviceBuffer<u32>,
buffers: &mut SortBuffers,
) -> Result<(), Error> {
for shift in (0..32).step_by(4) {
digit_pass(module, stream, keys, shift, buffers)?;
std::mem::swap(keys, &mut buffers.spare);
}
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: 8 keys of 3 bits, 3 splits, then 1 pass on a 4-bit digit.
fn small_example(module: &Module, stream: &Arc<CudaStream>) -> Result<bool, Error> {
let host = [5u32, 2, 7, 2, 0, 6, 3, 5];
let sorted = [0u32, 2, 2, 3, 5, 5, 6, 7];
let mut buffers = SortBuffers::new(stream, 8)?;
let mut keys = DeviceBuffer::from_host(stream, &host)?;
println!("radix sort of 5 2 7 2 0 6 3 5");
for bit in 0..3 {
split(module, stream, &keys, bit, &mut buffers)?;
std::mem::swap(&mut keys, &mut buffers.spare);
print(&format!("split bit {bit}"), &keys.to_host_vec(stream)?);
}
let by_splits = keys.to_host_vec(stream)?;
let keys = DeviceBuffer::from_host(stream, &host)?;
let bins = DeviceBuffer::<u32>::zeroed(stream, RADIX)?.cast_elem::<DeviceAtomicU32>();
let one = module.prepare_hist_shared(LaunchConfig1D::new(1, 256, 0))?;
module.hist_shared(stream, &one, &keys, 0, &bins)?;
let hist = bins.cast_elem::<u32>().to_host_vec(stream)?[..8].to_vec();
print("histogram", &hist);
digit_pass(module, stream, &keys, 0, &mut buffers)?;
let inclusive = buffers.positions.to_host_vec(stream)?;
let starts: Vec<u32> = (0..8).map(|d| inclusive[d] - hist[d]).collect();
print("digit starts", &starts);
let by_digits = buffers.spare.to_host_vec(stream)?;
print("4-bit pass", &by_digits);
Ok(by_splits == sorted && by_digits == sorted)
}
/// The 3 histograms of the low 4 bits of N keys, on random keys and on keys all equal.
fn histograms(module: &Module, stream: &Arc<CudaStream>) -> Result<bool, Error> {
let grid = LaunchConfig1D::new(GRID, 256, 0);
let global = module.prepare_hist_global(grid)?;
let shared = module.prepare_hist_shared(grid)?;
let aggregated = module.prepare_hist_aggregated(grid)?;
let gb = 4.0 * N as f64 / 1e9;
let mut ok = true;
println!("histograms of the low 4 bits of {N} keys, average of 20 runs");
print!(" keys global ms GB/s shared ms GB/s");
println!(" warp-aggregated ms GB/s");
for (name, host) in [("random", random(N, 7)), ("all 7", vec![7u32; N])] {
let keys = DeviceBuffer::from_host(stream, &host)?;
let mut expected = vec![0u32; RADIX];
for k in &host {
expected[(k & 15) as usize] += 1;
}
let run = |kernel: usize, bins: &Bins| -> Result<(), Error> {
match kernel {
0 => module.hist_global(stream, &global, &keys, 0, bins)?,
1 => module.hist_shared(stream, &shared, &keys, 0, bins)?,
_ => module.hist_aggregated(stream, &aggregated, &keys, 0, bins)?,
}
Ok(())
};
let mut ms = [0.0; 3];
for (kernel, time) in ms.iter_mut().enumerate() {
let scratch = DeviceBuffer::<u32>::zeroed(stream, RADIX)?.cast_elem();
*time = time_ms(stream, || run(kernel, &scratch))?;
let bins = DeviceBuffer::<u32>::zeroed(stream, RADIX)?.cast_elem();
run(kernel, &bins)?;
ok &= bins.cast_elem::<u32>().to_host_vec(stream)? == expected;
}
let rate = |t: f64| gb / (t / 1e3);
let (a, b, c) = (ms[0], ms[1], ms[2]);
print!(" {name:10} {a:10.2} {:6.1} {b:11.2} {:6.1}", rate(a), rate(b));
println!(" {c:20.2} {:6.1}", rate(c));
}
Ok(ok)
}
/// Both radix sorts of N random keys, best of 3 runs each, checked against sort_unstable.
fn sorts(module: &Module, stream: &Arc<CudaStream>) -> Result<bool, Error> {
let host = random(N, 11);
let mut expected = host.clone();
expected.sort_unstable();
let mut buffers = SortBuffers::new(stream, N)?;
let mut ok = true;
let mut best = [f64::MAX; 2];
for (method, fastest) in best.iter_mut().enumerate() {
for run in 0..4 {
let mut keys = DeviceBuffer::from_host(stream, &host)?;
stream.synchronize()?;
let start = Instant::now();
if method == 0 {
sort_bits(module, stream, &mut keys, &mut buffers)?;
} else {
sort_digits(module, stream, &mut keys, &mut buffers)?;
}
stream.synchronize()?;
let ms = start.elapsed().as_secs_f64() * 1e3;
if run > 0 {
*fastest = fastest.min(ms); // run 0 warms up
}
ok &= keys.to_host_vec(stream)? == expected;
}
}
let rate = |ms: f64| N as f64 / 1e6 / (ms / 1e3);
println!("radix sorts of {N} random 32-bit keys, best of 3 runs");
println!(" 32 passes of 1 bit {:8.2} ms {:7.1} Mkeys/s", best[0], rate(best[0]));
println!(" 8 passes of 4 bits {:8.2} ms {:7.1} Mkeys/s", best[1], rate(best[1]));
// The 3 parts of 1 pass of 4 bits on the random keys, averaged like the histograms.
let keys = DeviceBuffer::from_host(stream, &host)?;
let tiles = LaunchConfig1D::new(N.div_ceil(TILE) as u32, 256, 0);
let count = module.prepare_digit_counts(tiles)?;
let scatter = module.prepare_scatter_digits(tiles)?;
let count_ms = time_ms(stream, || {
Ok(module.digit_counts(stream, &count, &keys, 0, &mut buffers.counts)?)
})?;
let scan_ms = time_ms(stream, || {
let levels = &mut buffers.count_levels;
scan(module, stream, &buffers.counts, &mut buffers.positions, levels)
})?;
let (counts, positions) = (&buffers.counts, &buffers.positions);
let out = &mut buffers.spare;
let scatter_ms = time_ms(stream, || {
Ok(module.scatter_digits(stream, &scatter, &keys, 0, counts, positions, out)?)
})?;
print!(" 1 pass of 4 bits: counts {count_ms:.2} ms, scan {scan_ms:.2} ms,");
println!(" scatter {scatter_ms:.2} ms");
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 &= histograms(&module, &stream)?;
passed &= sorts(&module, &stream)?;
println!("{}", if passed { "PASSED" } else { "FAILED" });
Ok(())
}
// Chapter 22: histograms of 4-bit digits with atomics, a radix sort by 1-bit splits,
// and a radix sort by 4-bit digits whose offsets come from a histogram and a scan.
// Build: nvcc -O3 -arch=native radix_sort_histogram.cu -o radix_sort_histogram
#include <algorithm>
#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cuda_runtime.h>
const int TILE = 1024; // keys per block in the scan and the sort
const int N = 16 << 20; // keys in the measured runs
const int RADIX = 16; // digit values of a 4-bit pass
const int GRID = 1024; // blocks of the histogram kernels
const unsigned FULL = 0xffffffff;
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 r = 0; r < 20; ++r) {
launch();
}
check(cudaGetLastError());
check(cudaDeviceSynchronize());
return (nowMs() - t0) / 20;
}
__device__ unsigned digitOf(unsigned key, int shift)
{
return (key >> shift) & (RADIX - 1);
}
// 1. Every count is an atomic addition on 1 of 16 bins in global memory.
__global__ void histGlobal(const unsigned* keys, int shift, unsigned* bins, int n)
{
int stride = gridDim.x * blockDim.x;
for (int index = blockIdx.x * blockDim.x + threadIdx.x; index < n; index += stride) {
atomicAdd(&bins[digitOf(keys[index], shift)], 1u);
}
}
// 2. Each block counts into private bins in shared memory and merges them once.
__global__ void histShared(const unsigned* keys, int shift, unsigned* bins, int n)
{
__shared__ unsigned local[RADIX];
if (threadIdx.x < RADIX) {
local[threadIdx.x] = 0;
}
__syncthreads();
int stride = gridDim.x * blockDim.x;
for (int index = blockIdx.x * blockDim.x + threadIdx.x; index < n; index += stride) {
atomicAdd(&local[digitOf(keys[index], shift)], 1u);
}
__syncthreads();
if (threadIdx.x < RADIX) {
atomicAdd(&bins[threadIdx.x], local[threadIdx.x]);
}
}
// 3. As 2, but the lanes of a warp with equal digits add their count with 1 atomic.
__global__ void histAggregated(const unsigned* keys, int shift, unsigned* bins, int n)
{
__shared__ unsigned local[RADIX];
if (threadIdx.x < RADIX) {
local[threadIdx.x] = 0;
}
__syncthreads();
int lane = threadIdx.x % 32;
int stride = gridDim.x * blockDim.x;
for (int base = blockIdx.x * blockDim.x; base < n; base += stride) {
int index = base + threadIdx.x;
unsigned digit = index < n ? digitOf(keys[index], shift) : RADIX;
unsigned peers = __match_any_sync(FULL, digit);
int leader = __ffs(peers) - 1;
if (lane == leader && digit < RADIX) {
atomicAdd(&local[digit], __popc(peers));
}
}
__syncthreads();
if (threadIdx.x < RADIX) {
atomicAdd(&bins[threadIdx.x], local[threadIdx.x]);
}
}
// The scan of Chapter 21: 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(FULL, 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];
}
}
__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;
}
}
}
// Inclusive scan of n elements: the tiles, then the tile totals (in place), then offsets.
void scan(const unsigned* x, unsigned* y, int n, unsigned* scratch)
{
int tiles = (n + TILE - 1) / TILE;
scanWarps<<<tiles, 256>>>(x, y, scratch, n);
if (tiles > 1) {
scan(scratch, scratch, tiles, scratch + tiles);
addOffsets<<<tiles, 256>>>(y, scratch, n);
}
}
// The split on 1 bit: flags[index] = 1 if the bit of keys[index] is 0.
__global__ void zeroFlags(const unsigned* keys, int bit, unsigned* flags, int n)
{
int index = blockIdx.x * blockDim.x + threadIdx.x;
if (index < n) {
flags[index] = 1 - ((keys[index] >> bit) & 1);
}
}
// Zero-bit keys go to their exclusive scan, one-bit keys after all zero-bit keys.
__global__ void splitScatter(const unsigned* keys, const unsigned* flags,
const unsigned* scanned, unsigned* out, int n)
{
int index = blockIdx.x * blockDim.x + threadIdx.x;
if (index < n) {
unsigned zeros = scanned[n - 1];
unsigned upto = scanned[index]; // zero-bit keys among 0 to index
unsigned at = flags[index] == 1 ? upto - 1 : zeros + index - upto;
out[at] = keys[index];
}
}
// The 4-bit pass, step 1: the digit histogram of every tile, stored digit by digit:
// counts[digit * tiles + tile] is the number of keys with that digit in that tile.
__global__ void digitCounts(const unsigned* keys, int shift, unsigned* counts, int n)
{
__shared__ unsigned local[RADIX];
if (threadIdx.x < RADIX) {
local[threadIdx.x] = 0;
}
__syncthreads();
for (int step = 0; step < 4; ++step) {
int index = blockIdx.x * TILE + step * 256 + threadIdx.x;
if (index < n) {
atomicAdd(&local[digitOf(keys[index], shift)], 1u);
}
}
__syncthreads();
if (threadIdx.x < RADIX) {
counts[threadIdx.x * gridDim.x + blockIdx.x] = local[threadIdx.x];
}
}
// The 4-bit pass, step 3: every key goes to the start of its digit in its tile, plus
// the keys with the same digit before it in the tile. 4 steps of 256 keys, in order.
__global__ void scatterDigits(const unsigned* keys, int shift, const unsigned* counts,
const unsigned* scanned, unsigned* out, int n)
{
__shared__ unsigned start[RADIX];
__shared__ unsigned warpCounts[8 * RADIX]; // [warp][digit]
int lane = threadIdx.x % 32;
int warp = threadIdx.x / 32;
unsigned below = (1u << lane) - 1;
if (threadIdx.x < RADIX) {
int entry = threadIdx.x * gridDim.x + blockIdx.x;
start[threadIdx.x] = scanned[entry] - counts[entry]; // the exclusive scan
}
for (int step = 0; step < 4; ++step) {
if (threadIdx.x < 8 * RADIX) {
warpCounts[threadIdx.x] = 0;
}
__syncthreads();
int index = blockIdx.x * TILE + step * 256 + threadIdx.x;
unsigned key = index < n ? keys[index] : 0;
unsigned digit = index < n ? digitOf(key, shift) : RADIX;
unsigned peers = __match_any_sync(FULL, digit);
unsigned rank = __popc(peers & below);
if (rank == 0 && digit < RADIX) {
warpCounts[warp * RADIX + digit] = __popc(peers);
}
__syncthreads();
if (digit < RADIX) {
unsigned before = 0;
for (int other = 0; other < warp; ++other) {
before += warpCounts[other * RADIX + digit];
}
out[start[digit] + before + rank] = key;
}
__syncthreads();
if (threadIdx.x < RADIX) {
for (int other = 0; other < 8; ++other) {
start[threadIdx.x] += warpCounts[other * RADIX + threadIdx.x];
}
}
__syncthreads();
}
}
struct Buffers {
unsigned* spare; // the other half of each pass
unsigned* flags; // 1-bit sort: flags, or 4-bit: counts
unsigned* scanned;
unsigned* scratch; // the tile totals of the scan
};
// 32 stable splits of 1 bit, bit 0 first. After an even number of passes the sorted
// keys are back in `keys`.
void sortBits(unsigned*& keys, Buffers& buffers, int n)
{
int blocks = (n + 255) / 256;
unsigned* flags = buffers.flags;
unsigned* scanned = buffers.scanned;
for (int bit = 0; bit < 32; ++bit) {
zeroFlags<<<blocks, 256>>>(keys, bit, flags, n);
scan(flags, scanned, n, buffers.scratch);
splitScatter<<<blocks, 256>>>(keys, flags, scanned, buffers.spare, n);
std::swap(keys, buffers.spare);
}
}
// 8 passes of 4 bits: digit histograms per tile, 1 scan of the table, a stable scatter.
void sortDigits(unsigned*& keys, Buffers& buffers, int n)
{
int tiles = (n + TILE - 1) / TILE;
unsigned* counts = buffers.flags;
unsigned* scanned = buffers.scanned;
for (int shift = 0; shift < 32; shift += 4) {
digitCounts<<<tiles, 256>>>(keys, shift, counts, n);
scan(counts, scanned, RADIX * tiles, buffers.scratch);
scatterDigits<<<tiles, 256>>>(keys, shift, counts, scanned, buffers.spare, n);
std::swap(keys, buffers.spare);
}
}
std::vector<unsigned> toHost(const unsigned* device, int n)
{
std::vector<unsigned> host(n);
check(cudaMemcpy(host.data(), device, n * sizeof(unsigned), cudaMemcpyDeviceToHost));
return host;
}
void print(const char* name, const std::vector<unsigned>& v)
{
std::printf(" %-13s", name);
for (unsigned x : v) {
std::printf(" %u", x);
}
std::printf("\n");
}
// The worked example: 8 keys of 3 bits, 3 splits, then 1 pass on a 4-bit digit.
bool smallExample(Buffers& buffers)
{
std::vector<unsigned> host = {5, 2, 7, 2, 0, 6, 3, 5};
unsigned *keys, *other, *bins;
check(cudaMalloc(&keys, 8 * sizeof(unsigned)));
check(cudaMalloc(&other, 8 * sizeof(unsigned)));
check(cudaMalloc(&bins, RADIX * sizeof(unsigned)));
check(cudaMemcpy(keys, host.data(), 8 * sizeof(unsigned), cudaMemcpyHostToDevice));
std::printf("radix sort of 5 2 7 2 0 6 3 5\n");
unsigned* from = keys;
unsigned* to = other;
for (int bit = 0; bit < 3; ++bit) {
zeroFlags<<<1, 256>>>(from, bit, buffers.flags, 8);
scan(buffers.flags, buffers.scanned, 8, buffers.scratch);
splitScatter<<<1, 256>>>(from, buffers.flags, buffers.scanned, to, 8);
std::swap(from, to);
char name[16];
std::snprintf(name, sizeof(name), "split bit %d", bit);
print(name, toHost(from, 8));
}
std::vector<unsigned> bySplits = toHost(from, 8);
check(cudaMemcpy(keys, host.data(), 8 * sizeof(unsigned), cudaMemcpyHostToDevice));
check(cudaMemset(bins, 0, RADIX * sizeof(unsigned)));
histShared<<<1, 256>>>(keys, 0, bins, 8);
std::vector<unsigned> hist = toHost(bins, 8);
print("histogram", hist);
digitCounts<<<1, 256>>>(keys, 0, buffers.flags, 8);
scan(buffers.flags, buffers.scanned, RADIX, buffers.scratch);
scatterDigits<<<1, 256>>>(keys, 0, buffers.flags, buffers.scanned, other, 8);
std::vector<unsigned> inclusive = toHost(buffers.scanned, 8);
std::vector<unsigned> starts(8);
for (int digit = 0; digit < 8; ++digit) {
starts[digit] = inclusive[digit] - hist[digit];
}
print("digit starts", starts);
std::vector<unsigned> byDigits = toHost(other, 8);
print("4-bit pass", byDigits);
check(cudaFree(keys));
check(cudaFree(other));
check(cudaFree(bins));
std::vector<unsigned> sorted = {0, 2, 2, 3, 5, 5, 6, 7};
return bySplits == sorted && byDigits == sorted;
}
// The 3 histograms of the low 4 bits of N keys, on random keys and on keys all equal.
bool histograms(unsigned* keys)
{
unsigned* bins;
check(cudaMalloc(&bins, RADIX * sizeof(unsigned)));
double gb = 4.0 * N / 1e9;
bool ok = true;
std::printf("histograms of the low 4 bits of %d keys, average of 20 runs\n", N);
std::printf(" keys global ms GB/s shared ms GB/s");
std::printf(" warp-aggregated ms GB/s\n");
for (int input = 0; input < 2; ++input) {
std::vector<unsigned> host(N);
unsigned state = 7;
for (int i = 0; i < N; ++i) {
state = state * 1664525u + 1013904223u;
host[i] = input == 0 ? state : 7;
}
check(cudaMemcpy(keys, host.data(), N * sizeof(unsigned), cudaMemcpyHostToDevice));
std::vector<unsigned> expected(RADIX, 0);
for (unsigned k : host) {
expected[k & 15] += 1;
}
double ms[3];
for (int kernel = 0; kernel < 3; ++kernel) {
auto run = [&] {
if (kernel == 0) {
histGlobal<<<GRID, 256>>>(keys, 0, bins, N);
} else if (kernel == 1) {
histShared<<<GRID, 256>>>(keys, 0, bins, N);
} else {
histAggregated<<<GRID, 256>>>(keys, 0, bins, N);
}
};
ms[kernel] = timeMs(run);
check(cudaMemset(bins, 0, RADIX * sizeof(unsigned)));
run();
ok = ok && toHost(bins, RADIX) == expected;
}
std::printf(" %-10s %10.2f %6.1f %11.2f %6.1f %20.2f %6.1f\n",
input == 0 ? "random" : "all 7", ms[0], gb / (ms[0] / 1e3),
ms[1], gb / (ms[1] / 1e3), ms[2], gb / (ms[2] / 1e3));
}
check(cudaFree(bins));
return ok;
}
// Both radix sorts of N random keys, best of 3 runs each, checked against std::sort.
bool sorts(unsigned* keys, Buffers& buffers)
{
std::vector<unsigned> host(N);
unsigned state = 11;
for (int i = 0; i < N; ++i) {
state = state * 1664525u + 1013904223u;
host[i] = state;
}
std::vector<unsigned> expected = host;
std::sort(expected.begin(), expected.end());
bool ok = true;
double best[2] = {1e30, 1e30};
for (int method = 0; method < 2; ++method) {
for (int run = 0; run < 4; ++run) {
size_t bytes = N * sizeof(unsigned);
check(cudaMemcpy(keys, host.data(), bytes, cudaMemcpyHostToDevice));
double start = nowMs();
if (method == 0) {
sortBits(keys, buffers, N);
} else {
sortDigits(keys, buffers, N);
}
check(cudaDeviceSynchronize());
double ms = nowMs() - start;
if (run > 0) { // run 0 warms up
best[method] = std::min(best[method], ms);
}
ok = ok && toHost(keys, N) == expected;
}
}
std::printf("radix sorts of %d random 32-bit keys, best of 3 runs\n", N);
std::printf(" 32 passes of 1 bit %8.2f ms %7.1f Mkeys/s\n", best[0],
N / 1e6 / (best[0] / 1e3));
std::printf(" 8 passes of 4 bits %8.2f ms %7.1f Mkeys/s\n", best[1],
N / 1e6 / (best[1] / 1e3));
// The 3 parts of 1 pass of 4 bits on the random keys, averaged like the histograms.
check(cudaMemcpy(keys, host.data(), N * sizeof(unsigned), cudaMemcpyHostToDevice));
int tiles = (N + TILE - 1) / TILE;
unsigned* counts = buffers.flags;
unsigned* starts = buffers.scanned;
unsigned* spare = buffers.spare;
unsigned* scratch = buffers.scratch;
double countMs = timeMs([&] { digitCounts<<<tiles, 256>>>(keys, 0, counts, N); });
double scanMs = timeMs([&] { scan(counts, starts, RADIX * tiles, scratch); });
auto move = [&] { scatterDigits<<<tiles, 256>>>(keys, 0, counts, starts, spare, N); };
double scatterMs = timeMs(move);
std::printf(" 1 pass of 4 bits: counts %.2f ms, scan %.2f ms, scatter %.2f ms\n",
countMs, scanMs, scatterMs);
return ok;
}
int main()
{
unsigned* keys;
Buffers buffers;
check(cudaMalloc(&keys, N * sizeof(unsigned)));
check(cudaMalloc(&buffers.spare, N * sizeof(unsigned)));
check(cudaMalloc(&buffers.flags, N * sizeof(unsigned)));
check(cudaMalloc(&buffers.scanned, N * sizeof(unsigned)));
check(cudaMalloc(&buffers.scratch, N / 512 * sizeof(unsigned)));
bool ok = smallExample(buffers);
ok = histograms(keys) && ok;
ok = sorts(keys, buffers) && ok;
check(cudaFree(keys));
check(cudaFree(buffers.spare));
check(cudaFree(buffers.flags));
check(cudaFree(buffers.scanned));
check(cudaFree(buffers.scratch));
std::printf("%s\n", ok ? "PASSED" : "FAILED");
return ok ? 0 : 1;
}
Common mistakes
- An unstable pass. Positions handed out by an atomic counter group the keys by digit but lose their order, and the sort fails on large inputs while it may pass on small ones (Section 22.8). Place keys by start plus rank.
- The most significant digit first. A least-significant-digit sort by stable passes must start at bit 0. Starting at the top requires sorting each group separately.
- Counting into global bins. With few bins, every global atomic operation queues behind others for the same address. Count into private bins in shared memory and merge once per block.
- Merging before every thread has counted. Without the barrier before the merge, a thread can add its private bin to the global bin while other threads still count into it.
- A match or a ballot inside a branch. All lanes of the warp must execute it. Give the lanes past the end of the array a value that no key has, and call it unconditionally.
- The table of counts laid out tile by tile. Only the digit-major layout makes 1 scan give the start of every digit in every tile.
Summary
- A radix sort orders integer keys by their digits, least significant first. Theorem 22.1 shows that it is correct when every pass is stable.
- A split on 1 bit is 2 stream compactions that share 1 exclusive scan: keys with bit 0 go to \(e_i\), and keys with bit 1 go to \(Z + i - e_i\).
- A histogram counts keys by digit. Atomic additions make one thread per key correct, but contention makes them slow when many threads update 1 bin, and private bins in shared memory remove most of it.
- A pass on a digit of \(r\) bits places every key at the exclusive scan of the digit histogram plus its rank. Laying out the counts of the tiles digit by digit lets 1 scan serve every tile.
- Passes of 4 bits move 96 bytes per key for a 32-bit sort, against 1,280 for passes of 1 bit, and the measured sort ran 6.5 times as fast.
In Chapter 23, we turn to softmax and layer normalization, which combine reductions with arithmetic on every element.
Exercises
- Sort \((13, 2, 9, 2, 15, 0, 7, 13)\), keys of 4 bits, by 2 passes of 2 bits. Give the histogram, the starts and the ranks of each pass.
- Extend the radix sort to sort pairs (key, index), so that it returns the permutation that sorts the keys. Which kernels change?
- Signed integers in two’s complement do not sort correctly as unsigned keys. Which single bit must be flipped before the sort, and after it?
- Measure the histogram of 8-bit digits (256 bins) with the three kernels of Section 22.6, on random keys and on keys that are all equal, and compare with the 16-bin results.
- Replace the 3 passes of Section 22.7 (count, scan, scatter) by a version that keeps each tile’s keys sorted by digit in shared memory before writing them, so that the writes of a warp go to fewer places. Measure the effect.
- Estimate, from the byte count of Section 22.7.4, the time of a sort of 16,777,216 keys by 4 passes of 8 bits at the measured rate of the 4-bit sort.
Sources and further reading
- D. E. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, 2nd ed., Addison-Wesley, 1998, Section 5.2.5: radix sorting.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, Sections 8.2 and 8.3: counting sort and radix sort.
- G. E. Blelloch, “Prefix Sums and Their Applications”, Technical Report CMU-CS-90-190, Carnegie Mellon University, 1990: the split and radix sort from scans.
- N. Satish, M. Harris and M. Garland, “Designing Efficient Sorting Algorithms for Manycore GPUs”, IEEE IPDPS, 2009.
- D. Merrill and A. Grimshaw, “High Performance and Scalable Radix Sorting”, Parallel Processing Letters 21(2), 2011.
- A. Adinets and D. Merrill, “Onesweep: A Faster Least Significant Digit Radix Sort for GPUs”, arXiv:2206.01784, 2022.
- A. Pathak, “An Introduction to Tiled Parallel Programming, Simplified”, 2026.
- NVIDIA, CUDA C++ Programming Guide, “Atomic Functions” and “Warp Match Functions”.