Associativity means regrouping operands leaves an operation’s result unchanged: (a + b) + c equals a + (b + c). This lets a reduction combine values as a tree instead of only in sequence. section 5.16
Why regrouping matters
A parallel integer sum can combine values in a different order from a sequential loop and still produce the same result. Floating-point addition rounds, however, so different groupings can produce slightly different answers. section 5.16
Check these properties before choosing a reduction tree:
- Associativity permits regrouping. Subtraction fails this test; max, min, product, AND, OR, and XOR pass. section 5.17
- Commutativity permits swapping operands. The stride-halving tree and atomic combination can change their order, so this kernel also relies on commutativity. Associative but noncommutative operations, such as string concatenation, need a tree that preserves order. section 5.17
Floating-point reductions may vary in their last digits across runs. In machine learning, tiny differences when summing gradients can compound; deterministic modes fix the reduction order in exchange for some speed. section 5.16
#include <stdio.h>
#include <stdlib.h>
#include <cuda_runtime.h>
__global__ void sumKernel(int* data, int* result, int n) {
__shared__ int sdata[256]; #A
int tid = threadIdx.x;
int idx = blockIdx.x * blockDim.x + threadIdx.x;
sdata[tid] = (idx < n) ? data[idx] : 0; #B
__syncthreads(); #C
for (int stride = blockDim.x / 2; stride > 0; stride >>= 1) { #D
if (tid < stride) {
sdata[tid] += sdata[tid + stride];
}
__syncthreads(); #E
}
if (tid == 0) {
atomicAdd(result, sdata[0]); #F
}
}
int main() {
int n;
scanf("%d", &n);
int threadsPerBlock = 256;
int numBlocks = (n + threadsPerBlock - 1) / threadsPerBlock; #G
int* h_data = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) scanf("%d", &h_data[i]);
int* d_data;
cudaMalloc(&d_data, n * sizeof(int));
cudaMemcpy(d_data, h_data, n * sizeof(int), cudaMemcpyHostToDevice);
int* d_result;
cudaMalloc(&d_result, sizeof(int));
cudaMemset(d_result, 0, sizeof(int)); #H
sumKernel<<<numBlocks, threadsPerBlock>>>(d_data, d_result, n);
int h_result;
cudaMemcpy(&h_result, d_result, sizeof(int), cudaMemcpyDeviceToHost); #I
printf("%d\n", h_result);
cudaFree(d_data);
cudaFree(d_result);
free(h_data);
return 0;
}The shared-memory kernel repeatedly halves the stride and combines partial sums, forming a tree reduction. section 5.16






