Sorting objects with Thrust CUDA

Question

Is it possible to sort objects using the Thrust library? I have the following struct:

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

Is it possible to use thrust in order to sort an array of OB according to N? Can you provide a simple example on using thrust to sort objects? If thrust is not able to do so, is there any other CUDA libraries that allows me to do so?

Answer 1

The docs for thrust::sort show it accepts a comparison operator. See in their example how those are defined and used. I haven't tested this, but based on the example, all you would need is a struct that looks something like this:

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

and then just invoke thrust::sort(obs.begin(), obs.end(), OBCmp()).

Answer 2

Even though you may sort the objects by using special struct definitions, using a struct as functor, it will make thrust to change the sort algorithm from radix-sort to merge-sort. Speed of radix-sort is noticeably faster than merge-sort. So when using thrust, try to use integer types as key values as possible.

I may suggest you using "thrust::sory_by_key(..)" function.

You should change your struct from AOS to SOA structure.

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

When you sort the indices with sort_by_key, the values will already be sorted.

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

Answer 3

you can sort objects by overloading operator< . For example:

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

the objects will be sorted after the distance.