The Reduction Tree Idea
Halving active threads each step.
The Reduction Tree Idea is a free CUDA Academy lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the CUDA Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Reduction Means
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. 🌳
The Sequential Way Is Slow
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.
Addition Is Associative
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.
Add in Parallel Pairs
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.
Halving Each Step
After one pass, half the elements are gone. Repeat, and the active count keeps halving: 8 to 4 to 2 to 1.
Logarithmic Depth
Halving means you finish in log2(n) steps instead of n. A million elements collapses in about 20 steps, not a million.
Picture the Tree
Drawing the pairings makes a binary tree. Leaves are the inputs, each level halves the nodes, and the root is your final sum.
Stride Doubles Each Pass
One way to code it: each step a thread adds its neighbor at distance stride, and that stride doubles every pass through the data.
for (int s = 1; s < blockDim.x; s *= 2) {
if (tid % (2 * s) == 0)
data[tid] += data[tid + s];
__syncthreads();
}Sync Between Steps
Every level depends on the previous one finishing, so threads must wait at a barrier before reading their partner's result.
Work Versus Span
Total additions stay about n, the work. But the longest dependency chain, the span, shrinks to log2(n). Same work, far less waiting.
Not Just Summing
The same tree works for any associative operation: max, min, product, or logical AND. Swap the operator and the structure stays.
Quick Check
Think about how many parallel steps a tree reduction needs.
Recap
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! 🎉
Frequently asked questions
Is the “The Reduction Tree Idea” lesson free?
Yes — the full text of “The Reduction Tree Idea” is free to read here on the web, and the CUDA Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the CUDA Academy course, upgrade to CoddyKit PRO.
What will I learn in “The Reduction Tree Idea”?
Halving active threads each step. You practise CUDA Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start CUDA Academy?
No prior experience is required. CUDA Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “The Reduction Tree Idea” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this CUDA Academy lesson?
Yes. Every CUDA Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- The Reduction Tree Idea
- Killing Warp Divergence
- Sequential Addressing
- Multi-Block Final Reduction