Copyright | (c) Philipps Universitaet Marburg 2009-2014 |
---|---|

License | BSD-style (see the file LICENSE) |

Maintainer | eden@mathematik.uni-marburg.de |

Stability | beta |

Portability | not portable |

Safe Haskell | None |

Language | Haskell98 |

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 )

- pipe :: forall a. Trans a => [a -> a] -> a -> a
- pipeRD :: forall a. Trans a => [a -> a] -> RD a -> RD a
- ringSimple :: (Trans i, Trans o, Trans r) => (i -> r -> (o, r)) -> [i] -> [o]
- ring :: (Trans a, Trans b, Trans r) => (i -> [a]) -> ([b] -> o) -> (a -> r -> (b, r)) -> i -> o
- ringFl :: (Trans a, Trans b, Trans r) => (i -> [a]) -> ([b] -> o) -> [a -> r -> (b, r)] -> i -> o
- ringAt :: (Trans a, Trans b, Trans r) => Places -> (i -> [a]) -> ([b] -> o) -> (a -> r -> (b, r)) -> i -> o
- ringFlAt :: (Trans a, Trans b, Trans r) => Places -> (i -> [a]) -> ([b] -> o) -> [a -> r -> (b, r)] -> i -> o
- torus :: (Trans a, Trans b, Trans c, Trans d) => (c -> [a] -> [b] -> (d, [a], [b])) -> [[c]] -> [[d]]
- allToAllRDAt :: forall a b i. (Trans a, Trans b, Trans i) => Places -> (Int -> a -> [i]) -> (a -> [i] -> b) -> [RD a] -> [RD b]
- allToAllRD :: forall a b i. (Trans a, Trans b, Trans i) => (Int -> a -> [i]) -> (a -> [i] -> b) -> [RD a] -> [RD b]
- parTransposeRDAt :: Trans b => Places -> [RD [[b]]] -> [RD [[b]]]
- parTransposeRD :: Trans b => [RD [[b]]] -> [RD [[b]]]
- allGatherRDAt :: forall a b c. (Trans a, Trans b, Trans c) => Places -> (a -> b) -> (a -> [b] -> c) -> [RD a] -> [RD c]
- allGatherRD :: forall a b c. (Trans a, Trans b, Trans c) => (a -> b) -> (a -> [b] -> c) -> [RD a] -> [RD c]
- allReduceRDAt :: forall a b c. (Trans a, Trans b, Trans c) => Places -> (a -> b) -> (b -> b -> b) -> (a -> b -> c) -> [RD a] -> [RD c]
- allReduceRD :: forall a b c. (Trans a, Trans b, Trans c) => (a -> b) -> (b -> b -> b) -> (a -> b -> c) -> [RD a] -> [RD c]
- allGatherBuFlyRDAt :: forall a b c. (Trans a, Trans b, Trans c) => Places -> (a -> b) -> (a -> [b] -> c) -> [RD a] -> [RD c]
- allGatherBuFlyRD :: forall a b c. (Trans a, Trans b, Trans c) => (a -> b) -> (a -> [b] -> c) -> [RD a] -> [RD c]

# Skeletons that are primarily characterized by their topology.

## Pipeline skeletons

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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