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 | 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 |
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.
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[]
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:
// 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[]
For sub-warp or full-warp scans, use shuffle intrinsics — no __syncthreads() needed:
__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;
}
For arrays larger than one block:
sums[blockIdx.x]sums array (recursively or with a single block)sumsThis pattern, called scan-then-propagate, is used by CUB's DeviceScan and Thrust's inclusive_scan.
| 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
// 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