liveBook · Manning

Identity element

As explained in Grokking GPU Programming

An identity element is a value that leaves the result of an operation unchanged when combined with another value.

When adding a grocery receipt, adding 0 leaves the total unchanged. That makes 0 the identity element for addition: a value that combines with another value without changing it. The right identity depends on the operation and the data type. section 5.2

Common operations use different identities:

  • Sum and count: 0. For a count, first map each item to 1 if it matches the condition, or 0 otherwise, then sum. section 5.2
  • Product: 1, because multiplying by 1 leaves a value unchanged. section 5.2
  • Integer maximum: INT_MIN; integer minimum: INT_MAX. Other data types use their own limits. section 5.2

An identity is especially useful as safe padding in a parallel reduction. If a block has more threads than input values, each spare thread writes the identity instead of reading past the input. The reduction can then combine every slot without changing the answer. section 5.2 section 5.11

Padding a partial block

Suppose six values are processed in blocks of four threads. The second block has only two real values, so its shared memory holds [data[4], data[5], 0, 0]. The first reduction round combines each value with 0; the next adds the two unchanged values. The block therefore returns data[4] + data[5]. section 5.11

A common mistake is to skip the store for an out-of-bounds thread. Its shared-memory slot is then uninitialized, so later reads can produce an incorrect result. Guard the load and write the operation’s identity instead; for a sum, use 0. section 11.3 section 5.11

Changing the operation means changing the identity too. For an integer maximum, padding with 0 would give the wrong answer when every input is negative. Use INT_MIN for padding and initialize the shared result to INT_MIN as well. The cross-block combine must also change from atomicAdd to atomicMax. section 5.17 section 5.2

#include <climits>    #A
 
__global__ void maxKernel(int* data, int* result, int n) {
    __shared__ int sdata[256];    #B
    int tid = threadIdx.x;
    int idx = blockIdx.x * blockDim.x + threadIdx.x;
 
    sdata[tid] = (idx < n) ? data[idx] : INT_MIN;    #C
    __syncthreads();
 
    for (int stride = blockDim.x / 2; stride > 0; stride >>= 1) {    #D
        if (tid < stride) {
            sdata[tid] = max(sdata[tid], sdata[tid + stride]);
        }
        __syncthreads();
    }
 
    if (tid == 0) {    #E
        atomicMax(result, sdata[0]);
    }
}

This CUDA maximum-reduction kernel loads INT_MIN for spare threads, then combines block results with atomicMax. section 5.17

In an exclusive scan, each output describes the values before its position. The first output has nothing before it, so it is the identity: an exclusive sum scan of [3, 1, 7] begins [0, 3, 4]. In a Blelloch scan, seeding the tree root with 0 before the down-sweep produces an exclusive sum scan; a maximum or product scan uses its own identity instead. section 6.1 section 7.8

An identity alone does not make an operation suitable for every parallel tree. Associativity permits regrouping; the stride-halving reduction also relies on commutativity because it can reorder operands. Choose the identity, tree, and final combine to match the operation. section 5.17

How Grokking GPU Programming covers it

How deep it goes
Defines identities and traces padding and scan seeding, extending the explanation to operation choice and cross-block combination.
Examples
Traces a six-value sum across partial blocks and seeds a Blelloch scan with zero.
What you can do after
Apply identities in CUDA reductions and exclusive scans, selecting padding and initialization values for the operation.
How it connects
Connects identities to reduction, exclusive scan, associativity, commutativity, shared memory, and atomic operations.

Also explained in

Compare how 6 books explain identity element →

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.