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





