1

Thrust を使用して配列をソートしようとしていますが、配列が大きすぎると機能しません。（私はGTX460 1GBメモリを持っています）

私はVS2012でc ++統合でcudaを使用しています。これが私のコードです:

私の.cpp

extern "C" void thrust_sort(uint32_t *data, int n);

int main(int argc, char **argv){
    int n = 2<<26;
    uint32_t * v = new uint32_t[n];
    srand(time(NULL));
    for (int i = 0; i < n; ++i) {
        v[i] = rand()%n;
    }

    thrust_sort(v, n);

    delete [] v;
    return 0;
}

私の.cu

extern "C"
void thrust_sort(uint32_t *data, int n){
    thrust::device_vector<uint32_t> d_data(data, data + n);
    thrust::stable_sort(d_data.begin(), d_data.end());
    thrust::copy(d_data.begin(), d_data.end(), data);
}

このプログラムは、stable_sort() の開始時に動作を停止します。

  1. stable_sort() にはあとどれくらいのメモリが必要ですか?
  2. これを修正する方法はありますか? （たとえそれが少し遅くなったとしても）
  3. 元の配列よりも多くのメモリを必要としない別の並べ替えアルゴリズムはありますか?

ご協力いただきありがとうございます ：）

4

1 に答える 1

1

文献にはRAM、ファイルに部分的な値を保存するなど、大きすぎて に収まらないデータの並べ替えの問題に対処するために使用されるいくつかの手法があります。例: Python を使用して 2MB の RAM で 100 万個の 32 ビット整数をソートする

入力は収まりますが、GPU にRAMは大きすぎるため、問題はそれほど複雑ではありません。この問題は、戦略 を使用して解決できますparallel by Regular Sampling。このテクニックを に適用した例をここで見ることができますquicksort。

簡単に言うと、GPU のメモリに収まる小さなサブ配列に配列を分割します。次に、各サブアレイを並べ替え、最後に、通常のサンプリング アプローチの前提に基づいて結果をマージします。

ハイブリッド アプローチを使用して、CPU 内の一部のサブ配列を (マルチスレッドを使用して) 異なるコアに割り当てることで並べ替え、同時に他のサブ配列を GPU に送信できます。などのメッセージ パッシング インターフェイスを使用して、この作業を別のプロセッサに分割することもできますMPI。または、GPU で各サブアレイを 1 つずつソートし、マルチコアを利用して (または利用せずに)、CPU を使用して最終的なマージ ステップを実行することもできます。

于 2013-02-11T16:12:46.543 に答える