Algorithms

Parallel Reduction Patterns

Parallel Reduction Patterns

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.

The Tree Reduction Idea

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.

Reduction 1 — Interleaved Addressing (Naive, Slow)

c
// 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.

Reduction 2 — Sequential Addressing (Better)

c
// 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.

Reduction 3 — First Add During Load

Half the blocks do nothing useful in reduction 2 (they just load one element). Load two elements per thread and add immediately:

c
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.

Reduction 4 — Warp Unrolling

For the final 32 threads (one warp), __syncthreads() is unnecessary because threads in a warp execute synchronously:

c
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();
}

Reduction 5 — Full Warp Shuffle (Best Practice)

Replace shared memory entirely for the warp-level phase:

c
__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().

Multi-Block Reduction

A single block handles at most 1,024 elements. For large arrays:

  1. ▸Pass 1: Each block reduces its chunk → writes partial sum to partial[blockIdx.x]
  2. ▸Pass 2: One block (or CPU) reduces the N/1024 partial sums
c
// 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

example.cu
// 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
main.cu
loading editor…