use alloc::string::String;
use alloc::vec::Vec;
use core::fmt;
use core::marker::PhantomData;
use core::ops::Mul;
use typenum::{NonZero, Prod, U1, Unsigned};
use crate::tensor::device::{DeviceId, DeviceKind};
pub use incin_macros::mesh;
pub struct Data<N>(PhantomData<N>);
pub struct TensorParallel<N>(PhantomData<N>);
pub struct Pipeline<N>(PhantomData<N>);
pub struct MeshSpec<DP, TP = TensorParallel<U1>, PP = Pipeline<U1>>(PhantomData<(DP, TP, PP)>);
#[diagnostic::on_unimplemented(
message = "`{Self}` is not a valid logical mesh",
label = "Invalid mesh topology",
note = "A mesh is `MeshSpec<Data<DP>, TensorParallel<TP>, Pipeline<PP>>` with the axes in \
that order and every degree nonzero"
)]
pub trait ValidMesh: 'static {
type World: Unsigned;
const DATA: usize;
const TENSOR: usize;
const PIPELINE: usize;
const WORLD: usize = <Self::World as Unsigned>::USIZE;
}
impl<DP, TP, PP> ValidMesh for MeshSpec<Data<DP>, TensorParallel<TP>, Pipeline<PP>>
where
DP: Unsigned + NonZero + Mul<TP> + 'static,
TP: Unsigned + NonZero + 'static,
PP: Unsigned + NonZero + 'static,
Prod<DP, TP>: Mul<PP>,
Prod<Prod<DP, TP>, PP>: Unsigned,
{
type World = Prod<Prod<DP, TP>, PP>;
const DATA: usize = DP::USIZE;
const TENSOR: usize = TP::USIZE;
const PIPELINE: usize = PP::USIZE;
}
pub trait TopologyProbe {
fn identify(&self, device: DeviceId) -> Option<DeviceIdentity>;
fn link(&self, from: DeviceId, to: DeviceId) -> LinkClass;
fn transport(&self) -> TransportVersion;
fn layout(&self) -> ProcessLayout;
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DeviceIdentity {
device: DeviceId,
persistent: String,
architecture: String,
}
impl DeviceIdentity {
#[must_use]
pub fn new(device: DeviceId, persistent: String, architecture: String) -> Self {
Self {
device,
persistent,
architecture,
}
}
#[must_use]
pub const fn device(&self) -> DeviceId {
self.device
}
#[must_use]
pub fn persistent(&self) -> &str {
&self.persistent
}
#[must_use]
pub fn architecture(&self) -> &str {
&self.architecture
}
}
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum LinkClass {
SameDevice,
HighBandwidth,
PeerCapable,
HostBounce,
Network,
Unreachable,
}
impl LinkClass {
#[must_use]
pub const fn reaches(self) -> bool {
!matches!(self, Self::Unreachable)
}
#[must_use]
pub const fn name(self) -> &'static str {
match self {
Self::SameDevice => "same-device",
Self::HighBandwidth => "high-bandwidth",
Self::PeerCapable => "peer-capable",
Self::HostBounce => "host-bounce",
Self::Network => "network",
Self::Unreachable => "unreachable",
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct TransportVersion {
library: String,
major: u32,
minor: u32,
patch: u32,
}
impl TransportVersion {
#[must_use]
pub fn new(library: String, major: u32, minor: u32, patch: u32) -> Self {
Self {
library,
major,
minor,
patch,
}
}
#[must_use]
pub fn library(&self) -> &str {
&self.library
}
#[must_use]
pub const fn version(&self) -> (u32, u32, u32) {
(self.major, self.minor, self.patch)
}
}
#[non_exhaustive]
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ProcessLayout {
SingleProcess,
ProcessPerRank {
rank: usize,
world: usize,
},
}
impl ProcessLayout {
#[must_use]
pub const fn name(&self) -> &'static str {
match self {
Self::SingleProcess => "single-process",
Self::ProcessPerRank { .. } => "process-per-rank",
}
}
}
pub const AXIS_COUNT: usize = 3;
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum MeshAxis {
Data,
Pipeline,
Tensor,
}
impl MeshAxis {
#[must_use]
pub const fn name(self) -> &'static str {
match self {
Self::Data => "data",
Self::Pipeline => "pipeline",
Self::Tensor => "tensor",
}
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CollectiveGroups {
axes: [(MeshAxis, usize); AXIS_COUNT],
}
impl CollectiveGroups {
#[must_use]
pub fn of<M: ValidMesh>() -> Self {
Self {
axes: [
(MeshAxis::Data, M::DATA),
(MeshAxis::Pipeline, M::PIPELINE),
(MeshAxis::Tensor, M::TENSOR),
],
}
}
#[must_use]
pub fn world(&self) -> usize {
self.axes.iter().map(|&(_, degree)| degree).product()
}
#[must_use]
pub fn degree(&self, axis: MeshAxis) -> usize {
self.position(axis).map_or(1, |i| self.axes[i].1)
}
fn position(&self, axis: MeshAxis) -> Option<usize> {
self.axes.iter().position(|&(a, _)| a == axis)
}
fn stride(&self, position: usize) -> usize {
self.axes[position + 1..]
.iter()
.map(|&(_, degree)| degree)
.product()
}
pub fn coordinates(&self, rank: usize) -> Option<[usize; AXIS_COUNT]> {
if rank >= self.world() {
return None;
}
let mut out = [0; AXIS_COUNT];
for (position, slot) in out.iter_mut().enumerate() {
*slot = (rank / self.stride(position)) % self.axes[position].1;
}
Some(out)
}
pub fn coordinate(&self, rank: usize, axis: MeshAxis) -> Option<usize> {
let position = self.position(axis)?;
Some(self.coordinates(rank)?[position])
}
pub fn rank_of(&self, coordinates: [usize; AXIS_COUNT]) -> Option<usize> {
let mut rank = 0;
for (position, &coordinate) in coordinates.iter().enumerate() {
if coordinate >= self.axes[position].1 {
return None;
}
rank += coordinate * self.stride(position);
}
Some(rank)
}
pub fn group(&self, axis: MeshAxis, rank: usize) -> Option<Vec<usize>> {
let position = self.position(axis)?;
let coordinate = self.coordinates(rank)?[position];
let stride = self.stride(position);
let base = rank - coordinate * stride;
Some(
(0..self.axes[position].1)
.map(|k| base + k * stride)
.collect(),
)
}
}
#[derive(Debug, Clone, Copy)]
struct Digest(u64);
impl Digest {
const OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
const PRIME: u64 = 0x0000_0100_0000_01b3;
const fn new() -> Self {
Self(Self::OFFSET)
}
fn bytes(mut self, bytes: &[u8]) -> Self {
for &byte in bytes {
self.0 = (self.0 ^ u64::from(byte)).wrapping_mul(Self::PRIME);
}
self
}
fn field(self, bytes: &[u8]) -> Self {
self.number(bytes.len() as u64).bytes(bytes)
}
fn text(self, text: &str) -> Self {
self.field(text.as_bytes())
}
fn number(self, value: u64) -> Self {
self.bytes(&value.to_le_bytes())
}
const fn finish(self) -> u64 {
self.0
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct TopologyFingerprint {
devices: Vec<DeviceIdentity>,
links: Vec<(usize, usize, LinkClass)>,
transport: TransportVersion,
layout: ProcessLayout,
}
impl TopologyFingerprint {
#[must_use]
pub fn devices(&self) -> &[DeviceIdentity] {
&self.devices
}
#[must_use]
pub fn links(&self) -> &[(usize, usize, LinkClass)] {
&self.links
}
#[must_use]
pub const fn transport(&self) -> &TransportVersion {
&self.transport
}
#[must_use]
pub const fn layout(&self) -> &ProcessLayout {
&self.layout
}
#[must_use]
pub fn digest(&self) -> u64 {
let mut digest = Digest::new().field(b"incin.topology.v1");
digest = digest.number(self.devices.len() as u64);
for identity in &self.devices {
digest = digest
.text(identity.device.kind().name())
.number(identity.device.ordinal() as u64)
.text(&identity.persistent)
.text(&identity.architecture);
}
digest = digest.number(self.links.len() as u64);
for &(from, to, class) in &self.links {
digest = digest
.number(from as u64)
.number(to as u64)
.text(class.name());
}
digest = digest
.text(&self.transport.library)
.number(u64::from(self.transport.major))
.number(u64::from(self.transport.minor))
.number(u64::from(self.transport.patch))
.text(self.layout.name());
digest = match self.layout {
ProcessLayout::SingleProcess => digest,
ProcessLayout::ProcessPerRank { world, .. } => digest.number(world as u64),
};
digest.finish()
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct MeshId(u64);
impl MeshId {
#[must_use]
pub const fn from_digest(digest: u64) -> Self {
Self(digest)
}
#[must_use]
pub const fn digest(self) -> u64 {
self.0
}
}
pub struct DeviceMesh<M> {
fingerprint: TopologyFingerprint,
id: MeshId,
spec: PhantomData<M>,
}
impl<M> fmt::Debug for DeviceMesh<M> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("DeviceMesh")
.field("id", &self.id)
.field("fingerprint", &self.fingerprint)
.finish()
}
}
impl<M> Clone for DeviceMesh<M> {
fn clone(&self) -> Self {
Self {
fingerprint: self.fingerprint.clone(),
id: self.id,
spec: PhantomData,
}
}
}
impl<M> PartialEq for DeviceMesh<M> {
fn eq(&self, other: &Self) -> bool {
self.id == other.id && self.fingerprint == other.fingerprint
}
}
impl<M> Eq for DeviceMesh<M> {}
#[non_exhaustive]
#[derive(thiserror::Error, Debug, Clone, PartialEq, Eq)]
pub enum BindError {
#[error("mesh needs {expected} ranks but {found} devices were given")]
RankCount {
expected: usize,
found: usize,
},
#[error("device {device:?} was given twice, as rank {first} and rank {second}")]
RepeatedDevice {
device: DeviceId,
first: usize,
second: usize,
},
#[error("rank {rank} names device {device:?}, which the probe cannot see")]
UnknownDevice {
rank: usize,
device: DeviceId,
},
#[error(
"rank {first} and rank {second} name different ordinals but the same physical device \
({persistent})"
)]
AliasedDevice {
first: usize,
second: usize,
persistent: String,
},
#[error(
"rank 0 is a {} device but rank {rank} is a {} device",
expected.name(),
found.name()
)]
MixedBackendFamily {
expected: DeviceKind,
found: DeviceKind,
rank: usize,
},
#[error("rank 0 is architecture {expected} but rank {rank} is {found}")]
MixedArchitecture {
expected: String,
found: String,
rank: usize,
},
#[error("process layout {layout} does not describe a {world}-rank mesh")]
UnsupportedProcessLayout {
layout: String,
world: usize,
},
#[error("rank {from} cannot reach rank {to}, which shares its {} group", axis.name())]
UnreachableGroup {
axis: MeshAxis,
from: usize,
to: usize,
},
}
impl<M: ValidMesh> DeviceMesh<M> {
pub fn bind<P: TopologyProbe>(devices: &[DeviceId], probe: &P) -> Result<Self, BindError> {
if devices.len() != M::WORLD {
return Err(BindError::RankCount {
expected: M::WORLD,
found: devices.len(),
});
}
for (second, &device) in devices.iter().enumerate() {
if let Some(first) = devices[..second].iter().position(|&seen| seen == device) {
return Err(BindError::RepeatedDevice {
device,
first,
second,
});
}
}
let mut identities: Vec<DeviceIdentity> = Vec::with_capacity(devices.len());
for (rank, &device) in devices.iter().enumerate() {
let identity = probe
.identify(device)
.ok_or(BindError::UnknownDevice { rank, device })?;
if let Some(first) = identities
.iter()
.position(|seen| seen.persistent == identity.persistent)
{
return Err(BindError::AliasedDevice {
first,
second: rank,
persistent: identity.persistent,
});
}
if let Some(head) = identities.first() {
if head.device.kind() != identity.device.kind() {
return Err(BindError::MixedBackendFamily {
expected: head.device.kind(),
found: identity.device.kind(),
rank,
});
}
if head.architecture != identity.architecture {
return Err(BindError::MixedArchitecture {
expected: head.architecture.clone(),
found: identity.architecture,
rank,
});
}
}
identities.push(identity);
}
let layout = probe.layout();
if let ProcessLayout::ProcessPerRank { rank, world } = layout
&& (world != M::WORLD || rank >= world)
{
return Err(BindError::UnsupportedProcessLayout {
layout: alloc::format!("{layout:?}"),
world: M::WORLD,
});
}
let groups = CollectiveGroups::of::<M>();
let mut links = Vec::new();
for &(axis, _) in &groups.axes {
for from in 0..M::WORLD {
let members = groups
.group(axis, from)
.expect("rank is below the world size the count guard already checked");
for to in members {
if to == from {
continue;
}
let class = probe.link(devices[from], devices[to]);
if !class.reaches() {
return Err(BindError::UnreachableGroup { axis, from, to });
}
links.push((from, to, class));
}
}
}
let fingerprint = TopologyFingerprint {
devices: identities,
links,
transport: probe.transport(),
layout,
};
let id = MeshId(
Digest::new()
.number(fingerprint.digest())
.number(M::DATA as u64)
.number(M::PIPELINE as u64)
.number(M::TENSOR as u64)
.finish(),
);
Ok(Self {
fingerprint,
id,
spec: PhantomData,
})
}
#[must_use]
pub const fn id(&self) -> MeshId {
self.id
}
#[must_use]
pub const fn fingerprint(&self) -> &TopologyFingerprint {
&self.fingerprint
}
#[must_use]
pub fn groups(&self) -> CollectiveGroups {
CollectiveGroups::of::<M>()
}
pub fn device(&self, rank: usize) -> Option<&DeviceIdentity> {
self.fingerprint.devices.get(rank)
}
}