私はGPUでかなり標準的な問題を解決する必要がありましたが、私は実際のGPGPUには全く新しいので、この問題にアプローチするアイデアを探しています。分散されたセグメントでセグメント化された縮小
非常に少数のグループ（各ポイントは1つのグループに属しています）に割り当てられた3つのスペースに多くのポイントがあります。具体的にはこの場合15です（これは変更されません）。今私はすべてのグループの平均と共分散行列を計算したいと思います。グループの数が極端に少ないため、最後のステップは、（私はとにかく、CPUにそれらの値を必要とする）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にそれは大体同じです。最初のステップは、実際にはセグメント化された削減ですが、セグメントが散在しています。
私が思いついた最初のアイデアは、最初にグループでポイントを並べ替えることでした。私はバケットサイズとポイント単位の再配置インデックスを計算するためにatomic_incを使用して単純なバケットソートについて考えました（ソートのために良いアイデアがありますが、アトミックがベストアイデアではないかもしれません）。その後、彼らはグループ別にソートされています。私は、hereというセグメント化されたスキャンアルゴリズムを採用する可能性があります。
しかし、この特殊なケースでは、必要な場合には非常に大量のデータが得られます（9-10浮動小数点、おそらく倍になることもあります）。したがって、スレッドごとに共有メモリ要素を使用する標準アルゴリズムと、マルチプロセッサごとのリソースを共有メモリまたはレジスタとして問題にする可能性があります（Ok、計算能力1.xでは2.xよりはるかに多いですが、それでもなお）。
非常に小さく、一定の数のグループのために、私はよりよいアプローチがあると思った。おそらく、このような標準的な問題のこれらの特定の特性に適した既存のアイデアがあるかもしれません。または、私の一般的なアプローチはそれほど悪くはなく、非常に少数のキーに適した適切なソートアルゴリズムや共有メモリ/レジスタの使用を最小限に抑えるセグメント化された削減アルゴリズムなど、個々のステップを改善するためのアイデアがあります。
私は一般的なアプローチを探していて、外部ライブラリを使用したくありません。 FWIW私はOpenCLを使用していますが、GPUコンピューティングの一般的な概念が主要なフレームワークと実際に異なるわけではないので、それは本当に重要ではありません。
これはかなり一般的なパターンです。推力を使って、各セグメントのデータを一緒に持ってきて 'reduce_by_key'して各グループの平均と共分散を計算します。 –