Parse Monad与Eval Monad之间的差异与deepseq

Question

我一直在阅读Simon Marlow在Haskell中的并行和并发Progaramming(很棒的书btw ..)并且他声明Eval Monad只是并行评估惰性数据结构,而Par Monad是为避免依赖懒惰评估而创建的.但是使用Eval Monad,您可以使用deepseq并force获得完全评估的数据结构,即非惰性数据结构.那么除了与Eval Monad相关的不同编程模型之外,Par Monad的价值主张是什么？

Answer 1

格拉斯哥并行Haskell中的并行性可以使用par组合子来表示潜在的并行性(类似于懒惰期货)和seq组合子来指定评估顺序.这被证明是一种非结构化的并行编程方法,因为它需要程序员理解语言的操作属性(部分依赖于实现)并将组合器插入算法代码中.因此,引入了评估策略(Algorithm + Strategy = Parallelism,Trinder等,1998),以分离计算和通信问题,并提供可组合的抽象(超过par和seq),而不会损害非严格语言的模块性.Eval Monad被设计用于解决与垃圾收集器的不良交互,这可能导致丢失的并行性或空间泄漏(详情:Seq no More:Better Strategies for Parallel Haskell,Marlow et al.,2010).

Eval Monad中的并行性是建议性的,即运行时系统(RTS)可以自由地丢弃所创建的spark(或thunk,指向未评估的闭包的指针),如果并行评估它是不利的.这允许父任务包含任务,因此启用动态和隐式粒度控制(诸如分块或阈值化的显式应用级技术可以帮助RTS进一步减少并行度并增加粒度).因此,并行性与处理器的数量无关,因为处理器越多,实际任务(轻量级线程)中的火花就越多.

Par Monad专为粗粒度并行而设计,受数据流模型的影响(详见:确定性并行的Monad,Marlow等,2011).它被引入来处理一些使用par和seq直接使用的缺点.作者声称,懒惰往往会妨碍成本估算(在非严格的设置中更难).常见的缺陷包括:将已经评估的值传递给par,而不是确保程序的其余部分稍后需要并行评估的值,或者不严格地推断严格性(参见具体示例的文章).Par Monad避免了懒惰问题,并在使用惰性数据结构对算法不重要的情况下帮助进行高效的并行编程.

Par Monad使用fork(或spawn)明确地和强制地创建(子)任务(显式粒度控制 ;给程序员提供更多控制,但可以被认为是更低级别并且取决于处理器的数量),同时明确地管理inter-任务通信(表示依赖关系)使用IVars,而在Eval Monad中,共享是通过减少的图形隐含的(程序员仍然需要表示程序的其余部分需要并行计算的值).在Eval Monad中,需要理解操作属性并明智地应用强制函数,这很容易出错(引入太多严格也可能是一个问题).通常,预定义的策略是充分的,并且可以避免大多数问题.另一种方法可以是在Par Monad之上定义算法骨架.

总之,使用评估策略可以被认为是更高级和模块化的,因为它将计算与协调分开(因此可以在不考虑协调的情况下理解算法),而Par Monad不要求程序员推理懒惰(尽管仍然可以在线程之间共享延迟计算,应该避免这种情况,因为monad调度程序无法检测到在惰性计算上阻塞的线程,而是安排另一个线程).似乎Par Monad更适合粗粒度严格的数据流类计算,而如果需要延迟并且可以在顺序算法中添加并行性,则可以使用策略.Par Monad的另一个优点是调度程序是在Haskell级别编写的,因此更容易修改(例如,Meta-Par使用:Meta-Scheduler用于异构云的Par-Monad可组合调度,A.Foltzer et因为Eval Monad依赖于RTS内部实施的调度程序.策略更好地支持推测并行性,因为当它被发现是未引用时可以被垃圾收集器消除,而在Par Monad中,所有推测并行性都被执行(例如,与parBuffer策略比较,不能从runPar并行评估的元素返回惰性列表)).最后,两种模型也可以组合在一起.两种模型的关键优势在于确定性,从而避免了竞争条件和死锁.