Parallel Reduction

Parallel Reduction — a fundamental parallel algorithm that combines N elements into a single result (sum, max, min, product) using $O(\log n)$ steps instead of $O(n)$ sequential steps.

Sequential vs Parallel

• Sequential sum of 8 elements: 7 additions, 7 steps
• Parallel reduction: 7 additions, 3 steps ($\log_2 8$)

Tree Reduction

Step 1: [a0+a1] [a2+a3] [a4+a5] [a6+a7]  (4 additions in parallel)
Step 2: [s01+s23]       [s45+s67]          (2 additions in parallel)
Step 3: [s0123+s4567]                      (1 addition — final result)

GPU Implementation (CUDA)

__shared__ float sdata[256];
sdata[tid] = input[i];
__syncthreads();
for (int s = blockDim.x/2; s > 0; s >>= 1) {
    if (tid < s) sdata[tid] += sdata[tid + s];
    __syncthreads();
}

Optimizations

• First reduction on load (reduce global memory reads)
• Warp-level reduction (no syncthreads needed within a warp)
• Sequential addressing (no bank conflicts in shared memory)

Applications

• Machine learning: Loss computation, gradient aggregation
• Graphics: Computing image statistics (histogram, brightness)
• Scientific computing: Norms, dot products, global sums

Parallel reduction is one of the most important parallel primitives — it appears as a building block in countless parallel algorithms.