4

私はCUDAを評価しており、現在Thrustライブラリを使用して数値をソートしています。

スラスト::ソート用の独自の比較子を作成したいのですが、劇的に遅くなります! Functional.hからコードをコピーするだけで、独自の少ない実装を作成しました。ただし、他の方法でコンパイルされているようで、動作が非常に遅いです。

  1. デフォルトの比較子: Thrust::less() - 94ミリ秒
  2. 私自身の比較子: less() - 906ミリ秒

Visual Studio 2010 を使用しています。オプション 1 と同じパフォーマンスを得るにはどうすればよいですか?

完全なコード:

#include <stdio.h>

#include <cuda.h>

#include <thrust/host_vector.h>
#include <thrust/device_vector.h>
#include <thrust/generate.h>
#include <thrust/sort.h>

int myRand()
{
        static int counter = 0;
        if ( counter++ % 10000 == 0 )
                srand(time(NULL)+counter);
        return (rand()<<16) | rand();
}

template<typename T>
struct less : public thrust::binary_function<T,T,bool>
{
  __host__ __device__ bool operator()(const T &lhs, const T &rhs) const {
     return lhs < rhs;
  }
}; 

int main()
{
    thrust::host_vector<int> h_vec(10 * 1000 * 1000);
    thrust::generate(h_vec.begin(), h_vec.end(), myRand);

    thrust::device_vector<int> d_vec = h_vec;

    int clc = clock();
    thrust::sort(d_vec.begin(), d_vec.end(), less<int>());
    printf("%dms\n", (clock()-clc) * 1000 / CLOCKS_PER_SEC);

    return 0;
}
4

1 に答える 1

6

パフォーマンスの違いを観察している理由は、Thrust が に提供された引数に応じて異なるアルゴリズムでソートを実装しているためthrust::sortです。

ケース 1. の場合、Thrust は基数ソートを使用してソートを線形時間で実装できることを証明できます。これは、並べ替えるデータの型が組み込みの数値型 ( int) であり、比較関数が組み込みのより小さい演算であるためです。Thrust はthrust::less<int>、 と同等の結果を生成することを認識しx < yます。

ケース 2. の場合、Thrust はユーザー提供の について何も認識せず、実際には が と同等less<int>であっても、漸近的な複雑さが異なる比較ソートに基づくより保守的なアルゴリズムを使用する必要があります。less<int>thrust::less<int>

一般に、ユーザー定義の比較演算子は、基数ソートなどのデータのバイナリ表現を操作する、より制限的で高速なソートでは使用できません。これらの場合、Thrust はより一般的ですが、より遅いソートにフォールバックします。

于 2012-01-27T22:13:07.217 に答える