use core::sync::atomic::{AtomicPtr, Ordering};
use std::sync::Arc;
use cudarc::nvrtc::Ptx;
use crate::sched::hybrid::{SplitReport, hybrid_auto_split_ranges};
use super::{GpuPeer, GpuPeerError, WideKernel};
use crate::backend::accel_op::{AccelOpId, AccelReport, bind_accel_kernel, dispatch_accel, register_accel_op};
use crate::backend::{Backend, BackendError, KernelArg};
use crate::sched::plan::JobPlan;
#[derive(Default)]
struct DeviceError(AtomicPtr<GpuPeerError>);
impl DeviceError {
fn record(&self, err: GpuPeerError) {
let fresh = Box::into_raw(Box::new(err));
let prev = self.0.swap(fresh, Ordering::AcqRel);
if !prev.is_null() {
drop(unsafe { Box::from_raw(prev) });
}
}
fn take(&self) -> Option<GpuPeerError> {
let held = self.0.swap(core::ptr::null_mut(), Ordering::AcqRel);
if held.is_null() {
return None;
}
Some(*unsafe { Box::from_raw(held) })
}
}
impl Drop for DeviceError {
fn drop(&mut self) {
let held = *self.0.get_mut();
if !held.is_null() {
drop(unsafe { Box::from_raw(held) });
}
}
}
pub const LINALG_PTX: &str = include_str!("../../kernels/linalg_f64.ptx");
pub const LINALG_CU: &str = include_str!("../../kernels/linalg_f64.cu");
pub const LINALG_BISECT_PTX: &str = include_str!("../../kernels/linalg_bisect_f64.ptx");
pub const LINALG_BISECT_CU: &str = include_str!("../../kernels/linalg_bisect_f64.cu");
pub const LINALG_LU_PTX: &str = include_str!("../../kernels/linalg_lu_f64.ptx");
pub const LINALG_LU_CU: &str = include_str!("../../kernels/linalg_lu_f64.cu");
pub const LINALG_MAX_N: usize = 64;
pub const LINALG_THR_MAX_N: usize = 16;
pub const EINSUM_MAX_RANK: usize = 12;
pub const LINALG_BLOCK: u32 = 256;
pub const JACOBI_THREAD_SHAPE_BATCH_PER_N: usize = 256;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum JacobiShape {
BlockPerMatrix,
ThreadPerMatrix,
}
pub fn jacobi_shape_for(n: usize, batch: usize) -> JacobiShape {
if n <= LINALG_THR_MAX_N && batch >= JACOBI_THREAD_SHAPE_BATCH_PER_N * n {
JacobiShape::ThreadPerMatrix
} else {
JacobiShape::BlockPerMatrix
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum LinalgMethod {
Jacobi,
Bisection,
}
pub const SYEV_BISECT_MIN_N: usize = 32;
pub const GESVD_BISECT_MIN_N: usize = 64;
pub fn syev_method_for(n: usize) -> LinalgMethod {
if n >= SYEV_BISECT_MIN_N { LinalgMethod::Bisection } else { LinalgMethod::Jacobi }
}
pub fn gesvd_method_for(n: usize) -> LinalgMethod {
if n >= GESVD_BISECT_MIN_N { LinalgMethod::Bisection } else { LinalgMethod::Jacobi }
}
pub fn default_sweeps(n: usize) -> u32 {
let mut sweeps = 8u32;
let mut nn = n.max(1);
while nn > 1 {
nn = nn.div_ceil(2);
sweeps += 4;
}
sweeps
}
pub struct LinalgKernels {
pub einsum: WideKernel,
pub gemm: WideKernel,
pub syev_blk: WideKernel,
pub syev_thr: WideKernel,
pub gesvd_blk: WideKernel,
pub gesvd_thr: WideKernel,
pub syev_bisect: WideKernel,
pub gesvd_bisect: WideKernel,
pub getrf: WideKernel,
pub getrs: WideKernel,
}
fn load_module(
peer: &GpuPeer,
what: &str,
ptx: &str,
cu: &str,
) -> Result<std::sync::Arc<cudarc::driver::CudaModule>, GpuPeerError> {
match peer.context().load_module(Ptx::from_src(ptx)) {
Ok(m) => Ok(m),
Err(ptx_err) => {
notice!(
"flynnel gpu_peer {what}: checked-in PTX rejected ({ptx_err:?}); \
compiling the {what} kernels with NVRTC instead"
);
let ptx = cudarc::nvrtc::compile_ptx(cu).map_err(|e| {
GpuPeerError::Driver(format!(
"{what} PTX load: {ptx_err:?}; NVRTC fallback compile: {e:?}"
))
})?;
peer.context()
.load_module(ptx)
.map_err(|e| GpuPeerError::Driver(format!("{what} NVRTC-fallback load: {e:?}")))
}
}
}
impl LinalgKernels {
pub fn load(peer: &GpuPeer) -> Result<Self, GpuPeerError> {
let module = load_module(peer, "linalg", LINALG_PTX, LINALG_CU)?;
let bisect = load_module(peer, "linalg_bisect", LINALG_BISECT_PTX, LINALG_BISECT_CU)?;
let lu = load_module(peer, "linalg_lu", LINALG_LU_PTX, LINALG_LU_CU)?;
let load = |module: &std::sync::Arc<cudarc::driver::CudaModule>,
entry: &str|
-> Result<WideKernel, GpuPeerError> {
let func = module
.load_function(entry)
.map_err(|e| GpuPeerError::Driver(format!("linalg entry `{entry}`: {e:?}")))?;
Ok(WideKernel::new(module.clone(), func))
};
Ok(Self {
einsum: load(&module, "flynnel_einsum_f64")?,
gemm: load(&module, "flynnel_gemm_batched_f64")?,
syev_blk: load(&module, "flynnel_syev_jacobi_f64_blk")?,
syev_thr: load(&module, "flynnel_syev_jacobi_f64_thr")?,
gesvd_blk: load(&module, "flynnel_gesvd_jacobi_f64_blk")?,
gesvd_thr: load(&module, "flynnel_gesvd_jacobi_f64_thr")?,
syev_bisect: load(&bisect, "flynnel_syev_bisect_f64_blk")?,
gesvd_bisect: load(&bisect, "flynnel_gesvd_bisect_f64_blk")?,
getrf: load(&lu, "flynnel_getrf_f64_blk")?,
getrs: load(&lu, "flynnel_getrs_f64_blk")?,
})
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum EinsumError {
BadSpec(String),
RankMismatch {
operand: usize,
subscripts: usize,
rank: usize,
},
ExtentMismatch {
letter: char,
first: usize,
second: usize,
},
UnknownOutputAxis(char),
RankTooLarge(usize),
}
impl std::fmt::Display for EinsumError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::BadSpec(s) => write!(f, "einsum: bad spec: {s}"),
Self::RankMismatch { operand, subscripts, rank } => write!(
f,
"einsum: operand {operand} has {subscripts} subscripts but rank {rank}"
),
Self::ExtentMismatch { letter, first, second } => write!(
f,
"einsum: axis `{letter}` has extent {first} and {second}"
),
Self::UnknownOutputAxis(c) => write!(f, "einsum: output axis `{c}` not in any operand"),
Self::RankTooLarge(r) => write!(f, "einsum: rank {r} exceeds {EINSUM_MAX_RANK}"),
}
}
}
impl std::error::Error for EinsumError {}
#[derive(Debug, Clone)]
pub struct EinsumSpec {
a_shape: Vec<usize>,
b_shape: Option<Vec<usize>>,
out_shape: Vec<usize>,
tables: Vec<i32>,
offsets: [usize; 6],
n_contract: usize,
}
impl EinsumSpec {
pub fn parse(
spec: &str,
a_shape: &[usize],
b_shape: Option<&[usize]>,
) -> Result<Self, EinsumError> {
let (lhs, rhs) = spec
.split_once("->")
.ok_or_else(|| EinsumError::BadSpec(format!("`{spec}` has no `->`")))?;
let inputs: Vec<&str> = lhs.split(',').map(str::trim).collect();
let rhs = rhs.trim();
if inputs.len() != if b_shape.is_some() { 2 } else { 1 } {
return Err(EinsumError::BadSpec(format!(
"`{spec}` names {} operands, {} given",
inputs.len(),
if b_shape.is_some() { 2 } else { 1 }
)));
}
for s in inputs.iter().chain(std::iter::once(&rhs)) {
if let Some(c) = s.chars().find(|c| !c.is_ascii_alphabetic()) {
return Err(EinsumError::BadSpec(format!("non-letter subscript `{c}`")));
}
}
let shapes: Vec<&[usize]> = match b_shape {
Some(b) => vec![a_shape, b],
None => vec![a_shape],
};
let mut extent_of: Vec<(char, usize)> = Vec::new();
for (oi, (sub, shape)) in inputs.iter().zip(&shapes).enumerate() {
let subs: Vec<char> = sub.chars().collect();
if subs.len() != shape.len() {
return Err(EinsumError::RankMismatch {
operand: oi,
subscripts: subs.len(),
rank: shape.len(),
});
}
if subs.len() > EINSUM_MAX_RANK {
return Err(EinsumError::RankTooLarge(subs.len()));
}
for (c, &e) in subs.iter().zip(shape.iter()) {
match extent_of.iter().find(|(l, _)| l == c) {
Some(&(_, first)) if first != e => {
return Err(EinsumError::ExtentMismatch { letter: *c, first, second: e });
}
Some(_) => {}
None => extent_of.push((*c, e)),
}
}
}
let out: Vec<char> = rhs.chars().collect();
if out.len() > EINSUM_MAX_RANK {
return Err(EinsumError::RankTooLarge(out.len()));
}
let mut out_shape = Vec::with_capacity(out.len());
for c in &out {
let (_, e) = extent_of
.iter()
.find(|(l, _)| l == c)
.ok_or(EinsumError::UnknownOutputAxis(*c))?;
out_shape.push(*e);
}
let contracted: Vec<(char, usize)> = extent_of
.iter()
.filter(|(l, _)| !out.contains(l))
.copied()
.collect();
if contracted.len() > EINSUM_MAX_RANK {
return Err(EinsumError::RankTooLarge(contracted.len()));
}
let row_major = |shape: &[usize]| -> Vec<i32> {
let mut strides = vec![0i32; shape.len()];
let mut acc = 1i32;
for i in (0..shape.len()).rev() {
strides[i] = acc;
acc *= shape[i] as i32;
}
strides
};
let kinds = |sub: &str| -> Vec<i32> {
sub.chars()
.map(|c| match out.iter().position(|o| *o == c) {
Some(pos) => pos as i32,
None => {
let pos = contracted.iter().position(|(l, _)| *l == c).expect("contracted");
(1 << 16) | pos as i32
}
})
.collect()
};
let a_strides = row_major(a_shape);
let b_strides = b_shape.map(row_major).unwrap_or_default();
let o_strides = row_major(&out_shape);
let c_extents: Vec<i32> = contracted.iter().map(|(_, e)| *e as i32).collect();
let a_kind = kinds(inputs[0]);
let b_kind = if b_shape.is_some() { kinds(inputs[1]) } else { Vec::new() };
let mut tables = Vec::new();
let mut offsets = [0usize; 6];
for (i, part) in [&a_strides, &b_strides, &o_strides, &c_extents, &a_kind, &b_kind]
.into_iter()
.enumerate()
{
offsets[i] = tables.len();
tables.extend_from_slice(part);
}
Ok(Self {
a_shape: a_shape.to_vec(),
b_shape: b_shape.map(<[usize]>::to_vec),
out_shape,
tables,
offsets,
n_contract: contracted.len(),
})
}
pub fn out_size(&self) -> usize {
self.out_shape.iter().product()
}
pub fn a_size(&self) -> usize {
self.a_shape.iter().product()
}
pub fn b_size(&self) -> usize {
self.b_shape.as_ref().map_or(0, |s| s.iter().product())
}
pub fn out_shape(&self) -> &[usize] {
&self.out_shape
}
pub fn tables(&self) -> &[i32] {
&self.tables
}
pub fn table_offsets(&self) -> [usize; 6] {
self.offsets
}
fn a_rank(&self) -> usize {
self.a_shape.len()
}
fn b_rank(&self) -> usize {
self.b_shape.as_ref().map_or(0, Vec::len)
}
fn has_b(&self) -> bool {
self.b_shape.is_some()
}
fn part(&self, i: usize) -> &[i32] {
let start = self.offsets[i];
let end = if i + 1 < 6 { self.offsets[i + 1] } else { self.tables.len() };
&self.tables[start..end]
}
}
pub(crate) fn check_dim(cond: bool, what: &'static str) -> Result<(), GpuPeerError> {
if cond { Ok(()) } else { Err(GpuPeerError::Unavailable(what)) }
}
#[allow(clippy::too_many_arguments)]
pub fn launch_einsum(
peer: &GpuPeer,
k: &LinalgKernels,
spec: &EinsumSpec,
tables_dev: u64,
a: u64,
b: u64,
out: u64,
batch: u32,
) -> Result<(), GpuPeerError> {
check_dim(batch > 0, "einsum: empty batch")?;
let off = spec.table_offsets();
let tp = |i: usize| tables_dev + (off[i] * 4) as u64;
let ptrs = [out, a, if spec.has_b() { b } else { a }, tp(0), tp(1), tp(2), tp(3), tp(4), tp(5)];
let o_size = spec.out_size() as u32;
let scalars = [
o_size,
spec.a_rank() as u32,
spec.b_rank() as u32,
spec.out_shape.len() as u32,
spec.n_contract as u32,
u32::from(spec.has_b()),
batch,
spec.a_size() as u32,
spec.b_size() as u32,
o_size,
];
let grid = (o_size as u64 * batch as u64).div_ceil(LINALG_BLOCK as u64).max(1) as u32;
peer.launch_wide_async(&k.einsum, grid, LINALG_BLOCK, &ptrs, &scalars)
}
#[allow(clippy::too_many_arguments)]
pub fn launch_gemm(
peer: &GpuPeer,
k: &LinalgKernels,
a: u64,
b: u64,
c: u64,
batch: u32,
m: u32,
n: u32,
kdim: u32,
) -> Result<(), GpuPeerError> {
check_dim(batch > 0 && m > 0 && n > 0 && kdim > 0, "gemm: empty dimension")?;
let tiles = m.div_ceil(16) * n.div_ceil(16);
let grid = tiles * batch;
peer.launch_wide_async(
&k.gemm,
grid,
LINALG_BLOCK,
&[a, b, c],
&[batch, m, n, kdim, kdim, n, n],
)
}
#[allow(clippy::too_many_arguments)]
pub fn launch_syev(
peer: &GpuPeer,
k: &LinalgKernels,
a: u64,
w: u64,
v: Option<u64>,
batch: u32,
n: u32,
max_sweeps: u32,
shape: JacobiShape,
) -> Result<(), GpuPeerError> {
check_dim(batch > 0 && n > 0, "syev: empty batch or n")?;
check_dim(n as usize <= LINALG_MAX_N, "syev: n exceeds LINALG_MAX_N")?;
let scalars = [batch, n, max_sweeps, u32::from(v.is_some())];
let ptrs = [a, w, v.unwrap_or(0)];
match shape {
JacobiShape::BlockPerMatrix => {
peer.launch_wide_async(&k.syev_blk, batch, LINALG_BLOCK, &ptrs, &scalars)
}
JacobiShape::ThreadPerMatrix => {
check_dim(n as usize <= LINALG_THR_MAX_N, "syev: n exceeds LINALG_THR_MAX_N")?;
let grid = batch.div_ceil(LINALG_BLOCK);
peer.launch_wide_async(&k.syev_thr, grid, LINALG_BLOCK, &ptrs, &scalars)
}
}
}
#[allow(clippy::too_many_arguments)]
pub fn launch_gesvd(
peer: &GpuPeer,
k: &LinalgKernels,
a: u64,
sigma: u64,
v: Option<u64>,
batch: u32,
m: u32,
n: u32,
max_sweeps: u32,
shape: JacobiShape,
) -> Result<(), GpuPeerError> {
check_dim(batch > 0 && n > 0 && m >= n, "gesvd: needs batch > 0 and m >= n > 0")?;
check_dim(m as usize <= LINALG_MAX_N, "gesvd: m exceeds LINALG_MAX_N")?;
let scalars = [batch, m, n, max_sweeps, u32::from(v.is_some())];
let ptrs = [a, sigma, v.unwrap_or(0)];
match shape {
JacobiShape::BlockPerMatrix => {
peer.launch_wide_async(&k.gesvd_blk, batch, LINALG_BLOCK, &ptrs, &scalars)
}
JacobiShape::ThreadPerMatrix => {
check_dim(m as usize <= LINALG_THR_MAX_N, "gesvd: m exceeds LINALG_THR_MAX_N")?;
let grid = batch.div_ceil(LINALG_BLOCK);
peer.launch_wide_async(&k.gesvd_thr, grid, LINALG_BLOCK, &ptrs, &scalars)
}
}
}
pub(crate) fn f64_bytes(v: &[f64]) -> Vec<u8> {
v.iter().flat_map(|x| x.to_le_bytes()).collect()
}
pub(crate) fn bytes_f64(b: &[u8]) -> Vec<f64> {
b.as_chunks::<8>().0.iter().map(|c| f64::from_le_bytes(*c)).collect()
}
fn i32_bytes(v: &[i32]) -> Vec<u8> {
v.iter().flat_map(|x| x.to_le_bytes()).collect()
}
pub(crate) struct Pinned {
pub(crate) handle: super::ResidentHandle,
pub(crate) ptr: u64,
}
pub(crate) fn pin(peer: &mut GpuPeer, bytes: &[u8]) -> Result<Pinned, GpuPeerError> {
let handle = peer.pin_bulk(bytes)?;
let (ptr, _) = peer.resident_ptr(&handle)?;
Ok(Pinned { handle, ptr })
}
impl Pinned {
pub(crate) fn release(self, peer: &mut GpuPeer) -> Result<(), GpuPeerError> {
peer.unpin(self.handle)
}
}
fn fetch_f64(peer: &mut GpuPeer, p: &Pinned, elems: usize) -> Result<Vec<f64>, GpuPeerError> {
let mut out = vec![0u8; elems * 8];
peer.fetch_bulk(&p.handle, &mut out)?;
Ok(bytes_f64(&out))
}
pub fn einsum_batched(
peer: &mut GpuPeer,
k: &LinalgKernels,
spec: &EinsumSpec,
a: &[f64],
b: Option<&[f64]>,
batch: u32,
) -> Result<Vec<f64>, GpuPeerError> {
let batch_us = batch as usize;
check_dim(a.len() == batch_us * spec.a_size(), "einsum: a length")?;
check_dim(
b.map_or(!spec.has_b(), |b| spec.has_b() && b.len() == batch_us * spec.b_size()),
"einsum: b length",
)?;
let out_elems = batch_us * spec.out_size();
let tables = pin(peer, &i32_bytes(spec.tables()))?;
let pa = pin(peer, &f64_bytes(a))?;
let pb = match b {
Some(b) => Some(pin(peer, &f64_bytes(b))?),
None => None,
};
let po = pin(peer, &vec![0u8; out_elems * 8])?;
launch_einsum(
peer,
k,
spec,
tables.ptr,
pa.ptr,
pb.as_ref().map_or(pa.ptr, |p| p.ptr),
po.ptr,
batch,
)?;
peer.sync_wide()?;
let out = fetch_f64(peer, &po, out_elems)?;
po.release(peer)?;
if let Some(pb) = pb {
pb.release(peer)?;
}
pa.release(peer)?;
tables.release(peer)?;
Ok(out)
}
#[allow(clippy::too_many_arguments)]
pub fn gemm_batched(
peer: &mut GpuPeer,
k: &LinalgKernels,
a: &[f64],
b: &[f64],
batch: u32,
m: u32,
n: u32,
kdim: u32,
) -> Result<Vec<f64>, GpuPeerError> {
let (bu, mu, nu, ku) = (batch as usize, m as usize, n as usize, kdim as usize);
check_dim(a.len() == bu * mu * ku && b.len() == bu * ku * nu, "gemm: operand length")?;
let pa = pin(peer, &f64_bytes(a))?;
let pb = pin(peer, &f64_bytes(b))?;
let pc = pin(peer, &vec![0u8; bu * mu * nu * 8])?;
launch_gemm(peer, k, pa.ptr, pb.ptr, pc.ptr, batch, m, n, kdim)?;
peer.sync_wide()?;
let out = fetch_f64(peer, &pc, bu * mu * nu)?;
pc.release(peer)?;
pb.release(peer)?;
pa.release(peer)?;
Ok(out)
}
pub fn syev_bisect_scratch_bytes(batch: u32, n: u32) -> usize {
batch as usize * n as usize * n as usize * 8
}
pub fn gesvd_bisect_scratch_bytes(batch: u32, m: u32, n: u32) -> usize {
let (bu, mu, nu) = (batch as usize, m as usize, n as usize);
bu * (3 * nu * nu + mu * nu) * 8
}
#[allow(clippy::too_many_arguments)]
pub fn launch_syev_bisect(
peer: &GpuPeer,
k: &LinalgKernels,
a: u64,
w: u64,
v: Option<u64>,
scratch: u64,
batch: u32,
n: u32,
) -> Result<(), GpuPeerError> {
check_dim(batch > 0 && n > 0, "syev_bisect: empty batch or n")?;
check_dim(n as usize <= LINALG_MAX_N, "syev_bisect: n exceeds LINALG_MAX_N")?;
check_dim(v.is_none() || scratch != 0, "syev_bisect: eigenvectors need a scratch buffer")?;
let scalars = [batch, n, u32::from(v.is_some())];
let ptrs = [a, w, v.unwrap_or(0), scratch];
peer.launch_wide_async(&k.syev_bisect, batch, LINALG_BLOCK, &ptrs, &scalars)
}
pub fn syev_bisect_batched(
peer: &mut GpuPeer,
k: &LinalgKernels,
a: &[f64],
batch: u32,
n: u32,
want_v: bool,
) -> Result<(Vec<f64>, Option<Vec<f64>>), GpuPeerError> {
let (bu, nu) = (batch as usize, n as usize);
check_dim(a.len() == bu * nu * nu, "syev_bisect: a length")?;
let pa = pin(peer, &f64_bytes(a))?;
let pw = pin(peer, &vec![0u8; bu * nu * 8])?;
let pv = if want_v { Some(pin(peer, &vec![0u8; bu * nu * nu * 8])?) } else { None };
let scratch = if want_v {
Some(pin(peer, &vec![0u8; syev_bisect_scratch_bytes(batch, n)])?)
} else {
None
};
launch_syev_bisect(
peer,
k,
pa.ptr,
pw.ptr,
pv.as_ref().map(|p| p.ptr),
scratch.as_ref().map_or(0, |p| p.ptr),
batch,
n,
)?;
peer.sync_wide()?;
let w = fetch_f64(peer, &pw, bu * nu)?;
let v = match &pv {
Some(p) => Some(fetch_f64(peer, p, bu * nu * nu)?),
None => None,
};
if let Some(p) = scratch {
p.release(peer)?;
}
if let Some(p) = pv {
p.release(peer)?;
}
pw.release(peer)?;
pa.release(peer)?;
Ok((w, v))
}
#[allow(clippy::too_many_arguments)]
pub fn launch_gesvd_bisect(
peer: &GpuPeer,
k: &LinalgKernels,
a: u64,
sigma: u64,
v: Option<u64>,
scratch: u64,
batch: u32,
m: u32,
n: u32,
) -> Result<(), GpuPeerError> {
check_dim(batch > 0 && n > 0 && m >= n, "gesvd_bisect: empty batch, empty n, or m < n")?;
check_dim(m as usize <= LINALG_MAX_N, "gesvd_bisect: m exceeds LINALG_MAX_N")?;
check_dim(scratch != 0, "gesvd_bisect: scratch buffer required")?;
let scalars = [batch, m, n, u32::from(v.is_some())];
let ptrs = [a, sigma, v.unwrap_or(0), scratch];
peer.launch_wide_async(&k.gesvd_bisect, batch, LINALG_BLOCK, &ptrs, &scalars)
}
#[allow(clippy::too_many_arguments)]
pub fn gesvd_bisect_batched(
peer: &mut GpuPeer,
k: &LinalgKernels,
a: &[f64],
batch: u32,
m: u32,
n: u32,
want_v: bool,
) -> Result<GesvdResult, GpuPeerError> {
let (bu, mu, nu) = (batch as usize, m as usize, n as usize);
check_dim(a.len() == bu * mu * nu, "gesvd_bisect: a length")?;
let pa = pin(peer, &f64_bytes(a))?;
let ps = pin(peer, &vec![0u8; bu * nu * 8])?;
let pv = if want_v { Some(pin(peer, &vec![0u8; bu * nu * nu * 8])?) } else { None };
let scratch = pin(peer, &vec![0u8; gesvd_bisect_scratch_bytes(batch, m, n)])?;
launch_gesvd_bisect(
peer,
k,
pa.ptr,
ps.ptr,
pv.as_ref().map(|p| p.ptr),
scratch.ptr,
batch,
m,
n,
)?;
peer.sync_wide()?;
let u = fetch_f64(peer, &pa, bu * mu * nu)?;
let sigma = fetch_f64(peer, &ps, bu * nu)?;
let v = match &pv {
Some(p) => Some(fetch_f64(peer, p, bu * nu * nu)?),
None => None,
};
scratch.release(peer)?;
if let Some(p) = pv {
p.release(peer)?;
}
ps.release(peer)?;
pa.release(peer)?;
Ok(GesvdResult { u, sigma, v })
}
pub fn syev_auto_batched(
peer: &mut GpuPeer,
k: &LinalgKernels,
a: &[f64],
batch: u32,
n: u32,
want_v: bool,
) -> Result<(Vec<f64>, Option<Vec<f64>>), GpuPeerError> {
match syev_method_for(n as usize) {
LinalgMethod::Bisection => syev_bisect_batched(peer, k, a, batch, n, want_v),
LinalgMethod::Jacobi => syev_batched(
peer,
k,
a,
batch,
n,
default_sweeps(n as usize),
want_v,
jacobi_shape_for(n as usize, batch as usize),
),
}
}
#[allow(clippy::too_many_arguments)]
pub fn gesvd_auto_batched(
peer: &mut GpuPeer,
k: &LinalgKernels,
a: &[f64],
batch: u32,
m: u32,
n: u32,
want_v: bool,
) -> Result<GesvdResult, GpuPeerError> {
match gesvd_method_for(n as usize) {
LinalgMethod::Bisection => gesvd_bisect_batched(peer, k, a, batch, m, n, want_v),
LinalgMethod::Jacobi => gesvd_batched(
peer,
k,
a,
batch,
m,
n,
default_sweeps(n as usize),
want_v,
jacobi_shape_for(m as usize, batch as usize),
),
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct LuResult {
pub lu: Vec<f64>,
pub piv: Vec<i32>,
pub info: Vec<i32>,
}
fn fetch_i32(peer: &mut GpuPeer, p: &Pinned, elems: usize) -> Result<Vec<i32>, GpuPeerError> {
let mut out = vec![0u8; elems * 4];
peer.fetch_bulk(&p.handle, &mut out)?;
Ok(out.as_chunks::<4>().0.iter().map(|c| i32::from_le_bytes(*c)).collect())
}
pub fn launch_getrf(
peer: &GpuPeer,
k: &LinalgKernels,
a: u64,
piv: u64,
info: u64,
batch: u32,
n: u32,
) -> Result<(), GpuPeerError> {
check_dim(batch > 0 && n > 0, "getrf: empty batch or n")?;
check_dim(n as usize <= LINALG_MAX_N, "getrf: n exceeds LINALG_MAX_N")?;
peer.launch_wide_async(&k.getrf, batch, LINALG_BLOCK, &[a, piv, info], &[batch, n])
}
#[allow(clippy::too_many_arguments)]
pub fn launch_getrs(
peer: &GpuPeer,
k: &LinalgKernels,
lu: u64,
piv: u64,
b: u64,
batch: u32,
n: u32,
nrhs: u32,
identity_rhs: bool,
) -> Result<(), GpuPeerError> {
check_dim(batch > 0 && n > 0 && nrhs > 0, "getrs: empty batch, n, or nrhs")?;
check_dim(n as usize <= LINALG_MAX_N, "getrs: n exceeds LINALG_MAX_N")?;
check_dim(nrhs as usize <= LINALG_MAX_N, "getrs: nrhs exceeds LINALG_MAX_N")?;
check_dim(!identity_rhs || nrhs == n, "getrs: the identity right-hand side needs nrhs == n")?;
let scalars = [batch, n, nrhs, u32::from(identity_rhs)];
peer.launch_wide_async(&k.getrs, batch, LINALG_BLOCK, &[lu, piv, b], &scalars)
}
pub fn getrf_batched(
peer: &mut GpuPeer,
k: &LinalgKernels,
a: &[f64],
batch: u32,
n: u32,
) -> Result<LuResult, GpuPeerError> {
let (bu, nu) = (batch as usize, n as usize);
check_dim(a.len() == bu * nu * nu, "getrf: a length")?;
let pa = pin(peer, &f64_bytes(a))?;
let ppiv = pin(peer, &vec![0u8; bu * nu * 4])?;
let pinfo = pin(peer, &vec![0u8; bu * 4])?;
launch_getrf(peer, k, pa.ptr, ppiv.ptr, pinfo.ptr, batch, n)?;
peer.sync_wide()?;
let lu = fetch_f64(peer, &pa, bu * nu * nu)?;
let piv = fetch_i32(peer, &ppiv, bu * nu)?;
let info = fetch_i32(peer, &pinfo, bu)?;
pinfo.release(peer)?;
ppiv.release(peer)?;
pa.release(peer)?;
Ok(LuResult { lu, piv, info })
}
#[allow(clippy::too_many_arguments)]
pub fn getrs_batched(
peer: &mut GpuPeer,
k: &LinalgKernels,
lu: &[f64],
piv: &[i32],
b: &[f64],
batch: u32,
n: u32,
nrhs: u32,
) -> Result<Vec<f64>, GpuPeerError> {
let (bu, nu, ru) = (batch as usize, n as usize, nrhs as usize);
check_dim(lu.len() == bu * nu * nu, "getrs: lu length")?;
check_dim(piv.len() == bu * nu, "getrs: piv length")?;
check_dim(b.len() == bu * nu * ru, "getrs: b length")?;
let plu = pin(peer, &f64_bytes(lu))?;
let ppiv = pin(peer, &i32_bytes(piv))?;
let pb = pin(peer, &f64_bytes(b))?;
launch_getrs(peer, k, plu.ptr, ppiv.ptr, pb.ptr, batch, n, nrhs, false)?;
peer.sync_wide()?;
let x = fetch_f64(peer, &pb, bu * nu * ru)?;
pb.release(peer)?;
ppiv.release(peer)?;
plu.release(peer)?;
Ok(x)
}
pub fn getri_batched(
peer: &mut GpuPeer,
k: &LinalgKernels,
lu: &[f64],
piv: &[i32],
batch: u32,
n: u32,
) -> Result<Vec<f64>, GpuPeerError> {
let (bu, nu) = (batch as usize, n as usize);
check_dim(lu.len() == bu * nu * nu, "getri: lu length")?;
check_dim(piv.len() == bu * nu, "getri: piv length")?;
let plu = pin(peer, &f64_bytes(lu))?;
let ppiv = pin(peer, &i32_bytes(piv))?;
let pinv = pin(peer, &vec![0u8; bu * nu * nu * 8])?;
launch_getrs(peer, k, plu.ptr, ppiv.ptr, pinv.ptr, batch, n, n, true)?;
peer.sync_wide()?;
let inv = fetch_f64(peer, &pinv, bu * nu * nu)?;
pinv.release(peer)?;
ppiv.release(peer)?;
plu.release(peer)?;
Ok(inv)
}
pub fn lu_det_batched(lu: &[f64], piv: &[i32], batch: usize, n: usize) -> Vec<f64> {
(0..batch)
.map(|item| {
let f = &lu[item * n * n..(item + 1) * n * n];
let pv = &piv[item * n..(item + 1) * n];
let mut det = 1.0;
for (k, &p) in pv.iter().enumerate() {
det *= f[k * n + k];
if p as usize != k {
det = -det;
}
}
det
})
.collect()
}
pub type EigenPairs = (Vec<f64>, Option<Vec<f64>>);
pub const TANDEM_CPU_CHUNK: usize = 64;
pub fn sort_eigenpairs_ascending(w: &mut [f64], v: Option<&mut [f64]>, n: usize) {
if n == 0 {
return;
}
let batch = w.len() / n;
let mut perm: Vec<usize> = Vec::with_capacity(n);
let mut row = vec![0f64; n];
let mut v = v;
for item in 0..batch {
let wi = &mut w[item * n..(item + 1) * n];
perm.clear();
perm.extend(0..n);
perm.sort_by(|&x, &y| wi[x].partial_cmp(&wi[y]).expect("finite eigenvalue"));
let sorted: Vec<f64> = perm.iter().map(|&j| wi[j]).collect();
wi.copy_from_slice(&sorted);
if let Some(v) = v.as_deref_mut() {
let vi = &mut v[item * n * n..(item + 1) * n * n];
for r in 0..n {
row.copy_from_slice(&vi[r * n..(r + 1) * n]);
for (j, &p) in perm.iter().enumerate() {
vi[r * n + j] = row[p];
}
}
}
}
}
pub fn sort_singular_descending(u: &mut [f64], sigma: &mut [f64], v: Option<&mut [f64]>, m: usize, n: usize) {
if n == 0 {
return;
}
let batch = sigma.len() / n;
let mut perm: Vec<usize> = Vec::with_capacity(n);
let mut row = vec![0f64; n];
let mut v = v;
for item in 0..batch {
let si = &mut sigma[item * n..(item + 1) * n];
perm.clear();
perm.extend(0..n);
perm.sort_by(|&x, &y| si[y].partial_cmp(&si[x]).expect("finite singular value"));
let sorted: Vec<f64> = perm.iter().map(|&j| si[j]).collect();
si.copy_from_slice(&sorted);
let ui = &mut u[item * m * n..(item + 1) * m * n];
for r in 0..m {
row.copy_from_slice(&ui[r * n..(r + 1) * n]);
for (j, &p) in perm.iter().enumerate() {
ui[r * n + j] = row[p];
}
}
if let Some(v) = v.as_deref_mut() {
let vi = &mut v[item * n * n..(item + 1) * n * n];
for r in 0..n {
row.copy_from_slice(&vi[r * n..(r + 1) * n]);
for (j, &p) in perm.iter().enumerate() {
vi[r * n + j] = row[p];
}
}
}
}
}
fn tandem_cpu_runs<F>(range: std::ops::Range<usize>, f: F)
where
F: Fn(usize, usize) + Sync,
{
let workers = crate::sched::arena::global_local_arena().total_workers().max(1);
let width = range.len().div_ceil(2 * workers).clamp(1, TANDEM_CPU_CHUNK);
let runs = range.len().div_ceil(width);
let (start, end) = (range.start, range.end);
let plan = JobPlan::set_profile(0, runs as u32, crate::DispatchProfile::LatencyBound);
crate::sched::par_iter::for_each_indexed(&plan, runs, 1, |ri| {
let lo = start + ri * width;
let hi = (lo + width).min(end);
f(lo, hi);
});
}
unsafe fn scatter(dst: usize, at: usize, src: &[f64]) {
unsafe { std::ptr::copy_nonoverlapping(src.as_ptr(), (dst as *mut f64).add(at), src.len()) };
}
#[track_caller]
#[allow(clippy::too_many_arguments)]
pub fn gemm_tandem_batched(
peer: &mut GpuPeer,
k: &LinalgKernels,
plan: &JobPlan,
a: &[f64],
b: &[f64],
batch: u32,
m: u32,
n: u32,
kdim: u32,
) -> Result<(Vec<f64>, SplitReport), GpuPeerError> {
let (bu, mu, nu, ku) = (batch as usize, m as usize, n as usize, kdim as usize);
check_dim(batch > 0 && m > 0 && n > 0 && kdim > 0, "gemm: empty dimension")?;
check_dim(a.len() == bu * mu * ku, "gemm: a length")?;
check_dim(b.len() == bu * ku * nu, "gemm: b length")?;
let (per_a, per_b, per_c) = (mu * ku, ku * nu, mu * nu);
let lanes = plan.k_inner_lanes();
let mut out = vec![0f64; bu * per_c];
let out_addr = out.as_mut_ptr() as usize;
let device_err: Arc<DeviceError> = Arc::new(DeviceError::default());
let err_slot = Arc::clone(&device_err);
let (peer_addr, k_addr) = (peer as *mut GpuPeer as usize, k as *const LinalgKernels as usize);
let (a_addr, a_len, b_addr, b_len) = (a.as_ptr() as usize, a.len(), b.as_ptr() as usize, b.len());
let report = hybrid_auto_split_ranges(
plan,
bu,
|r| {
tandem_cpu_runs(r, |lo, hi| {
let c = cpu::gemm_batched_lanes(
&a[lo * per_a..hi * per_a],
&b[lo * per_b..hi * per_b],
hi - lo,
mu,
nu,
ku,
lanes,
);
unsafe { scatter(out_addr, lo * per_c, &c) };
});
},
move |r| {
let peer = unsafe { &mut *(peer_addr as *mut GpuPeer) };
let k = unsafe { &*(k_addr as *const LinalgKernels) };
let a = unsafe { std::slice::from_raw_parts(a_addr as *const f64, a_len) };
let b = unsafe { std::slice::from_raw_parts(b_addr as *const f64, b_len) };
let (lo, hi) = (r.start, r.end);
match gemm_batched(peer, k, &a[lo * per_a..hi * per_a], &b[lo * per_b..hi * per_b], (hi - lo) as u32, m, n, kdim) {
Ok(c) => unsafe { scatter(out_addr, lo * per_c, &c) },
Err(e) => err_slot.record(e),
}
},
);
if let Some(e) = device_err.take() {
return Err(e);
}
Ok((out, report))
}
#[track_caller]
pub fn syev_tandem_batched(
peer: &mut GpuPeer,
k: &LinalgKernels,
plan: &JobPlan,
a: &[f64],
batch: u32,
n: u32,
want_v: bool,
) -> Result<(EigenPairs, SplitReport), GpuPeerError> {
let (bu, nu) = (batch as usize, n as usize);
check_dim(batch > 0 && n > 0, "syev: empty batch or n")?;
check_dim(a.len() == bu * nu * nu, "syev: a length")?;
let mut w = vec![0f64; bu * nu];
let mut v = if want_v { vec![0f64; bu * nu * nu] } else { Vec::new() };
let (w_addr, v_addr) = (w.as_mut_ptr() as usize, v.as_mut_ptr() as usize);
let device_err: Arc<DeviceError> = Arc::new(DeviceError::default());
let err_slot = Arc::clone(&device_err);
let (peer_addr, k_addr) = (peer as *mut GpuPeer as usize, k as *const LinalgKernels as usize);
let (a_addr, a_len) = (a.as_ptr() as usize, a.len());
let sweeps = default_sweeps(nu);
let report = hybrid_auto_split_ranges(
plan,
bu,
|r| {
tandem_cpu_runs(r, |lo, hi| {
let (mut wc, mut vc) = cpu::syev_jacobi_batched(&a[lo * nu * nu..hi * nu * nu], hi - lo, nu, sweeps, want_v);
sort_eigenpairs_ascending(&mut wc, vc.as_deref_mut(), nu);
unsafe { scatter(w_addr, lo * nu, &wc) };
if let Some(vc) = vc {
unsafe { scatter(v_addr, lo * nu * nu, &vc) };
}
});
},
move |r| {
let peer = unsafe { &mut *(peer_addr as *mut GpuPeer) };
let k = unsafe { &*(k_addr as *const LinalgKernels) };
let a = unsafe { std::slice::from_raw_parts(a_addr as *const f64, a_len) };
let (lo, hi) = (r.start, r.end);
match syev_auto_batched(peer, k, &a[lo * nu * nu..hi * nu * nu], (hi - lo) as u32, n, want_v) {
Ok((mut wd, mut vd)) => {
sort_eigenpairs_ascending(&mut wd, vd.as_deref_mut(), nu);
unsafe { scatter(w_addr, lo * nu, &wd) };
if let Some(vd) = vd {
unsafe { scatter(v_addr, lo * nu * nu, &vd) };
}
}
Err(e) => err_slot.record(e),
}
},
);
if let Some(e) = device_err.take() {
return Err(e);
}
Ok(((w, if want_v { Some(v) } else { None }), report))
}
#[track_caller]
#[allow(clippy::too_many_arguments)]
pub fn gesvd_tandem_batched(
peer: &mut GpuPeer,
k: &LinalgKernels,
plan: &JobPlan,
a: &[f64],
batch: u32,
m: u32,
n: u32,
want_v: bool,
) -> Result<(GesvdResult, SplitReport), GpuPeerError> {
let (bu, mu, nu) = (batch as usize, m as usize, n as usize);
check_dim(batch > 0 && n > 0 && m >= n, "gesvd: empty batch, empty n, or m < n")?;
check_dim(a.len() == bu * mu * nu, "gesvd: a length")?;
let mut u = vec![0f64; bu * mu * nu];
let mut sigma = vec![0f64; bu * nu];
let mut v = if want_v { vec![0f64; bu * nu * nu] } else { Vec::new() };
let (u_addr, s_addr, v_addr) = (u.as_mut_ptr() as usize, sigma.as_mut_ptr() as usize, v.as_mut_ptr() as usize);
let device_err: Arc<DeviceError> = Arc::new(DeviceError::default());
let err_slot = Arc::clone(&device_err);
let (peer_addr, k_addr) = (peer as *mut GpuPeer as usize, k as *const LinalgKernels as usize);
let (a_addr, a_len) = (a.as_ptr() as usize, a.len());
let sweeps = default_sweeps(nu);
let report = hybrid_auto_split_ranges(
plan,
bu,
|r| {
tandem_cpu_runs(r, |lo, hi| {
let (mut uc, mut sc, mut vc) =
cpu::gesvd_jacobi_batched(&a[lo * mu * nu..hi * mu * nu], hi - lo, mu, nu, sweeps, want_v);
sort_singular_descending(&mut uc, &mut sc, vc.as_deref_mut(), mu, nu);
unsafe {
scatter(u_addr, lo * mu * nu, &uc);
scatter(s_addr, lo * nu, &sc);
}
if let Some(vc) = vc {
unsafe { scatter(v_addr, lo * nu * nu, &vc) };
}
});
},
move |r| {
let peer = unsafe { &mut *(peer_addr as *mut GpuPeer) };
let k = unsafe { &*(k_addr as *const LinalgKernels) };
let a = unsafe { std::slice::from_raw_parts(a_addr as *const f64, a_len) };
let (lo, hi) = (r.start, r.end);
match gesvd_auto_batched(peer, k, &a[lo * mu * nu..hi * mu * nu], (hi - lo) as u32, m, n, want_v) {
Ok(mut res) => {
sort_singular_descending(&mut res.u, &mut res.sigma, res.v.as_deref_mut(), mu, nu);
unsafe {
scatter(u_addr, lo * mu * nu, &res.u);
scatter(s_addr, lo * nu, &res.sigma);
}
if let Some(vd) = res.v {
unsafe { scatter(v_addr, lo * nu * nu, &vd) };
}
}
Err(e) => err_slot.record(e),
}
},
);
if let Some(e) = device_err.take() {
return Err(e);
}
Ok((GesvdResult { u, sigma, v: if want_v { Some(v) } else { None } }, report))
}
#[allow(clippy::too_many_arguments)]
pub fn syev_batched(
peer: &mut GpuPeer,
k: &LinalgKernels,
a: &[f64],
batch: u32,
n: u32,
max_sweeps: u32,
want_v: bool,
shape: JacobiShape,
) -> Result<(Vec<f64>, Option<Vec<f64>>), GpuPeerError> {
let (bu, nu) = (batch as usize, n as usize);
check_dim(a.len() == bu * nu * nu, "syev: a length")?;
let pa = pin(peer, &f64_bytes(a))?;
let pw = pin(peer, &vec![0u8; bu * nu * 8])?;
let pv = if want_v { Some(pin(peer, &vec![0u8; bu * nu * nu * 8])?) } else { None };
launch_syev(peer, k, pa.ptr, pw.ptr, pv.as_ref().map(|p| p.ptr), batch, n, max_sweeps, shape)?;
peer.sync_wide()?;
let w = fetch_f64(peer, &pw, bu * nu)?;
let v = match &pv {
Some(p) => Some(fetch_f64(peer, p, bu * nu * nu)?),
None => None,
};
if let Some(p) = pv {
p.release(peer)?;
}
pw.release(peer)?;
pa.release(peer)?;
Ok((w, v))
}
#[derive(Debug, Clone)]
pub struct GesvdResult {
pub u: Vec<f64>,
pub sigma: Vec<f64>,
pub v: Option<Vec<f64>>,
}
#[allow(clippy::too_many_arguments)]
pub fn gesvd_batched(
peer: &mut GpuPeer,
k: &LinalgKernels,
a: &[f64],
batch: u32,
m: u32,
n: u32,
max_sweeps: u32,
want_v: bool,
shape: JacobiShape,
) -> Result<GesvdResult, GpuPeerError> {
let (bu, mu, nu) = (batch as usize, m as usize, n as usize);
check_dim(a.len() == bu * mu * nu, "gesvd: a length")?;
let pa = pin(peer, &f64_bytes(a))?;
let ps = pin(peer, &vec![0u8; bu * nu * 8])?;
let pv = if want_v { Some(pin(peer, &vec![0u8; bu * nu * nu * 8])?) } else { None };
launch_gesvd(
peer, k, pa.ptr, ps.ptr, pv.as_ref().map(|p| p.ptr), batch, m, n, max_sweeps, shape,
)?;
peer.sync_wide()?;
let u = fetch_f64(peer, &pa, bu * mu * nu)?;
let sigma = fetch_f64(peer, &ps, bu * nu)?;
let v = match &pv {
Some(p) => Some(fetch_f64(peer, p, bu * nu * nu)?),
None => None,
};
if let Some(p) = pv {
p.release(peer)?;
}
ps.release(peer)?;
pa.release(peer)?;
Ok(GesvdResult { u, sigma, v })
}
pub fn group_by_shape<S: Ord + Copy>(shapes: &[S]) -> Vec<(S, Vec<usize>)> {
let mut order: Vec<usize> = (0..shapes.len()).collect();
order.sort_by_key(|&i| (shapes[i], i));
let mut groups: Vec<(S, Vec<usize>)> = Vec::new();
for i in order {
match groups.last_mut() {
Some((s, idx)) if *s == shapes[i] => idx.push(i),
_ => groups.push((shapes[i], vec![i])),
}
}
groups
}
pub fn gather_items(src: &[f64], offsets: &[usize], item_len: usize, indices: &[usize]) -> Vec<f64> {
let mut out = Vec::with_capacity(indices.len() * item_len);
for &i in indices {
out.extend_from_slice(&src[offsets[i]..offsets[i] + item_len]);
}
out
}
pub fn scatter_items(batch: &[f64], offsets: &[usize], item_len: usize, indices: &[usize], dst: &mut [f64]) {
for (j, &i) in indices.iter().enumerate() {
dst[offsets[i]..offsets[i] + item_len].copy_from_slice(&batch[j * item_len..(j + 1) * item_len]);
}
}
pub mod cpu {
use super::EinsumSpec;
pub fn getrf_batched(a: &[f64], batch: usize, n: usize) -> (Vec<f64>, Vec<i32>, Vec<i32>) {
let mut lu = a.to_vec();
let mut piv = vec![0i32; batch * n];
let mut info = vec![0i32; batch];
for item in 0..batch {
let s = &mut lu[item * n * n..(item + 1) * n * n];
for k in 0..n {
let mut p = k;
let mut best = s[k * n + k].abs();
for i in k + 1..n {
let v = s[i * n + k].abs();
if v > best {
best = v;
p = i;
}
}
piv[item * n + k] = p as i32;
if s[p * n + k] == 0.0 && info[item] == 0 {
info[item] = k as i32 + 1;
}
if p != k {
for j in 0..n {
s.swap(k * n + j, p * n + j);
}
}
let pivot = s[k * n + k];
if pivot != 0.0 {
for i in k + 1..n {
s[i * n + k] /= pivot;
}
for i in k + 1..n {
let l = s[i * n + k];
for j in k + 1..n {
s[i * n + j] = (-l).mul_add(s[k * n + j], s[i * n + j]);
}
}
}
}
}
(lu, piv, info)
}
pub fn getrs_batched(lu: &[f64], piv: &[i32], b: &[f64], batch: usize, n: usize, nrhs: usize) -> Vec<f64> {
let mut x = b.to_vec();
for item in 0..batch {
let f = &lu[item * n * n..(item + 1) * n * n];
let pv = &piv[item * n..(item + 1) * n];
let xs = &mut x[item * n * nrhs..(item + 1) * n * nrhs];
for (k, &p) in pv.iter().enumerate() {
let p = p as usize;
if p != k {
for j in 0..nrhs {
xs.swap(k * nrhs + j, p * nrhs + j);
}
}
}
for k in 0..n.saturating_sub(1) {
for i in k + 1..n {
let l = f[i * n + k];
for j in 0..nrhs {
xs[i * nrhs + j] = (-l).mul_add(xs[k * nrhs + j], xs[i * nrhs + j]);
}
}
}
for k in (0..n).rev() {
let d = f[k * n + k];
for j in 0..nrhs {
xs[k * nrhs + j] /= d;
}
for i in 0..k {
let u = f[i * n + k];
for j in 0..nrhs {
xs[i * nrhs + j] = (-u).mul_add(xs[k * nrhs + j], xs[i * nrhs + j]);
}
}
}
}
x
}
pub fn getri_batched(lu: &[f64], piv: &[i32], batch: usize, n: usize) -> Vec<f64> {
let mut eye = vec![0f64; batch * n * n];
for item in 0..batch {
for i in 0..n {
eye[item * n * n + i * n + i] = 1.0;
}
}
getrs_batched(lu, piv, &eye, batch, n, n)
}
pub fn einsum(spec: &EinsumSpec, a: &[f64], b: Option<&[f64]>, batch: usize) -> Vec<f64> {
let o_size = spec.out_size();
let a_size = spec.a_size();
let b_size = spec.b_size();
let (a_strides, b_strides, o_strides, c_extents, a_kind, b_kind) =
(spec.part(0), spec.part(1), spec.part(2), spec.part(3), spec.part(4), spec.part(5));
let c_total: usize = c_extents.iter().map(|e| *e as usize).product::<usize>().max(1);
let mut out = vec![0f64; batch * o_size];
let mut p_idx = vec![0i32; o_strides.len()];
let mut c_idx = vec![0i32; c_extents.len()];
let offset = |strides: &[i32], kinds: &[i32], p_idx: &[i32], c_idx: &[i32]| -> usize {
let mut off = 0i32;
for (axis, k) in kinds.iter().enumerate() {
let idx = if (k >> 16) & 0xFFFF == 0 {
p_idx[(k & 0xFFFF) as usize]
} else {
c_idx[(k & 0xFFFF) as usize]
};
off += idx * strides[axis];
}
off as usize
};
for bi in 0..batch {
let ab = &a[bi * a_size..(bi + 1) * a_size];
let bb = b.map(|b| &b[bi * b_size..(bi + 1) * b_size]);
for tid in 0..o_size {
let mut rem = tid as i32;
for (axis, s) in o_strides.iter().enumerate() {
let v = if *s == 0 { 0 } else { rem / s };
p_idx[axis] = v;
rem -= v * s;
}
let mut acc = 0f64;
for c_flat in 0..c_total {
let mut r = c_flat as i32;
for j in (0..c_extents.len()).rev() {
let e = c_extents[j];
let v = if e <= 1 { 0 } else { r % e };
c_idx[j] = v;
if e > 1 {
r /= e;
}
}
let a_off = offset(a_strides, a_kind, &p_idx, &c_idx);
match bb {
Some(bb) => {
let b_off = offset(b_strides, b_kind, &p_idx, &c_idx);
acc = ab[a_off].mul_add(bb[b_off], acc);
}
None => acc += ab[a_off],
}
}
out[bi * o_size + tid] = acc;
}
}
out
}
pub fn gemm_batched(a: &[f64], b: &[f64], batch: usize, m: usize, n: usize, k: usize) -> Vec<f64> {
let mut c = vec![0f64; batch * m * n];
for bi in 0..batch {
let ab = &a[bi * m * k..(bi + 1) * m * k];
let bb = &b[bi * k * n..(bi + 1) * k * n];
let cb = &mut c[bi * m * n..(bi + 1) * m * n];
for i in 0..m {
for j in 0..n {
let mut acc = 0f64;
for kk in 0..k {
acc = ab[i * k + kk].mul_add(bb[kk * n + j], acc);
}
cb[i * n + j] = acc;
}
}
}
c
}
pub fn gemm_batched_lanes(
a: &[f64],
b: &[f64],
batch: usize,
m: usize,
n: usize,
k: usize,
lanes: usize,
) -> Vec<f64> {
if lanes <= 1 {
return gemm_batched(a, b, batch, m, n, k);
}
let mut c = vec![0f64; batch * m * n];
let mut acc = vec![0f64; lanes];
for bi in 0..batch {
let ab = &a[bi * m * k..(bi + 1) * m * k];
let bb = &b[bi * k * n..(bi + 1) * k * n];
let cb = &mut c[bi * m * n..(bi + 1) * m * n];
for i in 0..m {
let arow = &ab[i * k..(i + 1) * k];
let mut j = 0;
while j + lanes <= n {
acc.iter_mut().for_each(|x| *x = 0.0);
for (kk, &aik) in arow.iter().enumerate() {
let brow = &bb[kk * n + j..kk * n + j + lanes];
for (x, &bkj) in acc.iter_mut().zip(brow) {
*x = aik.mul_add(bkj, *x);
}
}
cb[i * n + j..i * n + j + lanes].copy_from_slice(&acc);
j += lanes;
}
while j < n {
let mut one = 0f64;
for (kk, &aik) in arow.iter().enumerate() {
one = aik.mul_add(bb[kk * n + j], one);
}
cb[i * n + j] = one;
j += 1;
}
}
}
c
}
fn jacobi_rotation(s_pp: f64, s_qq: f64, s_pq: f64) -> (f64, f64) {
if s_pq.abs() < 1e-40 {
return (1.0, 0.0);
}
let theta_num = s_qq - s_pp;
let theta_den = 2.0 * s_pq;
let t = if theta_den.abs() < 1e-40 * theta_num.abs() {
0.0
} else {
let theta = theta_num / theta_den;
let disc = (1.0 + theta * theta).sqrt();
if theta >= 0.0 { 1.0 / (theta + disc) } else { 1.0 / (theta - disc) }
};
let c = 1.0 / (1.0 + t * t).sqrt();
(c, c * t)
}
pub fn syev_jacobi(a: &[f64], n: usize, max_sweeps: u32, want_v: bool) -> (Vec<f64>, Option<Vec<f64>>) {
let mut s = vec![0f64; n * n];
for i in 0..n {
for j in 0..n {
s[i * n + j] = 0.5 * (a[i * n + j] + a[j * n + i]);
}
}
let mut v = if want_v {
let mut v = vec![0f64; n * n];
for i in 0..n {
v[i * n + i] = 1.0;
}
Some(v)
} else {
None
};
let mut prev_off: Option<f64> = None;
for _ in 0..max_sweeps {
let mut off = 0f64;
for p in 0..n {
for q in (p + 1)..n {
off = s[p * n + q].mul_add(s[p * n + q], off);
}
}
if off == 0.0 {
break;
}
if let Some(prev) = prev_off
&& off >= prev
{
break;
}
prev_off = Some(off);
for p in 0..n.saturating_sub(1) {
for q in (p + 1)..n {
let (c, sn) = jacobi_rotation(s[p * n + p], s[q * n + q], s[p * n + q]);
if sn == 0.0 && c == 1.0 {
continue;
}
for k in 0..n {
let s_kp = s[k * n + p];
let s_kq = s[k * n + q];
s[k * n + p] = c * s_kp - sn * s_kq;
s[k * n + q] = sn * s_kp + c * s_kq;
}
for k in 0..n {
let s_pk = s[p * n + k];
let s_qk = s[q * n + k];
s[p * n + k] = c * s_pk - sn * s_qk;
s[q * n + k] = sn * s_pk + c * s_qk;
}
let avg = 0.5 * (s[p * n + q] + s[q * n + p]);
s[p * n + q] = avg;
s[q * n + p] = avg;
if let Some(v) = v.as_mut() {
for k in 0..n {
let v_kp = v[k * n + p];
let v_kq = v[k * n + q];
v[k * n + p] = c * v_kp - sn * v_kq;
v[k * n + q] = sn * v_kp + c * v_kq;
}
}
}
}
}
let w: Vec<f64> = (0..n).map(|i| s[i * n + i]).collect();
(w, v)
}
pub fn syev_jacobi_batched(
a: &[f64],
batch: usize,
n: usize,
max_sweeps: u32,
want_v: bool,
) -> (Vec<f64>, Option<Vec<f64>>) {
let mut w = Vec::with_capacity(batch * n);
let mut v = if want_v { Some(Vec::with_capacity(batch * n * n)) } else { None };
for bi in 0..batch {
let (wi, vi) = syev_jacobi(&a[bi * n * n..(bi + 1) * n * n], n, max_sweeps, want_v);
w.extend_from_slice(&wi);
if let (Some(v), Some(vi)) = (v.as_mut(), vi) {
v.extend_from_slice(&vi);
}
}
(w, v)
}
pub fn gesvd_jacobi(
a: &[f64],
m: usize,
n: usize,
max_sweeps: u32,
want_v: bool,
) -> (Vec<f64>, Vec<f64>, Option<Vec<f64>>) {
let tol = f64::EPSILON;
let mut u = a.to_vec();
let mut v = if want_v {
let mut v = vec![0f64; n * n];
for i in 0..n {
v[i * n + i] = 1.0;
}
Some(v)
} else {
None
};
for _ in 0..max_sweeps {
let mut converged = true;
for p in 0..n.saturating_sub(1) {
for q in (p + 1)..n {
let (mut aa, mut bb, mut cc) = (0f64, 0f64, 0f64);
for i in 0..m {
let up = u[i * n + p];
let uq = u[i * n + q];
aa = up.mul_add(up, aa);
bb = uq.mul_add(uq, bb);
cc = up.mul_add(uq, cc);
}
let denom = (aa * bb).sqrt();
if denom == 0.0 || cc.abs() / denom < tol {
continue;
}
converged = false;
let zeta = (bb - aa) / (2.0 * cc);
let mut t = 1.0 / (zeta.abs() + (1.0 + zeta * zeta).sqrt());
if zeta < 0.0 {
t = -t;
}
let c = 1.0 / (1.0 + t * t).sqrt();
let sn = t * c;
for i in 0..m {
let up = u[i * n + p];
let uq = u[i * n + q];
u[i * n + p] = c * up - sn * uq;
u[i * n + q] = sn * up + c * uq;
}
if let Some(v) = v.as_mut() {
for i in 0..n {
let vp = v[i * n + p];
let vq = v[i * n + q];
v[i * n + p] = c * vp - sn * vq;
v[i * n + q] = sn * vp + c * vq;
}
}
}
}
if converged {
break;
}
}
let mut sigma = vec![0f64; n];
for j in 0..n {
let mut ss = 0f64;
for i in 0..m {
ss = u[i * n + j].mul_add(u[i * n + j], ss);
}
let sj = ss.sqrt();
sigma[j] = sj;
if sj > 0.0 {
for i in 0..m {
u[i * n + j] /= sj;
}
}
}
(u, sigma, v)
}
pub fn gesvd_jacobi_batched(
a: &[f64],
batch: usize,
m: usize,
n: usize,
max_sweeps: u32,
want_v: bool,
) -> (Vec<f64>, Vec<f64>, Option<Vec<f64>>) {
let mut u = Vec::with_capacity(batch * m * n);
let mut sigma = Vec::with_capacity(batch * n);
let mut v = if want_v { Some(Vec::with_capacity(batch * n * n)) } else { None };
for bi in 0..batch {
let (ui, si, vi) = gesvd_jacobi(&a[bi * m * n..(bi + 1) * m * n], m, n, max_sweeps, want_v);
u.extend_from_slice(&ui);
sigma.extend_from_slice(&si);
if let (Some(v), Some(vi)) = (v.as_mut(), vi) {
v.extend_from_slice(&vi);
}
}
(u, sigma, v)
}
}
#[derive(Clone, Copy, Debug)]
pub struct LinalgAccelOps {
pub gemm: AccelOpId,
pub syev: AccelOpId,
pub gesvd: AccelOpId,
}
pub fn register_linalg_accel_ops() -> LinalgAccelOps {
fn ptr(a: &KernelArg<'_>) -> u64 {
match a {
KernelArg::U64(p) => *p,
KernelArg::DevicePtr(p) => *p as u64,
other => panic!("linalg accel op: expected a pointer argument, got {other:?}"),
}
}
fn u32_of(a: &KernelArg<'_>) -> u32 {
match a {
KernelArg::U32(v) => *v,
other => panic!("linalg accel op: expected a u32 argument, got {other:?}"),
}
}
let gemm = register_accel_op("flynnel.linalg.gemm_batched_f64", 0, |_count, args| {
let (a, b, c) = (ptr(&args[0]), ptr(&args[1]), ptr(&args[2]));
let (batch, m, n, k) = (
u32_of(&args[3]) as usize,
u32_of(&args[4]) as usize,
u32_of(&args[5]) as usize,
u32_of(&args[6]) as usize,
);
let (a, b, c) = unsafe {
(
std::slice::from_raw_parts(a as *const f64, batch * m * k),
std::slice::from_raw_parts(b as *const f64, batch * k * n),
std::slice::from_raw_parts_mut(c as *mut f64, batch * m * n),
)
};
c.copy_from_slice(&cpu::gemm_batched(a, b, batch, m, n, k));
});
let syev = register_accel_op("flynnel.linalg.syev_jacobi_f64", 0, |_count, args| {
let (a, w, v) = (ptr(&args[0]), ptr(&args[1]), ptr(&args[2]));
let (batch, n, sweeps, want_v) = (
u32_of(&args[3]) as usize,
u32_of(&args[4]) as usize,
u32_of(&args[5]),
u32_of(&args[6]) != 0,
);
let a = unsafe { std::slice::from_raw_parts(a as *const f64, batch * n * n) };
let (wv, vv) = cpu::syev_jacobi_batched(a, batch, n, sweeps, want_v);
unsafe { std::slice::from_raw_parts_mut(w as *mut f64, batch * n) }.copy_from_slice(&wv);
if let Some(vv) = vv {
unsafe { std::slice::from_raw_parts_mut(v as *mut f64, batch * n * n) }
.copy_from_slice(&vv);
}
});
let gesvd = register_accel_op("flynnel.linalg.gesvd_jacobi_f64", 0, |_count, args| {
let (a, s, v) = (ptr(&args[0]), ptr(&args[1]), ptr(&args[2]));
let (batch, m, n, sweeps, want_v) = (
u32_of(&args[3]) as usize,
u32_of(&args[4]) as usize,
u32_of(&args[5]) as usize,
u32_of(&args[6]),
u32_of(&args[7]) != 0,
);
let a_mut = unsafe { std::slice::from_raw_parts_mut(a as *mut f64, batch * m * n) };
let (u, sv, vv) = cpu::gesvd_jacobi_batched(a_mut, batch, m, n, sweeps, want_v);
a_mut.copy_from_slice(&u);
unsafe { std::slice::from_raw_parts_mut(s as *mut f64, batch * n) }.copy_from_slice(&sv);
if let Some(vv) = vv {
unsafe { std::slice::from_raw_parts_mut(v as *mut f64, batch * n * n) }
.copy_from_slice(&vv);
}
});
LinalgAccelOps { gemm, syev, gesvd }
}
pub fn bind_linalg_kernels(ops: &LinalgAccelOps, backend: Backend) -> Result<(), BackendError> {
let ptx = LINALG_PTX.as_bytes();
bind_accel_kernel(ops.gemm, backend, "flynnel_gemm_batched_f64", ptx)?;
bind_accel_kernel(ops.syev, backend, "flynnel_syev_jacobi_f64_blk", ptx)?;
bind_accel_kernel(ops.gesvd, backend, "flynnel_gesvd_jacobi_f64_blk", ptx)?;
Ok(())
}
fn blocks_as_count(blocks: u32) -> u32 {
blocks.max(1) * LINALG_BLOCK
}
#[track_caller]
#[allow(clippy::too_many_arguments)]
pub fn gemm_accel(
plan: &JobPlan,
ops: &LinalgAccelOps,
a: &[f64],
b: &[f64],
c: &mut [f64],
dev: (u64, u64, u64),
batch: u32,
m: u32,
n: u32,
k: u32,
) -> AccelReport {
let tail = [
KernelArg::U32(batch),
KernelArg::U32(m),
KernelArg::U32(n),
KernelArg::U32(k),
KernelArg::U32(k),
KernelArg::U32(n),
KernelArg::U32(n),
];
let cpu_args = [
KernelArg::U64(a.as_ptr() as u64),
KernelArg::U64(b.as_ptr() as u64),
KernelArg::U64(c.as_mut_ptr() as u64),
tail[0], tail[1], tail[2], tail[3], tail[4], tail[5], tail[6],
];
let kernel_args = [
KernelArg::DevicePtr(dev.0 as usize),
KernelArg::DevicePtr(dev.1 as usize),
KernelArg::DevicePtr(dev.2 as usize),
tail[0], tail[1], tail[2], tail[3], tail[4], tail[5], tail[6],
];
let count = blocks_as_count(m.div_ceil(16) * n.div_ceil(16) * batch);
dispatch_accel(plan, ops.gemm, count, &cpu_args, &kernel_args)
}
#[track_caller]
#[allow(clippy::too_many_arguments)]
pub fn syev_accel(
plan: &JobPlan,
ops: &LinalgAccelOps,
a: &[f64],
w: &mut [f64],
v: Option<&mut [f64]>,
dev: (u64, u64, u64),
batch: u32,
n: u32,
max_sweeps: u32,
) -> AccelReport {
let want_v = v.is_some();
let v_ptr = v.map_or(0u64, |v| v.as_mut_ptr() as u64);
let tail = [
KernelArg::U32(batch),
KernelArg::U32(n),
KernelArg::U32(max_sweeps),
KernelArg::U32(u32::from(want_v)),
];
let cpu_args = [
KernelArg::U64(a.as_ptr() as u64),
KernelArg::U64(w.as_mut_ptr() as u64),
KernelArg::U64(v_ptr),
tail[0], tail[1], tail[2], tail[3],
];
let kernel_args = [
KernelArg::DevicePtr(dev.0 as usize),
KernelArg::DevicePtr(dev.1 as usize),
KernelArg::DevicePtr(dev.2 as usize),
tail[0], tail[1], tail[2], tail[3],
];
dispatch_accel(plan, ops.syev, blocks_as_count(batch), &cpu_args, &kernel_args)
}
#[track_caller]
#[allow(clippy::too_many_arguments)]
pub fn gesvd_accel(
plan: &JobPlan,
ops: &LinalgAccelOps,
a: &mut [f64],
sigma: &mut [f64],
v: Option<&mut [f64]>,
dev: (u64, u64, u64),
batch: u32,
m: u32,
n: u32,
max_sweeps: u32,
) -> AccelReport {
let want_v = v.is_some();
let v_ptr = v.map_or(0u64, |v| v.as_mut_ptr() as u64);
let tail = [
KernelArg::U32(batch),
KernelArg::U32(m),
KernelArg::U32(n),
KernelArg::U32(max_sweeps),
KernelArg::U32(u32::from(want_v)),
];
let cpu_args = [
KernelArg::U64(a.as_mut_ptr() as u64),
KernelArg::U64(sigma.as_mut_ptr() as u64),
KernelArg::U64(v_ptr),
tail[0], tail[1], tail[2], tail[3], tail[4],
];
let kernel_args = [
KernelArg::DevicePtr(dev.0 as usize),
KernelArg::DevicePtr(dev.1 as usize),
KernelArg::DevicePtr(dev.2 as usize),
tail[0], tail[1], tail[2], tail[3], tail[4],
];
dispatch_accel(plan, ops.gesvd, blocks_as_count(batch), &cpu_args, &kernel_args)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn jacobi_shape_follows_measured_crossovers() {
use JacobiShape::{BlockPerMatrix as Blk, ThreadPerMatrix as Thr};
assert_eq!(jacobi_shape_for(4, 1024), Thr);
assert_eq!(jacobi_shape_for(4, 512), Blk);
assert_eq!(jacobi_shape_for(8, 1024), Blk);
assert_eq!(jacobi_shape_for(8, 2048), Thr);
assert_eq!(jacobi_shape_for(16, 2048), Blk);
assert_eq!(jacobi_shape_for(16, 4096), Thr);
assert_eq!(jacobi_shape_for(32, 65536), Blk);
assert_eq!(jacobi_shape_for(64, 65536), Blk);
}
#[test]
fn einsum_spec_matmul_tables() {
let s = EinsumSpec::parse("ij,jk->ik", &[2, 3], Some(&[3, 4])).expect("spec");
assert_eq!(s.out_shape(), &[2, 4]);
assert_eq!(s.out_size(), 8);
assert_eq!(s.n_contract, 1);
assert_eq!(s.part(4), &[0, 1 << 16]);
assert_eq!(s.part(5), &[1 << 16, 1]);
assert_eq!(s.part(3), &[3]);
}
#[test]
fn einsum_spec_rejects_mismatch() {
assert!(matches!(
EinsumSpec::parse("ij,jk->ik", &[2, 3], Some(&[5, 4])),
Err(EinsumError::ExtentMismatch { letter: 'j', .. })
));
assert!(matches!(
EinsumSpec::parse("ij->ik", &[2, 3], None),
Err(EinsumError::UnknownOutputAxis('k'))
));
assert!(matches!(
EinsumSpec::parse("ijk->i", &[2, 3], None),
Err(EinsumError::RankMismatch { .. })
));
}
#[test]
fn a_lane_blocked_matmul_is_bit_identical_to_the_one_cell_loop() {
let (batch, m, k) = (3usize, 5usize, 7usize);
for n in [1usize, 2, 3, 4, 5, 7, 8, 9, 16, 17] {
let a: Vec<f64> = (0..batch * m * k).map(|i| (i as f64 * 0.37).sin()).collect();
let b: Vec<f64> = (0..batch * k * n).map(|i| (i as f64 * 0.11).cos()).collect();
let want = cpu::gemm_batched(&a, &b, batch, m, n, k);
for lanes in [0usize, 1, 2, 3, 4, 8, 16, 64] {
let got = cpu::gemm_batched_lanes(&a, &b, batch, m, n, k, lanes);
assert_eq!(got.len(), want.len(), "n={n} lanes={lanes}");
for (i, (g, w)) in got.iter().zip(&want).enumerate() {
assert_eq!(
g.to_bits(),
w.to_bits(),
"n={n} lanes={lanes} cell {i}: {g} vs {w}"
);
}
}
}
}
#[test]
fn cpu_einsum_matches_direct_matmul() {
let (m, k, n) = (3usize, 4usize, 5usize);
let a: Vec<f64> = (0..m * k).map(|i| i as f64 * 0.5 + 1.0).collect();
let b: Vec<f64> = (0..k * n).map(|i| (i as f64).sin()).collect();
let spec = EinsumSpec::parse("ij,jk->ik", &[m, k], Some(&[k, n])).expect("spec");
let e = cpu::einsum(&spec, &a, Some(&b), 1);
let g = cpu::gemm_batched(&a, &b, 1, m, n, k);
assert_eq!(e, g);
}
#[test]
fn cpu_trace_and_axissum() {
let n = 4usize;
let a: Vec<f64> = (0..n * n).map(|i| i as f64).collect();
let tr = cpu::einsum(&EinsumSpec::parse("ii->", &[n, n], None).expect("spec"), &a, None, 1);
let expect_tr: f64 = (0..n).map(|i| a[i * n + i]).sum();
assert_eq!(tr, vec![expect_tr]);
let rows = cpu::einsum(&EinsumSpec::parse("ij->i", &[n, n], None).expect("spec"), &a, None, 1);
for i in 0..n {
let s: f64 = a[i * n..(i + 1) * n].iter().sum();
assert_eq!(rows[i], s);
}
}
#[test]
fn cpu_syev_diagonalizes_known_matrix() {
let (w, v) = cpu::syev_jacobi(&[2.0, 1.0, 1.0, 2.0], 2, default_sweeps(2), true);
let mut sorted = w.clone();
sorted.sort_by(|a, b| a.partial_cmp(b).expect("finite"));
assert!((sorted[0] - 1.0).abs() < 1e-14 && (sorted[1] - 3.0).abs() < 1e-14);
let v = v.expect("vectors");
for (col, lambda) in w.iter().enumerate() {
let x = [v[col], v[2 + col]];
let ax = [2.0 * x[0] + x[1], x[0] + 2.0 * x[1]];
assert!((ax[0] - lambda * x[0]).abs() < 1e-13 && (ax[1] - lambda * x[1]).abs() < 1e-13);
}
}
#[test]
fn cpu_gesvd_recovers_singular_values() {
let (u, s, v) = cpu::gesvd_jacobi(&[3.0, 0.0, 0.0, 2.0], 2, 2, default_sweeps(2), true);
let mut ss = s.clone();
ss.sort_by(|a, b| b.partial_cmp(a).expect("finite"));
assert!((ss[0] - 3.0).abs() < 1e-14 && (ss[1] - 2.0).abs() < 1e-14);
let v = v.expect("v");
for i in 0..2 {
for j in 0..2 {
let mut acc = 0.0;
for k in 0..2 {
acc += u[i * 2 + k] * s[k] * v[j * 2 + k];
}
let want = [[3.0, 0.0], [0.0, 2.0]][i][j];
assert!((acc - want).abs() < 1e-13);
}
}
}
#[test]
fn group_by_shape_covers_every_index_once_in_shape_order() {
let shapes = [(4usize, 4usize), (2, 3), (4, 4), (2, 3), (8, 8), (2, 3)];
let groups = group_by_shape(&shapes);
assert_eq!(groups, vec![((2, 3), vec![1, 3, 5]), ((4, 4), vec![0, 2]), ((8, 8), vec![4])]);
assert!(group_by_shape::<(usize, usize)>(&[]).is_empty());
}
#[test]
fn gather_then_scatter_round_trips_ragged_items() {
let src: Vec<f64> = (0..17).map(|x| x as f64).collect();
let offsets = [0usize, 4, 13];
let small = [0usize, 2];
let batch = gather_items(&src, &offsets, 4, &small);
assert_eq!(batch, vec![0.0, 1.0, 2.0, 3.0, 13.0, 14.0, 15.0, 16.0]);
let doubled: Vec<f64> = batch.iter().map(|x| 2.0 * x).collect();
let mut dst = vec![0f64; 17];
scatter_items(&doubled, &offsets, 4, &small, &mut dst);
assert_eq!(&dst[0..4], &[0.0, 2.0, 4.0, 6.0]);
assert_eq!(&dst[13..17], &[26.0, 28.0, 30.0, 32.0]);
assert!(dst[4..13].iter().all(|&x| x == 0.0), "the untouched item stays zero");
}
}