multithreading - 功能语言中的并行性

Question

标榜的FP功能之一是程序“默认为并行”，并且自然适合现代多核处理器。确实，减少一棵树在本质上是平行的。但是，我不明白它如何映射到多线程。考虑以下片段(伪代码):

let y = read-and-parse-a-number-from-console
let x = get-integer-from-web-service-call
let r = 5 * x - y * 4
write-r-to-file

转换器如何确定应该在线程上运行哪些 Twig ？在获得 x或 y之后，减少在单独线程上的 5 * x或 y * 4表达式(即使我们从线程池中获取)是愚蠢的，不是吗？那么不同的功能语言如何处理呢？

Answer 1

我们还没到那儿。

纯声明性风格的程序(功能性风格包括在该类别中，其他风格也包括在内)往往更适合并行化，因为所有数据相关性都是显式的。这使程序员很容易手动使用语言提供的原语，以指定应并行执行两个独立的计算，而不管它们是否共享对任何数据的访问。如果一切都是不可变的，并且没有副作用，那么更改完成顺序不会影响结果。

如果纯度是由语言强制执行的(如Haskell，Mercury等，但与Scala，F#等鼓励纯度但未强制执行的语言不同)，则编译器可能会尝试自动并行化程序，但不存在该程序我所知道的语言默认情况下会执行此操作。如果该语言允许未经检查的不纯运算，则编译器通常无法进行必要的分析，以证明自动对程序进行给定尝试是有效的。因此，我不希望任何这样的语言都能非常有效地支持自动并行化。

请注意，您编写的伪程序可能是而非纯声明性代码。 let y = read-and-parse-a-number-from-console和let x = get-integer-from-web-service-call正在通过不正确的外部操作来计算x和y，并且程序中没有任何内容可以固定它们的运行顺序。通常，以两种顺序执行两个不纯操作可能会产生不同的结果，并且在不同线程中运行这两个操作会放弃对它们运行顺序的控制。因此，如果像这样的语言能够自动并行化您的程序，则几乎可以肯定会引入可怕的并发错误，或者拒绝对任何事物进行显着并行化。

但是，功能样式仍然使手动并行化此类程序变得容易。人类的程序员可以告诉您，从控制台和网络中读取的顺序几乎毫无关系。知道没有共享的可变状态可以决定并行运行这两个操作，而无需深入研究它们的实现(您必须在命令式算法中执行这些操作，在这些命令中可能存在可变的共享状态，即使看起来不像是来自接口(interface))。

但是，用于强制执行纯语言的自动并行化编译器的最大麻烦在于，它知道要进行多少并行化。并行运行每个计算可能极大地淹没了产生新线程的所有启动成本(更不用说上下文切换)的任何可能的好处，因为您尝试在少量处理器上运行大量非常短命的线程。编译器需要识别数量较少的相当大的“块”计算，并在顺序运行每个块的子计算的同时并行运行这些块。

但是，只有“令人尴尬的并行”程序才能很好地分解为非常大的完全独立的计算。大多数程序是相互依赖的。因此，除非您只希望能够自动并行化非常容易手动并行化的程序，否则您的自动并行化可能需要能够识别并并行运行部分依赖于彼此的“块”，并等待它们当他们到达确实需要由另一个“块”计算的结果的点时。这引入了线程之间同步的额外开销，因此选择并行运行内容的逻辑需要更好，以便击败仅按顺序运行所有内容的琐碎策略。

Mercury(一种纯逻辑编程语言)的开发人员正在研究解决这些问题的各种方法，从静态分析到使用概要分析数据。如果您有兴趣，他们的research papers提供了更多信息。我认为其他研究正在用其他语言在这一领域开展工作，但是我对其他任何项目都不了解。