Difference between Par Monad and Eval Monad with deepseq

Question

I have been reading Parallel and Concurrent Progaramming in Haskell by Simon Marlow (Great book btw..) And he states that the Eval Monad only evaluates lazy data structures in parallel, while the Par Monad is created to avoid the reliance on lazy evaluation. But with the Eval Monad you could use deepseq and force to get fully evaluated datastructures, i.e NON-lazy datastructures. So what is the the value proposition of the Par Monad other than the different programming model in relation to the the Eval Monad?

Answer 1

Parallelism in Glasgow Parallel Haskell can be expressed using the par combinator to represent potential parallelism (similar to lazy futures) and seq combinator to specify evaluation order. This turned out as a rather unstructured approach to parallel programming, as it requires the programmer to understand operational properties of the language (partly implementation-dependent) and to insert the combinators inside the algorithmic code. Hence, Evaluation Strategies have been introduced (Algorithm + Strategy = Parallelism, Trinder et al., 1998), to separate computation and communication concerns and provide a composable abstraction (over par and seq) without compromising modularity in a non-strict language. Eval Monad was devised to work around undesirable interaction with the garbage collector that could result either in lost parallelism or in space leaks (details: Seq no More: Better Strategies for Parallel Haskell, Marlow et al., 2010).

Parallelism in the Eval Monad is advisory, that is the run-time system (RTS) is free to discard the created spark (or thunk, a pointer to an unevaluated closure), if it is not beneficial to evaluate it in parallel. This allows for tasks to be subsumed by the parent task hence enabling dynamic and implicit granularity control (explicit application-level techniques such as chunking or thresholding can help the RTS to futher reduce the amount of parallelism and increase granularityr). Thus, parallelism is independent of the number of processors, since the more processors there are the more sparks will be turned in actual tasks (lightweight threads).

Par Monad is designed for coarse-grain parallelism and was influenced by the dataflow model (details: A Monad for Deterministic Parallelism, Marlow et al., 2011). It has been introduced to deal with some perceived shortcomings of using par and seq directly. The authors claim that often lazyness gets in a way and obscures cost estimation (more difficult in the non-strict setting). Among the common pitfalls are: passing an already evaluated value to par, not ensuring that the value evaluated in parallel is required later by the rest of the program, or reasoning incorrectly about strictness (see the paper for concrete examples). Par Monad avoids the lazyness issues and helps productive parallel programming in cases where the use of lazy data structures is not essential for the algorithm.

Par Monad uses fork (or spawn) to explicitly and mandatorily create (child) tasks (explicit granularity control; gives more control to the programmer, but can be considered more low-level and depending on the number of processors), whilst explicitly managing the inter-task communication (representing dependencies) using IVars, whereas in the Eval Monad the sharing is implicit via the graph being reduced (the programmer still needs to express that the value of a parallel computation is required by the rest of the program). In the Eval Monad, there is a need to understand operational properties and judiciously apply forcing functions, which is easy to get wrong (introducing too much strictness can also be an issue). Often the predefined strategies are sufficient and most of the issues can be avoided. An alternative approach could be to define Algorithmic Skeletons on top of the Par Monad.

In summary, using Evaluation Strategies can be considered more high-level and modular as it separates computation from coordination (so that it is possible to understand the algorithm without considering the coordination), whereas Par Monad doesn't require the programmer to reason about laziness (although it is still possible to share lazy computations between threads, which should be avoided as monad scheduler cannot detect a thread blocked on a lazy computation and schedule another thread instead). It appears that Par Monad is more suitable for coarse-grain strict dataflow-like computations, whereas Strategies can be used if lazyness is required and for adding parallelism to a sequential algorithm. Another advantage of Par Monad is that the scheduler is written at the Haskell level, so it is easier to modify (e.g. used by Meta-Par: A Meta-Scheduler for the Par-Monad Composable Scheduling for the Heterogeneous Cloud, A. Foltzer et al., 2012), as Eval Monad relies on the scheduler implemented inside the RTS. Strategies better support speculative parallelism as it can be eliminated by the garbage collector when it is found to be unreferenced, whereas in Par Monad, all speculative parallelism is executed (e.g. comparing to parBuffer strategy, one cannot return a lazy list from runPar with elements evaluated in parallel). Finally, both models can also be combined. The key advantage of both models is determinism so that race conditions and deadlocks are avoided.