並べ替える配列には約 100 万個の文字列があり、各文字列の長さは最大 100 万文字です。
GPU の並べ替えアルゴリズムの実装を探しています。
サイズが約 1MB のデータ ブロックがあり、サフィックス arrayを構築する必要があります。これで、非常に少量のメモリ内に 100 万個の文字列を格納できることがわかりました。
2848 次
1 に答える
4
GPU ソートの最新技術は、特に心強いものではありません。
32 ビット整数のソートについて、2009 年の次の論文 (Nvidia の研究者である 2 人の著者による) では、4 コアの Yorkfield での最高の CPU ソートと比較して、GTX280 での最高の CUDA ソートが 23% 増加しただけであると主張しています。
http://www.mgarland.org/files/papers/gpusort-ipdps09.pdf
これは、GPU で基数ソートを使用し、CPU でマージ ソートを使用しました。接尾辞配列を構築するには、比較ベースのソートが必要になるため、GPU 基数ソートの代わりに、この論文で最も優れているのは GPU マージ ソートであり、これは GPU 基数ソートの約半分の速度を達成しました (100 万キー) - つまり、CPU マージ ソートよりも約 40% 遅くなります。
可変長キーを追加すると、ワープ内のスレッドが GPU で同期しなくなる可能性が高いため、CPU よりも GPU のパフォーマンスが低下します。
全体として、効率的なシステムを構築することが目的である場合は、この問題に対して CPU 実装を使用することをお勧めします。より高速で簡単に記述できるからです。
ただし、GPU について実験することや単に学習することが目的である場合は、CUDA SDK の論文からマージ ソートの CUDA 実装を見つけることができます。
http://developer.download.nvidia.com/compute/cuda/sdk/website/Data-Parallel_Algorithms.html
于 2010-07-17T05:37:21.913 に答える