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.