Сортировка объектов с помощью Thrust CUDA

Question

Можно ли сортировать объекты с помощью библиотеки Thrust? У меня есть следующая структура:

struct OB{
  int N;
  Cls *C; //CLS is another struct.
}

Можно ли использовать тягу для сортировки массива OB по N? Можете ли вы привести простой пример использования Thrust для сортировки объектов? Если Thrust не в состоянии сделать это, есть ли другие библиотеки CUDA, которые позволяют мне сделать это?

Answer 1

Документы для thrust::sort показывают, что он принимает оператор сравнения. Посмотрите в их примере, как они определены и используются. Я не проверял это, но на основе примера все, что вам нужно, это структура, которая выглядит примерно так:

struct OBCmp {
  __host__ __device__
  bool operator()(const OB& o1, const OB& o2) {
      return o1.N < o2.N;
  }
};

а затем просто вызвать thrust::sort(obs.begin(), obs.end(), OBCmp()),

Answer 2

Даже если вы можете сортировать объекты с помощью специальных определений структуры, используя структуру в качестве функтора, это приведет к изменению алгоритма сортировки с радикальной сортировки на сортировку слиянием. Скорость radix-sort заметно выше, чем merge-sort. Поэтому при использовании thrust старайтесь использовать целочисленные типы как ключевые значения, насколько это возможно.

Я могу предложить вам использовать функцию "thrust::sory_by_key(..)".

Вы должны изменить свою структуру с AOS на структуру SOA.

struct OB{
  int N;
  Cls *C; //CLS is another struct.
}

в

struct OBs{
   int []Ns; -> thrust::device_vector<int> indices;
   Cls *C[]; -> thrust::device_vector<Cls> values;
}

Когда вы сортируете индексы с помощью sort_by_key, значения уже будут отсортированы.

thrust::sort_by_key(indices.begin(), indices.end(), values.begin());

Answer 3

Вы можете сортировать объекты, перегрузив оператор<. Например:

__host__ __device__ struct Color{
  double blue, green, red;
  double distance;
  void dist()
  {
    distance = sqrt(blue*blue + green*green + red*red);
  }
};

__host__ __device__ bool operator<(const Color &lhs, const Color &rhs) 
{
   return lhs.distance < rhs.distance;
}

int main(void)
{
   thrust::device_vector<Color> cd;
   thrust::host_vector<Color> ch;
   for (int i = 0; i<6; i++)
   {
      Color c;
      c.blue = rand()*255;
      c.green = rand()*255;
      c.red = rand()*255;
      c.dist();
      ch.push_back(c);
   }
   cd = ch;
   thrust::sort(cd.begin(), cd.end());
   ch = cd;
   return 0;
}

объекты будут отсортированы после расстояния.

Answer 4

До сих пор вы не можете сортировать пользовательские объекты. Вы можете выполнять сортировку на основе ключей, но не пользовательских объектов, таких как упомянутая вами структура. Есть несколько других открытых алгоритмов на основе CUDA, доступных для этого, но это также требует некоторой модификации и т.д., чтобы они работали для вас.

Answer 5

Я еще не пробовал Thrust, но в CUDPP есть аналогичная функция сортировки, которая называется cudppSort. Вы не можете напрямую сортировать структуры, используя cudppSort, он может обрабатывать только целые числа или числа с плавающей точкой.

Итак, один из способов сортировки массива структур - это сортировка ключей (вашей структуры) и индексного массива значений вместе с ним. Позже, используйте отсортированный индексный массив, чтобы переместить структуры в их окончательно отсортированные местоположения. Я описал, как сделать это для алгоритма уплотнения cudppCompact в блоге здесь. Техника должна быть похожа на cudppSort тоже.