CUDA Academy · Aula

A ideia da árvore de redução

Reduza pela metade as threads ativas a cada etapa.

A ideia da árvore de redução é uma aula grátis de CUDA Academy no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de CUDA Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de CUDA Academy inclui 4 aulas no total.

Partes desta aula ainda não foram traduzidas e aparecem em inglês.

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

Perguntas Frequentes

A aula “A ideia da árvore de redução” é grátis?

Sim — o texto completo de “A ideia da árvore de redução” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de CUDA Academy, atualize para CoddyKit PRO. O curso de CUDA Academy inclui 4 aulas no total.

O que vou aprender em “A ideia da árvore de redução”?

Reduza pela metade as threads ativas a cada etapa. Você pratica CUDA Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar CUDA Academy?

Nenhuma experiência prévia é necessária. CUDA Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.

Quanto tempo leva a aula “A ideia da árvore de redução”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de CUDA Academy?

Sim. Cada aula de CUDA Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

← Voltar para CUDA Academy