primal-barracuda 0.4.0

barraCuda — BARrier-free Rust Abstracted Cross-platform Unified Dimensional Algebra. Vendor-agnostic GPU compute via WGSL.
Documentation
// SPDX-License-Identifier: AGPL-3.0-or-later
// LU Decomposition (f64) - Shader-First Implementation
//
// Full f64 precision via WGSL native f64 support (SPIR-V/Vulkan)
// FP64 performance: 1:2-3 (not 1:32 like CUDA consumer cards)
//
// Parallel row elimination for LU factorization: PA = LU
//
// For each column k:
//   1. find_pivot: GPU parallel reduction to find max|A[i,k]| for i >= k
//   2. row_swap: GPU parallel swap rows k and pivot_row
//   3. compute_multipliers: GPU parallel L[i,k] = A[i,k]/A[k,k] for i > k
//   4. row_elimination: GPU parallel A[i,j] -= L[i,k]*A[k,j] for i,j > k
//
// Reference: Golub & Van Loan, "Matrix Computations" (2013)

struct LuParams {
    n: u32,           // Matrix dimension
    k: u32,           // Current elimination column
    pivot_row: u32,   // Row with pivot (from CPU selection)
    _pad: u32,
}

@group(0) @binding(0) var<uniform> params: LuParams;
@group(0) @binding(1) var<storage, read_write> A: array<f64>;    // Matrix [n × n], row-major
@group(0) @binding(2) var<storage, read_write> perm: array<u32>; // Permutation vector [n]

// Row swap: Swap rows pivot_row and k
// Parallel over columns
@compute @workgroup_size(256, 1, 1)
fn row_swap(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let j = global_id.x;  // Column index
    let n = params.n;
    let k = params.k;
    let pivot = params.pivot_row;
    
    if (j >= n || k == pivot) {
        return;
    }
    
    let idx_k = k * n + j;
    let idx_pivot = pivot * n + j;
    
    let temp = A[idx_k];
    A[idx_k] = A[idx_pivot];
    A[idx_pivot] = temp;
}

// Compute L multipliers: L[i,k] = A[i,k] / A[k,k]
// Parallel over rows i > k
@compute @workgroup_size(256, 1, 1)
fn compute_multipliers(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let i = global_id.x + params.k + 1u;  // Row index (i > k)
    let n = params.n;
    let k = params.k;
    
    if (i >= n) {
        return;
    }
    
    let pivot_val = A[k * n + k];
    if (abs(pivot_val) > 1e-14) {
        // Store L[i,k] in place of A[i,k] (below diagonal)
        A[i * n + k] = A[i * n + k] / pivot_val;
    }
}

// Row elimination: A[i,j] -= L[i,k] * A[k,j] for all i > k, j > k
// Parallel over all (i,j) pairs
@compute @workgroup_size(16, 16, 1)
fn row_elimination(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let local_i = global_id.y;  // Relative row index
    let local_j = global_id.x;  // Relative column index
    let n = params.n;
    let k = params.k;
    
    let i = local_i + k + 1u;  // Actual row (i > k)
    let j = local_j + k + 1u;  // Actual column (j > k)
    
    if (i >= n || j >= n) {
        return;
    }
    
    let L_ik = A[i * n + k];    // Multiplier (already computed)
    let A_kj = A[k * n + j];    // Row k element
    
    A[i * n + j] = A[i * n + j] - L_ik * A_kj;
}

// Find pivot: Find max absolute value in column k (rows k to n-1)
// Returns the row index - used for CPU orchestration
// This is a parallel reduction returning an index
struct PivotParams {
    n: u32,
    k: u32,
    _pad1: u32,
    _pad2: u32,
}

@group(0) @binding(0) var<uniform> pivot_params: PivotParams;
@group(0) @binding(1) var<storage, read> A_pivot: array<f64>;
@group(0) @binding(2) var<storage, read_write> pivot_result: array<u32>;  // [row_idx]

var<workgroup> shared_vals: array<f64, 256>;
var<workgroup> shared_idxs: array<u32, 256>;

@compute @workgroup_size(256, 1, 1)
fn find_pivot(@builtin(local_invocation_id) local_id: vec3<u32>,
              @builtin(global_invocation_id) global_id: vec3<u32>) {
    let tid = local_id.x;
    let n = pivot_params.n;
    let k = pivot_params.k;
    
    // Each thread finds max in its portion
    var max_val: f64 = 0.0;
    var max_idx: u32 = k;
    
    var i = k + tid;
    while (i < n) {
        let val = abs(A_pivot[i * n + k]);
        if (val > max_val) {
            max_val = val;
            max_idx = i;
        }
        i = i + 256u;
    }
    
    shared_vals[tid] = max_val;
    shared_idxs[tid] = max_idx;
    workgroupBarrier();
    
    // Parallel reduction to find global max
    for (var stride = 128u; stride > 0u; stride = stride >> 1u) {
        if (tid < stride) {
            if (shared_vals[tid + stride] > shared_vals[tid]) {
                shared_vals[tid] = shared_vals[tid + stride];
                shared_idxs[tid] = shared_idxs[tid + stride];
            }
        }
        workgroupBarrier();
    }
    
    if (tid == 0u) {
        pivot_result[0] = shared_idxs[0];
    }
}

// Forward substitution: Solve Ly = b (L is unit lower triangular)
// Each row depends on previous rows, so we do one row at a time
// But within a row, the dot product is parallel
struct SolveParams {
    n: u32,
    row: u32,         // Current row being solved
    _pad1: u32,
    _pad2: u32,
}

@group(0) @binding(0) var<uniform> solve_params: SolveParams;
@group(0) @binding(1) var<storage, read> L: array<f64>;      // Lower triangular [n × n]
@group(0) @binding(2) var<storage, read_write> y: array<f64>; // Solution/RHS [n]

var<workgroup> partial_dot: array<f64, 256>;

// Compute y[row] = b[row] - Σ_{j<row} L[row,j] * y[j]
// The sum is a parallel reduction
@compute @workgroup_size(256, 1, 1)
fn forward_sub_row(@builtin(local_invocation_id) local_id: vec3<u32>,
                   @builtin(global_invocation_id) global_id: vec3<u32>) {
    let tid = local_id.x;
    let row = solve_params.row;
    let n = solve_params.n;
    
    // Each thread handles multiple elements of the sum
    var sum: f64 = 0.0;
    var j = tid;
    while (j < row) {
        sum = sum + L[row * n + j] * y[j];
        j = j + 256u;
    }
    
    partial_dot[tid] = sum;
    workgroupBarrier();
    
    // Parallel reduction
    for (var stride = 128u; stride > 0u; stride = stride >> 1u) {
        if (tid < stride) {
            partial_dot[tid] = partial_dot[tid] + partial_dot[tid + stride];
        }
        workgroupBarrier();
    }
    
    if (tid == 0u) {
        y[row] = y[row] - partial_dot[0];
    }
}

// Back substitution: Solve Ux = y (U is upper triangular)
// Similar pattern: one row at a time, parallel dot product within row
@group(0) @binding(0) var<uniform> back_params: SolveParams;
@group(0) @binding(1) var<storage, read> U: array<f64>;      // Upper triangular [n × n]
@group(0) @binding(2) var<storage, read_write> x: array<f64>; // Solution [n]

var<workgroup> partial_back: array<f64, 256>;

// Compute x[row] = (y[row] - Σ_{j>row} U[row,j] * x[j]) / U[row,row]
@compute @workgroup_size(256, 1, 1)
fn back_sub_row(@builtin(local_invocation_id) local_id: vec3<u32>,
                @builtin(global_invocation_id) global_id: vec3<u32>) {
    let tid = local_id.x;
    let row = back_params.row;
    let n = back_params.n;
    
    // Sum over j > row
    var sum: f64 = 0.0;
    var j = row + 1u + tid;
    while (j < n) {
        sum = sum + U[row * n + j] * x[j];
        j = j + 256u;
    }
    
    partial_back[tid] = sum;
    workgroupBarrier();
    
    // Parallel reduction
    for (var stride = 128u; stride > 0u; stride = stride >> 1u) {
        if (tid < stride) {
            partial_back[tid] = partial_back[tid] + partial_back[tid + stride];
        }
        workgroupBarrier();
    }
    
    if (tid == 0u) {
        let diag = U[row * n + row];
        if (abs(diag) > 1e-14) {
            x[row] = (x[row] - partial_back[0]) / diag;
        }
    }
}