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



在维基百科的这篇文章中: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 时,我通常运行和内核一样多的线程,但在论文中他们说 go 专家也这样做了,他们简要提到了创建新线程的开销是 go 专家优化代码的方式之一,但似乎没有详细说明。

我会非常小心地将你从 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/通道性能方面所做的重大改进可能实际上使结果过时了。

    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 框架级别(如果您使用的是框架)或操作系统级别从您的程序中抽象出来。在这种情况下,您的解决方案并不完全负责适应语言平台、问题大小或计算机硬件的变化,您应该能够在不接触解决方案的情况下从底层的优化中受益。

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

最新更新