これが私が試みる 1 つのアプローチです: isAlive のフラグを残りのデータ構造から分離します。これは、頻繁に読み取られるがほとんど書き込まれないデータのように見えます。1 つの uint を使用して 32 個の粒子の状態を追跡します。生きている場合は 0、死んでいる場合は 1 を使用します。基本的には isDead リストを作成します。死んだ粒子よりも生きている粒子の方が多いと思います。
値は、必要に応じてローカル メモリに読み込むことができます (一度に 32 個)。これにより、ゼロ以外の値を探してデータをすばやく反復処理するカーネルを作成できます。ここでのパフォーマンスの大幅な向上は、データの密度が高いため、フラグの格納と読み込みのメモリ オーバーヘッドが削減されます。これにより、これらの値のいずれかをチェックする操作がはるかに安価になり、それらをより迅速に反復処理できます。同じ uint を共有する他のデータを破損しないように、32 ビット値を変更するときは注意が必要です (インターレースがこれに役立ちます)。命令 clz および popcount は、1 ビットの正確な位置を絞り込む必要がある場合に役立ちます。opencl 1.2 refcard
可能な最適化 #1: 必要に応じて、最初の uint がインデックス 0,32,64,96,...,992 を追跡し、2 番目の uint が 1,33,65,97 を表すように、値をインターレースしてみることができます。 ...、993など。これにより、通常は特定のパーティクルで動作するワークアイテムが 32 個の連続する isDead 状態を読み取ることができるようになります。これは、価値がある以上の労力になる可能性がありますが、それはアプリケーションによって異なります。
可能な最適化 #2: デッド パーティクルが本当にまばらな場合は、より高いレベルで isDead リストを追跡する価値があるかもしれません。同じ手法を使用して、isDead ビット/uint リストを再び 32 分の 1 に減らすのは簡単です。第 2 レベルの各ビットは、対応する uint の状態を表します。つまり、uint N のいずれかのビットが設定されている場合、このリストのビット N も設定されます。データに多数のゼロが予想される場合にのみ役立ちますが、この追加の手順により、データ内のまれな「オン」ビットを検索するサイクルを大幅に節約できます。元の isDead データを含むこれの総メモリ オーバーヘッドは、memBits = ceil(particleCount/32) + ceil(particleCount/32^2)、つまり 2^20 パーティクルごとに約 128kb + 4kb になります。
上記を使用して、指定された範囲内のデッド パーティクルの数を返すカーネルを記述し、次に使用可能なデッド パーティクルの 1 つをすばやく見つけることができます。