быстрый настраиваемый оператор сравнения CUDA

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

Я хотел бы создать свой собственный компаратор для тяги:: сортировка, но он резко замедляется! Я создал свою собственную реализацию less, просто скопировав код из 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;
}

cuda thrust
person Anton Burtsev    schedule 27.01.2012    source источник
comment
Любопытно, пробовали ли вы функцию сортировки ArrayFire. Может пригодится в вашем анализе.   -  person arrayfire    schedule 28.01.2012

Ответы (1)


arrow_upward
6
arrow_downward

Причина, по которой вы наблюдаете разницу в производительности, заключается в том, что Thrust реализует сортировку с разными алгоритмами в зависимости от аргументов, предоставленных thrust::sort.

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

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

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

person Jared Hoberock    schedule 27.01.2012
comment
Чтобы дать более подробную информацию, Thrust использует сортировку по основанию, если данные являются числовыми и компаратором по умолчанию. В противном случае он использует сортировку слиянием. github.com/NVIDIA/thrust/ блоб/ - person lxkarthi; 18.01.2021