How do threads combine their results?

Idea 1 of 3

Build a safe tree of partial sums

Multiplication gave each thread an independent output. A sum is different: values handled by different threads must meet. We need somewhere to exchange partial results and a way to wait until those results are ready.

Each thread first writes one input into shared memory. The initial barrier ensures all those writes precede the first partner reads. At partner distance 2, threads 0 and 1 add values from words 2 and 3. After another barrier, thread 0 adds the two partial sums at distance 1.

Step through the writes before the arithmetic. “Unwritten” means a thread has not yet stored its input there. Each model arithmetic stage reads a snapshot of the preceding stage, representing the ordering between stages. Only some threads add, but every thread reaches each block barrier.

import torch

x = torch.arange(1, 5, dtype=torch.float32, device="cuda")
total = x.sum()
print(total.cpu())

Idea 2 of 3

Add another level without losing inputs

The synchronised algorithm starts at partner distance N / 2, then halves the distance down to 1. Each new partial sum combines disjoint sets of input contributions. The final node should contain every input index exactly once.

Change from four to eight inputs. Follow the same write, barrier and combine sequence, now with one more arithmetic stage. Both examples use one block with one partially filled warp. The small input count does not remove the need to express the required ordering.

import torch

x = torch.arange(1, 5, dtype=torch.float32, device="cuda")
total = x.sum()
print(total.cpu())

Idea 3 of 3

Diagnose a missing ordering guarantee

Start with the safe eight-input sum. Then select the diagnostic without synchronisation. The model deliberately lets thread 0 read its first partner before that partner writes. This shows one missing ordering guarantee; it does not enumerate every possible interleaving.

The later partner write cannot repair the earlier read. The diagnostic therefore reports the unwritten access and assigns no numeric output to the racy program. Seeing a plausible sum in some other execution would not establish safety. The PyTorch example still expresses the safe sum; the diagnostic is a change to our teaching algorithm, not a PyTorch option.