GPUの文字列の配列をソートするためのアルゴリズムはありますか？

Question

並べ替えには、すべての文字列が最大100万文字の長さを持つことができる約100万文字の文字列があります。

GPUのソートアルゴリズムの実装を探しています。

サイズが約1MBのデータブロックを持っていて、サフィックス配列を構築する必要があります。これで、本当に少量のメモリ内に100万文字列を持つことが可能なのかを見ることができます。

Answer 1

GPU選別における最先端技術は特に励まされていない。

32ビット整数をソートするための2009年からの次の論文（NVIDIAの研究者である2人の作者と）は、4 CORヨークフィールドで最高のCPUソートと比較して、最高のCUDA SORTのBEST CUDA SORTの23％の増加を主張しています。

http://www.mgarland.org/files/papers/gpusort. -ipdps09.pdf

これはGPU上の基数ソートを使用し、CPU上のソートをマージしました。サフィックス配列を構築するために比較ベースのソートを必要とするため、GPU Radixの代わりに紙の中の最も善意の最良のものがGPUマージソートになります。これは、GPU Radix Sortの速度の約半分に達成されました（100万ありキー） - すなわちCPUマージソートより約40％遅くなります。

可変長キーを追加すると、WARP内のスレッドがGPUで同期しなくなる可能性が高いように思われるので、CPUよりもGPUのパフォーマンスを低下させます。

全体的にあなたの目的が効率的なシステムを構築することであるならば、あなたがこの問題のためにCPU実装を使用することをお勧めします。

しかし、あなたの目的が実験やGPUについて学ぶことがあるならば、あなたはCUDA SDKの紙からマージソートのCUDA実装を見つけることができます：

http：//developer.download.nvidia .com / compute / cuda / sdk / website / data-parallel_algorithms.html