分布式工作同步和 fork-join 并行编程方法有什么区别

Question

在维基百科的这篇文章中：https ://en.wikipedia.org/wiki/Go_(programming_language)#Suitability_for_parallel_programming据称 Go 专家使用分布式工作同步模式来组织他的并行程序，而非专家使用叉连接：https : //upload.wikimedia.org/wikipedia/commons/thumb/f/ f1/Fork_join.svg/2000px-Fork_join.svg.png我在学校就熟悉 fork-join，但我想知道分布式工作同步模式是什么，它与我熟悉的经典 fork-join 模型有什么区别？当我执行 fork join 时，我通常会运行与运行内核一样多的线程，但在论文中他们说 go 专家也这样做了，并且他们简要地提到了创建新线程的开销是 go 专家优化的方式之一代码，但似乎没有详细说明。

Answer 1

我会非常小心地将您从https://en.wikipedia.org/wiki/Go_(programming_language)#Suitability_for_parallel_programming引述为 Go 编程的一般真理。

我假设研究中描述的分布式工作同步是将问题划分为子任务的方法，这主要取决于可以在硬件中实现的并行化，而不是由问题分解成更小的任务的自然方式决定.

根据您的具体问题和专业知识，这种方法可能会给您带来一些性能优势，但即使应用于令人尴尬的并行问题也可能并非易事。此外，这种方法更依赖于您使用的特定硬件（例如 2-32 与 64-1024 核、常规 CAS 与 LL/SC）、特定问题的大小（例如适合 L1 与几乎适合 RAM )，最重要的是，关于您使用该方法和用于解决问题的工具的专业知识。

以上是标准的“过早优化是万恶之源”/“简单、充分和正确胜过复杂、超快和潜在错误”的建议，但论文中引用的实际实验也给出了一些例子，为什么你应该这样做使用您自己的判断来使用哪种方法。

1. 该研究使用了 Go 1.0.3。在调度、垃圾收集和 goroutine/channel 性能方面所做的重大改进可能已经有效地使结果过时了。

   1.1. 具有讽刺意味的是，该论文提到了对于 Chapel 解决方案之一，当使用 Chapel 1.6（而不是 1.5）时，专家版的速度慢了约 68%。

2. 该研究并未声称提供了具有统计意义的结果——对于 4 个平台中的每一个，一个非专家解决了 6 个符合特定蓝图的综合问题，然后根据一个专家的建议重写了他的解决方案。

3. 专家不应对在特定背景之外应用他的建议负责。如果您是 Golang 团队 (Luuk van Dijk) 的高级软件工程师，并且您的替代方案是在 Go 1.0.3 中使用简单的分而治之，那么分布式工作同步是解决这些特定问题的更好方法。

当我执行 fork join 时，我通常会运行与运行内核一样多的线程，但在论文中他们说 go 专家也这样做了，并且他们简要地提到了创建新线程的开销是 go 专家优化的方式之一代码，但似乎没有详细说明。

我假设创建新线程的开销与接近递归树底部时任务的扩散有关。

我认为属于主定理案例 2 和 3 的算法将受到特别影响，但即使属于案例 1 的算法（在树的叶级别上完成的工作最重要，即生成的线程被稀释最多）将受到影响。例如，在自上而下的归并排序中为每对元素的比较创建一个新的逻辑任务可能是多余的。

恕我直言，运行的线程数与内核数一样多，但在逻辑上自然地/在每个递归级别上划分工作是我对分布式工作同步和简单分而治之的理解之间的巨大妥协。

您仍在为在 K 个工作线程上调度 N 个任务的复杂性（可能，但不一定，在运行时间方面）付出一些代价。这个价格可能会让你在运行时错过并行化机会，例如因为缓存颠簸，因为次优调度，因为线程或核心亲和性等。但是这可能会从你的程序中抽象出来在语言平台级别，或在 Fork-Join 框架级别（如果您正在使用框架），或者在操作系统级别。在这种情况下，您的解决方案并不完全负责适应语言平台、问题规模或机器硬件的变化，您应该能够从底层的优化中受益，而无需触及您的解决方案。

我敢打赌，只有当你能证明你的自然分而治之解决方案是不够的并且你知道后果时，定制的分布式工作同步解决方案增加的复杂性和降低的可移植性是值得的。