私は別のソートアルゴリズムを探していましたが、実際にソートせずにこのソートの考えを得たときにGPUに移植する方法を考えようとしていました。これは私のカーネルがどのように見えるかです：ソートの迅速なハック：私はこの権利をしていますか？
__global__ void noSort(int *inarr, char *outarr, int size)
{
int idx = threadIdx.x + blockIdx.x * blockDim.x;
if (idx < size)
outarr[inarr[idx]] = 1;
}
は、その後、ホスト側では、私はちょうどoutarr[i] == 1配列のインデックスを印刷しています。今では事実上、上記のように整数リストをソートすることができ、それも実際にソートするアルゴリズムよりも速いかもしれません。
これは正当ですか？
あなたの例は、本質的に、一意のキーを持つ入力（つまり重複しない）のための特殊化されたcounting sortです。コードを適切なカウントソートにするには、outarr[inarr[idx]] = 1をatomicAdd(inarr + idx, 1)に置き換えて、重複するキーを数えます。しかし、原子操作がかなり高価であることを除けば、メソッドの複雑さは入力の最大値に比例するという問題があります。幸いにも、radix sortはこれらの問題の両方を解決します。
基数ソートは、一度に入力のBビットだけを見るカウントソートの一般化と考えることができます。 Bビットの整数は[0,2^B)の範囲の値しか取ることができないので、値の全範囲を調べることはできません。
CUDAで基数ソートを実行する前に、studied extensivelyとextremely fastの実装がすぐに利用可能であることを警告する必要があります。実際には、Thrustライブラリは可能な限り自動的に基数ソートを適用します。
私はあなたがここで何をしているかを見ていますが、それは特別な場合にのみ有用だと思います。たとえば、inarrの要素の値が非常に大きい場合はどうなりますか？これは、それを処理するためには、少なくとも多くの要素を持つことが必要です。重複数はどうですか？
配列内で小さな値を持つ配列を使い始めると、これは興味深いソート方法です。しかし、一般的には、並列マージソートなどのアルゴリズムを使って、すでにうまく処理されているものを実行するために膨大な量のメモリを使用するように思えます。出力配列を読み込むことは、非常にコストのかかる処理（特に、入力配列に大きな値がある場合）です。これは基本的に非常にまばらな配列になります。
いくつかの素晴らしいリソースをご指摘いただきありがとうございます。私は複数のGPUを使ってソートを行うプログラムを書くつもりであるので、ちょっとしたことがあります。複数のGPUを使用して大量の数値をソートする実装はありますか？ NVidiaのサイトのsortingNetworksコードサンプルは、単一のGPUで動作すると思います。それとも、私はそれをこのように置いてみましょう...実用的な世界ではどれほど有用なのでしょうか？ – Sayan
私はマルチGPUソーティングコードを認識していませんが、確かにそれを構築することは可能です。最も簡単なことは、各デバイスで既存の（シングルGPU）ソートを使用して、結果をまとめて、おそらくP2Pコピーを使用してGPU間通信を高速化することです。 – wnbell