如何使用TBB并行化std :: partition

Question

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

这是我在想的:

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

*我希望在平均情况下,与阵列的长度相比,该区域将是小的,或者与在连续块中分区阵列所需的交换相比较.

我尝试之前的任何想法？

Answer 1

您的方法应该是正确的，但为什么不遵循常规的分而治之（或parallel_for）方法呢？对于两个线程：

1. 将数组分成两部分。将 [start, end) 变成 [start, middle), [middle, end)。
2. 在两个范围上并行运行 std::partition。
3. 合并分区结果。这可以通过parallel_for 来完成。

这应该可以更好地利用缓存。