AlgorithmsIntermediate~75 min

Parallel Reduction — Six Optimizations

Follow the classic NVIDIA reduction progression. Start with a naive implementation and apply six successive optimizations — from divergent warps to warp shuffle intrinsics.

reductionwarp-shuffle__shfl_down_syncunrollingshared-memory

// PREREQUISITES

// PROJECT PHASES

  1. 1

    Divergent reduction (baseline)

    Tree reduction with warp divergence.

  2. 2

    Bank-conflict-free reduction

    Contiguous active threads.

  3. 3

    Idle first-step elimination

    Load two elements per thread.

  4. 4

    Unrolled last warp

    Avoid syncthreads when < 32 threads.

  5. 5

    Full loop unroll

    Template parameter for blockSize.

  6. 6

    Warp shuffle reduction

    __shfl_down_sync replaces shared memory.

// SANDBOX

GPU execution
main.cu
loading editor…

// EXPECTED OUTPUT

Reduce0 (divergent):   18.4 ms  22.9 GB/s
Reduce5 (shuffle):      2.5 ms 168.4 GB/s

// YOUR PROGRESS

Log in to save progress

// DETAILS

Category
Algorithms
Difficulty
Intermediate
Est. time
~75 min
Prerequisites
1

// LEARN THE THEORY

Algorithms concepts