Bitonic Sorting NetworkとThrust :: sort_by_key

Question

ソートを使ったアルゴリズムを実装しました。私はThrust :: sort_by_keyを試してみたところ、10^7要素の配列をソートするのに0.4秒かかりました。

私は、ビートソートネットワークがThrust :: sort_by_keyよりも速くなければならないと考えました。しかし、上記の同じアレイをソートするには、ビートソートに約2.5秒かかりました。 SDKで提供されているビートソートソートネットワークを使用しました。私はちょうど元のビットニックソートを少し変更しました。

なぜ教えてください。または私にいくつかのアドバイスを与える？

おかげで、

YIK

8月、15、2011

Answer 1

短い答えは、CUDA SDKが提供するバイトニックソートの例は、主に教育的であることを意味するということです。 Merrillによって提供される非常に効率的な基数ソートに基づくThrustのソート実装ほど最適化されていません。

2つのアルゴリズムのasymptotic performanceも異なっています。ビートソートソートネットワークはO(n lg^2 n)の複雑さを持ち、スラストによって採用された基数ソートはO(#bits n)のような複雑さを持ちます。ここで、#bitsは入力データを表すために必要なビット数を示します。言い換えると、基数ソートでは、ビートソートよりもグローバルメモリの読み書きが漸近的に少なくて済むことになります。

小さなワークロードでは、ビートソートの方が優れている場合があります。