| Safe Haskell | None |
|---|---|
| Language | GHC2024 |
Tile.Collective
Contents
Description
This module lifts each collective operation into a value of type
Collective m a b, where m is the member type, a is the
element type, and b is the result type.
Input and output shapes
+-------------+----------------------+--------------------+
| Operation | Input | Output (b) |
+=============+======================+====================+
| Broadcast | one value (a) | Map m a |
| Scatter | Map m a | Map m a |
| Gather | Map m a | [(m, a)] |
| Reduce | Map m a, a->a->a | a |
| AllReduce | Map m a, a->a->a | Map m a |
+-------------+----------------------+--------------------+
Orientation duality
Broadcast and Reduce use opposite orientations of the same
routing tree. Scatter and Gather do the same for
destination-indexed payloads.
Compositional law
AllReduce decomposes as Reduce followed by Broadcast:
interpret s r (AllReduce vals f) == interpret s r (Broadcast (interpret s r (Reduce vals f)))
This identity is stated as a machine-checked property (T15).
Synopsis
- data Collective m a b where
- Broadcast :: forall a m. a -> Collective m a (Map m a)
- Scatter :: forall m a. Map m a -> Collective m a (Map m a)
- Gather :: forall m a. Map m a -> Collective m a [(m, a)]
- Reduce :: forall m a. Map m a -> (a -> a -> a) -> Collective m a a
- AllReduce :: forall m a. Map m a -> (a -> a -> a) -> Collective m a (Map m a)
- interpret :: Ord m => Schedule m -> m -> Collective m a b -> b
- runCollective :: Ord m => Schedule m -> m -> Collective m a b -> IO b
Collective type
data Collective m a b where Source #
A collective operation over members of type m, element type
a, and result type b.
Constructors embed all inputs except the schedule and root member,
which are supplied by interpret and runCollective.
Constructors
| Broadcast :: forall a m. a -> Collective m a (Map m a) | Deliver one value to every reachable member. |
| Scatter :: forall m a. Map m a -> Collective m a (Map m a) | Deliver a per-member payload from the root. The map is destination-indexed; duplicate destinations cannot be represented, which matches scatter's semantics. |
| Gather :: forall m a. Map m a -> Collective m a [(m, a)] | Collect every member's value at the root as a list, in preorder over the routing tree. |
| Reduce :: forall m a. Map m a -> (a -> a -> a) -> Collective m a a | Combine all member values into one at the root. The combine function is applied in tree order, left-to-right. |
| AllReduce :: forall m a. Map m a -> (a -> a -> a) -> Collective m a (Map m a) | Combine all member values and deliver the result to every member. Precondition: the value map must contain every member reachable from the root. |
Interpreters
interpret :: Ord m => Schedule m -> m -> Collective m a b -> b Source #
Interpret a collective purely, delegating to Execution.
Precondition: the schedule is rooted at root.
runCollective :: Ord m => Schedule m -> m -> Collective m a b -> IO b Source #
Run a collective concurrently, delegating to
Concurrent.
Presents a uniform (schedule, root, collective) argument order,
hiding the positional inconsistencies in the underlying run*
functions.
Precondition: the schedule is rooted at root.