use super::csr::CsrMatrix;
use crate::device::WgpuDevice;
use crate::device::capabilities::WORKGROUP_SIZE_1D;
use crate::error::{BarracudaError, Result};
use std::sync::Arc;
#[derive(Debug, Clone)]
pub struct BiCgStabGpuResult {
pub x: Vec<f64>,
pub iterations: usize,
pub residual: f64,
pub converged: bool,
}
impl BiCgStabGpuResult {
#[must_use]
pub fn is_ok(&self) -> bool {
self.converged
}
}
pub struct BiCgStabGpu;
impl BiCgStabGpu {
fn spmv_shader() -> &'static str {
include_str!("../../shaders/sparse/spmv_f64.wgsl")
}
fn dot_reduce_shader() -> &'static str {
include_str!("../../shaders/sparse/dot_reduce_f64.wgsl")
}
pub fn solve(
device: Arc<WgpuDevice>,
a: &CsrMatrix,
b: &[f64],
tol: f64,
max_iter: usize,
) -> Result<BiCgStabGpuResult> {
let n = a.n_rows;
if a.n_cols != n {
return Err(BarracudaError::InvalidInput {
message: "BiCGSTAB requires square matrix".to_string(),
});
}
if b.len() != n {
return Err(BarracudaError::InvalidInput {
message: format!("Vector length {} doesn't match matrix size {}", b.len(), n),
});
}
let b_norm: f64 = b.iter().map(|x| x * x).sum::<f64>().sqrt();
if b_norm < 1e-14 {
return Ok(BiCgStabGpuResult {
x: vec![0.0; n],
iterations: 0,
residual: 0.0,
converged: true,
});
}
let values_buffer = Self::create_f64_buffer(&device, "BiCG values", &a.values);
let col_indices_buffer = Self::create_u32_buffer(&device, "BiCG col_idx", &a.col_indices);
let row_ptrs_buffer = Self::create_u32_buffer(&device, "BiCG row_ptr", &a.row_ptr);
let x_buffer = Self::create_zero_f64_buffer(&device, "BiCG x", n);
let r_buffer = Self::create_f64_buffer(&device, "BiCG r", b); let r_hat_buffer = Self::create_f64_buffer(&device, "BiCG r_hat", b); let p_buffer = Self::create_zero_f64_buffer(&device, "BiCG p", n);
let v_buffer = Self::create_zero_f64_buffer(&device, "BiCG v", n);
let s_buffer = Self::create_zero_f64_buffer(&device, "BiCG s", n);
let t_buffer = Self::create_zero_f64_buffer(&device, "BiCG t", n);
let _temp_buffer = Self::create_zero_f64_buffer(&device, "BiCG temp", n);
let num_workgroups = n.div_ceil(WORKGROUP_SIZE_1D as usize);
let _partial_sums_buffer =
Self::create_zero_f64_buffer(&device, "BiCG partial", num_workgroups);
let spmv_shader = device.compile_shader_f64(Self::spmv_shader(), Some("BiCGSTAB SpMV"));
let dot_reduce_shader =
device.compile_shader_f64(Self::dot_reduce_shader(), Some("BiCGSTAB Dot"));
let spmv_bgl = Self::create_spmv_bgl(&device);
let dot_bgl = Self::create_dot_bgl(&device);
let spmv_pl = device
.device
.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor {
label: Some("SpMV PL"),
bind_group_layouts: &[&spmv_bgl],
immediate_size: 0,
});
let dot_pl = device
.device
.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor {
label: Some("Dot PL"),
bind_group_layouts: &[&dot_bgl],
immediate_size: 0,
});
let spmv_pipeline =
device
.device
.create_compute_pipeline(&wgpu::ComputePipelineDescriptor {
label: Some("SpMV f64"),
layout: Some(&spmv_pl),
module: &spmv_shader,
entry_point: Some("spmv_f64"),
cache: None,
compilation_options: Default::default(),
});
let _dot_pipeline =
device
.device
.create_compute_pipeline(&wgpu::ComputePipelineDescriptor {
label: Some("Dot f64"),
layout: Some(&dot_pl),
module: &dot_reduce_shader,
entry_point: Some("dot_f64"),
cache: None,
compilation_options: Default::default(),
});
let spmv_params = [n as u32];
let spmv_params_buf = device
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("SpMV params"),
contents: bytemuck::cast_slice(&spmv_params),
usage: wgpu::BufferUsages::UNIFORM,
});
let dot_params = [n as u32];
let _dot_params_buf = device
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some("Dot params"),
contents: bytemuck::cast_slice(&dot_params),
usage: wgpu::BufferUsages::UNIFORM,
});
let mut rho: f64 = 1.0;
let mut alpha: f64 = 1.0;
let mut omega: f64 = 1.0;
for iter in 0..max_iter {
let r_data = device.read_f64_buffer(&r_buffer, n)?;
let r_hat_data = device.read_f64_buffer(&r_hat_buffer, n)?;
let rho_new: f64 = r_data.iter().zip(&r_hat_data).map(|(a, b)| a * b).sum();
if rho_new.abs() < 1e-14 {
let x_data = device.read_f64_buffer(&x_buffer, n)?;
let r_norm: f64 = r_data.iter().map(|x| x * x).sum::<f64>().sqrt();
return Ok(BiCgStabGpuResult {
x: x_data,
iterations: iter + 1,
residual: r_norm / b_norm,
converged: false,
});
}
let beta = (rho_new / rho) * (alpha / omega);
rho = rho_new;
let p_data = device.read_f64_buffer(&p_buffer, n)?;
let v_data = device.read_f64_buffer(&v_buffer, n)?;
let new_p: Vec<f64> = r_data
.iter()
.zip(&p_data)
.zip(&v_data)
.map(|((ri, pi), vi)| ri + beta * (pi - omega * vi))
.collect();
Self::write_f64_buffer(&device, &p_buffer, &new_p);
let spmv_p_bg = device.device.create_bind_group(&wgpu::BindGroupDescriptor {
label: Some("SpMV p BG"),
layout: &spmv_bgl,
entries: &[
wgpu::BindGroupEntry {
binding: 0,
resource: values_buffer.as_entire_binding(),
},
wgpu::BindGroupEntry {
binding: 1,
resource: col_indices_buffer.as_entire_binding(),
},
wgpu::BindGroupEntry {
binding: 2,
resource: row_ptrs_buffer.as_entire_binding(),
},
wgpu::BindGroupEntry {
binding: 3,
resource: p_buffer.as_entire_binding(),
},
wgpu::BindGroupEntry {
binding: 4,
resource: v_buffer.as_entire_binding(),
},
wgpu::BindGroupEntry {
binding: 5,
resource: spmv_params_buf.as_entire_binding(),
},
],
});
let mut encoder = device.create_encoder_guarded(&wgpu::CommandEncoderDescriptor {
label: Some("SpMV p"),
});
{
let mut pass = encoder.begin_compute_pass(&wgpu::ComputePassDescriptor {
label: Some("SpMV p Pass"),
timestamp_writes: None,
});
pass.set_pipeline(&spmv_pipeline);
pass.set_bind_group(0, Some(&spmv_p_bg), &[]);
pass.dispatch_workgroups((n as u32).div_ceil(WORKGROUP_SIZE_1D), 1, 1);
}
device.submit_commands(Some(encoder.finish()));
let v_data = device.read_f64_buffer(&v_buffer, n)?;
let rv: f64 = r_hat_data.iter().zip(&v_data).map(|(a, b)| a * b).sum();
if rv.abs() < 1e-14 {
let x_data = device.read_f64_buffer(&x_buffer, n)?;
let r_norm: f64 = r_data.iter().map(|x| x * x).sum::<f64>().sqrt();
return Ok(BiCgStabGpuResult {
x: x_data,
iterations: iter + 1,
residual: r_norm / b_norm,
converged: false,
});
}
alpha = rho / rv;
let s_data: Vec<f64> = r_data
.iter()
.zip(&v_data)
.map(|(ri, vi)| ri - alpha * vi)
.collect();
let s_norm: f64 = s_data.iter().map(|x| x * x).sum::<f64>().sqrt();
if s_norm / b_norm < tol {
let x_data = device.read_f64_buffer(&x_buffer, n)?;
let new_x: Vec<f64> = x_data
.iter()
.zip(&new_p)
.map(|(xi, pi)| xi + alpha * pi)
.collect();
return Ok(BiCgStabGpuResult {
x: new_x,
iterations: iter + 1,
residual: s_norm / b_norm,
converged: true,
});
}
Self::write_f64_buffer(&device, &s_buffer, &s_data);
let spmv_s_bg = device.device.create_bind_group(&wgpu::BindGroupDescriptor {
label: Some("SpMV s BG"),
layout: &spmv_bgl,
entries: &[
wgpu::BindGroupEntry {
binding: 0,
resource: values_buffer.as_entire_binding(),
},
wgpu::BindGroupEntry {
binding: 1,
resource: col_indices_buffer.as_entire_binding(),
},
wgpu::BindGroupEntry {
binding: 2,
resource: row_ptrs_buffer.as_entire_binding(),
},
wgpu::BindGroupEntry {
binding: 3,
resource: s_buffer.as_entire_binding(),
},
wgpu::BindGroupEntry {
binding: 4,
resource: t_buffer.as_entire_binding(),
},
wgpu::BindGroupEntry {
binding: 5,
resource: spmv_params_buf.as_entire_binding(),
},
],
});
let mut encoder = device.create_encoder_guarded(&wgpu::CommandEncoderDescriptor {
label: Some("SpMV s"),
});
{
let mut pass = encoder.begin_compute_pass(&wgpu::ComputePassDescriptor {
label: Some("SpMV s Pass"),
timestamp_writes: None,
});
pass.set_pipeline(&spmv_pipeline);
pass.set_bind_group(0, Some(&spmv_s_bg), &[]);
pass.dispatch_workgroups((n as u32).div_ceil(WORKGROUP_SIZE_1D), 1, 1);
}
device.submit_commands(Some(encoder.finish()));
let t_data = device.read_f64_buffer(&t_buffer, n)?;
let ts: f64 = t_data.iter().zip(&s_data).map(|(ti, si)| ti * si).sum();
let tt: f64 = t_data.iter().map(|ti| ti * ti).sum();
omega = if tt.abs() < 1e-14 { 0.0 } else { ts / tt };
let x_data = device.read_f64_buffer(&x_buffer, n)?;
let new_x: Vec<f64> = x_data
.iter()
.zip(&new_p)
.zip(&s_data)
.map(|((xi, pi), si)| xi + alpha * pi + omega * si)
.collect();
Self::write_f64_buffer(&device, &x_buffer, &new_x);
let new_r: Vec<f64> = s_data
.iter()
.zip(&t_data)
.map(|(si, ti)| si - omega * ti)
.collect();
let r_norm: f64 = new_r.iter().map(|x| x * x).sum::<f64>().sqrt();
if r_norm / b_norm < tol {
return Ok(BiCgStabGpuResult {
x: new_x,
iterations: iter + 1,
residual: r_norm / b_norm,
converged: true,
});
}
Self::write_f64_buffer(&device, &r_buffer, &new_r);
if omega.abs() < 1e-14 {
return Ok(BiCgStabGpuResult {
x: new_x,
iterations: iter + 1,
residual: r_norm / b_norm,
converged: false,
});
}
}
let x_data = device.read_f64_buffer(&x_buffer, n)?;
let r_data = device.read_f64_buffer(&r_buffer, n)?;
let r_norm: f64 = r_data.iter().map(|x| x * x).sum::<f64>().sqrt();
Ok(BiCgStabGpuResult {
x: x_data,
iterations: max_iter,
residual: r_norm / b_norm,
converged: false,
})
}
fn create_f64_buffer(device: &Arc<WgpuDevice>, label: &str, data: &[f64]) -> wgpu::Buffer {
let bytes: &[u8] = bytemuck::cast_slice(data);
device
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some(label),
contents: bytes,
usage: wgpu::BufferUsages::STORAGE
| wgpu::BufferUsages::COPY_SRC
| wgpu::BufferUsages::COPY_DST,
})
}
fn create_zero_f64_buffer(device: &Arc<WgpuDevice>, label: &str, count: usize) -> wgpu::Buffer {
let zeros = vec![0u8; count * 8];
device
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some(label),
contents: &zeros,
usage: wgpu::BufferUsages::STORAGE
| wgpu::BufferUsages::COPY_SRC
| wgpu::BufferUsages::COPY_DST,
})
}
fn create_u32_buffer(device: &Arc<WgpuDevice>, label: &str, data: &[usize]) -> wgpu::Buffer {
let u32_data: Vec<u32> = data.iter().map(|&x| x as u32).collect();
device
.device
.create_buffer_init(&wgpu::util::BufferInitDescriptor {
label: Some(label),
contents: bytemuck::cast_slice(&u32_data),
usage: wgpu::BufferUsages::STORAGE,
})
}
fn write_f64_buffer(device: &Arc<WgpuDevice>, buffer: &wgpu::Buffer, data: &[f64]) {
let bytes: &[u8] = bytemuck::cast_slice(data);
device.queue.write_buffer(buffer, 0, bytes);
}
fn create_spmv_bgl(device: &Arc<WgpuDevice>) -> wgpu::BindGroupLayout {
device
.device
.create_bind_group_layout(&wgpu::BindGroupLayoutDescriptor {
label: Some("SpMV BGL"),
entries: &[
wgpu::BindGroupLayoutEntry {
binding: 0,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only: true },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
wgpu::BindGroupLayoutEntry {
binding: 1,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only: true },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
wgpu::BindGroupLayoutEntry {
binding: 2,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only: true },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
wgpu::BindGroupLayoutEntry {
binding: 3,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only: true },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
wgpu::BindGroupLayoutEntry {
binding: 4,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only: false },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
wgpu::BindGroupLayoutEntry {
binding: 5,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Uniform,
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
],
})
}
fn create_dot_bgl(device: &Arc<WgpuDevice>) -> wgpu::BindGroupLayout {
device
.device
.create_bind_group_layout(&wgpu::BindGroupLayoutDescriptor {
label: Some("Dot BGL"),
entries: &[
wgpu::BindGroupLayoutEntry {
binding: 0,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only: true },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
wgpu::BindGroupLayoutEntry {
binding: 1,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only: true },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
wgpu::BindGroupLayoutEntry {
binding: 2,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Storage { read_only: false },
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
wgpu::BindGroupLayoutEntry {
binding: 3,
visibility: wgpu::ShaderStages::COMPUTE,
ty: wgpu::BindingType::Buffer {
ty: wgpu::BufferBindingType::Uniform,
has_dynamic_offset: false,
min_binding_size: None,
},
count: None,
},
],
})
}
}
#[cfg(test)]
mod tests {
use super::*;
#[tokio::test]
async fn test_bicgstab_gpu_non_symmetric() {
let Some(device) = crate::device::test_pool::get_test_device_if_f64_gpu_available().await
else {
return; };
let a = CsrMatrix::from_triplets(
3,
3,
&[
(0, 0, 4.0),
(0, 1, 1.0),
(1, 0, -1.0),
(1, 1, 3.0),
(1, 2, 1.0),
(2, 1, -1.0),
(2, 2, 2.0),
],
);
let b = vec![1.0, 2.0, 3.0];
let result = BiCgStabGpu::solve(device, &a, &b, 1e-10, 100).unwrap();
assert!(result.converged, "BiCGSTAB should converge");
let ax = a.matvec(&result.x).unwrap();
for (axi, bi) in ax.iter().zip(b.iter()) {
assert!((axi - bi).abs() < 1e-8, "Ax should equal b");
}
}
}