Chapter 3. Evaluation Strategies
Evaluation Strategies, or simply Strategies, are a means for modularizing parallel code by separating the algorithm from the parallelism. Sometimes they require you to rewrite your algorithm, but once you do so, you will be able to parallelize it in different ways just by substituting a new Strategy.
Concretely, a Strategy is a function in the Eval monad that takes a
value of type a and returns the same value:
typeStrategya=a->Evala
The idea is that a Strategy takes a data structure as input, traverses
the structure creating parallelism with rpar and rseq, and then
returns the original value.
Here’s a simple example: Let’s create a Strategy for pairs that
evaluates the two components of the pair in parallel. We want a
function parPair with the following type:
parPair::Strategy(a,b)
From the definition of the Strategy type previously shown, we know that this
type is the same as (a,b) -> Eval (a,b). So parPair is a function
that takes a pair, does some computation in the Eval monad, and
returns the pair again. Here is its definition:
strat.hs
parPair::Strategy(a,b)parPair(a,b)=doa'<-rparab'<-rparbreturn(a',b')
This is similar to the rpar/rpar pattern that we saw in
The Eval Monad, rpar, and rseq. The difference is that we’ve packaged it up
as a Strategy: It takes a data structure (in this case a pair),
creates some parallelism using rpar, and then returns the same data structure.
We’ll see this in action in a moment, but first we ...