แนวคิดต้นไม้ลดรูป

A reduction collapses a whole array into one value, like summing every element down to a single total. It is one of the most common GPU patterns. 🌳

On a CPU you add elements one after another. That is O(n) sequential steps, so a million numbers means a million dependent additions in a row.

The trick is that addition is associative: (a+b)+c equals a+(b+c). So you are free to add pairs in any grouping you like.

Because grouping is free, you can add many independent pairs at the same time. Every thread handles one pair, all in a single parallel step.

After one pass, half the elements are gone. Repeat, and the active count keeps halving: 8 to 4 to 2 to 1.

Halving means you finish in log2(n) steps instead of n. A million elements collapses in about 20 steps, not a million.

Drawing the pairings makes a binary tree. Leaves are the inputs, each level halves the nodes, and the root is your final sum.

One way to code it: each step a thread adds its neighbor at distance stride, and that stride doubles every pass through the data.

Every level depends on the previous one finishing, so threads must wait at a barrier before reading their partner's result.

Total additions stay about n, the work. But the longest dependency chain, the span, shrinks to log2(n). Same work, far less waiting.

The same tree works for any associative operation: max, min, product, or logical AND. Swap the operator and the structure stays.

Think about how many parallel steps a tree reduction needs.

You learned the reduction tree: add pairs in parallel, halve each step, finish in log2(n). It works for any associative operator. Next, keep warps busy! 🎉