быстрый CUDA упорный пользовательский оператор сравнения

Question

Я оцениваю CUDA и в настоящее время использую библиотеку Thrust для сортировки чисел.

Я хотел бы создать свой собственный компаратор для тяги :: сортировать, но он резко замедляется! Я создал (а) свой собственный less Выполнение простого копирования кода с functional.h. Однако он, похоже, скомпилирован каким-то другим способом и работает очень медленно.

1. компаратор по умолчанию: тяговые :: меньше() - мс
2. моя Comparer: меньше() - мс

Я использую 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 реализует сортировку с различными алгоритмами в зависимости от аргументов, предоставленных thrust::sort.

В случае 1. Thrust может доказать, что сортировка может быть реализована в линейном времени с помощью сортировки по основанию. Это связано с тем, что тип сортировки данных является встроенным числовым типом (int), а функция сравнения является встроенной меньше, чем операция. Thrust распознает, что thrust::less<int> произведет эквивалентный результат как x < y.

В случае 2. пусти ничего не знает о вашем предоставленном пользователе less<int>, и приходится использовать более консервативный алгоритм, основанный на сравнении рода, который имеет другую асимптотическую сложность, даже если на самом деле ваш less<int> эквивалентно thrust::less<int>.

В общем случае пользовательские операторы сравнения не могут использоваться с более строгими, более быстрыми сортировками, которые управляют двоичным представлением данных, таких как сортировка по методу radix. В этих случаях Thrust возвращается к более общей, но более медленной сортировке.