CUDA Academy · レッスン

リダクションツリーの考え方

各ステップでアクティブなスレッドを半分にします。

「リダクションツリーの考え方」はCoddyKit上の無料CUDA Academyレッスンです。これはレッスン1/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはCUDA Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 CUDA Academyコースには全4レッスンが含まれています。

このレッスンの一部はまだ翻訳されておらず、英語で表示されています。

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

よくある質問

「リダクションツリーの考え方」レッスンは無料ですか？

はい。「リダクションツリーの考え方」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、CUDA Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 CUDA Academyコースには全4レッスンが含まれています。

「リダクションツリーの考え方」で何を学びますか？

各ステップでアクティブなスレッドを半分にします。ブラウザで直接実行するハンズオンコードでCUDA Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

CUDA Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCUDA Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン1/4です。

「リダクションツリーの考え方」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCUDA Academyレッスンでコードを書いて実行できますか？

はい。すべてのCUDA Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

← CUDA Academyに戻る