

Main 



Algorithmic SkeletonsThe task of parallel programming is further simplified by a library of predefined skeletons. Skeletons are higherorder 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 skeletonsThis 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)) tasksFunction 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 sublist 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 noPe1) 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 sublist. Therefore we name the functions unshuffle / shuffle (defined in the Auxiliary module of the skeleton library). Example: Process PipeThe 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 fsIf 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 conquerA 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 nontrivial 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  
Eden  Parallel Functional Programming. EMail This page: http://www.mathematik.unimarburg.de/~eden 
Last change: 14/06/12  