Sorting a structure of arrays using Thrust

Question

I am working on CUDA and facing the following problem. I have a following structure of arrays:

typedef struct Edge{
    int *from, *to, *weight;
}

I want to sort this structure on weight array such that the corresponding "from" and "to" arrays get updated too. I thought of using Thrust library but it works only on vectors is what I understood. I can sort_by_key and get two arrays sorted but I am not able to understand how to sort three arrays? I even looked at zip_iterator but did not understand how to use it to serve my purpose. Please help

Answer 1

First decouple the structure into 1) keys, and 2) paddings. Then sort the keys and reorder paddings accordingly. For example, break this structure:

typedef struct Edge{
    int from, to, weight;
}

into:

int weight[N];
typedef struct Edge{
    int from, to;
}

The full code is here:

#include <thrust/device_vector.h>
#include <thrust/host_vector.h>
#include <cmath>
#include <thrust/sort.h>

typedef struct pad {
        int from;
        int to;
} padd;

__host__ padd randPad() {
        padd p;
        p.from = rand();
        p.to = rand();
        return p;
}

__host__ std::ostream& operator<< (std::ostream& os, const padd& p) {
        os << "(" << p.to << " , " << p.from << " )";
        return os;
}

int main(void)
{
  // allocation
  #define N 4
  thrust::host_vector<int> h_keys(4);
  thrust::host_vector<padd> h_pad(4);

  // initilization
  thrust::generate(h_keys.begin(), h_keys.end(), rand);
  thrust::generate(h_pad.begin(), h_pad.end(), randPad);

  // print unsorted data
  std::cout<<"Unsorted keys\n";
  thrust::copy(h_keys.begin(), h_keys.end(), std::ostream_iterator<int>(std::cout, "\n"));
  std::cout<<"\nUnsorted paddings\n";
  thrust::copy(h_pad.begin(), h_pad.end(), std::ostream_iterator<padd>(std::cout, "\n"));

  // transfer to device
  thrust::device_vector<int> d_keys = h_keys;
  thrust::device_vector<padd> d_pad = h_pad;
  //thrust::sort(d_keys.begin(), d_keys.end());

  // sort
  thrust::sort_by_key(d_keys.begin(), d_keys.end(), d_pad.begin());

  // transfer back to host
  thrust::copy(d_keys.begin(), d_keys.end(), h_keys.begin());
  thrust::copy(d_pad.begin(), d_pad.end(), h_pad.begin());

  // print the results
  std::cout<<"\nSorted keys\n";
  thrust::copy(h_keys.begin(), h_keys.end(), std::ostream_iterator<int>(std::cout, "\n"));
  std::cout<<"\nSorted paddings\n";
  thrust::copy(h_pad.begin(), h_pad.end(), std::ostream_iterator<padd>(std::cout, "\n"));

  return 0;
}

The output would be something like this:

Unsorted keys
1804289383
846930886
1681692777
1714636915

Unsorted paddings
(424238335 , 1957747793 )
(1649760492 , 719885386 )
(1189641421 , 596516649 )
(1350490027 , 1025202362 )

Sorted keys
846930886
1681692777
1714636915
1804289383

Sorted paddings
(1649760492 , 719885386 )
(1189641421 , 596516649 )
(1350490027 , 1025202362 )
(424238335 , 1957747793 )