3

私の問題では、ドメインに N 個のポイントがあり、それらはどういうわけかランダムに分布しています。各ポイントについて、指定された倍精度浮動小数点数 DIST 未満の距離にあるすべての隣接ポイントを見つける必要があります。Thrustでこれを行う効率的な方法はありますか? シリアルでは、近傍テーブルを使用して、O(n^2) の素朴なアルゴリズムではなく、ほぼ O(n) を達成したいと考えています。
2D バケット ソートの推力の例を見つけました。これは、問題の最初の部分にぴったりです。しかし、それだけでは十分ではありません。バケットごとに、隣接するバケット内のすべてのポイントを見つけてから、それらの距離を計算し、それらのいずれかが DIST より小さいかどうかを確認する必要があるためです。近傍を見つけて距離を計算するのは比較的簡単なはずですが、これらの適格なポイントを結果配列に追加することは、Thrust で実装するのが非常に難しいようです。この特定の問題を言い換える方法は次のとおりです。2 つの 2D 配列 A1 と A2 があり、列番号は 2D バケットのインデックスを表し、各列にはポイントのインデックスである要素の数が異なります。A1 の列 (i) の各要素は、A2 の列 (i) の各要素と潜在的なペアを形成し、すべての適格なペアを結果配列に記録する必要があります。回避策として、CUDA カーネルを使用して、潜在的に未使用のメモリを大量に割り当てることもできますが、それは私がやりたくないことです。前もって感謝します。

4

2 に答える 2

2

四分木を作成するよりも簡単な別の可能性は、近傍行列を使用することです。

まず、すべての点を 2D 正方行列 (3 次元を扱っている場合は 3D 立方格子) に配置します。次に、完全または部分的な空間ソートを実行して、ポイントがマトリックス内で順序付けられるようにします。

Y が小さい点は行列の一番上の行に移動し、同様に、Y が大きい点は一番下の行に移動します。X 座標が小さい点でも同じことが起こり、左側の列に移動する必要があります。そして対称的に、大きな X 値を持つポイントは右側の列に移動します。

空間的な並べ替えを行った後 (シリアルまたはパラレル アルゴリズムの両方で、これを達成する方法はたくさんあります)、点 P が実際に近傍行列に格納されている隣接セルにアクセスするだけで、特定の点 P の最も近い点を検索できます。

このマトリックスがテクスチャ メモリに配置されている場合、CUDA からのすべての空間キャッシュを使用して、すべてのネイバーに非常に高速にアクセスできます。

このアイデアの詳細については、次の論文を参照してください (オンラインで PDF コピーを見つけることができます): Supermassive Crowd Simulation on GPU based on Emergent Behavior。

並べ替えの手順により、興味深い選択肢が得られます。ペーパーで説明されている偶奇転置ソートのみを使用できます。これは、実装が非常に簡単です（CUDAでも）。このパスを 1 回だけ実行すると、部分的な並べ替えが行われます。これは、マトリックスがほぼ並べ替えられている場合にすでに役立つ可能性があります。つまり、ポイントの動きが遅い場合は、多くの計算を節約できます。

完全な並べ替えが必要な場合は、そのような偶奇転置パスを数回実行できます (次の Wikipedia ページで説明されています)。

http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort

同じ著者による 2 番目の論文があり、3D への拡張について説明し、バイトニック ソート (これは高度に並列ですが、空間ソートではありません) の 3 つのパスを使用しています。彼らは、単一の偶奇転置パスよりも正確であり、完全な並べ替えよりも効率的であると主張しています。この論文はA Neighborhood Grid Data Structure for Massive 3D Crowd Simulation on GPUです。

于 2014-02-08T21:18:46.797 に答える