edenskel-1.1.0.0: Semi-explicit parallel programming skeleton library

Portabilitynot portable
Stabilitybeta
Maintainereden@mathematik.uni-marburg.de
Safe HaskellSafe-Infered

Control.Parallel.Eden.EdenSkel.TopoSkels

Contents

Description

This Haskell module defines topology skeletons for the parallel functional language Eden. Topology skeletons are skeletons that implement a network of processes interconnected by a characteristic communication topology.

Depends on GHC. Using standard GHC, you will get a threaded simulation of Eden. Use the forked GHC-Eden compiler from http://www.mathematik.uni-marburg.de/~eden for a parallel build.

Eden Group ( http://www.mathematik.uni-marburg.de/~eden )

Synopsis

Skeletons that are primarily characterized by their topology.

Pipeline skeletons

 

pipeSource

Arguments

:: forall a . Trans a 
=> [a -> a]

functions of the pipe

-> a

input

-> a

output

Simple pipe where the parent process creates all pipe processes. The processes communicate their results via the caller process.

pipeRDSource

Arguments

:: forall a . Trans a 
=> [a -> a]

functions of the pipe

-> RD a

remote input

-> RD a

remote output

Process pipe where the processes communicate their Remote Data handles via the caller process but fetch the actual data from their predecessor processes

Ring skeletons

 

ringSimpleSource

Arguments

:: (Trans i, Trans o, Trans r) 
=> (i -> r -> (o, r))

ring process function

-> [i] 
-> [o]

input output mapping

Simple ring skeleton (tutorial version) using remote data for providing direct inter-ring communication without input distribution and output combination

ringSource

Arguments

:: (Trans a, Trans b, Trans r) 
=> (i -> [a])

distribute input

-> ([b] -> o)

combine output

-> (a -> [r] -> (b, [r]))

ring process fct

-> i

ring input

-> o

ring output

The ring establishes a ring topology, the ring process function transforms the initial input of a ring process and the input stream from the ring into the ring output stream and the ring processes final result. The same function is used by every ring process. Use ringFl if you need different functions in the processes. Use ringAt if explicit placement is desired.

ringFlSource

Arguments

:: (Trans a, Trans b, Trans r) 
=> (i -> [a])

distribute input

-> ([b] -> o)

combine output

-> [a -> [r] -> (b, [r])]

ring process fcts

-> i

ring input

-> o

ring output

The ringFl establishes a ring topology, the ring process functions transform the initial input of a ring process and the input stream from the ring into the ring output stream and the ring processes' final result. Every ring process applies an individual function which e.g. allows to route individual offline input into the ring processes. Use ringFlAt if explicit placement is desired.

ringAtSource

Arguments

:: (Trans a, Trans b, Trans r) 
=> Places

where to put workers

-> (i -> [a])

distribute input

-> ([b] -> o)

combine output

-> (a -> [r] -> (b, [r]))

ring process fct

-> i

ring input

-> o

ring output

Skeleton ringAt establishes a ring topology, the ring process function transforms the initial input of a ring process and the input stream from the ring into the ring output stream and the ring processes' final result. The same function is used by every ring process. Use ringFlAt if you need different functions in the processes. This version uses explicit placement.

ringFlAtSource

Arguments

:: (Trans a, Trans b, Trans r) 
=> Places

where to put workers

-> (i -> [a])

distribute input

-> ([b] -> o)

combine output

-> [a -> [r] -> (b, [r])]

ring process fcts

-> i

ring input

-> o

ring output

The ringFlAt establishes a ring topology, the ring process functions transform the initial input of a ring process and the input stream from the ring into the ring output stream and the ring processes' final result. Every ring process applies its individual function which e.g. allows to route individual offline input into the ring processes. This version uses explicit placement.

Torus skeleton

 

torusSource

Arguments

:: (Trans a, Trans b, Trans c, Trans d) 
=> (c -> [a] -> [b] -> (d, [a], [b]))

node function

-> [[c]] 
-> [[d]]

input-output mapping

Parallel torus skeleton (tutorial version) with stream rotation in 2 directions: initial inputs for each torus element are given. The node function is used on each torus element to transform the initial input and a stream of inputs from each direction to a stream of outputs to each direction. Each torus input should have the same size in both dimensions, otherwise the smaller input will determine the size of the torus.

The Hypercube skeleton

 

The All-To-All skeleton

The allToAll skeleton allows distributed data exchange and transformation including data of all processes. Input and output are provided as remote data. A typical application is the distributed transposition of a distributed matrix.

allToAllRDSource

Arguments

:: forall a b i . (Trans a, Trans b, Trans i) 
=> (Int -> a -> [i])

transform before bcast (num procs, input, sync-data out)

-> (a -> [i] -> b)

transform after bcast (input, sync-data in, output)

-> [RD a]

remote input for each process

-> [RD b]

remote output for each process

The allToAllRD skeleton creates as many processes as elements in the input list (np). The processes are all-to-all connected, each process' input is transformed to np intermediate values by the first parameter function, where the i-th value will be sent to process i. The second transformation function combines the initial input and the np received intermediate values to the final output.

parTransposeRDSource

Arguments

:: Trans b 
=> [RD [[b]]]

input list of remote partial matrices

-> [RD [[b]]]

output list of remote partial matrices

Parallel transposition for matrices which are row-wise round robin distributed among the machines, the transposed result matrix is also row-wise round robin distributed.

The All-Reduce skeleton

The All-Reduce skeleton uses a butterfly topology to reduce the data of participating processes P in log(|P|) communication stages. Input and output are provided as remote data.

Notice: The number of processes has to be a power of 2!

allReduceRDSource

Arguments

:: forall a b c . (Trans a, Trans b, Trans c) 
=> (a -> b)

initial transform function

-> (b -> b -> b)

reduce function

-> (a -> b -> c)

final combine function

-> [RD a]

remote input

-> [RD c]

remote output

Performs an all-reduce with the reduce function using a butterfly scheme. The input list should have length 2^i, where i is an arbitrary natural number. If not, the input list will be truncated to the next smaller power of two. The initial transformation is applied in the processes to obtain the values that will be reduced. The final combine function is used to create a processes result from the initial input and the reduced value.