GPU でかなり標準的な問題を解決する必要がありましたが、実用的な GPGPU にはまったく慣れていないので、この問題に取り組むためのアイデアを探しています。
非常に少数のグループ (各ポイントは 1 つのグループに属します)、特にこの場合は 15 (変更されません) に割り当てられる 3 空間に多くのポイントがあります。ここで、すべてのグループの平均と共分散行列を計算したいと思います。したがって、CPU では、次とほぼ同じです。
for each point p
{
mean[p.group] += p.pos;
covariance[p.group] += p.pos * p.pos;
++count[p.group];
}
for each group g
{
mean[g] /= count[g];
covariance[g] = covariance[g]/count[g] - mean[g]*mean[g];
}
グループの数が非常に少ないため、最後のステップは CPU で実行できます (とにかく、CPU でこれらの値が必要です)。最初のステップは、実際には単なるセグメント化された削減ですが、セグメントが散らばっています。
そこで私が思いついた最初のアイデアは、まずポイントをグループ別にソートすることでした。バケットのサイズとポイントごとの再配置インデックスを計算するために使用する単純なバケットの並べ替えについて考えましたatomic_inc
(並べ替えについてより良いアイデアを思いつきましたか? アトミックは最良のアイデアではないかもしれません)。その後、それらはグループごとに分類され、ここで提示されたセグメント化されたスキャン アルゴリズムの適応を考え出すことができます。
しかし、この特別なケースでは、ポイントごとに非常に大量のデータ (9-10 フロート、必要に応じて 2 倍になることもあります) を取得したため、スレッドごとの共有メモリ要素とポイントごとのスレッドを使用する標準アルゴリズムでは問題が発生する可能性があります。マルチプロセッサごとのリソースを共有メモリまたはレジスタと見なします(わかりました、コンピューティング機能1.xでは2.xよりもはるかに多くなりますが、それでも)。
グループの数が非常に少なく一定しているため、より良いアプローチがあるのではないかと考えました。おそらく、そのような標準的な問題のこれらの特定の特性に適した既存のアイデアが既に存在します。または、私の一般的なアプローチはそれほど悪くなく、非常に少数のキーに適した優れた並べ替えアルゴリズムや、共有メモリ/レジスタの使用を最小限に抑えるセグメント化された削減アルゴリズムなど、個々のステップを改善するためのアイデアを得たかもしれません。
私は一般的なアプローチを探しており、外部ライブラリを使用したくありません。FWIW 私は OpenCL を使用していますが、GPU コンピューティングの一般的な概念は主要なフレームワーク間で実際には異ならないため、それほど重要ではありません。