facett-graphview/src/fdeb_gpu.rs
//! **FDEB on the GPU** — `fdeb::bundle`'s force iteration as a compute shader.
//!
//! The 2026-09-18 note (`.nornir/gpu-prep-in-the-browser.md`) ranked this the best
//! remaining compute-shader fit in the tree: per-point spring + electrostatic
//! iteration over subdivided edges, the same ping-pong storage-buffer shape as
//! [`crate::gpu_layout`]. Compatibility is still computed on the CPU (O(E²) once, a
//! pointer-free table the kernel then reads as CSR); the `iterations × E × m` force
//! loop — the part that grows with iterations — runs on the device.
//!
//! [`bundle_gpu_on`] takes a device the HOST already owns (eframe's, natively or in
//! a browser) and returns the same `Vec<BundledEdge>` as [`crate::fdeb::bundle`].
//! The readback is a blocking `map_async` + `poll`, so this function is NATIVE-only
//! in practice: a browser cannot block its main thread. The non-blocking job form
//! (`gpu_layout::LayoutJob`) is the shape a wasm caller needs and is not written yet —
//! said here so nobody reads "GPU" as "browser".
//!
//! Parity with the CPU lane is held by `cpu_and_gpu_bundle_agree` below, on a real
//! adapter; with no adapter the test prints SKIPPED and fails under CI.
use crate::fdeb::{BundleParams, BundledEdge, P2};
use wgpu::util::DeviceExt;
pub const FDEB_WGSL: &str = include_str!("fdeb.wgsl");
#[repr(C)]
#[derive(Clone, Copy, bytemuck::Pod, bytemuck::Zeroable)]
struct Params {
n: u32,
m: u32,
step: f32,
_pad: f32,
}
#[repr(C)]
#[derive(Clone, Copy, bytemuck::Pod, bytemuck::Zeroable)]
struct EdgeMeta {
kp: f32,
off: u32,
cnt: u32,
_pad: u32,
}
#[repr(C)]
#[derive(Clone, Copy, bytemuck::Pod, bytemuck::Zeroable)]
struct Compat {
q: u32,
c: f32,
}
/// Bundle on a device the caller owns. `None` when there is nothing to bundle or
/// the device refuses the buffers; the caller falls back to [`crate::fdeb::bundle`].
#[must_use]
pub fn bundle_gpu_on(
device: &wgpu::Device,
queue: &wgpu::Queue,
nodes: &[P2],
edges: &[(usize, usize)],
p: &BundleParams,
) -> Option<Vec<BundledEdge>> {
let m = p.subdivisions.max(1);
let n = edges.len();
if n == 0 {
return Some(Vec::new());
}
let stride = m + 2;
// ── the same initialisation as the CPU lane: straight chords, evenly spaced ──
let mut pts: Vec<[f32; 2]> = Vec::with_capacity(n * stride);
let mut endpoints: Vec<(P2, P2)> = Vec::with_capacity(n);
for &(a, b) in edges {
let (pa, pb) = match (nodes.get(a), nodes.get(b)) {
(Some(&pa), Some(&pb)) => (pa, pb),
_ => ([0.0, 0.0], [0.0, 0.0]),
};
endpoints.push((pa, pb));
for i in 0..stride {
let t = i as f32 / (m + 1) as f32;
pts.push([pa[0] + (pb[0] - pa[0]) * t, pa[1] + (pb[1] - pa[1]) * t]);
}
}
// ── compatibility, CPU, symmetric, pruned — laid out as CSR for the kernel ──
let mut lists: Vec<Vec<Compat>> = vec![Vec::new(); n];
for i in 0..n {
let (pi0, pi1) = endpoints[i];
for j in (i + 1)..n {
let (qj0, qj1) = endpoints[j];
let c = crate::fdeb::compatibility(pi0, pi1, qj0, qj1);
if c >= p.compat_threshold {
lists[i].push(Compat { q: j as u32, c });
lists[j].push(Compat { q: i as u32, c });
}
}
}
let mut meta: Vec<EdgeMeta> = Vec::with_capacity(n);
let mut compat: Vec<Compat> = Vec::new();
for (e, l) in lists.iter().enumerate() {
let (pa, pb) = endpoints[e];
let rest = ((pb[0] - pa[0]).powi(2) + (pb[1] - pa[1]).powi(2)).sqrt().max(1e-4);
let kp = p.stiffness / (rest * (m + 1) as f32);
meta.push(EdgeMeta { kp, off: compat.len() as u32, cnt: l.len() as u32, _pad: 0 });
compat.extend_from_slice(l);
}
if compat.is_empty() {
compat.push(Compat { q: 0, c: 0.0 }); // a zero-sized storage buffer is refused
}
let bytes = (pts.len() * 8) as u64;
if bytes > device.limits().max_storage_buffer_binding_size {
return None;
}
let mk_pts = |label: &str| {
device.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some(label),
contents: bytemuck::cast_slice(&pts),
usage: wgpu::BufferUsages::STORAGE | wgpu::BufferUsages::COPY_SRC,
})
};
let buf_a = mk_pts("fdeb-pts-a");
let buf_b = mk_pts("fdeb-pts-b");
let buf_meta = device.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("fdeb-meta"),
contents: bytemuck::cast_slice(&meta),
usage: wgpu::BufferUsages::STORAGE,
});
let buf_compat = device.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("fdeb-compat"),
contents: bytemuck::cast_slice(&compat),
usage: wgpu::BufferUsages::STORAGE,
});
let buf_params = device.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("fdeb-params"),
contents: bytemuck::bytes_of(&Params { n: n as u32, m: m as u32, step: p.step, _pad: 0.0 }),
usage: wgpu::BufferUsages::UNIFORM,
});
let staging = device.create_buffer(&wgpu::BufferDescriptor {
label: Some("fdeb-readback"),
size: bytes,
usage: wgpu::BufferUsages::MAP_READ | wgpu::BufferUsages::COPY_DST,
mapped_at_creation: false,
});
let shader = device.create_shader_module(wgpu::ShaderModuleDescriptor {
label: Some("fdeb"),
source: wgpu::ShaderSource::Wgsl(FDEB_WGSL.into()),
});
let entry = |binding, ty| wgpu::BindGroupLayoutEntry {
binding,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer { ty, has_dynamic_offset: false, min_binding_size: None },
count: None,
};
let ro = wgpu::BufferBindingType::Storage { read_only: true };
let rw = wgpu::BufferBindingType::Storage { read_only: false };
let bgl = device.create_bind_group_layout(&wgpu::BindGroupLayoutDescriptor {
label: Some("fdeb-bgl"),
entries: &[
entry(0, wgpu::BufferBindingType::Uniform),
entry(1, ro),
entry(2, rw),
entry(3, ro),
entry(4, ro),
],
});
let layout = device.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor {
label: Some("fdeb-pl"),
bind_group_layouts: &[Some(&bgl)],
immediate_size: 0,
});
let pipeline = device.create_compute_pipeline(&wgpu::ComputePipelineDescriptor {
label: Some("fdeb-pipeline"),
layout: Some(&layout),
module: &shader,
entry_point: Some("cs_fdeb"),
compilation_options: Default::default(),
cache: None,
});
let bind = |src: &wgpu::Buffer, dst: &wgpu::Buffer| {
device.create_bind_group(&wgpu::BindGroupDescriptor {
label: Some("fdeb-bg"),
layout: &bgl,
entries: &[
wgpu::BindGroupEntry { binding: 0, resource: buf_params.as_entire_binding() },
wgpu::BindGroupEntry { binding: 1, resource: src.as_entire_binding() },
wgpu::BindGroupEntry { binding: 2, resource: dst.as_entire_binding() },
wgpu::BindGroupEntry { binding: 3, resource: buf_meta.as_entire_binding() },
wgpu::BindGroupEntry { binding: 4, resource: buf_compat.as_entire_binding() },
],
})
};
let bg_ab = bind(&buf_a, &buf_b);
let bg_ba = bind(&buf_b, &buf_a);
let mut enc = device.create_command_encoder(&wgpu::CommandEncoderDescriptor { label: Some("fdeb") });
let groups = ((n * m) as u32).div_ceil(64);
for it in 0..p.iterations {
let mut pass = enc.begin_compute_pass(&wgpu::ComputePassDescriptor { label: Some("fdeb-step"), timestamp_writes: None });
pass.set_pipeline(&pipeline);
pass.set_bind_group(0, if it % 2 == 0 { &bg_ab } else { &bg_ba }, &[]);
pass.dispatch_workgroups(groups, 1, 1);
}
// After k iterations the newest points sit in B when k is odd, A when k is even.
let latest = if p.iterations % 2 == 1 { &buf_b } else { &buf_a };
enc.copy_buffer_to_buffer(latest, 0, &staging, 0, bytes);
queue.submit(Some(enc.finish()));
let slice = staging.slice(..);
let (tx, rx) = std::sync::mpsc::channel();
slice.map_async(wgpu::MapMode::Read, move |r| {
let _ = tx.send(r);
});
device.poll(wgpu::PollType::wait_indefinitely()).ok()?;
rx.recv().ok()?.ok()?;
let out: Vec<[f32; 2]> = bytemuck::cast_slice(&slice.get_mapped_range().expect("wgpu: get_mapped_range on a mapped buffer")).to_vec();
staging.unmap();
Some(
edges
.iter()
.enumerate()
.map(|(e, &(from, to))| BundledEdge { from, to, path: out[e * stride..(e + 1) * stride].to_vec() })
.collect(),
)
}
/// Native convenience: make a device, bundle, drop it. `None` with no adapter.
#[must_use]
pub fn bundle_gpu(nodes: &[P2], edges: &[(usize, usize)], p: &BundleParams) -> Option<Vec<BundledEdge>> {
let (device, queue) = crate::gpu_layout::gpu::compute_device()?;
bundle_gpu_on(&device, &queue, nodes, edges, p)
}
#[cfg(test)]
mod tests {
use super::*;
fn graph(seed: u64, n_nodes: usize, n_edges: usize) -> (Vec<P2>, Vec<(usize, usize)>) {
// A tiny LCG so the test needs no rand dependency.
let mut s = seed;
let mut next = move || {
s = s.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
((s >> 33) as f32) / (u32::MAX >> 1) as f32
};
let nodes: Vec<P2> = (0..n_nodes).map(|_| [next() * 100.0, next() * 100.0]).collect();
let edges: Vec<(usize, usize)> = (0..n_edges)
.map(|_| ((next() * n_nodes as f32) as usize % n_nodes, (next() * n_nodes as f32) as usize % n_nodes))
.filter(|(a, b)| a != b)
.collect();
(nodes, edges)
}
#[test]
fn cpu_and_gpu_bundle_agree() {
// THE GPU TURN (facett_core::render::gputurn): one device bring-up at a time.
let _gpu = facett_core::render::gputurn::hold();
let Some((device, queue)) = crate::gpu_layout::gpu::compute_device() else {
eprintln!("[gpu-gate] facett-graphview::fdeb_gpu: SKIPPED — no compute adapter. A skip is not a pass.");
assert!(std::env::var("CI").is_err() && std::env::var("FACETT_REQUIRE_GPU").is_err());
return;
};
let (nodes, edges) = graph(7, 60, 240);
let p = BundleParams::default();
let cpu = crate::fdeb::bundle(&nodes, &edges, &p);
let gpu = bundle_gpu_on(&device, &queue, &nodes, &edges, &p).expect("the device took the buffers");
assert_eq!(cpu.len(), gpu.len());
let mut worst = 0.0f32;
for (c, g) in cpu.iter().zip(&gpu) {
assert_eq!((c.from, c.to), (g.from, g.to));
assert_eq!(c.path.len(), g.path.len());
for (a, b) in c.path.iter().zip(&g.path) {
worst = worst.max((a[0] - b[0]).abs().max((a[1] - b[1]).abs()));
}
}
// 60 iterations of f32 arithmetic in a different summation order over a 100×100
// field: the two lanes agree to well under a hundredth of a unit.
assert!(worst < 1e-2, "CPU and GPU bundling diverge: max |Δ| = {worst}");
// And it is not a no-op: the bundled wires moved off their chords.
let straight = crate::fdeb::straight(&nodes, &edges, p.subdivisions);
let moved = gpu.iter().zip(&straight).any(|(g, s)| g.path.iter().zip(&s.path).any(|(a, b)| (a[0] - b[0]).abs() > 1e-3));
assert!(moved, "the GPU lane returned the straight chords — nothing ran");
}
/// `cargo test -p facett-graphview --features gpu --lib fdeb_gpu -- --ignored --nocapture`
/// prints CPU vs GPU wall time at three edge counts. Ignored by default: a timing
/// is a measurement to read, not an assertion to fail a build on.
#[test]
#[ignore]
fn timing_cpu_vs_gpu() {
let _gpu = facett_core::render::gputurn::hold();
let Some((device, queue)) = crate::gpu_layout::gpu::compute_device() else { return };
for &(nn, ne) in &[(200usize, 500usize), (400, 2000), (800, 8000)] {
let (nodes, edges) = graph(3, nn, ne);
let p = BundleParams::default();
let t = std::time::Instant::now();
let _ = crate::fdeb::bundle(&nodes, &edges, &p);
let cpu = t.elapsed();
let t = std::time::Instant::now();
let _ = bundle_gpu_on(&device, &queue, &nodes, &edges, &p);
let gpu = t.elapsed();
eprintln!("fdeb {ne} edges × {} iters: cpu {cpu:?} · gpu {gpu:?} (incl. CPU compatibility + readback)", p.iterations);
}
}
}