0
CUDAベースの環境で使用するヒストグラムの実装を作成しました。 私が理解しにくいのは、アルゴリズムの作業の複雑さです。ヒストグラムの並列実装の作業の複雑さ
シリアル実装の複雑さは線形-O(n)であると言うことができます。ここで、nはすべての入力を少なくとも1回ループしなければならないという事実に基づく入力数です。別のスレッドへ
スプリットグループに測定
パス測定値の各グループ
は各スレッドに
- ローカルヒストグラムを計算する:
実装希望
グローバルヒストグラムに縮小する
各ステップの複雑さを解消してマージする必要がありますか?
ヒストグラムは計算上バインドされているか、IOにバインドされていますか? (通常は後であります)...単一のコアよりも高いIO帯域幅をGPUに得ることができない限り、SIMDを使用するだけで、単一のコアでまともなパフォーマンスを得ることができます。 raw IOで1600 MB /秒のIOをわずかに下回ることは珍しいことではなく、ヒストグラムを追加すると〜900 MB /秒が得られます。データをGPUに戻すことは、通常、GPUのボトルネックであり、この場合は操作が最小限に抑えられるため、GPUを選択するには最適ではない場合があります。 – Holmz