Algorithms

Parallel Prefix Scan (Inclusive and Exclusive)

Parallel Prefix Scan

A prefix scan (prefix sum) produces a running cumulative result: given [a0, a1, a2, a3], the inclusive scan is [a0, a0+a1, a0+a1+a2, a0+a1+a2+a3]. It is a fundamental building block for stream compaction, sorting, histogram normalization, and load balancing.

Inclusive vs. Exclusive

| | Inclusive | Exclusive | |---|---|---| | Result[i] | a[0] + … + a[i] | a[0] + … + a[i-1] | | Result[0] | a[0] | Identity (0 for sum) | | Convert | Shift right by 1, prepend identity | Shift left by 1, append total |

Hillis-Steele (Work-Inefficient)

log2(N) steps, but each step touches all N elements → O(N log N) work (vs O(N) sequential). Good when extra parallelism outweighs extra work.

c
for (int d = 1; d < n; d <<= 1) {
    if (tid >= d)
        tmp[tid] = s[tid] + s[tid - d];
    else
        tmp[tid] = s[tid];
    __syncthreads();
    s[tid] = tmp[tid];
    __syncthreads();
}
// Result: inclusive scan in s[]

Blelloch (Work-Efficient)

Two-phase approach — O(N) work, O(log N) depth. Preferred for large inputs.

Phase 1 — Reduce (up-sweep):

d=1: s[1]+=s[0], s[3]+=s[2], s[5]+=s[4], ... d=2: s[3]+=s[1], s[7]+=s[5], ... d=4: s[7]+=s[3], ...

After up-sweep, s[N-1] holds the total.

Phase 2 — Down-sweep:

c
// Set last element to identity
if (tid == 0) s[n - 1] = 0;
__syncthreads();

for (int d = n/2; d >= 1; d >>= 1) {
    // Each active thread performs a butterfly swap + add
    int left = 2*d*tid + d - 1, right = left + d;
    float t = s[left];
    s[left]  = s[right];
    s[right] += t;
    __syncthreads();
}
// Result: exclusive scan in s[]

Warp Scan (Fastest, No Shared Memory Sync)

For sub-warp or full-warp scans, use shuffle intrinsics — no __syncthreads() needed:

c
__device__ float warpInclusiveScan(float val) {
    unsigned mask = 0xffffffff;
    for (int offset = 1; offset < 32; offset <<= 1) {
        float y = __shfl_up_sync(mask, val, offset);
        if (threadIdx.x % 32 >= offset) val += y;
    }
    return val;
}

Multi-Block Scan Pattern

For arrays larger than one block:

  1. ▸Block scan: each block scans its chunk, writes the block total to sums[blockIdx.x]
  2. ▸Scan the sums: run scan on the sums array (recursively or with a single block)
  3. ▸Add prefix: each block adds its corresponding prefix sum from sums

This pattern, called scan-then-propagate, is used by CUB's DeviceScan and Thrust's inclusive_scan.

Applications

| Pattern | Uses scan for | |---|---| | Stream compaction | Writing only valid elements to a compact output array | | Radix sort | Digit histogram offsets (counting sort step) | | Sparse matrix-vector multiply | Row pointer generation | | Dynamic memory allocation | Allocating variable-size per-thread output buffers |

// CODE EXAMPLE

example.cu
// Blelloch exclusive scan within a single block (power-of-2 size)
#define BLOCK_N 512

__global__ void exclusiveScan(float *data, int n) {
    __shared__ float s[BLOCK_N];
    int tid = threadIdx.x;

    // Load input
    s[tid] = (tid < n) ? data[tid] : 0.f;
    __syncthreads();

    // Up-sweep (reduce)
    for (int d = 1; d < BLOCK_N; d <<= 1) {
        int right = 2 * d * (tid + 1) - 1;
        int left  = right - d;
        if (right < BLOCK_N) s[right] += s[left];
        __syncthreads();
    }

    // Set root to identity
    if (tid == 0) s[BLOCK_N - 1] = 0.f;
    __syncthreads();

    // Down-sweep
    for (int d = BLOCK_N / 2; d >= 1; d >>= 1) {
        int right = 2 * d * (tid + 1) - 1;
        int left  = right - d;
        if (right < BLOCK_N) {
            float t   = s[left];
            s[left]   = s[right];
            s[right] += t;
        }
        __syncthreads();
    }

    if (tid < n) data[tid] = s[tid];
}

// TRY IT

GPU execution
main.cu
loading editor…