Reduction maps an array of N values to a single value (sum, max, count) using an associative operator. The naive sequential approach is O(N); the parallel approach achieves O(N/P + log P) — the dominant pattern in GPU programming.
Think of it as a binary tree of pairwise operations:
[a0 a1 a2 a3 a4 a5 a6 a7] N = 8 elements
↓ ↓ ↓ ↓ step 1: stride 1 (4 ops)
[a0+a1 a2+a3 a4+a5 a6+a7]
↓ ↓ step 2: stride 2 (2 ops)
[a0..a3 a4..a7]
↓ step 3: stride 4 (1 op)
[a0..a7]
log2(8) = 3 steps. With 1,024 threads this becomes 10 steps — much less than 1,023 sequential adds.
// DIVERGES: threadIdx.x % stride != 0 causes half the warp to idle
for (int s = 1; s < blockDim.x; s *= 2) {
if (threadIdx.x % (2 * s) == 0)
smem[threadIdx.x] += smem[threadIdx.x + s];
__syncthreads();
}
Problem: thread IDs 0, 2, 4... are active while 1, 3, 5... are idle — heavy divergence.
// No divergence: first blockDim.x/2 threads are always active
for (int s = blockDim.x / 2; s > 0; s >>= 1) {
if (threadIdx.x < s)
smem[threadIdx.x] += smem[threadIdx.x + s];
__syncthreads();
}
All active threads are contiguous (0 to s−1) — no divergence. Also improves cache behavior.
Half the blocks do nothing useful in reduction 2 (they just load one element). Load two elements per thread and add immediately:
int i = blockIdx.x * (blockDim.x * 2) + threadIdx.x;
smem[tid] = g_idata[i] + g_idata[i + blockDim.x]; // adds on load
Halves the number of blocks needed for the same input size.
For the final 32 threads (one warp), __syncthreads() is unnecessary because threads in a warp execute synchronously:
if (tid < 32) {
// warpReduce: no __syncthreads() needed
smem[tid] += smem[tid + 32]; __syncwarp();
smem[tid] += smem[tid + 16]; __syncwarp();
smem[tid] += smem[tid + 8]; __syncwarp();
smem[tid] += smem[tid + 4]; __syncwarp();
smem[tid] += smem[tid + 2]; __syncwarp();
smem[tid] += smem[tid + 1]; __syncwarp();
}
Replace shared memory entirely for the warp-level phase:
__device__ float warpReduceSum(float val) {
for (int offset = 16; offset > 0; offset >>= 1)
val += __shfl_down_sync(0xffffffff, val, offset);
return val; // lane 0 has the total
}
Shuffle intrinsics have lower latency than shared memory and require no __syncthreads().
A single block handles at most 1,024 elements. For large arrays:
partial[blockIdx.x]// Grid-stride loop: one kernel handles arbitrarily large arrays
int i = blockIdx.x * blockDim.x + threadIdx.x;
float val = 0.f;
while (i < n) {
val += g_in[i];
i += gridDim.x * blockDim.x; // stride = total thread count
}
// then tree-reduce val within the block...
// CODE EXAMPLE
// Complete optimized block reduction: first-add-on-load + warp shuffles
#include <cuda_runtime.h>
__device__ float warpReduceSum(float val) {
val += __shfl_down_sync(0xffffffff, val, 16);
val += __shfl_down_sync(0xffffffff, val, 8);
val += __shfl_down_sync(0xffffffff, val, 4);
val += __shfl_down_sync(0xffffffff, val, 2);
val += __shfl_down_sync(0xffffffff, val, 1);
return val;
}
__global__ void reduce(const float *g_in, float *g_out, int n) {
__shared__ float smem[32]; // one slot per warp
// Grid-stride loop: load 2 elements per thread and add immediately
int tid = threadIdx.x;
int gid = blockIdx.x * (blockDim.x * 2) + tid;
float val = 0.f;
if (gid < n) val += g_in[gid];
if (gid + blockDim.x < n) val += g_in[gid + blockDim.x];
// Warp-level reduction
val = warpReduceSum(val);
// First lane of each warp writes to shared memory
int lane = tid % 32;
int warpId = tid / 32;
if (lane == 0) smem[warpId] = val;
__syncthreads();
// Final warp reduces all warp sums
int numWarps = (blockDim.x + 31) / 32;
if (tid < 32) {
val = (tid < numWarps) ? smem[tid] : 0.f;
val = warpReduceSum(val);
if (tid == 0) g_out[blockIdx.x] = val;
}
}// TRY IT
GPU execution