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?

score 17 · Answer 1 · answered Mar 18 '11 at 21:18

17

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

answered Mar 18 '11 at 21:18

Davor Cubranic

1,051
10
16

1

this should've been taken as an answer, I tested it and it worked. Thanks for the post! – Glove Nov 20 '13 at 14:13

score 6 · Answer 2 · answered Jun 18 '12 at 13:21

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

Just wondering, how can I know which sorting algorithm thrust is using? — BRabbit27, Oct 22 '14 at 10:11
AFAIK, if integer values are used they use Radix-sort. If user defined comparison method is used they use merge-sort. If floating point numbers are used they might be using the merge-sort again. I remember that I have converted (stored) my floating point values to integer values to achieve better sorting performance. — phoad, Oct 23 '14 at 20:48

score 2 · Answer 3 · answered Mar 25 '13 at 16:08

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.

score -1 · Answer 4 · answered Mar 12 '11 at 18:39

-1

Up until now you cannot sort custom objects. You can do key based sorting but not of custom objects like the struct you mentioned. There are a couple of other open CUDA based algorithms available for doing this but that too requires some modification etc to make them work for you.

answered Mar 12 '11 at 18:39

Salman Ul Haq

241
2
6

1

That is not correct. There are versions of all the basic thrust sorting algorithms which take a functor modelled on the STL strict weak ordering binary predicate. If you provide a functor which acts like this model on a given user object, the sort will work correctly. – talonmies Apr 03 '11 at 11:02

score -1 · Answer 5 · answered Mar 14 '11 at 02:57

I have not tried Thrust yet, but there is a similar sort function in CUDPP called cudppSort. You cannot directly sort structures using cudppSort, it can only handle integers or floats.

So, one way to sort array of structures is to sort the keys (of your structure) and an index array of values along with it. Later, use the sorted index array to move the structures to their final sorted locations. I have described how to do this for the cudppCompact compaction algorithm in a blog post here. The technique should be similar for cudppSort too.

Sorting objects with Thrust CUDA

5 Answers5

Linked