Algorithmic Skeletons

The task of parallel programming is further simplified by a library of predefined skeletons. Skeletons are higher-order functions defining parallel interaction patterns which are shared in many parallel applications. The programmer can simply use such known schemes to achieve an instant parallelisation of a program.

The skeleton library is available on hackage, see also our installation instructions.

Example: Parallel map skeletons

This is one of the most common process schemes. It calculates the map function using one parallel process for each list element. It is easily defined using Eden's library function spawn:

parMap :: (Trans a, Trans b) => 
                (a -> b)   -- ^worker function
                -> [a]     -- ^task list
                -> [b]     -- ^result list
parMap f tasks = spawn (repeat (process f)) tasks

Function spawn eagerly instantiates a list of process abstractions with a list of corresponding inputs. The parMap functionality is similar but uses the same process abstraction for every process.
The parMap skeleton parallelises with on process for each list element, independent of task granularity or the number of machines available. It is often better to use a process farm:

farm :: (Trans a, Trans b) => 
        ([a] -> [[a]])    -- ^input distribution function 
        -> ([[b]] -> [b]) -- ^result combination function
        -> (a ->  b)      -- ^mapped function
        -> [a]            -- ^input 
        -> [b]            -- ^output
farm np distr combine f tasks = combine $ parMap (map f) (distr xs)

The farm takes the number of processes (np) to be instantiated, a function to define how to distribute the list elements for the processes (distr), inverse to the distribution a combine function for the result lists of the worker processes which reestablishes the original list order. A worker function, which processes the sublists created by the distribution function as a whole. Each process instantiation can be applied directly to a sub-list of the task distribution, which is done using the parMap skeleton.

The skeletons signature of map and parMap are the same, but the signature of the farm skeleton differs a lot. We need the complex signature to expose some parameters for the parallelization, but we want to have a simple map interface for all parallel map skeletons as well. We predefined such a simple version for each parallel map skeleton, named with the prefix map_:

map_par    = parMap 
map_farm f = farm (max 1 noPe-1) unshuffle shuffle (map f)

To define a skeleton with map signature based on the farm we need to select default distribution / combine functions and the number of processes. We choose to distribute tasks round robin. The inverse combine function is a regular shuffle of the sub-list. Therefore we name the functions unshuffle / shuffle (defined in the Auxiliary module of the skeleton library).

Example: Process Pipe

The following example defines a process pipe where the processes communicate their results via the caller process. An optimised version using Remote Data avoids this indirection:

pipe :: forall a . Trans a => [a -> a] -> a -> a
pipe fs xs = last outs where 
  outs = spawn ps (xs : outs) 
  ps :: [Process a a]
  ps = map process fs

If the skeleton is instantiated for data of type [a], then the list of inputs and the intermediate results will be streamed element by element through the process pipe.

Example: Divide and conquer

A simple skeleton for the well known divide and conquer scheme is defined as follows:

divCon_c :: (Trans a, Trans b) => 
       (a -> Bool)        -- ^trivial?
       -> (a -> b)        -- ^solve
       -> (a -> [a])      -- ^split
       -> (a -> [b] -> b) -- ^combine (incl. input)       
       ->  a -> b         -- ^resulting mapping
divCon_c trivial solve split combine x
  | trivial x = solve x
  | otherwise = combine x children
    where children = parMap (divCon_c trivial solve split combine) (split x)

The skeleton is parameterised with the typical control functions for divide and conquer which decide if a (sub-)problem is trivial, how to solve a trivial (sub-)problem, how to split a non-trivial problem and how to combine solutions of (sub-)subproblems to a solution of the (sub-)problem. The recursion tree is mapped to a corresponding process tree by calling parMap in every recursion step.
The drawbacks of this naive version are irregular process placement and a missing parallel depth control.

The complete API of Edens skeleton library is here