使用 Thrust CUDA 对对象进行排序

Question

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

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

是否可以使用推力根据 N 对 OB 数组进行排序？您能提供一个使用推力对对象进行排序的简单示例吗？如果推力无法做到这一点，是否有其他 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

即使您可以使用特殊的结构定义对对象进行排序，使用结构作为函子，也会促使将排序算法从基数排序更改为合并排序。基数排序的速度明显快于合并排序。所以在使用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<中有类似的排序功能/a> 称为cudppSort。您不能使用 cudppSort 直接对结构进行排序，它只能处理整数或浮点数。

因此，对结构数组进行排序的一种方法是对（结构的）键和值的索引数组进行排序。稍后，使用排序后的索引数组将结构移动到最终排序的位置。我在博客文章 此处。 cudppSort 的技术也应该类似。