Algorithms

Thrust and CUB: GPU Algorithm Libraries

Thrust and CUB: GPU Algorithm Libraries

Writing optimized CUDA kernels from scratch for every standard algorithm is unnecessary — NVIDIA provides two libraries that cover most data-parallel primitives at near-peak performance.

Thrust: High-Level STL-Like Interface

Thrust mirrors the C++ STL (<algorithm>, <numeric>) for GPU execution. It works with both device vectors and raw pointers.

cpp
#include <thrust/device_vector.h>
#include <thrust/transform.h>
#include <thrust/reduce.h>
#include <thrust/sort.h>

thrust::device_vector<float> d_vec(1 << 20, 1.0f);

// Transform: square every element
thrust::transform(d_vec.begin(), d_vec.end(), d_vec.begin(),
                  [] __device__ (float x) { return x * x; });

// Reduce: sum all elements
float total = thrust::reduce(d_vec.begin(), d_vec.end(), 0.0f, thrust::plus<float>());

// Sort in ascending order
thrust::sort(d_vec.begin(), d_vec.end());

// Exclusive scan: prefix sum
thrust::device_vector<float> d_scan(d_vec.size());
thrust::exclusive_scan(d_vec.begin(), d_vec.end(), d_scan.begin());

Useful Thrust Algorithms

| Algorithm | Function | |---|---| | thrust::reduce | Reduction (sum, max, min, custom) | | thrust::inclusive_scan / exclusive_scan | Prefix scan | | thrust::sort / sort_by_key | Radix sort (keys only or key-value pairs) | | thrust::copy_if | Stream compaction (filter elements) | | thrust::transform_reduce | Fused map + reduce | | thrust::unique | Remove consecutive duplicates | | thrust::scatter / gather | Indexed copy | | thrust::fill / sequence | Initialize vectors |

CUB: Block-Level and Device-Level Primitives

CUB (CUDA UnBound) is lower-level than Thrust and designed for use inside kernels. It provides optimized collective operations for thread blocks and warps.

Device-Level (Host API — entire array)

cpp
#include <cub/cub.cuh>

float *d_in, *d_out;
int N = 1 << 24;

// Determine temporary storage size
void   *d_temp = nullptr;
size_t  temp_bytes = 0;
cub::DeviceReduce::Sum(d_temp, temp_bytes, d_in, d_out, N);  // query pass

cudaMalloc(&d_temp, temp_bytes);

// Actual reduction
cub::DeviceReduce::Sum(d_temp, temp_bytes, d_in, d_out, N);
cudaDeviceSynchronize();

Block-Level (Inside Kernels)

cpp
__global__ void myKernel(float *data, float *block_sums, int n) {
    using BlockReduce = cub::BlockReduce<float, 256>;
    __shared__ typename BlockReduce::TempStorage temp;

    int i = blockIdx.x * blockDim.x + threadIdx.x;
    float val = (i < n) ? data[i] : 0.f;

    // CUB handles the shared-memory tree reduction automatically
    float block_sum = BlockReduce(temp).Sum(val);

    if (threadIdx.x == 0) block_sums[blockIdx.x] = block_sum;
}

Warp-Level (Inside Kernels)

cpp
using WarpScan = cub::WarpScan<float>;
__shared__ WarpScan::TempStorage temp[WARPS];
float prefix_sum;
WarpScan(temp[warpId]).InclusiveSum(val, prefix_sum);

Thrust vs. CUB: When to Use Each

| Criterion | Thrust | CUB | |---|---|---| | Ease of use | High (STL-like) | Medium (more boilerplate) | | Flexibility | Limited to provided algorithms | Mix with custom kernel logic | | Use from host | Yes | Device-level APIs yes; block/warp level from inside kernels | | Custom operators | Lambda functions | Custom functors | | Performance | Near-peak | Peak (tuned per architecture) |

Rule of thumb: Use Thrust for standalone data-parallel steps. Use CUB when you need to fuse a standard primitive with custom logic inside a kernel.

// CODE EXAMPLE

example.cu
// Thrust: sort, scan, and stream compaction in a few lines
#include <thrust/device_vector.h>
#include <thrust/sort.h>
#include <thrust/scan.h>
#include <thrust/copy.h>
#include <cstdio>

int main() {
    const int N = 16;
    thrust::device_vector<int> d(N);

    // Fill: 15, 14, 13, ..., 0
    thrust::sequence(d.begin(), d.end(), N-1, -1);

    // Sort ascending: 0, 1, 2, ..., 15
    thrust::sort(d.begin(), d.end());

    // Inclusive scan: 0, 1, 3, 6, 10, 15, 21, ...
    thrust::device_vector<int> scan(N);
    thrust::inclusive_scan(d.begin(), d.end(), scan.begin());

    // Stream compaction: keep only even numbers
    thrust::device_vector<int> evens(N);
    auto end = thrust::copy_if(d.begin(), d.end(), evens.begin(),
                               [] __device__ (int x) { return x % 2 == 0; });
    evens.resize(end - evens.begin());

    printf("Sorted[0..3]: %d %d %d %d\n", (int)d[0], (int)d[1], (int)d[2], (int)d[3]);
    printf("Scan[0..3]:   %d %d %d %d\n", (int)scan[0], (int)scan[1], (int)scan[2], (int)scan[3]);
    printf("Even count: %d\n", (int)evens.size());  // 8: 0,2,4,6,8,10,12,14
}

// TRY IT

GPU execution
main.cu
loading editor…