首页 文章

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

提问于
浏览
5

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

这是我在想的:

  • 如果数组很小,std :: partition it(serial)并返回

  • else,使用自定义迭代器将数组视为2个交错数组(在缓存大小的块中交错)

  • 为每对迭代器启动并行分区任务(递归到第1步)

  • 两个分区/中间指针之间的交换元素*

  • 返回合并的分区/中间指针

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

我尝试之前的任何想法?

4 回答

  • 3

    我将它视为并行样本排序的退化情况 . (可以找到样本排序的并行代码here . )设N是项目数 . 简并样本排序将需要Θ(N)临时空间,具有Θ(N)工作和Θ(P lg N) Span (关键路径) . 最后两个值对于分析很重要,因为加速仅限于工作/ Span .

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

    • 分配一个足够大的临时数组来保存输入序列的副本 .

    • 将输入分为K个块 . K是调整参数 . 对于具有P硬件线程的系统,K = max(4 * P,L)可能是好的,其中L是用于避免可笑小块的常量 . "4*P"允许一些负载 balancer .

    • 将每个块移动到临时数组中的相应位置,并使用std :: partition对其进行分区 . 块可以并行处理 . 记住每个块的"middle"的偏移量 . 您可能需要考虑编写一个自定义例程,它同时移动(在C 11意义上)并对块进行分区 .

    • 计算块的每个部分应该在最终结果中的偏移量 . 每个块的第一部分的偏移可以使用来自步骤3的中间偏移的exclusive prefix sum来完成 . 每个块的第二部分的偏移可以通过使用每个中间相对于末端的偏移来类似地计算 . 它的块 . 后一种情况下的运行总和成为最终输出序列末尾的偏移量 . 除非您处理超过100个硬件线程,否则我建议使用串行独占扫描 .

    • 将每个块的两个部分从临时阵列移回原始序列中的适当位置 . 复制每个块可以并行完成 .

    有一种方法可以将步骤4的扫描嵌入到步骤3和5中,这样可以将 Span 减小到Θ(lg N),但我怀疑它是否值得额外的复杂性 .

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

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

  • 0

    为什么不与std::partition_copy类似的东西并行?原因是:

    • for std::partition ,就像Adam的解决方案中的就地交换需要由于结果的递归合并而具有对数复杂性 .

    • 在使用线程和任务时,无论如何都会为并行性支付内存 .

    • 如果对象很重,那么交换(共享)指针更合理

    • 如果结果可以同时存储,那么线程可以独立工作 .

    应用 parallel_for (用于随机访问迭代器)或tbb::parallel_for_each(用于非随机访问迭代器)开始处理输入范围非常简单 . 每个任务都可以独立存储'true'和'false'结果 . 有很多方法可以存储结果,有些方法来自我的头脑:

    • 使用tbb::parallel_reduce(仅用于随机访问迭代器),将结果本地存储到任务主体,并在 join() 中从另一个任务移动附加它们

    • 使用tbb::concurrent_vector的方法 grow_by() 复制本地结果,或者在到达时单独复制每个结果 push() .

    • 缓存线程局部导致tbb::combinable TLS容器并在以后合并它们

    std::partition_copy 的确切语义可以通过从上面的临时存储器复制来实现

    • (仅用于随机访问输出迭代器)使用 atomic<size_t> 游标同步存储结果的位置(假设有足够的空间)
  • 2

    你的方法应该是正确的,但为什么不遵循常规的分而治之(或parallel_for)方法?对于两个线程:

    • 将数组拆分为两个 . 将[开始,结束]转换为[开始,中间],[中间,结束] .

    • 并行地在两个范围上运行std :: partition .

    • 合并分区结果 . 这可以使用parallel_for完成 .

    这应该更好地利用缓存 .

  • 0

    在我看来,在我尝试之前,这应该很好地并行化,任何想法?

    嗯......可能是几个:

    • 那里只是不必要的努力 .

    • 请记住,拆分和合并数组会降低处理能力,因此请以某种方式设置拆分大小,这实际上不会减慢计算速度 . 拆分10个元素阵列可能很诱人,但不会让你到达你想要的位置 . 由于 std::partition 的复杂性是线性的,因此很容易高估任务的速度 .

    既然你问过并给出了一个算法,我希望你真的需要在这里进行并行化 . 如果是这样 - 没有什么可补充的,算法本身看起来很好:)

相关问题