Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 31 ยท Synchronization and Parallel Patterns

Parallel Reduction

Learn parallel reduction in CUDA: tree reduction, interleaved vs sequential addressing, warp shuffles, an atomic final step, and why float sums change with order.

A reduction turns many values into one: a sum, a maximum, a minimum, a count. On a CPU you write a loop with a running total. On a GPU that loop is a trap, because a running total is a chain of dependent steps and thousands of threads would all have to wait in line for it. Reduction is one of the most common parallel patterns, and it is also the best small example of how to think about GPU code: break the work into a tree, keep every thread busy, and avoid threads of one warp taking different paths.

This lesson builds a reduction in four layers: a tree inside a block, a better memory layout for that tree, warp shuffles for the last 32 values, and an atomic or second kernel to combine the blocks. It finishes with an unexpected side effect: the answer for floating-point data depends on the order of the additions. You should already know shared memory and synchronization with atomics.

The CUDA C++ in this lesson is read-only, because this site has no GPU. The runnable examples are Python stand-ins: they apply the same arithmetic steps that the GPU threads would, so the indexing, the counts and the rounding behavior are real, but nothing here measures speed.

Why a running total does not scale

A sequential sum of n numbers takes n - 1 additions in a row. A tree reduction adds pairs at the same time, then adds the pairs of pairs, and so on. With n values it needs about log2(n) rounds, and in each round all the additions are independent of one another.

flowchart TD
    A["8 inputs"] --> B["round 1: 4 pair sums"]
    B --> C["round 2: 2 partial sums"]
    C --> D["round 3: 1 total"]

Eight values need three rounds instead of seven dependent additions.

The total number of additions is still n - 1, so the tree does not do less work. It does the same work in fewer sequential steps. That matters because a GPU has the width to run each round in parallel.

Inside a CUDA block, the threads cooperate through shared memory. Each thread first loads one element, then the block repeatedly halves the number of active threads. A barrier, __syncthreads(), separates the rounds so no thread reads a partial sum before it has been written.

Naive tree: interleaved addressing

The first version most people write pairs up neighbours, then pairs of pairs, doubling the distance each round.

C++
__global__ void reduceInterleaved(const float* in, float* out, int n) {
    extern __shared__ float s[];
    int tid = threadIdx.x;
    int i = blockIdx.x * blockDim.x + tid;
    s[tid] = (i < n) ? in[i] : 0.0f;
    __syncthreads();

    for (int stride = 1; stride < blockDim.x; stride *= 2) {
        if (tid % (2 * stride) == 0) {
            s[tid] += s[tid + stride];
        }
        __syncthreads();
    }
    if (tid == 0) out[blockIdx.x] = s[0];
}

It is correct, but the if (tid % (2 * stride) == 0) test is a problem. In round 1 every second thread works, in round 2 every fourth, and so on. The active threads are scattered across all the warps, so each warp executes the addition with most of its lanes switched off. A warp executes one instruction at a time for all 32 lanes, so half-empty warps waste the hardware (you will study this cost in divergence). The % operator is also slow compared to a plain compare.

Better tree: sequential addressing

The fix is to keep the active threads together. Instead of pairing neighbours, pair each element with the one stride positions away, starting with half the block and shrinking the stride each round.

C++
__global__ void reduceSequential(const float* in, float* out, int n) {
    extern __shared__ float s[];
    int tid = threadIdx.x;
    int i = blockIdx.x * blockDim.x + tid;
    s[tid] = (i < n) ? in[i] : 0.0f;
    __syncthreads();

    for (int stride = blockDim.x / 2; stride > 0; stride /= 2) {
        if (tid < stride) {
            s[tid] += s[tid + stride];
        }
        __syncthreads();
    }
    if (tid == 0) out[blockIdx.x] = s[0];
}

Now the active threads are always 0 .. stride - 1, one contiguous group. Whole warps are either busy or completely idle, and an idle warp costs nothing to schedule. The shared-memory reads are also contiguous, which avoids bank conflicts. The next stand-in counts both effects for a block of 128 threads and 32-thread warps.

Python Interleaved vs sequential addressing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions produce 128, but look at the last column. The interleaved tree touches all four warps for its first five rounds, with idle lanes in every one of them: 23 warp-steps with idle lanes in total. The sequential tree touches fewer warps each round and leaves no warp half-filled until the stride drops below 32: only 5 such warp-steps. Those last rounds (stride 16 and below) must live inside a single warp, and that is exactly the part the next section replaces with a better tool.

Finishing inside the warp: shuffles

Once only 32 values remain, they all live in one warp. Warp threads run in lockstep, so they can pass values to each other directly through registers with __shfl_down_sync, with no shared memory and no __syncthreads(). (Warp primitives get their own lesson: Warp Primitives and Cooperative Groups.)

C++
__inline__ __device__ float warpReduceSum(float v) {
    for (int offset = 16; offset > 0; offset /= 2) {
        v += __shfl_down_sync(0xffffffff, v, offset);
    }
    return v;   // lane 0 holds the warp's sum
}

__shfl_down_sync(mask, v, offset) gives each lane the value of v held by the lane offset positions higher. Lanes whose source would be beyond lane 31 keep their own value, and their results are never used. After five steps (offsets 16, 8, 4, 2, 1) lane 0 holds the sum of all 32 lanes.

A whole-block reduction then runs in two stages: every warp reduces its own 32 values with shuffles, lane 0 of each warp writes the warp sum into a small shared array, and the first warp reduces that array.

C++
__global__ void reduceBlock(const float* in, float* total, int n) {
    __shared__ float warpSums[32];
    int tid = threadIdx.x;
    int lane = tid % 32;
    int warp = tid / 32;

    // grid-stride loop: each thread sums many inputs first
    float v = 0.0f;
    for (int i = blockIdx.x * blockDim.x + tid; i < n; i += gridDim.x * blockDim.x) {
        v += in[i];
    }

    v = warpReduceSum(v);
    if (lane == 0) warpSums[warp] = v;
    __syncthreads();

    v = (tid < blockDim.x / 32) ? warpSums[lane] : 0.0f;
    if (warp == 0) {
        v = warpReduceSum(v);
        if (tid == 0) atomicAdd(total, v);   // combine blocks
    }
}

Two more ideas are packed into this kernel. First, the grid-stride loop (from Grids, Blocks and Threads) lets a modest number of threads walk over a huge array, adding many values in registers before any cooperation happens. That is far cheaper than loading one value per thread and paying for a reduction tree on each. Second, the last line uses atomicAdd so each block adds its partial result to one total in global memory.

Python Warp shuffle reduction, simulated

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simulation uses a list of 32 values where the real hardware uses 32 registers in 32 lanes, and it performs the shuffle as a whole-list operation instead of true lockstep. What is real is the data movement: lane 0 collects exactly the values it would on a GPU, and you can watch the partial sum grow with each offset.

Combining the blocks

Blocks cannot synchronize with each other inside one kernel launch (see Synchronization and Atomics), so each block ends with one partial result. There are three common ways to turn those partials into a final answer:

  • Atomic final step. Every block does one atomicAdd into a single global value, as in the kernel above. It is the shortest code. There is one atomic per block, not per thread, so contention is small. The drawback is that the order of the additions varies from run to run, which affects floating-point results (see the next section).
  • Second kernel launch. Write one partial per block to an array, then launch a second, small reduction over that array. The order is fixed, so the result is the same every run. The cost is one more launch.
  • Recursive launches. For very large data, repeat the launch until a single value remains. In practice a grid-stride loop with a few hundred blocks makes two passes enough.

For production code, a library does this better than you will on a first try: CUB's DeviceReduce and Thrust's reduce are tuned per GPU generation. Write your own only to learn the pattern or when you need to fuse the reduction into a bigger kernel. See The CUDA Library Ecosystem.

Numerical order effects

Floating-point addition is not associative. In float arithmetic, (a + b) + c can differ from a + (b + c) because each addition rounds its result. A parallel reduction adds the same numbers in a different order than a CPU loop, so the two answers may differ in the last digits, and an atomic final step may even differ between two runs of the same program.

Python The same numbers, three orders, three answers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice three things in the output. The sequential and tree sums are both close to the float64 reference but are not equal to each other. The shuffled orders mimic what an atomic final step can do when blocks finish in a different order: each shuffle can give a slightly different float. And a tree with a fixed shape returns the same answer every time, which is why reproducibility-minded code prefers a fixed-order reduction (a second kernel, not atomics) or accumulates in double.

None of these answers is "wrong". Each is a valid rounding of the true sum, and the tree is often more accurate than the straight loop, because it adds numbers of similar size to each other. When you compare a GPU result with a CPU result, use a tolerance, not ==.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is a tree reduction faster on a GPU than a sequential running total?

    The tree still performs n - 1 additions, but they are grouped into about log2(n) rounds of independent work, which the GPU can run in parallel.
  2. 2. Why is sequential addressing (active threads 0 to stride - 1) better than interleaved addressing (tid % (2 * stride) == 0)?

    Interleaved addressing leaves lanes switched off inside every warp, which wastes issue slots. Sequential addressing packs the active threads into whole warps and also avoids bank conflicts.
  3. 3. What does __shfl_down_sync(0xffffffff, v, 8) do for lane 3?

    A down-shuffle by an offset returns the value held by the lane that many positions higher, so lane 3 receives lane 11's v.
  4. 4. Which statement about an atomicAdd final step across blocks is true for float data?

    Blocks finish in an unpredictable order, and floating-point addition is not associative, so the rounded total can change in the last digits. A second kernel with a fixed order is reproducible.

Summary

  • A reduction combines many values into one; a tree needs about log2(n) rounds of independent additions instead of n - 1 dependent ones.
  • Interleaved addressing scatters active threads across warps; sequential addressing keeps them contiguous and is faster and bank-conflict free.
  • Warp shuffles (__shfl_down_sync) finish the last 32 values in registers with no shared memory or barrier.
  • A grid-stride loop lets each thread add many inputs privately before cooperating.
  • Block results are combined with one atomic per block, or with a second small kernel for a fixed order.
  • Floating-point sums depend on addition order, so compare GPU and CPU results with a tolerance.

Next, apply the same tree thinking to running totals in Scan, Histogram and Other Patterns.