c++ - CUDA Thrust sort_by_key 的内存节省替代方案？

Question

在cuda/thrust: Trying to sort_by_key 2.8GB of data in 6GB of GPU RAM throws bad_alloc ，我读到 sort_by_key 消耗了其中考虑的测试用例的大部分内存。

是否有替代方案可以完全执行 sort_by_key 正在做的事情，即使它稍微慢一点但可以对更大的数据集进行排序？

Answer 1

我搜索了一下，我认为以下是您问题的候选答案。

引用 N. Bell 和 J. Hoberock 的“Thrust:面向 CUDA 的生产力库”，在 GPU Computing Gems Jade Edition 中:

Thrust statically selects a highly-optimized Radix Sort algorithm for sorting primitive types (char, int, float and double) with the standard less and greater comparison operators. For all other types (e.g., user-defined data types) and comparison operators, Thrust uses a general Merge Sort algorithm. Because sorting primitives with Radix Sort is considerably faster than Merge Sort, this static optimization has significant value.

现在，合并排序需要O(N) 内存空间，参见Space requirements of a merge-sort .

此外，Radix Sort 仍然需要O(N) 内存空间，参见Comparison of Bucket Sort and RADIX Sort .

两者中哪一个消耗更多内存未定义，取决于要排序的输入序列以及算法调整参数，请参阅对 Why quicksort is more popular than radix-sort? 的其中一个答案的评论。 .

与此相反，快速排序如果执行就地需要O(logN)内存空间，否则需要O (N)。对于快速排序算法的 CUDA 实现，您可以查看 How Tesla K20 Speeds Quicksort .

对于其他就地排序算法(就地策略值得探索，因为与非就地- place 对应)，看看双调排序，参见Fast in-place sorting with CUDA based on bitonic sort .