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

Question

是否有人有任何使用TBB有效并行std::分区的技巧？这已经完成了吗？

以下是我的想法：

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

*我希望在一般情况下，与数组的长度相比，或者与将数组划分为连续块时所需的交换相比，该区域将很小。

在我尝试之前有什么想法吗？

Answer 1

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

1. 将阵列一分为二。把你的[开始，结束]变成[开始，中间]，[中间，结束]。
2. 在两个范围上并行运行std:：partition
3. 合并分区结果。这可以通过一个并行_来完成

这将更好地利用缓存。

Answer 2

为什么不并行类似于std:：partition\u copy的东西呢？原因是:

• 对于std:：partition，由于结果的递归合并，Adam解决方案中的就地交换需要对数复杂性
• 在使用线程和任务时，您将为并行性支付内存
• 如果对象很重，则交换（共享）指针更为合理
• 如果结果可以并发存储，那么线程可以独立工作

对于（对于随机访问迭代器）应用parallel\u或对于每个（对于非随机访问迭代器）应用tbb:：parallel\u来开始处理输入范围非常简单。每个任务都可以独立存储“真”和“假”结果。有很多方法可以存储结果，有些是从我的头顶上存储的：

• 使用tbb:：parallel\u reduce（仅适用于随机访问迭代器），将结果本地存储到任务体，并将它们从另一个任务移动到join（）中
• 使用tbb:：concurrent_vector的方法grow_by（）将本地结果复制成一堆，或者在到达时单独推送（）每个结果
• 将线程本地结果缓存在tbb:：combinableTLS容器中，然后将其合并

std:：partition\u copy的确切语义可以通过从上面或下面的临时存储中复制来实现

• （仅用于随机访问输出迭代器）使用原子

Answer 3

我会把它当作并行样本排序的退化情况。示例排序的并行代码可以在这里找到。）设N为项目数。该退化样本排序将需要Θ（N）临时空间，具有Θ（N）功，以及Θ（P lg N）跨度（临界路径）。最后两个值对于分析很重要，因为加速比仅限于工作/跨度。

我假设输入是随机访问序列。这些步骤是：

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

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

如果使用TBB::RoopyOracle将步骤3和5并行化，考虑使用AffythyId分区器来帮助步骤5中的线程从步骤3拾取它们在缓存中留下的内容。

注意，分区仅需要Θ（N）工作，用于Θ（N）存储器加载和存储。内存带宽很容易成为加速的限制资源。