haskell - 带有Deepseq的Par Monad和Eval Monad之间的区别

Question

我一直在阅读Simon Marlow撰写的Haskell中的Parallel and Concurrent Progaramming(并行和并发编程)，他指出Eval Monad仅并行评估惰性数据结构，而Par Monad的创建是为了避免依赖于惰性评估。但是使用Eval Monad，您可以使用deepseq和force来获得经过全面评估的数据结构，即NON-lazy数据结构。那么，与Eval Monad不同的编程模型之外，Par Monad的值(value)主张是什么？

Answer 1

可以使用par组合器表示潜在的并行性(类似于惰性 future )，并使用seq组合器指定评估顺序来表示Glasgow Parallel Haskell中的并行性。事实证明，这是并行编程的一种非结构化方法，因为它要求程序员理解语言的操作属性(部分取决于实现)，并将组合器插入算法代码内。因此，引入了评估策略(Algorithm + Strategy = Parallelism，Trinder等，1998)，以分离计算和通信问题，并提供可组合的抽象(在par和seq之上)，而不会损害非严格语言的模块化。 Eval Monad旨在解决与垃圾收集器发生的不良交互，这种交互可能导致并行性丢失或空间泄漏(详细信息:Seq no More: Better Strategies for Parallel Haskell，Marlow等人，2010年)。

Eval Monad中的并行性是建议性的，也就是说，如果出现以下情况，运行时系统(RTS)可以自由丢弃所创建的 Spark (或thunk，指向未评估的闭包的指针)
并行评估它是没有好处的。这允许任务被父任务包含，从而实现动态和隐式粒度控制(显式应用程序级技术，例如组块或阈值化可以帮助RTS进一步减少并行度并增加粒度)。因此，并行性与处理器的数量无关，因为在实际任务(轻量级线程)中，处理器越多， Spark 就越多。

Par Monad是专为粗粒度并行性而设计的，并受数据流模型的影响(详细信息:A Monad for Deterministic Parallelism，Marlow等人，2011年)。引入它是为了解决直接使用par和seq的一些缺点。作者声称，懒惰经常会在某种程度上妨碍成本估算(在非严格条件下更加困难)。常见的陷阱包括:将已经求值的值传递给par，不确保程序的其余部分稍后需要并行求值，或者不正确地推理严格性(具体示例请参见本文)。 Par Monad避免了惰性问题，并在算法不需要使用惰性数据结构的情况下，有助于进行高效的并行编程。

Par Monad使用fork(或spawn)显式并强制创建(子)任务(显式粒度控制；向程序员提供更多控制权，但可以视作更底层的操作，具体取决于处理器数量)，同时显式管理使用IVars进行任务间通信(表示依赖关系)，而在Eval Monad中，共享是通过减少图形来隐含的(程序员仍然需要表达程序其余部分需要并行计算的值)。在Eval Monad中，需要了解操作属性并明智地应用强制功能，这很容易出错(引入过多的严格性也可能是一个问题)。通常，预定义的策略就足够了，并且可以避免大多数问题。另一种方法可能是在Par Monad的顶部定义算法骨架。

总之，使用评估策略可以被认为是更高级和模块化的，因为它可以将计算与协调分开(这样就可以在不考虑协调的情况下理解算法)，而Par Monad则不需要程序员对懒惰进行推理。 (尽管仍然可以在线程之间共享延迟计算，但应避免这种情况，因为monad调度程序无法检测到在延迟计算上阻塞的线程，而是调度另一个线程)。看来，Par Monad更适合用于粗粒度严格的类似于数据流的计算，而如果需要惰性并为顺序算法增加并行性，则可以使用策略。 Par Monad的另一个优点是，调度程序是在Haskell级别编写的，因此更容易修改(例如，由Meta-Par使用:A Meta-Scheduler for the Par-Monad Composable Scheduling for the Heterogeneous Cloud，A. Foltzer等人，2012)，因为Eval Monad依赖于已实现的调度程序在RTS中。策略可以更好地支持推测性并行性，因为它可以通过以下方式消除
垃圾回收器被发现未被引用时，而在Par Monad中，所有推测性并行性都被执行(例如，与parBuffer策略相比，无法从runPar返回带有并行评估元素的惰性列表)。最后，两个模型也可以合并。两种模型的主要优点是确定性，从而避免了竞争情况和僵局。