Par Monad和Eval Monad与deepseq的差异

Question

我一直在读西蒙·马洛( Simon Marlow )的“Haskell中的并行和并发的Progaramming”(顺便说一句)他说Eval Monad只并行地评估延迟的数据结构，而Par Monad是为了避免依赖懒惰的评估而创建的。但是使用evaluated，您可以使用deepseq和force来获得完全评估的数据结构，即非惰性数据结构。那么，除了与Eval Monad相关的不同编程模型之外，Par Monad的价值命题是什么？

Answer 1

格拉斯哥平行Haskell中的并行性可以使用par组合器来表示潜在的并行性(类似于懒惰的未来)，seq组合器可以指定评估顺序。这是一种相当非结构化的并行编程方法，因为它要求程序员理解语言的操作属性(部分取决于实现)，并在算法代码中插入组合器。因此，评估策略被引入(算法+策略=并行性，Trinder等人，1998年)，以分离计算和通信关注点，并提供一个可组合的抽象(超过par和seq)，而不损害非严格语言的模块化。Eval Monad的设计是为了解决与垃圾收集器的不受欢迎的交互，这可能会导致并行性的丢失或空间泄漏(详细信息：Seq不再:并行Haskell的更好策略，Marlow等人，2010年)。

Eval Monad中的并行性是咨询性的，即运行时系统(RTS)可以自由地丢弃所创建的火花(或者是指向未评估的闭包的指针)，如果并行评估对它没有好处的话。这允许将任务包含在父任务中，从而启用动态和隐式粒度控制(显式应用层技术，如分块或阈值，可以帮助RTS进一步减少并行性并增加粒度)。因此，并行性与处理器数量无关，因为处理器越多，实际任务(轻量级线程)中的火花就越多。

Par Monad是为粗粒度并行设计的，并受数据流模型的影响(详细信息：确定性并行的Monad，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-Monad可组合调度的元调度程序，A.Foltzer等人，2012年)，因为Eval Monad依赖于RTS内部实现的调度器。策略更好地支持推测并行，因为当垃圾收集器发现它没有引用时，它可以被消除，而在Par Monad中，所有推测并行性都被执行(例如，与parBuffer策略相比，不能从runPar返回一个具有并行计算元素的惰性列表)。最后，这两种模型也可以结合起来。这两种模型的主要优点是确定性，从而避免了竞争条件和死锁。