Control.Parallel.Eden.Topology

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 )

Skeletons that are primarily characterized by their topology.

Pipeline skeletons

pipe

Arguments

:: 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.

pipeRD

Arguments

:: 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

ringSimple

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

ring

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.

ringFl

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.

ringAt

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.

ringFlAt

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

torus

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 Martrix.

allToAllRDAt

Arguments

:: (Trans a, Trans b, Trans i)

=> Places

where to instantiate

-> (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 skeleton creates as many processes as elements in the input list (np). The processes get 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 send to process i. The second transformation function combines the initial input and the np received intermediate values to the final output.

allToAllRD

Arguments

:: (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 skeleton creates as many processes as elements in the input list (np). The processes get 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 send to process i. The second transformation function combines the initial input and the np received intermediate values to the final output.

parTransposeRDAt

Arguments

:: Trans b

=> Places

-> [RD [[b]]]

input list of remote partial matrizes

-> [RD [[b]]]

output list of remote partial matrizes

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

parTransposeRD

Arguments

:: Trans b

=> [RD [[b]]]

input list of remote partial matrizes

-> [RD [[b]]]

output list of remote partial matrizes

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

allGatherRDAt

Arguments

:: (Trans a, Trans b, Trans c)

=> Places

where to instantiate

-> (a -> b)

initial transform function

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

final combine function

-> [RD a]

-> [RD c]

Performs an all-gather using all to all comunication (based on allToAllRDAt). 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 outputs from the initial input and the gathered values.

allGatherRD

Arguments

:: (Trans a, Trans b, Trans c)

=> (a -> b)

initial transform function

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

final combine function

-> [RD a]

-> [RD c]

Performs an all-gather using all to all comunication (based on allToAllRDAt). 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 outputs from the initial input and the gathered values.

The All-Reduce skeleton

The 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.

allReduceRDAt

Arguments

:: (Trans a, Trans b, Trans c)

=> Places

where to instantiate

-> (a -> b)

initial transform function

-> (b -> b -> b)

reduce function

-> (a -> b -> c)

final combine function

-> [RD a]

-> [RD c]

Performs an all-reduce with the reduce function using a butterfly scheme. 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 output. result from the initial input and the reduced value.

allReduceRD

Arguments

:: (Trans a, Trans b, Trans c)

=> (a -> b)

initial transform function

-> (b -> b -> b)

reduce function

-> (a -> b -> c)

final combine function

-> [RD a]

-> [RD c]

Performs an all-reduce with the reduce function using a butterfly scheme. 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 outputs. result from the initial input and the reduced value.

allGatherBuFlyRDAt

Arguments

:: (Trans a, Trans b, Trans c)

=> Places

where to instantiate

-> (a -> b)

initial transform function

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

final combine function

-> [RD a]

-> [RD c]

Performs an all-gather using a butterfly scheme (based on allReduceRDAt). 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 outputs from the initial input and the gathered values.

allGatherBuFlyRD

Arguments

:: (Trans a, Trans b, Trans c)

=> (a -> b)

initial transform function

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

final combine function

-> [RD a]

-> [RD c]

Performs an all-gather using a butterfly scheme (based on allReduceRDAt). 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 outputs from the initial input and the gathered values.