Parallel Prefix Sum / Scan

This explanation is currently available in Japanese.

ひとことで

数の列の、先頭からの累積和（プレフィックスサム、スキャン）を、たくさんの演算器で並列に求める方法です。[3, 1, 4, 1, 5] の累積和は [3, 4, 8, 9, 14] です。1 つずつ足せば $n$ ステップかかりますが、全員が同時に「少し前の値」を足すことを、距離を 1, 2, 4, 8… と倍にしながらくり返せば、$\log_2 n$ ステップで終わります。GPU で「生きている粒子だけを前に詰める」「各グループの書き込み先を決める」といった処理の土台になる、とても重要な部品です。

ゲームでの使いどころ

• ストリームコンパクション：生きている粒子、見えている物体だけを、隙間なく配列の前に詰める（インダイレクト描画の準備）。
• 空間ハッシュの構築：セルごとの粒子の数の累積和で、各セルの置き場所を決める（空間ハッシュの数え上げソート）。
• 基数ソート：GPU での並べ替え（モートン符号の順に並べる BVH の構築など）の中核。
• 可変長のデータの配置：物体ごとに違う数の頂点や粒子を生成するとき、それぞれの書き込み開始位置を決める。

しくみ

包括的スキャンと排他的スキャン：自分を含む合計（[3, 4, 8, 9, 14]）が包括的、自分の手前までの合計（[0, 3, 4, 8, 9]）が排他的スキャンです。書き込み先の番号を決めるには、排他的スキャンを使います。

ヒリスとスティールの方法：ステップ $k$（$k = 0, 1, 2, \dots$）で、すべての $i \ge 2^k$ について同時に

を行います。$\log_2 n$ ステップで終わりますが、足し算の回数は約 $n \log_2 n$ 回と、1 つずつ足す場合より多くなります。

ブレロックの方法：足し算の回数も約 $2n$ 回に抑えた方法です。

1. 上り：隣り合う 2 つをまとめ、その結果をさらにまとめる、と木の形に部分和を作ります（最後の要素に全体の合計が入る）。
2. 最後の要素を 0 にします。
3. 下り：木を上から下へたどり、「右の子に、左の子の値を足し、左の子には親の値を渡す」ことをくり返します。最後に排他的スキャンが得られます。

大きな配列：GPU では、ブロック（数百〜数千要素）ごとにグループ内の共有メモリでスキャンし、各ブロックの合計をさらにスキャンして、最後に各ブロックへ足し戻します。

実装のポイント

• ぶつからない書き込み：スキャンで求めた番号は、全員が違う値になるので、並列に書き込んでも場所が重なりません。アトミックな加算で詰めるより、順番も保たれます。
• バンク競合：GPU の共有メモリには、同時に同じ区画（バンク）を読むと遅くなる性質があります。添え字に少し隙間を入れて避けます。
• 既存の実装を使う：スキャンは正しく速く書くのが難しいので、CUB、Thrust、各エンジンや WebGPU のライブラリの実装を使うのが安全です。
• CPU では 1 つずつで十分：CPU で数千個程度なら、単純なループの方が速く簡単です。並列の方法は GPU で大量のデータを扱うときのものです。

つまずきやすい点

• 包括的と排他的の取り違え：1 つずれると、すべての書き込み先がずれます。どちらが必要かを決めてから使います。
• ステップの間の同期：各ステップで全員が「前のステップの値」を読む必要があります。同期を忘れると、書きかけの値を読んで結果が壊れます（ピンポンバッファと同じ問題）。
• 合計のあふれ：大量の値を足すと、整数の上限を超えることがあります。型の大きさに注意します。

デモで試すこと

1. 「ヒリスとスティールの方法」では、16 本の棒（値）について、各ステップで黄色の矢印の元の値を先に足していきます。距離が 1, 2, 4, 8 と倍になり、4 ステップで先頭からの合計がそろいます。
2. 「ブレロックの方法」では、上りで木の形に部分和をまとめ、いちばん右を 0 にしてから、下りで配り直します。左下の足し算の回数が、ヒリスとスティールより少ないことを確かめてください。
3. 「使い道：生きている粒子を詰める」では、上の段の粒子の上に「自分より左にいる生きている粒子の数」（排他的スキャン）が表示され、生きている粒子（緑）がその番号の位置へ詰められます。
4. 「値を入れ替える」で、別の値や粒子の並びで試せます。