GPUプログラミング
GPUで多数の値の総和を求めるとき、木の形のリダクション(隣どうしを足して半分にすることを繰り返す)を使う理由として正しいものはどれか。
- A1つのスレッドが順番に足すよりも、足し算の回数が大きく減るから
- B各段で多くのスレッドが同時に足し算でき、n個の値をlog2 n段で合計できるから
- C浮動小数点の誤差が必ず0になるから
答えと解説を見る
正解：B. 各段で多くのスレッドが同時に足し算でき、n個の値をlog2 n段で合計できるから
1つのスレッドが順に足すとn-1段かかりますが、木の形にすると、1段目でn/2本のスレッドが隣どうしを足し、2段目でn/4本が…と繰り返して、log2 n段で終わります。足し算の総回数は変わりませんが、段数が少ないので並列に速く計算できます。ブロックの中では共有メモリで段を進め、ブロックごとの結果を最後にまとめて合計します。
- A. 足し算の回数はどちらもn-1回です。
- B. 正しい。並列に足せる形に組み替えています。
- C. 誤差はなくなりません(小さくなることはあります)。