Сортировка объектов с помощью Thrust CUDA - PullRequest
Новая
       61

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

7 голосов
/ 12 марта 2011

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

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

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

Ответы [ 5 ]

14 голосов
/ 19 марта 2011

Документы для 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()).

6 голосов
/ 18 июня 2012

Даже если вы можете сортировать объекты с помощью специальных определений структуры, используя структуру в качестве функтора, это заставит вас изменить алгоритм сортировки с радикальной сортировки на сортировку слиянием.Скорость 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());
2 голосов
/ 25 марта 2013

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

__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;
}

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

0 голосов
/ 14 марта 2011

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

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

0 голосов
/ 12 марта 2011

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

...