Combining contributions#

When several participants each compute part of an update, something has to put the parts together. In most distributed training stacks that is a collective call (all_reduce) whose operand order belongs to a library. In Alpha it is an ordered combine: a typed numerical expression tree that the compiler checks, the participants execute, and the frames and checkpoints name.

This page covers:

• what a combine tree is and how it runs on a star and on a hierarchy;
• how a result reaches every owner or only one;
• what the numerical contract fixes;
• how Alpha shows that the order which ran is the order that was declared.

A combine is a numerical tree#

Runtime.OrderedCombine defines OrderedCombineTree:

• An OrderedCombineLeaf is one owner's contribution.
• An OrderedCombineBranch combines its left subtree, then its right subtree, at its named owner.

No associativity or commutativity is assumed. In finite precision (a + b) + c and a + (b + c) differ, so the tree, not the network, fixes the result. A placement may change only through an explicit new tree with a new identity.

A leaf may carry a numerator and a weight mass together, for example a sum of gradients and its sample count. Normalization is a separate learning operation, not part of the combine. This is what lets owners hold unequal shares of a batch: the combine adds (Σ gradients, Σ samples) pairs, and the learner divides once, Σ G_i / Σ n_i.

Coverage is declared in one of two ways:

• Ordered members: an explicit list, which also fixes the leaf order.
• A participant group: a compact membership. The tree must then cover every member exactly once.

Compiler.Planning.OrderedCombine derives the reduce and replicate phases from the tree and checks exact coverage. A missing or duplicated leaf is refused even when the byte totals happen to match.

Two realizations of the same idea#

Runtime.NativeCombine realizes the tree on the two topologies from Participants, endpoints and framesDistributed · explanationParticipants, endpoints and framesRoles and compact membership, star and hierarchy topologies, native connection setup, bounded identity-checked frames, and protocols projected to every role.:

The data-parallel learners choose between them with DataParallelTopology (DataParallelStar or DataParallelHierarchy fanout), defined in Runtime.NativeDataParallel. Because the topology fixes the combine tree, and the tree fixes the floating-point order, the topology is part of the numerical contract. A star and a hierarchy over the same owners are two different contracts, and a peer compiled for one refuses frames from the other.

Delivering the result#

After the reduction, the result goes where the plan says. CombineDelivery has two forms:

• CombineReplicateAll sends the reduced value back to every leaf owner. This is replication.
• CombineDeliverTo target moves it from the root down the tree path to one leaf owner. Every other owner's value is left as it was. This is a reduction to one owner, used when one participant owns the coordinates being reduced.

The delivery laws (NativeCombineDeliveryLaws) check the traffic directly:

• On the star, the hub sends one result instead of three.
• On a fan-out-2 tree of seven owners, a forwarder on the path relays the value, and the other subtree receives nothing.

Assembly is a different operation. When each owner holds disjoint coordinates, the full vector is assembled by selection: each word comes from exactly the owner that holds it, and no arithmetic is performed. Overlapping or incomplete assemblies are refused as data-parallel-assembly-overlap and data-parallel-assembly-coverage.

Numerical contracts#

Every combine and every learner names a numerical contract. In Learning.Numerics a NumericalContract is a numeric profile (formats, rounding, subnormals, exceptional values), the ordered list of operations, and a relation. The relation has three kinds:

A tolerance on its own never authorizes execution. numericalCompatibility refuses a peer or a checkpoint whose profile differs (NumericalProfileMismatch) or whose order differs (NumericalOrderMismatch).

Conversions are explicit too. StdNumericConversion in Std.Numeric.Profile is StdNumericKeepFormat, StdNumericWidenBinary32 or StdNumericRoundBinary64: widening preserves every finite binary32 value, and narrowing is an explicit nearest-even rounding site, never inferred from a transport. Under StdExceptionalFiniteOrRefuse, every arithmetic input and output must be finite or execution refuses by name. The SM86 pointwise compiler applies that to a whole state update, so a NaN refuses the update even if a later assignment would overwrite it.

The policies the current learners declare:

Showing that the declared order ran#

A bit-exact match against a reference is only informative if a different order would have produced different bits. The data-parallel gates arrange that:

• An independent binary64 oracle. Every owner's state and every checkpoint shard is compared with an oracle that evaluates the declared tree. The oracle is a separate model, not the program under test.
• An order that matters. At ten owners, the star's chain order and the hierarchy's order give different bits. The hierarchical owners matched the hierarchy oracle, which shows which order actually executed.
• Executed mutants. The ordered-combine gate runs mutants that swap operands or duplicate a weight mass. They complete their communication and are refused by the oracle.
• Instruction sets. The same comparisons hold when some owners are AArch64 executables running under emulation and the others are x86-64. AArch64 fsqrt/fdiv and x86-64 sqrtsd/divsd agree for Adam's update. A host reciprocal square root is refused because it would round twice.

Not built yet#

• A bandwidth-optimal reduce-scatter, and ring or topology-derived collectives.
• Automatic collective synthesis from a traffic pattern.
• Executing bounded-difference contracts. They are defined and refuse without conformance evidence.

Read next#

• Distributing learning stateDistributed · explanationDistributing learning stateThe distributed learners, and partitioning of optimizer state, parameters and gradients, each equal bit for bit to the replicated learner.: the learners these combines serve.
• Distributed checkpoints and resumeDistributed · explanationDistributed checkpoints and resumeLogical shard manifests, immutable publication, manifest trees, path-only restore, and resuming on a different owner count.: how the contract travels into saved state.