Safe Haskell | None |
---|

- type Strategy a = a -> Par a
- using :: a -> Strategy a -> Par a
- r0 :: Strategy a
- rseq :: Strategy a
- rdeepseq :: NFData a => Strategy a
- forceC :: (NFData a, ToClosure a) => Strategy (Closure a)
- forceCC :: ForceCC a => Closure (Strategy (Closure a))
- class (NFData a, ToClosure a) => ForceCC a where
- locForceCC :: LocT (Strategy (Closure a))

- type StaticForceCC a = Static (Env -> Strategy (Closure a))
- staticForceCC :: ForceCC a => StaticForceCC a
- type ProtoStrategy a = a -> Par (IVar a)
- sparkClosure :: Closure (Strategy (Closure a)) -> ProtoStrategy (Closure a)
- pushClosure :: Closure (Strategy (Closure a)) -> NodeId -> ProtoStrategy (Closure a)
- evalList :: Strategy a -> Strategy [a]
- evalClosureListClosure :: Strategy (Closure a) -> Strategy (Closure [Closure a])
- parClosureList :: Closure (Strategy (Closure a)) -> Strategy [Closure a]
- pushClosureList :: Closure (Strategy (Closure a)) -> [NodeId] -> Strategy [Closure a]
- pushRandClosureList :: Closure (Strategy (Closure a)) -> [NodeId] -> Strategy [Closure a]
- parClosureListClusterBy :: ([Closure a] -> [[Closure a]]) -> ([[Closure a]] -> [Closure a]) -> Closure (Strategy (Closure a)) -> Strategy [Closure a]
- parClosureListChunked :: Int -> Closure (Strategy (Closure a)) -> Strategy [Closure a]
- parClosureListSliced :: Int -> Closure (Strategy (Closure a)) -> Strategy [Closure a]
- parMap :: ToClosure a => Closure (Strategy (Closure b)) -> Closure (a -> b) -> [a] -> Par [b]
- parMapNF :: (ToClosure a, ForceCC b) => Closure (a -> b) -> [a] -> Par [b]
- parMapChunked :: ToClosure a => Int -> Closure (Strategy (Closure b)) -> Closure (a -> b) -> [a] -> Par [b]
- parMapChunkedNF :: (ToClosure a, ForceCC b) => Int -> Closure (a -> b) -> [a] -> Par [b]
- parMapSliced :: ToClosure a => Int -> Closure (Strategy (Closure b)) -> Closure (a -> b) -> [a] -> Par [b]
- parMapSlicedNF :: (ToClosure a, ForceCC b) => Int -> Closure (a -> b) -> [a] -> Par [b]
- parClosureMapM :: Closure (Closure a -> Par (Closure b)) -> [Closure a] -> Par [Closure b]
- parMapM :: ToClosure a => Closure (a -> Par (Closure b)) -> [a] -> Par [b]
- parMapM_ :: ToClosure a => Closure (a -> Par b) -> [a] -> Par ()
- pushMap :: ToClosure a => Closure (Strategy (Closure b)) -> [NodeId] -> Closure (a -> b) -> [a] -> Par [b]
- pushMapNF :: (ToClosure a, ForceCC b) => [NodeId] -> Closure (a -> b) -> [a] -> Par [b]
- pushClosureMapM :: [NodeId] -> Closure (Closure a -> Par (Closure b)) -> [Closure a] -> Par [Closure b]
- pushMapM :: ToClosure a => [NodeId] -> Closure (a -> Par (Closure b)) -> [a] -> Par [b]
- pushMapM_ :: ToClosure a => [NodeId] -> Closure (a -> Par b) -> [a] -> Par ()
- pushRandClosureMapM :: [NodeId] -> Closure (Closure a -> Par (Closure b)) -> [Closure a] -> Par [Closure b]
- pushRandMapM :: ToClosure a => [NodeId] -> Closure (a -> Par (Closure b)) -> [a] -> Par [b]
- pushRandMapM_ :: ToClosure a => [NodeId] -> Closure (a -> Par b) -> [a] -> Par ()
- divideAndConquer :: (a -> Bool) -> (a -> [a]) -> (a -> [b] -> b) -> (a -> b) -> a -> b
- parDivideAndConquer :: Closure (Closure a -> Bool) -> Closure (Closure a -> [Closure a]) -> Closure (Closure a -> [Closure b] -> Closure b) -> Closure (Closure a -> Par (Closure b)) -> Closure a -> Par (Closure b)
- pushDivideAndConquer :: [NodeId] -> Closure (Closure a -> Bool) -> Closure (Closure a -> [Closure a]) -> Closure (Closure a -> [Closure b] -> Closure b) -> Closure (Closure a -> Par (Closure b)) -> Closure a -> Par (Closure b)
- declareStatic :: StaticDecl

# Strategy type

using :: a -> Strategy a -> Par aSource

Strategy application is actual application (in the

monad).
`Par`

# Basic sequential strategies

# Fully forcing Closure strategy

class (NFData a, ToClosure a) => ForceCC a whereSource

Indexing class, recording which types support

; see the
tutorial in module `forceCC`

`Closure`

for a more thorough
explanation.

locForceCC :: LocT (Strategy (Closure a))Source

Only method of class `ForceCC`

, recording the source location
where an instance of `ForceCC`

is declared.

staticForceCC :: ForceCC a => StaticForceCC aSource

# Proto-strategies for generating parallelism

type ProtoStrategy a = a -> Par (IVar a)Source

A

is almost a `ProtoStrategy`

.
More precisely, a `Strategy`

for type `ProtoStrategy`

`a`

is a *delayed* (semantic)
identity function in the

monad, ie. it returns an `Par`

(rather
than a term) of type `IVar`

`a`

.

sparkClosure :: Closure (Strategy (Closure a)) -> ProtoStrategy (Closure a)Source

`sparkClosure clo_strat`

is a

that sparks a `ProtoStrategy`

;
evaluation of the sparked `Closure`

is governed by the strategy
`Closure`

.
`unClosure`

clo_strat

pushClosure :: Closure (Strategy (Closure a)) -> NodeId -> ProtoStrategy (Closure a)Source

`pushClosure clo_strat n`

is a

that pushes a `ProtoStrategy`

to be executed in a new thread on node `Closure`

`n`

;
evaluation of the pushed

is governed by the strategy
`Closure`

.
`unClosure`

clo_strat

# Strategies for lists

evalList :: Strategy a -> Strategy [a]Source

Evaluate each element of a list according to the given strategy.

evalClosureListClosure :: Strategy (Closure a) -> Strategy (Closure [Closure a])Source

Specialisation of

to a list of Closures (wrapped in a
Closure). Useful for building clustering strategies.
`evalList`

parClosureList :: Closure (Strategy (Closure a)) -> Strategy [Closure a]Source

Evaluate each element of a list of Closures in parallel according to the given strategy (wrapped in a Closure). Work is distributed by lazy work stealing.

pushClosureList :: Closure (Strategy (Closure a)) -> [NodeId] -> Strategy [Closure a]Source

Evaluate each element of a list of Closures in parallel according to the given strategy (wrapped in a Closure). Work is pushed round-robin to the given list of nodes.

pushRandClosureList :: Closure (Strategy (Closure a)) -> [NodeId] -> Strategy [Closure a]Source

Evaluate each element of a list of Closures in parallel according to the given strategy (wrapped in a Closure). Work is pushed randomly to the given list of nodes.

## Clustering strategies

parClosureListClusterBy :: ([Closure a] -> [[Closure a]]) -> ([[Closure a]] -> [Closure a]) -> Closure (Strategy (Closure a)) -> Strategy [Closure a]Source

`parClosureListClusterBy cluster uncluster`

is a generic parallel
clustering strategy combinator for lists of Closures, evaluating
clusters generated by `cluster`

in parallel.
Clusters are distributed by lazy work stealing.
The function `uncluster`

must be a *left inverse* of `cluster`

,
that is `uncluster . cluster`

must be the identity.

parClosureListChunked :: Int -> Closure (Strategy (Closure a)) -> Strategy [Closure a]Source

`parClosureListChunked n`

evaluates chunks of size `n`

of a list of
Closures in parallel according to the given strategy (wrapped in a Closure).
Chunks are distributed by lazy work stealing.
For instance, dividing the list `[c1,c2,c3,c4,c5]`

into chunks of size 3
results in the following list of chunks `[[c1,c2,c3], [c4,c5]]`

.

parClosureListSliced :: Int -> Closure (Strategy (Closure a)) -> Strategy [Closure a]Source

`parClosureListSliced n`

evaluates `n`

slices of a list of Closures in
parallel according to the given strategy (wrapped in a Closure).
Slices are distributed by lazy work stealing.
For instance, dividing the list `[c1,c2,c3,c4,c5]`

into 3 slices
results in the following list of slices `[[c1,c4], [c2,c5], [c3]]`

.

# Task farm skeletons

Task farm skeletons are parallel maps, applying a function to a list in parallel. For technical reasons, the function to be applied must wrapped in a Closure (ie. a function Closure).

## Lazy task placement

parMap :: ToClosure a => Closure (Strategy (Closure b)) -> Closure (a -> b) -> [a] -> Par [b]Source

Task farm, evaluates tasks (function Closure applied to an element
of the input list) in parallel and according to the given strategy (wrapped
in a Closure).
Note that `parMap`

should only be used if the terms in the input list are
already in normal form, as they may be forced sequentially otherwise.

parMapNF :: (ToClosure a, ForceCC b) => Closure (a -> b) -> [a] -> Par [b]Source

Specialisation of

to the fully forcing Closure strategy.
That is, `parMap`

`parMapNF`

forces every element of the output list to normalform.

parMapChunked :: ToClosure a => Int -> Closure (Strategy (Closure b)) -> Closure (a -> b) -> [a] -> Par [b]Source

Chunking task farm, divides the input list into chunks of given size
and evaluates tasks (function Closure mapped on a chunk of the input list)
in parallel and according to the given strategy (wrapped in a Closure).
`parMapChunked`

should only be used if the terms in the input list
are already in normal form.

parMapChunkedNF :: (ToClosure a, ForceCC b) => Int -> Closure (a -> b) -> [a] -> Par [b]Source

Specialisation of

to the fully forcing Closure strategy.
`parMapChunked`

parMapSliced :: ToClosure a => Int -> Closure (Strategy (Closure b)) -> Closure (a -> b) -> [a] -> Par [b]Source

Slicing task farm, divides the input list into given number of slices
and evaluates tasks (function Closure mapped on a slice of the input list)
in parallel and according to the given strategy (wrapped in a Closure).
`parMapSliced`

should only be used if the terms in the input list
are already in normal form.

parMapSlicedNF :: (ToClosure a, ForceCC b) => Int -> Closure (a -> b) -> [a] -> Par [b]Source

Specialisation of

to the fully forcing Closure strategy.
`parMapSliced`

parClosureMapM :: Closure (Closure a -> Par (Closure b)) -> [Closure a] -> Par [Closure b]Source

Monadic task farm for Closures, evaluates tasks (

-monadic function
Closure applied to a Closure of the input list) in parallel.
Note the absence of a strategy argument; strategies aren't needed because
they can be baked into the monadic function Closure.
`Par`

parMapM :: ToClosure a => Closure (a -> Par (Closure b)) -> [a] -> Par [b]Source

Monadic task farm, evaluates tasks (

-monadic function Closure
applied to an element of the input list) in parallel.
Note the absence of a strategy argument; strategies aren't needed because
they can be baked into the monadic function Closure.
`Par`

`parMap`

should only be used if the terms in the input list are already
in normal form, as they may be forced sequentially otherwise.

parMapM_ :: ToClosure a => Closure (a -> Par b) -> [a] -> Par ()Source

Specialisation of

, not returning any result.
`parMapM`

## Round-robin task placement

pushMap :: ToClosure a => Closure (Strategy (Closure b)) -> [NodeId] -> Closure (a -> b) -> [a] -> Par [b]Source

Task farm like

but pushes tasks in a round-robin fashion
to the given list of nodes.
`parMap`

pushMapNF :: (ToClosure a, ForceCC b) => [NodeId] -> Closure (a -> b) -> [a] -> Par [b]Source

Task farm like

but pushes tasks in a round-robin fashion
to the given list of nodes.
`parMapNF`

pushClosureMapM :: [NodeId] -> Closure (Closure a -> Par (Closure b)) -> [Closure a] -> Par [Closure b]Source

Monadic task farm for Closures like

but pushes tasks
in a round-robin fashion to the given list of nodes.
`parClosureMapM`

pushMapM :: ToClosure a => [NodeId] -> Closure (a -> Par (Closure b)) -> [a] -> Par [b]Source

Monadic task farm like

but pushes tasks
in a round-robin fashion to the given list of nodes.
`parMapM`

pushMapM_ :: ToClosure a => [NodeId] -> Closure (a -> Par b) -> [a] -> Par ()Source

Monadic task farm like

but pushes tasks
in a round-robin fashion to the given list of nodes.
`parMapM_`

## Random task placement

pushRandClosureMapM :: [NodeId] -> Closure (Closure a -> Par (Closure b)) -> [Closure a] -> Par [Closure b]Source

Monadic task farm for Closures like

but pushes to random nodes on the given list.
`parClosureMapM`

pushRandMapM :: ToClosure a => [NodeId] -> Closure (a -> Par (Closure b)) -> [a] -> Par [b]Source

Monadic task farm like

but pushes to random nodes on the given list.
`parMapM`

pushRandMapM_ :: ToClosure a => [NodeId] -> Closure (a -> Par b) -> [a] -> Par ()Source

Monadic task farm like

but pushes to random nodes on the given list.
`parMapM_`

# Divide and conquer skeletons

divideAndConquer :: (a -> Bool) -> (a -> [a]) -> (a -> [b] -> b) -> (a -> b) -> a -> bSource

Sequential divide-and-conquer skeleton.
`didvideAndConquer trivial decompose combine f x`

repeatedly decomposes
the problem `x`

until trivial, applies `f`

to the trivial sub-problems
and combines the solutions.

parDivideAndConquer :: Closure (Closure a -> Bool) -> Closure (Closure a -> [Closure a]) -> Closure (Closure a -> [Closure b] -> Closure b) -> Closure (Closure a -> Par (Closure b)) -> Closure a -> Par (Closure b)Source

Parallel divide-and-conquer skeleton with lazy work distribution.
`parDivideAndConquer trivial_clo decompose_clo combine_clo f_clo x`

follows
the divide-and-conquer pattern of

except that, for
technical reasons, all arguments are Closures.
`divideAndConquer`

pushDivideAndConquer :: [NodeId] -> Closure (Closure a -> Bool) -> Closure (Closure a -> [Closure a]) -> Closure (Closure a -> [Closure b] -> Closure b) -> Closure (Closure a -> Par (Closure b)) -> Closure a -> Par (Closure b)Source

Parallel divide-and-conquer skeleton with eager random work distribution,
pushing work to the given list of nodes.
`pushDivideAndConquer nodes trivial_clo decompose_clo combine_clo f_clo x`

follows the divide-and-conquer pattern of

except that,
for technical reasons, all arguments are Closures.
`divideAndConquer`