use crate::dist::mesh::ValidMesh;
use crate::dist::placement::{
ConstPlacement, Local, Partial, PipelineStage, Placement, PlacementBuf, PlacementKind,
Replicated, Sharded,
};
use crate::exec::ExecutionDescriptor;
use crate::shapes::ShapeBuf;
use crate::shapes::shape::Shape;
use alloc::vec::Vec;
use core::fmt;
use core::marker::PhantomData;
use core::ops::{Div, Rem};
use typenum::operator_aliases::{Mod, Quot};
use typenum::{NonZero, Same, U0, Unsigned};
#[non_exhaustive]
#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, Hash)]
pub enum ShardRemainderPolicy {
#[default]
Reject,
PadAndMask,
Ragged,
}
#[diagnostic::on_unimplemented(
message = "dimension `{Self}` cannot be evenly sharded by `{Degree}`",
label = "non-integral local dimension",
note = "static sharding requires a zero typenum remainder"
)]
pub trait ShardDivisible<Degree>: Unsigned {
type Local: Unsigned;
const LOCAL: usize = <Self::Local as Unsigned>::USIZE;
}
impl<Extent, Degree> ShardDivisible<Degree> for Extent
where
Extent: Unsigned + Div<Degree> + Rem<Degree>,
Degree: Unsigned + NonZero,
Mod<Extent, Degree>: Same<U0, Output = U0>,
Quot<Extent, Degree>: Unsigned,
{
type Local = Quot<Extent, Degree>;
}
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum PlacementTransition {
Identity,
LocalShard,
AllGather,
AllReduce,
ReduceScatter,
}
#[diagnostic::on_unimplemented(
message = "placement transition from `{Self}` to `{To}` is not legal",
label = "no direct placement transition",
note = "use an explicit replicated intermediate when no direct collective exists"
)]
pub trait LegalTransition<To: Placement>: Placement {
const TRANSITION: PlacementTransition;
}
impl LegalTransition<Local> for Local {
const TRANSITION: PlacementTransition = PlacementTransition::Identity;
}
impl<Mesh> LegalTransition<Replicated<Mesh>> for Replicated<Mesh>
where
Mesh: ValidMesh,
{
const TRANSITION: PlacementTransition = PlacementTransition::Identity;
}
impl<Mesh, Axis> LegalTransition<Sharded<Mesh, Axis>> for Sharded<Mesh, Axis>
where
Mesh: ValidMesh,
Axis: crate::dist::placement::PlacementAxis,
{
const TRANSITION: PlacementTransition = PlacementTransition::Identity;
}
impl<Mesh, Reduction> LegalTransition<Partial<Mesh, Reduction>> for Partial<Mesh, Reduction>
where
Mesh: ValidMesh,
Reduction: crate::dist::placement::PartialReduction,
{
const TRANSITION: PlacementTransition = PlacementTransition::Identity;
}
impl<Mesh, const INDEX: usize> LegalTransition<PipelineStage<Mesh, INDEX>>
for PipelineStage<Mesh, INDEX>
where
Mesh: ValidMesh,
{
const TRANSITION: PlacementTransition = PlacementTransition::Identity;
}
impl<Mesh, Axis> LegalTransition<Sharded<Mesh, Axis>> for Replicated<Mesh>
where
Mesh: ValidMesh,
Axis: crate::dist::placement::PlacementAxis,
{
const TRANSITION: PlacementTransition = PlacementTransition::LocalShard;
}
impl<Mesh, Axis> LegalTransition<Replicated<Mesh>> for Sharded<Mesh, Axis>
where
Mesh: ValidMesh,
Axis: crate::dist::placement::PlacementAxis,
{
const TRANSITION: PlacementTransition = PlacementTransition::AllGather;
}
impl<Mesh, Reduction> LegalTransition<Replicated<Mesh>> for Partial<Mesh, Reduction>
where
Mesh: ValidMesh,
Reduction: crate::dist::placement::PartialReduction,
{
const TRANSITION: PlacementTransition = PlacementTransition::AllReduce;
}
impl<Mesh, Reduction, Axis> LegalTransition<Sharded<Mesh, Axis>> for Partial<Mesh, Reduction>
where
Mesh: ValidMesh,
Reduction: crate::dist::placement::PartialReduction,
Axis: crate::dist::placement::PlacementAxis,
{
const TRANSITION: PlacementTransition = PlacementTransition::ReduceScatter;
}
pub trait CompletePlacement: Placement {}
impl CompletePlacement for Local {}
impl<Mesh: ValidMesh> CompletePlacement for Replicated<Mesh> {}
impl<Mesh, Axis> CompletePlacement for Sharded<Mesh, Axis>
where
Mesh: ValidMesh,
Axis: crate::dist::placement::PlacementAxis,
{
}
impl<Mesh: ValidMesh, const INDEX: usize> CompletePlacement for PipelineStage<Mesh, INDEX> {}
pub trait ElementwisePlacement<Rhs: Placement>: CompletePlacement {
type Output: CompletePlacement;
}
impl ElementwisePlacement<Local> for Local {
type Output = Local;
}
impl<Mesh: ValidMesh> ElementwisePlacement<Replicated<Mesh>> for Replicated<Mesh> {
type Output = Replicated<Mesh>;
}
impl<Mesh, Axis> ElementwisePlacement<Sharded<Mesh, Axis>> for Sharded<Mesh, Axis>
where
Mesh: ValidMesh,
Axis: crate::dist::placement::PlacementAxis,
{
type Output = Sharded<Mesh, Axis>;
}
impl<Mesh, Axis> ElementwisePlacement<Replicated<Mesh>> for Sharded<Mesh, Axis>
where
Mesh: ValidMesh,
Axis: crate::dist::placement::PlacementAxis,
{
type Output = Sharded<Mesh, Axis>;
}
impl<Mesh, Axis> ElementwisePlacement<Sharded<Mesh, Axis>> for Replicated<Mesh>
where
Mesh: ValidMesh,
Axis: crate::dist::placement::PlacementAxis,
{
type Output = Sharded<Mesh, Axis>;
}
impl<Mesh: ValidMesh, const INDEX: usize> ElementwisePlacement<PipelineStage<Mesh, INDEX>>
for PipelineStage<Mesh, INDEX>
{
type Output = PipelineStage<Mesh, INDEX>;
}
pub trait ReduceShardedAxis<Reduction>: CompletePlacement
where
Reduction: crate::dist::placement::PartialReduction,
{
type Output: Placement;
}
impl<Mesh, Axis, Reduction> ReduceShardedAxis<Reduction> for Sharded<Mesh, Axis>
where
Mesh: ValidMesh,
Axis: crate::dist::placement::PlacementAxis,
Reduction: crate::dist::placement::PartialReduction,
{
type Output = Partial<Mesh, Reduction>;
}
#[non_exhaustive]
#[derive(thiserror::Error, Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum DistributedError {
#[error("cannot shard an extent into zero parts")]
ZeroShards,
#[error("axis {axis} is outside rank {rank}")]
AxisOutOfBounds {
axis: usize,
rank: usize,
},
#[error("axis {axis} extent {extent} is not divisible by {shards} shards")]
NonDivisible {
axis: usize,
extent: usize,
shards: usize,
},
#[error("shard remainder policy {policy:?} is not available")]
UnsupportedRemainderPolicy {
policy: ShardRemainderPolicy,
},
#[error("pipeline stage {index} is outside a pipeline with {stages} stages")]
PipelineStageOutOfRange {
index: usize,
stages: usize,
},
#[error("operation output does not match the typed global output")]
GlobalShapeMismatch,
#[error("distributed output must contain at least one local shape")]
NoLocalShapes,
#[error("local shape {local} has rank {found}, expected {expected}")]
LocalRankMismatch {
local: usize,
expected: usize,
found: usize,
},
#[error("placement {placement:?} requires {expected} local shapes, found {found}")]
LocalShapeCount {
placement: PlacementKind,
expected: usize,
found: usize,
},
#[error("local shape {local} axis {axis} has extent {found}, expected {expected}")]
LocalExtentMismatch {
local: usize,
axis: usize,
expected: usize,
found: usize,
},
#[error("a placement transition requires at least one input placement")]
NoInputPlacements,
#[error("input {input} has placement {found:?}, expected {expected:?}")]
UnexpectedInputPlacement {
input: usize,
expected: PlacementKind,
found: PlacementKind,
},
#[error("placement transition from {from:?} to {to:?} is not legal")]
IllegalTransition {
from: PlacementKind,
to: PlacementKind,
},
}
pub fn validate_transition(
from: PlacementKind,
to: PlacementKind,
) -> Result<PlacementTransition, DistributedError> {
let transition = match (from, to) {
(PlacementKind::Local, PlacementKind::Local)
| (PlacementKind::Replicated, PlacementKind::Replicated) => PlacementTransition::Identity,
(PlacementKind::Sharded { axis: from_axis }, PlacementKind::Sharded { axis: to_axis })
if from_axis == to_axis =>
{
PlacementTransition::Identity
}
(
PlacementKind::Partial {
reduction: from_reduction,
},
PlacementKind::Partial {
reduction: to_reduction,
},
) if from_reduction == to_reduction => PlacementTransition::Identity,
(
PlacementKind::PipelineStage { index: from_index },
PlacementKind::PipelineStage { index: to_index },
) if from_index == to_index => PlacementTransition::Identity,
(PlacementKind::Replicated, PlacementKind::Sharded { .. }) => {
PlacementTransition::LocalShard
}
(PlacementKind::Sharded { .. }, PlacementKind::Replicated) => {
PlacementTransition::AllGather
}
(PlacementKind::Partial { .. }, PlacementKind::Replicated) => {
PlacementTransition::AllReduce
}
(PlacementKind::Partial { .. }, PlacementKind::Sharded { .. }) => {
PlacementTransition::ReduceScatter
}
_ => return Err(DistributedError::IllegalTransition { from, to }),
};
Ok(transition)
}
pub fn validate_shard(
global: &ShapeBuf,
axis: usize,
shards: usize,
policy: ShardRemainderPolicy,
) -> Result<ShapeBuf, DistributedError> {
if shards == 0 {
return Err(DistributedError::ZeroShards);
}
let Some(&extent) = global.dims().get(axis) else {
return Err(DistributedError::AxisOutOfBounds {
axis,
rank: global.rank(),
});
};
if extent % shards != 0 {
return match policy {
ShardRemainderPolicy::Reject => Err(DistributedError::NonDivisible {
axis,
extent,
shards,
}),
ShardRemainderPolicy::PadAndMask | ShardRemainderPolicy::Ragged => {
Err(DistributedError::UnsupportedRemainderPolicy { policy })
}
};
}
let mut local = global.dims().to_vec();
local[axis] = extent / shards;
Ok(ShapeBuf::from_slice(&local))
}
pub const fn validate_pipeline_stage(index: usize, stages: usize) -> Result<(), DistributedError> {
if index < stages {
Ok(())
} else {
Err(DistributedError::PipelineStageOutOfRange { index, stages })
}
}
pub struct DistributedInputs<O, S>
where
S: Shape,
{
operation: O,
marker: PhantomData<fn() -> S>,
global_shape: ShapeBuf,
local_shapes: Vec<ShapeBuf>,
input_placements: PlacementBuf,
}
impl<O, S> DistributedInputs<O, S>
where
S: Shape,
{
#[must_use]
pub fn new(
operation: O,
global_shape: ShapeBuf,
local_shapes: Vec<ShapeBuf>,
input_placements: PlacementBuf,
) -> Self {
Self {
operation,
marker: PhantomData,
global_shape,
local_shapes,
input_placements,
}
}
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct ValidatedDistributed<O> {
operation: O,
global_shape: ShapeBuf,
local_shapes: Vec<ShapeBuf>,
input_placements: PlacementBuf,
output_placement: PlacementKind,
transition: PlacementTransition,
}
impl<O> ValidatedDistributed<O> {
pub(crate) fn new(
operation: O,
global_shape: ShapeBuf,
local_shapes: Vec<ShapeBuf>,
input_placements: PlacementBuf,
output_placement: PlacementKind,
transition: PlacementTransition,
) -> Self {
Self {
operation,
global_shape,
local_shapes,
input_placements,
output_placement,
transition,
}
}
#[must_use]
pub const fn operation(&self) -> &O {
&self.operation
}
#[must_use]
pub const fn global_shape(&self) -> &ShapeBuf {
&self.global_shape
}
#[must_use]
pub fn local_shapes(&self) -> &[ShapeBuf] {
&self.local_shapes
}
#[must_use]
pub const fn input_placements(&self) -> &PlacementBuf {
&self.input_placements
}
#[must_use]
pub const fn output_placement(&self) -> PlacementKind {
self.output_placement
}
#[must_use]
pub const fn transition(&self) -> PlacementTransition {
self.transition
}
}
impl<O: fmt::Debug> fmt::Display for ValidatedDistributed<O> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(
f,
"{:?} [{:?} -> {:?}]",
self.operation, self.input_placements, self.output_placement
)
}
}
pub trait DistributedRule<Inputs> {
type GlobalOutput: Shape;
type OutputPlacement: Placement;
type Descriptor: ExecutionDescriptor;
fn lower_distributed(
inputs: &Inputs,
) -> Result<ValidatedDistributed<Self::Descriptor>, DistributedError>;
}
pub struct PlacementTransitionRule<From, To>(PhantomData<fn() -> (From, To)>);
impl<From, To> PlacementTransitionRule<From, To> {
pub fn lower<O, S>(
inputs: &DistributedInputs<O, S>,
) -> Result<ValidatedDistributed<O>, DistributedError>
where
O: ExecutionDescriptor,
S: Shape,
From: LegalTransition<To> + ConstPlacement,
To: ConstPlacement,
{
<Self as DistributedRule<DistributedInputs<O, S>>>::lower_distributed(inputs)
}
}
impl<O, S, From, To> DistributedRule<DistributedInputs<O, S>> for PlacementTransitionRule<From, To>
where
O: ExecutionDescriptor,
S: Shape,
From: LegalTransition<To> + ConstPlacement,
To: ConstPlacement,
{
type GlobalOutput = S;
type OutputPlacement = To;
type Descriptor = O;
fn lower_distributed(
inputs: &DistributedInputs<O, S>,
) -> Result<ValidatedDistributed<O>, DistributedError> {
let global = inputs.global_shape.clone();
if inputs.operation.output_shape() != Some(&global) {
return Err(DistributedError::GlobalShapeMismatch);
}
if inputs.input_placements.is_empty() {
return Err(DistributedError::NoInputPlacements);
}
let expected_input = From::PLACEMENT;
for (input, &found) in inputs.input_placements.as_slice().iter().enumerate() {
if found != expected_input {
return Err(DistributedError::UnexpectedInputPlacement {
input,
expected: expected_input,
found,
});
}
}
let output = To::PLACEMENT;
validate_placement::<From>(expected_input)?;
validate_placement::<To>(output)?;
validate_local_shapes::<To>(&global, &inputs.local_shapes, output)?;
Ok(ValidatedDistributed::new(
inputs.operation.clone(),
global,
inputs.local_shapes.clone(),
inputs.input_placements.clone(),
output,
From::TRANSITION,
))
}
}
fn validate_placement<P: Placement>(placement: PlacementKind) -> Result<(), DistributedError> {
if let PlacementKind::PipelineStage { index } = placement {
validate_pipeline_stage(index, P::PIPELINE_DEGREE)?;
}
Ok(())
}
fn validate_local_shapes<P: Placement>(
global: &ShapeBuf,
locals: &[ShapeBuf],
placement: PlacementKind,
) -> Result<(), DistributedError> {
if locals.is_empty() {
return Err(DistributedError::NoLocalShapes);
}
let expected_count = match placement {
PlacementKind::Local => 1,
PlacementKind::PipelineStage { .. } => P::RANKS / P::PIPELINE_DEGREE,
PlacementKind::Replicated
| PlacementKind::Sharded { .. }
| PlacementKind::Partial { .. } => P::RANKS,
};
if locals.len() != expected_count {
return Err(DistributedError::LocalShapeCount {
placement,
expected: expected_count,
found: locals.len(),
});
}
for (local_index, local) in locals.iter().enumerate() {
if local.rank() != global.rank() {
return Err(DistributedError::LocalRankMismatch {
local: local_index,
expected: global.rank(),
found: local.rank(),
});
}
}
let sharded_axis = match placement {
PlacementKind::Sharded { axis } => Some(axis),
PlacementKind::Local
| PlacementKind::Replicated
| PlacementKind::Partial { .. }
| PlacementKind::PipelineStage { .. } => None,
};
if let Some(axis) = sharded_axis {
let expected_local =
validate_shard(global, axis, P::SHARD_DEGREE, ShardRemainderPolicy::Reject)?;
for (local_index, local) in locals.iter().enumerate() {
for (axis_index, (&found, &expected)) in local
.dims()
.iter()
.zip(expected_local.dims().iter())
.enumerate()
{
if found != expected {
return Err(DistributedError::LocalExtentMismatch {
local: local_index,
axis: axis_index,
expected,
found,
});
}
}
}
} else {
for (local_index, local) in locals.iter().enumerate() {
for (axis, (&found, &expected)) in
local.dims().iter().zip(global.dims().iter()).enumerate()
{
if found != expected {
return Err(DistributedError::LocalExtentMismatch {
local: local_index,
axis,
expected,
found,
});
}
}
}
}
Ok(())
}