1

我正在尝试使用 Thrust 对数组进行排序，但如果数组太大，它将不起作用。（我有一个 GTX460 1GB 内存）

我在 VS2012 上使用带有 c++ 集成的 cuda，这是我的代码：

我的.cpp

extern "C" void thrust_sort(uint32_t *data, int n);

int main(int argc, char **argv){
    int n = 2<<26;
    uint32_t * v = new uint32_t[n];
    srand(time(NULL));
    for (int i = 0; i < n; ++i) {
        v[i] = rand()%n;
    }

    thrust_sort(v, n);

    delete [] v;
    return 0;
}

我的.cu

extern "C"
void thrust_sort(uint32_t *data, int n){
    thrust::device_vector<uint32_t> d_data(data, data + n);
    thrust::stable_sort(d_data.begin(), d_data.end());
    thrust::copy(d_data.begin(), d_data.end(), data);
}

程序在 stable_sort() 开始时停止工作。

  1. stable_sort() 需要多少内存？
  2. 有没有办法解决这个问题 ？（即使它让它变慢了一点或其他）
  3. 是否有另一种排序算法不需要比原始数组更多的内存？

谢谢你的帮助 ：）

4

1 回答 1

1

文献中有一些技术用于处理数据太大而无法放入的排序问题RAM，例如将部分值保存在文件中等。示例：使用 Python 对 2MB RAM 中的一百万个 32 位整数进行排序

您的问题不那么复杂，因为您的输入适合RAM但对于您的 GPU来说太多了。你可以通过使用策略来解决这个问题parallel by Regular Sampling。您可以在此处看到此技术应用于quicksort.

长话短说，您将数组划分为适合 GPU 内存的较小子数组。然后对每个子数组进行排序，最后在常规采样方法的前提下合并结果。

You can use a hybrid approach, sorting some of the sub-arrays in the CPU by assigning each one to a different core (using multi-threading), and at the same time, sending others sub-arrays to the GPU. You can even subdivide this work also to different processors using a message passing interface such as MPI. Or you can simply sort each sub-array one-by-one on the GPU and do the final merge step using the CPU, taking (or not) advantage of the multi-cores.

于 2013-02-11T16:12:46.543 回答