In pipelined parallelism a sequence of stream-processing functions are composed together, each consuming the stream of values constructed by the previous stage and producing new values for the next stage. This kind of parallelism is easily expressed in a non-strict language by function composition. The non-strict semantics ensures that no barrier synchronisation is required between the different stages.
The generic pipeline combinator uses strategies to describe a simple pipeline, where every stage constructs values of the same type, and the same strategy is applied to the result of each stage.
pipeline :: Strategy a -> a -> [a->a] -> a
pipeline s inp [] = inp
pipeline s inp (f:fs) =
pipeline s out fs `sparking` s out
where
out = f inp
list = pipeline rnf [1..4] [map fib, map fac, map (* 2)]
A pipeline process diagram has a node for each stage, and an arc connecting one stage with the next. Typically an arc represents a list or stream of values passing between the stages. Figure gives the process diagram for the example above.
Some of the large applications described in the next section use more elaborate pipelines where different types of values are passed between stages, and stages may use different strategies. For example, the back end in Lolita's top level pipeline is as follows:
back_end inp opts
= r8 `demanding` strat
where
r1 = unpackTrees inp
r2 = unifySameEvents opts r1
r3 = storeCategoriseInformation r2
r4 = unifyBySurfaceString r3
r5 = addTitleTextrefs r4
r6 = traceSemWhole r5
r7 = optQueryResponse opts r6
r8 = mkWholeTextAnalysis r7
strat = (parPair rwhnf (parList rwhnf)) inp `seq`
(parPair rwhnf (parList (parPair rwhnf rwhnf))) r1 `seq`
rnf r2 `par`
rnf r3 `par`
rnf r4 `par`
rnf r5 `par`
rnf r6 `par`
(parTriple rwhnf (parList rwhnf) rwhnf) r7 `seq`
()
A disadvantage of using strategies like this over long pipelines is
that every intermediate structure must be named (r1,...,r8). Because pipelines are so common we
introduce two strategic combinators to express sequential and parallel
function application. Explicit function application is written $,
and f $ x = f x. The new combinators take an additional
strategic parameter that specifies the strategy to be applied to the
argument, and hence textually separate the algorithmic and behavioural
code.
The definition of the new combinators is as follows:
infixl 6 $||, $| ($|), ($||) :: (a -> b) -> Strategy a -> a -> b ($|) f s x = f x `demanding` s x ($||) f s x = f x `sparking` s x
We have also defined similar combinators for strategic function composition, which can be viewed as a basic pipeline combinator. Pipelines can now be expressed more concisely, for example the pipeline above becomes:
back_end inp opts = mkWholeTextAnalysis $| parTriple rwhnf (parList rwhnf) rwhnf $ optQueryResponse opts $|| rnf $ traceSemWhole $|| rnf $ addTitleTextrefs $|| rnf $ unifyBySurfaceString $|| rnf $ storeCategoriseInf $|| rnf $ unifySameEvents opts $| parPair rwhnf (parList (parPair rwhnf rwhnf)) $ unpackTrees $| parPair rwhnf (parList rwhnf) $ inp
|
|
|