GPUで、条件に合う要素だけを配列から取り出して別の配列に詰めて書き出したい(各スレッドが出力する数は0か1)。各スレッドの書き込み先の番地を決めるのによく使われる並列の計算はどれか。

正解：B. プレフィックスサム(スキャン、前からの累積和)

各スレッドが出力するかどうかを0か1で表し、その前からの累積和(排他的なプレフィックスサム)を求めると、各スレッドの値は「自分より前に出力するスレッドの数」になり、それがそのまま書き込み先の番地になります。スキャンはリダクションと同じように木の形で並列に計算できます。出力の数が要素ごとに違う処理を、並列のまま詰めて書き出すための基本の道具です。

• A. 転置では書き込み先は決まりません。
• B. 正しい。自分より前の出力の数が書き込み先になります。
• C. 周波数の変換とは関係ありません。