使用Thrust CUDA进行对象排序

Question

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

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

是否可以使用Thrust根据N对OB数组进行排序？您能提供一个使用Thrust对对象进行排序的简单示例吗？如果Thrust无法实现此功能，是否有其他CUDA库可以实现？

- liz

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())。

- Davor Cubranic

---

这应该被视为一个答案，我测试过它并且有效。感谢您的帖子！ - Glove

Answer 2

尽管您可以使用特殊的结构定义对对象进行排序，但是将结构用作函数对象会使thrust将排序算法从基数排序更改为归并排序。 基数排序的速度明显快于归并排序。 因此，在使用thrust时，请尽可能使用整数类型作为键值。

我建议您使用“thrust :: sort_by_key（..）”函数。

您应该将结构从AOS结构更改为SOA结构。

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

to

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());

- phoad

---

只是想知道，我怎么知道Thrust正在使用哪个排序算法？ - BRabbit27

据我所知，如果使用整数值，则使用基数排序。如果使用用户定义的比较方法，则使用归并排序。如果使用浮点数，则可能再次使用归并排序。我记得我曾将我的浮点值转换（存储）为整数值，以获得更好的排序性能。 - phoad

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

这些对象将根据距离进行排序。

- yuy

Answer 4

到目前为止，您无法对自定义对象进行排序。您可以进行基于键的排序，但不能对自定义对象（如您提到的结构体）进行排序。还有一些其他基于CUDA的开放算法可用于执行此操作，但这也需要进行一些修改等才能使它们适用于您。

- Salman Ul Haq

---

那个不正确。所有基本的推力排序算法都有一个仿函数模拟STL严格弱序二元谓词的版本。如果您提供一个像这个模型一样在给定用户对象上操作的仿函数，排序将正常工作。 - talonmies

Answer 5

我还没有尝试过Thrust，但是在CUDPP中有一个类似的排序函数叫做cudppSort。你不能直接使用cudppSort对结构体进行排序，它只能处理整数或浮点数。

因此，对结构体数组进行排序的一种方法是同时对键（即结构体的关键字）和值的索引数组进行排序。然后，使用排序后的索引数组将结构体移动到它们最终排序的位置。我在博客文章here中描述了如何在cudppCompact压缩算法中执行此操作。这种技术对于cudppSort也应该是类似的。

- Ashwin Nanjappa