CUDA Academy · Leçon

L’idée de l’arbre de réduction

Réduisez de moitié le nombre de threads actifs à chaque étape.

L’idée de l’arbre de réduction est une leçon CUDA Academy gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage CUDA Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours CUDA Academy comprend 4 leçons au total.

Certaines parties de cette leçon n'ont pas encore été traduites et s'affichent en anglais.

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! 🎉

Questions Fréquemment Posées

La leçon « L’idée de l’arbre de réduction » est-elle gratuite ?

Oui — le texte complet de « L’idée de l’arbre de réduction » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours CUDA Academy, passe à CoddyKit PRO. Le cours CUDA Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « L’idée de l’arbre de réduction » ?

Réduisez de moitié le nombre de threads actifs à chaque étape. Tu pratiques CUDA Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer CUDA Academy ?

Aucune expérience préalable n'est requise. CUDA Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.

Combien de temps prend la leçon « L’idée de l’arbre de réduction » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon CUDA Academy ?

Oui. Chaque leçon CUDA Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

← Retour à CUDA Academy