Prev Up
Go backward to Producer/Consumer Parallelism
Go up to Evaluation Strategies for Parallel Paradigms

Pipelines

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

Process Diagram
Pipeline Process Diagram


{trinder,hwloidl,simonpj}@dcs.gla.ac.uk, kh@dcs.st-and.ac.uk

Prev Up