我正在移植使用的 C++ 代码std::nth_element
and std::partition
到 OpenCL。
nth_element http://www.cplusplus.com/reference/algorithm/nth_element/ is a 选择算法 http://en.wikipedia.org/wiki/Selection_algorithm它将数组中第 n 个最小的数字放在第 n 个位置,并排列其余元素,使所有小于该数字的元素在数组中位于该数字之前,所有大于该数字的元素位于该数字之后。有效,nth_element
将数组分为 3 个桶:数字本身、所有小于该数字的数字以及所有大于该数字的数字。
按照规范,nth_element
使用递归分区实现:选择一个元素,根据元素是否小于该元素对元素进行分区。然后,选择包含数组第 n 个元素的存储桶并在该存储桶上递归。之间的主要区别nth_element
完整的快速排序是快速排序在两个存储桶上递归,而不仅仅是包含第 n 个元素的存储桶。
partition http://www.cplusplus.com/reference/algorithm/partition/是一个较弱的版本nth_element
它仅将数组分为 2 个桶:条件为 true 的桶和条件为 false 的桶。我链接到的网站给出了实现:
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
and partition
:
分区可以使用原子比较和交换来实现,但我不确定如何覆盖所有可能交换的值对。没有明显的方法可以在多个线程之间划分工作,因为分区需要比较可能彼此相邻或位于数组两端的元素。我也没有找到一种方法来避免线程 B 与已被线程 A 交换的元素进行比较,这是低效的。
nth_element 似乎更难并行化,因为它是递归的:每个分区都依赖于前一个分区部分排序的元素。
据推测,对于这两个功能,有效的并行化策略将需要与典型串行代码完全不同的方法。
高效并行实现nth_element
and partition
已经存在?如果不是,什么是好的并行化策略?