sorting - 使用 Thrust CUDA 对对象进行排序

Question

是否可以使用 Thrust 库对对象进行排序？我有以下结构：

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

是否可以使用推力来根据 N 对 OB 数组进行排序？您能否提供一个使用推力对对象进行排序的简单示例？如果推力不能这样做，是否有任何其他 CUDA 库允许我这样做？

Answer 1

push ::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

即使您可以使用特殊的结构定义对对象进行排序，使用结构作为函子，它也会推动将排序算法从基数排序更改为合并排序。基数排序的速度明显快于合并排序。所以在使用推力的时候，尽量使用整数类型作为键值。

我可能会建议你使用“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

您可以通过重载 operator< 对对象进行排序。例如：

__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 的技术也应该类似。