2

我正在将使用std::nth_element和的 C++ 代码移植std::partition到 OpenCL。

nth_element是一种选择算法，它将数组中第 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已经存在吗？如果不是，什么是好的并行化策略？

4

1 回答 1

2

Cuda THRUST 实现了分区功能（http://docs.nvidia.com/cuda/thrust/index.html#reordering）。

主要思想应该是：使用前缀和来计算元素在数组中的位置，然后重新排列数组。

于 2013-08-30T13:04:56.897 回答