liveBook · Manning

Associativity

As explained in Grokking GPU Programming

Associativity is the property that regrouping operands does not change the result of an operation.

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

How Grokking GPU Programming covers it

How deep it goes
Defines regrouping, tests reduction operators, and notes floating-point limits without developing formal algebra.
Examples
Uses integer and floating-point sums, subtraction, max, min, products, logical operations, and string concatenation.
What you can do after
Apply it to decide whether an operation supports tree reduction and whether its operand order must be preserved.
How it connects
Connects associativity to parallel reduction, commutativity, identity elements, and floating-point rounding.

Also explained in

Compare how 7 books explain associativity →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Grokking GPU Programming. The section links point to the parts of the book it draws on.