高速CUDA推力カスタム比較演算子

Question

私はCUDAを評価中で、現在推力ライブラリを使用して数値をソートしています。

私はthrust :: sortのために自分のcomparerを作成したいと思いますが、それは劇的に減速します！ functional.hからコードをコピーするだけで、の実装が少なくなりました。 しかし、それは他の方法でコンパイルされているようで、非常にゆっくりと動作します。

1. 既定の比較：推力::以下（） - ミリ秒
2. 私自身の比較演算：以下（） - ミリ秒

は、私は、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; 
} 

Answer 1

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

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

、推力は、ユーザーが提供するless<int>について何も知らないし、真実のあなたのless<int>がthrust::less<int>と同等であっても、異なる漸近的複雑性を有する比較ソートに基づいて、より保守的なアルゴリズムを使用する必要があります。

一般に、ユーザー定義比較演算子は、基数ソートなどのデータのバイナリ表現を操作する、より制限的で高速なソートでは使用できません。このような場合、スラストはより一般的だがゆっくりと後退します。