c++ - 如何使用 TBB 并行化 std::partition

Question

有没有人有任何使用 TBB 有效并行化 std::partition 的技巧？这已经完成了吗？

这是我的想法:

1. 如果数组很小，std::partition it (serial) and return
2. 否则，使用自定义迭代器将数组视为 2 个交错数组(在缓存大小的 block 中交错)
3. 为每对迭代器启动一个并行分区任务(递归到步骤 1)
4. 在两个分区/中间指针之间交换元素*
5. 返回合并后的分区/中间指针

*我希望在一般情况下，与数组的长度相比，或者与将数组分成连续 block 时所需的交换相比，这个区域会很小。

尝试之前有什么想法吗？

Answer 1

我会将其视为平行样本排序的退化情况。 (可以找到样本排序的并行代码 here 。)令 N 为项目数。退化样本排序将需要 Θ(N) 个临时空间，具有 Θ(N) 个工作量和 Θ(P+ lg N) 个跨度(关键路径)。最后两个值对于分析很重要，因为加速仅限于工作/跨度。

我假设输入是一个随机访问序列。步骤是:

1. 分配一个足够大的临时数组来保存输入序列的拷贝。
2. 将输入分成 K 个 block 。 K 是调整参数。对于具有 P 个硬件线程的系统，K=max(4*P,L) 可能很好，其中 L 是一个常数，用于避免可笑的小块。 “4*P”允许一些负载平衡。
3. 将每个 block 移动到临时数组中的相应位置并使用 std::partition 对其进行分区。 block 可以并行处理。记住每个 block 的“中间”的偏移量。您可能需要考虑编写一个既可以移动(在 C++11 意义上)又可以对 block 进行分区的自定义例程。
4. 计算 block 的每个部分在最终结果中应到达的位置的偏移量。每个 block 的第一部分的偏移量可以使用 exclusive prefix sum 来完成。在第 3 步的中间部分的偏移量上。每个 block 的第二部分的偏移量可以通过使用每个中间部分相对于其 block 的 end 的偏移量来类似地计算。后一种情况下的运行和成为最终输出序列末尾的偏移量。除非您要处理超过 100 个硬件线程，否则我建议使用串行独占扫描。
5. 将每个 block 的两个部分从临时数组中移回原始序列中的适当位置。复制每个 block 可以并行完成。

有一种方法可以将第 4 步的扫描嵌入到第 3 步和第 5 步中，这样跨度就可以减小到 Θ(lg N)，但我怀疑是否值得增加额外的复杂性。

如果使用 tbb::parallel_for 循环并行化第 3 步和第 5 步，请考虑使用 affinity_partitioner 来帮助第 5 步中的线程获取它们在第 3 步中留在缓存中的内容。

请注意，对于 Θ(N) 内存加载和存储，分区只需要 Θ(N) 工作。内存带宽很容易成为加速的限制资源。