CUDA推力和sort_by_key

Question

我正在尋找一種CUDA上的排序算法，它可以對元素（double）的數組A進行排序並返回該數組A的鍵B的陣列。 我知道Thrust庫中的sort_by_key函數但我希望我的元素A數組保持不變。 我能做什麼？

我的代碼是：

void sortCUDA(double V[], int P[], int N) { 

     real_t *Vcpy = (double*) malloc(N*sizeof(double)); 
     memcpy(Vcpy,V,N*sizeof(double)); 

     thrust::sort_by_key(V, V + N, P); 
     free(Vcpy); 
} 

我正在比較推力算法對別人說我有序貫CPU

N    mergesort  sortCUDA 
113    0.000008  0.000010 
226    0.000018  0.000016 
452    0.000036  0.000020 
905    0.000061  0.000034 
1810   0.000135  0.000071 
3621   0.000297  0.000156 
7242   0.000917  0.000338 
14484   0.001421  0.000853 
28968   0.003069  0.001931 
57937   0.006666  0.003939 
115874   0.014435  0.008025 
231749   0.031059  0.016718 
463499   0.067407  0.039848 
926999   0.148170  0.118003 
1853998   0.329005  0.260837 
3707996   0.731768  0.544357 
7415992   1.638445  1.073755 
14831984  3.668039  2.150179 
115035495  39.276560  19.812200 
230070990  87.750377  39.762915 
460141980  200.940501  74.605219 

推力性能也不錯，但我想如果我使用OMP可能會輕鬆獲得更好的CPU時間

我認爲這是因爲對memcpy

SOLUTION：

void thrustSort(double V[], int P[], int N) 
{ 
     thrust::device_vector<int> d_P(N); 
     thrust::device_vector<double> d_V(V, V + N); 
     thrust::sequence(d_P.begin(), d_P.end()); 

     thrust::sort_by_key(d_V.begin(), d_V.end(), d_P.begin()); 

     thrust::copy(d_P.begin(),d_P.end(),P); 
} 

其中V是我的雙值進行排序

Answer 1

多大這個數組？就速度而言，最有效的方法可能是在排序之前複製原始數組，如果內存可用。

Answer 2

您可以修改比較運算符來排序鍵而不是值。 @Robert Crovella正確指出，不能從主機分配原始設備指針。修改後的算法如下：

struct cmp : public binary_function<int,int,bool> 
{ 
    cmp(const double *ptr) : rawA(ptr) { } 

    __host__ __device__ bool operator()(const int i, const int j) const 
    {return rawA[i] > rawA[j];} 

    const double *rawA; // an array in global mem 
}; 

void sortkeys(double *A, int n) { 
    // move data to the gpu 
    thrust::device_vector<double> devA(A, A + n); 
    double *rawA = thrust::raw_pointer_cast(devA.data()); 

    thrust::device_vector<int> B(n); 
    // initialize keys 
    thrust::sequence(B.begin(), B.end()); 
    thrust::sort(B.begin(), B.end(), cmp(rawA)); 
    // B now contains the sorted keys 
} 

這裏是arrayfire的替代方案。雖然我不知道哪一個是更有效，因爲arrayfire解決方案使用了兩個額外的陣列：

void sortkeys(double *A, int n) { 
    af::array devA(n, A, af::afHost); 
    af::array vals, indices; 
    // sort and populate vals/indices arrays 
    af::sort(vals, indices, devA); 
    std::cout << devA << "\n" << indices << "\n"; 
} 

Answer 3

大廈由@asm提供的答案（我是不是能夠得到它的工作），該代碼似乎工作對我而言，並且只對鑰匙進行排序。但是，我相信它僅限於鍵對應於（雙）值的順序爲0,1,2,3,4 ...的情況。由於這是一種「索引值」排序，因此可以將其擴展到任意鍵序列的情況下，可能通過執行索引副本。然而，我不確定生成索引序列然後重新排列原始鍵的過程將比將原始值數據複製到新的向量（對於任意鍵的情況）更快。

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

using namespace std; 

__device__ double *rawA; // an array in global mem 

struct cmp : public binary_function<int, int, bool> 
{ 
    __host__ __device__ bool operator()(const int i, const int j) const 
    {return (rawA[i] < rawA[j]);} 
}; 

void sortkeys(double *A, int n) { 
    // move data to the gpu 
    thrust::device_vector<double> devA(A, A + n); 
// rawA = thrust::raw_pointer_cast(&(devA[0])); 
    double *test = raw_pointer_cast(devA.data()); 
    cudaMemcpyToSymbol(rawA, &test, sizeof(double *)); 

    thrust::device_vector<int> B(n); 
    // initialize keys 
    thrust::sequence(B.begin(), B.end()); 
    thrust::sort(B.begin(), B.end(), cmp()); 
    // B now contains the sorted keys 
    thrust::host_vector<int> hostB = B; 
    for (int i=0; i<hostB.size(); i++) 
    std::cout << hostB[i] << " "; 
    std::cout<<std::endl; 
    for (int i=0; i<hostB.size(); i++) 
    std::cout << A[hostB[i]] << " "; 
    std::cout<<std::endl; 
} 


int main(){ 

    double C[] = {0.7, 0.3, 0.4, 0.2, 0.6, 1.2, -0.5, 0.5, 0.0, 10.0}; 
    sortkeys(C, 9); 
    std::cout << std::endl; 
    return 0; 
}