use crate::device::WgpuDevice;
use crate::device::capabilities::WORKGROUP_SIZE_1D;
use crate::device::compute_pipeline::ComputeDispatch;
use crate::error::Result;
use bytemuck::{Pod, Zeroable};
use std::sync::Arc;
#[repr(C)]
#[derive(Copy, Clone, Pod, Zeroable)]
struct FelsensteinParamsGpu {
n_sites: u32,
n_nodes_this_level: u32,
n_states: u32,
n_nodes_total: u32,
}
pub struct PhyloTree {
pub left_child: Vec<i32>,
pub right_child: Vec<i32>,
pub branch_lengths: Vec<f64>,
pub levels: Vec<Vec<u32>>,
}
impl PhyloTree {
#[must_use]
pub fn n_nodes(&self) -> usize {
self.left_child.len()
}
}
pub struct FelsensteinGpu {
device: Arc<WgpuDevice>,
}
pub struct FelsensteinResult {
pub likelihoods: Vec<f64>,
pub n_nodes: usize,
pub n_sites: usize,
pub n_states: usize,
}
impl FelsensteinResult {
#[must_use]
pub fn root_likelihoods(&self, root_node: usize) -> &[f64] {
let stride = self.n_sites * self.n_states;
&self.likelihoods[root_node * stride..(root_node + 1) * stride]
}
#[must_use]
pub fn log_likelihood(&self, root_node: usize, pi: &[f64]) -> f64 {
let root = self.root_likelihoods(root_node);
let mut log_lik = 0.0_f64;
for site in 0..self.n_sites {
let mut site_lik = 0.0_f64;
for s in 0..self.n_states {
site_lik = pi[s].mul_add(root[site * self.n_states + s], site_lik);
}
log_lik += site_lik.max(f64::MIN_POSITIVE).ln();
}
log_lik
}
}
impl FelsensteinGpu {
#[must_use]
pub fn new(device: &WgpuDevice) -> Self {
Self::with_device(Arc::new(device.clone()))
}
#[must_use]
pub fn with_device(device: Arc<WgpuDevice>) -> Self {
Self { device }
}
pub fn prune(
&self,
tree: &PhyloTree,
tip_likelihoods: &[f64],
transition_probs: &[f64],
n_sites: usize,
n_states: usize,
) -> Result<FelsensteinResult> {
let dev = &self.device;
let n_nodes = tree.n_nodes();
let left_buf = dev
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("Fels left_child"),
contents: bytemuck::cast_slice(&tree.left_child),
usage: wgpu::BufferUsages::STORAGE,
});
let right_buf = dev
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("Fels right_child"),
contents: bytemuck::cast_slice(&tree.right_child),
usage: wgpu::BufferUsages::STORAGE,
});
let tp_buf = dev
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("Fels transition_probs"),
contents: bytemuck::cast_slice(transition_probs),
usage: wgpu::BufferUsages::STORAGE,
});
let lik_buf = dev
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("Fels likelihoods"),
contents: bytemuck::cast_slice(tip_likelihoods),
usage: wgpu::BufferUsages::STORAGE | wgpu::BufferUsages::COPY_SRC,
});
const SHADER: &str = include_str!("../../shaders/bio/felsenstein_f64.wgsl");
for level_nodes in &tree.levels {
if level_nodes.is_empty() {
continue;
}
let has_internal = level_nodes
.iter()
.any(|&n| tree.left_child[n as usize] >= 0);
if !has_internal {
continue;
}
let node_ids_buf = dev
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: None,
contents: bytemuck::cast_slice(level_nodes),
usage: wgpu::BufferUsages::STORAGE,
});
let params = FelsensteinParamsGpu {
n_sites: n_sites as u32,
n_nodes_this_level: level_nodes.len() as u32,
n_states: n_states as u32,
n_nodes_total: n_nodes as u32,
};
let params_buf = dev
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: None,
contents: bytemuck::bytes_of(¶ms),
usage: wgpu::BufferUsages::UNIFORM,
});
let total = (level_nodes.len() * n_sites) as u32;
ComputeDispatch::new(dev, "FelsensteinF64")
.shader(SHADER, "main")
.f64()
.uniform(0, ¶ms_buf)
.storage_read(1, &node_ids_buf)
.storage_read(2, &left_buf)
.storage_read(3, &right_buf)
.storage_read(4, &tp_buf)
.storage_rw(5, &lik_buf)
.dispatch(total.div_ceil(WORKGROUP_SIZE_1D), 1, 1)
.submit()?;
}
let likelihoods = dev.read_buffer_f64(&lik_buf, n_nodes * n_sites * n_states)?;
Ok(FelsensteinResult {
likelihoods,
n_nodes,
n_sites,
n_states,
})
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::device::test_pool;
fn eye_tp(n_nodes: usize) -> Vec<f64> {
let eye: [f64; 16] = [
1., 0., 0., 0., 0., 1., 0., 0., 0., 0., 1., 0., 0., 0., 0., 1.,
];
eye.iter().copied().cycle().take(n_nodes * 16).collect()
}
#[tokio::test]
async fn test_root_inherits_identical_tips() {
let Some(device) = test_pool::get_test_device_if_f64_gpu_available().await else {
return;
};
let pruner = FelsensteinGpu::new(&device);
let tree = PhyloTree {
left_child: vec![1, -1, -1],
right_child: vec![2, -1, -1],
branch_lengths: vec![0.1, 0.1, 0.1],
levels: vec![vec![1, 2], vec![0]],
};
let n_sites = 1;
let n_states = 4;
let mut lik = vec![0.0_f64; 3 * n_sites * n_states];
lik[n_states] = 1.0;
lik[2 * n_states] = 1.0;
let tp = eye_tp(3);
let result = pruner.prune(&tree, &lik, &tp, n_sites, n_states).unwrap();
let root = result.root_likelihoods(0);
assert!(
(root[0] - 1.0).abs() < 1e-9,
"root L[A] should be 1.0, got {}",
root[0]
);
assert!(
root[1].abs() < 1e-9,
"root L[C] should be 0.0, got {}",
root[1]
);
}
#[tokio::test]
async fn test_log_likelihood_two_sites() {
let Some(device) = test_pool::get_test_device_if_f64_gpu_available().await else {
return;
};
let pruner = FelsensteinGpu::new(&device);
let tree = PhyloTree {
left_child: vec![1, -1, -1],
right_child: vec![2, -1, -1],
branch_lengths: vec![0.1, 0.1, 0.1],
levels: vec![vec![1, 2], vec![0]],
};
let n_sites = 2;
let n_states = 4;
let mut lik = vec![0.0_f64; 3 * n_sites * n_states];
lik[n_sites * n_states] = 1.0; lik[n_sites * n_states + n_states + 1] = 1.0; lik[2 * n_sites * n_states] = 1.0; lik[2 * n_sites * n_states + n_states + 1] = 1.0;
let tp = eye_tp(3);
let result = pruner.prune(&tree, &lik, &tp, n_sites, n_states).unwrap();
let pi = vec![0.25_f64; 4];
let log_lik = result.log_likelihood(0, &pi);
let expected = 2.0 * (0.25_f64).ln();
assert!(
(log_lik - expected).abs() < 1e-9,
"log_lik={log_lik:.6}, expected={expected:.6}"
);
}
}