GPU で動的に分岐するパーティクル システムに取り組んでいます。次のプロパティを持つ並列データ構造が必要です。
- 1 つのスレッドが一定時間内に要素を 1 つずつ削除できる必要があります。返される要素は、アルゴリズムにとって重要ではありません。ただし、空でない場合に何らかの要素が返される限りです。さらに素晴らしいものにするために、任意の数のスレッドに変更します。
- 任意の数のスレッドが一定時間内に要素をデータ構造に追加できなければなりません。ある程度のロックは許可されていますが (必要です)、スレッド数に関係なくスケーリングする必要があることに注意してください。つまり、スレッドを増やしても速度が低下することはありません。
基本的な同期プリミティブ (ミューテックス、セマフォ)、およびそれらを使用して実装できるものはすべて利用可能です。
私はリンクされたリストのアイデアをいじりましたが、これは条件 2 に違反しています (ロックを考慮する必要があるため、追加は m スレッドに対して O(m) になるため)。そのようなデータ構造が存在するかどうかはわかりませんが、聞いてみようと思いました。