ソートを使用するアルゴリズムを実装しました。10^7要素の配列をソートするのに約0.4秒かかるThrust::sort_by_keyを試しました。
バイトニックソートネットワークはThrust::sort_by_keyよりも高速である必要があると思いました。ただし、バイトニックソートでは、上記と同じ配列をソートするのに約2.5秒かかりました。SDKが提供するバイトニックソートネットワークを使用しました。元のバイトニックソートを少し変更しました。
理由を教えてください。または私にいくつかのアドバイスを与えますか？
ありがとう、
Yik
2011年8月15日
簡単に言えば、CUDA SDK によって提供されるバイトニック ソートの例は、主に教育的なものであるということです。Merrillが提供する非常に効率的な基数ソートに基づく Thrust のソート実装ほど最適化されていません。
2 つのアルゴリズムの漸近的なパフォーマンスも異なります。バイトニック ソート ネットワークにはO(n lg^2 n)複雑性がありますが、Thrust で採用されている基数ソートにはO(#bits n)複雑性に似たものがあります。ここで#bits、入力データを表すのに必要なビット数を示します。つまり、基数ソートでは、ビットニック ソートよりもグローバル メモリの読み取りと書き込みが漸近的に少なくて済みます。
ワークロードが小さい場合は、ビットニック ソートのパフォーマンスが向上することがあります。