我正在将使用 std::nth_element
和 std::partition
的 C++ 代码移植到 OpenCL。
nth_element
是 selection algorithm它将数组中第 n 个最小的数字放在第 n 个位置,并排列剩余元素,以便所有小于该数字的元素在数组中位于它之前,所有大于它的元素都在它之后。实际上,nth_element
将数组排序为 3 个桶:数字本身、所有小于它的数字以及所有大于它的数字。
规范地,nth_element
是使用递归分区实现的:选择一个元素,根据元素是否小于该元素对元素进行分区。然后,选择包含数组的第 n 个元素的桶并在该桶上递归。 nth_element
和完整快速排序之间的主要区别是快速排序在两个桶上递归,而不仅仅是包含第 n 个元素的桶。
partition
是 nth_element
的较弱版本,它只将数组排序为 2 个桶:条件为真的那些和条件为假的那些。我链接到的站点提供了实现:
while (first!=last) {
while (pred(*first)) {
++first;
if (first==last) return first;
}
do {
--last;
if (first==last) return first;
} while (!pred(*last));
swap (*first,*last);
++first;
}
return first;
其中 pred 是一个函数,用于评估一个元素是否应该在第一个桶中。基本上,这个函数迭代地找到数组中位于错误位置的最外层元素对,并交换它们,当这对元素是相同元素时停止。
以下是我对并行化 nth_element
和 partition
的初步想法:
分区可以使用原子比较和交换来实现,但我不确定如何涵盖所有可能的可以交换的值对。没有明显的方法可以在多个线程之间划分工作,因为分区需要比较可能彼此相邻或位于数组两端的元素。我也没有看到一种方法来避免让线程 B 与已经被线程 A 交换的元素进行比较,这是低效的。
nth_element 似乎更难并行化,因为它是递归的:每个分区都取决于前一个分区已部分排序的元素。
据推测,对于这两个函数,高效的并行化策略将需要与典型串行代码完全不同的方法。
nth_element
和partition
的高效并行实现是否已经存在?如果不是,什么是好的并行化策略?
最佳答案
Cuda THRUST 实现了分区功能(http://docs.nvidia.com/cuda/thrust/index.html#reordering)。
主要思想应该如下: 使用前缀和计算元素在数组中的位置,然后重新排列数组。
关于c++ - 并行化 std::nth_element 和 std::partition,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18515772/