divide and conquer & fork and join的区别

Question

在C++中，divide and conquer & fork and join有什么区别？ fork 和 join 是否是分而治之的特定情况，因为 fork 和 join 仅适用于并行性？谢谢！

Answer 1

"Divide and conquer" 是一种通用的编程方法，用于将较大的问题分解为更易解决的子问题，分别求解（有时递归），最后通过组合子问题的答案产生大问题的答案-问题。这是一个不特定于 C++ 的想法。

"Fork" 和 "Join" 命名在多种语言中可用的特定并行原语。 "Fork" 导致启动另一个执行线程； "join" 导致当前线程等待另一个线程完成并同步。我相信 C++14 标准内置了这样的原语。许多其他语言没有这个内置的，但它通常可以通过库（包括早期版本的 C++）获得。

人们可能会使用 "Fork" 和 "Join" 来实现 "Divide and conquer" 增强的并行性。像这样使用，"fork" 将线程发送到单独的子问题，并且 "join" 是必要的，作为表示子问题完成的步骤。但是 "join" 并没有专门计算 "big" 问题的综合答案。您可能需要更多的代码，而不仅仅是 fork 和 join。

Answer 2

基本上，Fork-Join 将手头的任务分解为小任务，直到小任务足够简单，无需进一步分解即可解决。这就像一个分而治之的算法。此框架中需要注意的一个重要概念是，理想情况下没有工作线程处于空闲状态。他们实施了一种工作窃取算法，让空闲的工作人员从忙碌的工作人员那里窃取工作。

  Result solve(Problem problem) 
  {
        if (problem is small)
            directly solve problem
        else 
             {
            split problem into independent parts
            fork new subtasks to solve each part
            join all subtasks
            compose result from subresults
          }
  }

C++14 有一些与 fork & join 相关的问题，您可以从这个站点阅读更多内容 (http://www.meetingcpp.com/index.php/br/items/a-look-at-c14-papers-part-2.html)

divide and conquer & fork and join的区别

difference of divide and conquer & fork and join

c++

parallel-processing

language-agnostic

divide-and-conquer

fork-join