在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
正在做的事情,即使它稍微慢一点但可以对更大的数据集进行排序?
最佳答案
我搜索了一下,我认为以下是您问题的候选答案。
引用 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
anddouble
) with the standardless
andgreater
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 .
关于c++ - CUDA Thrust sort_by_key 的内存节省替代方案?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24493810/