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
// Cyclic Reduction (Odd-Even Reduction) for Tridiagonal Systems
//
// Solves tridiagonal system: a[i]*x[i-1] + b[i]*x[i] + c[i]*x[i+1] = d[i]
//
// PARALLEL ALGORITHM (O(log n) steps vs O(n) for Thomas):
// 1. Reduction phase: Eliminate odd-indexed equations
// 2. After log2(n) reductions, solve 1-element system
// 3. Substitution phase: Back-substitute to recover all x[i]
//
// This is the SHADER-FIRST approach to tridiagonal solve:
// - Same math as Thomas algorithm
// - Parallel execution on GPU
// - When future sequential hardware available, same code runs there
//
// Applications:
// - Crank-Nicolson PDE (TTM, heat equation)
// - Cubic spline interpolation
// - Implicit finite difference
//
// Reference: Hockney & Jesshope, "Parallel Computers" (1988)

struct Params {
    n: u32,           // System size (must be power of 2 for simplicity)
    step: u32,        // Current reduction step (0 = first reduction)
    phase: u32,       // 0 = reduction, 1 = substitution
    _pad: u32,
}

@group(0) @binding(0) var<uniform> params: Params;
@group(0) @binding(1) var<storage, read_write> a: array<f32>;  // Sub-diagonal
@group(0) @binding(2) var<storage, read_write> b: array<f32>;  // Main diagonal
@group(0) @binding(3) var<storage, read_write> c: array<f32>;  // Super-diagonal
@group(0) @binding(4) var<storage, read_write> d: array<f32>;  // RHS / solution

// Reduction step: Eliminate odd-indexed unknowns
// After this, even-indexed equations form a smaller tridiagonal system
@compute @workgroup_size(256, 1, 1)
fn reduction(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let stride = 1u << (params.step + 1u);  // 2^(step+1)
    let half_stride = stride >> 1u;          // 2^step
    
    let i = global_id.x * stride + half_stride;  // Odd indices at this level
    
    if (i >= params.n) {
        return;
    }
    
    let i_prev = i - half_stride;  // Previous even index
    let i_next = i + half_stride;  // Next even index
    
    // Skip boundary cases
    if (i_prev >= params.n || i_next >= params.n) {
        return;
    }
    
    // Compute elimination factors
    let alpha = -a[i] / b[i_prev];
    let gamma = -c[i] / b[i_next];
    
    // Update coefficients for the reduced system
    // New equation for index i combines neighbors
    b[i] = b[i] + alpha * c[i_prev] + gamma * a[i_next];
    d[i] = d[i] + alpha * d[i_prev] + gamma * d[i_next];
    
    // Update connections to farther neighbors
    a[i] = alpha * a[i_prev];
    c[i] = gamma * c[i_next];
}

// Substitution step: Back-substitute to recover solution
@compute @workgroup_size(256, 1, 1)
fn substitution(@builtin(global_invocation_id) global_id: vec3<u32>) {
    let stride = 1u << (params.step + 1u);
    let half_stride = stride >> 1u;
    
    let i = global_id.x * stride + half_stride;
    
    if (i >= params.n) {
        return;
    }
    
    let i_prev = i - half_stride;
    let i_next = i + half_stride;
    
    // x[i] = (d[i] - a[i]*x[i_prev] - c[i]*x[i_next]) / b[i]
    var x_prev: f32 = 0.0;
    var x_next: f32 = 0.0;
    
    if (i_prev < params.n) {
        x_prev = d[i_prev];  // d now holds solution
    }
    if (i_next < params.n) {
        x_next = d[i_next];
    }
    
    d[i] = (d[i] - a[i] * x_prev - c[i] * x_next) / b[i];
}

// Single-pass for small systems (n <= 256)
// Uses shared memory for efficiency
var<workgroup> shared_a: array<f32, 256>;
var<workgroup> shared_b: array<f32, 256>;
var<workgroup> shared_c: array<f32, 256>;
var<workgroup> shared_d: array<f32, 256>;

@compute @workgroup_size(256, 1, 1)
fn solve_small(@builtin(local_invocation_id) local_id: vec3<u32>,
               @builtin(workgroup_id) wg_id: vec3<u32>) {
    let tid = local_id.x;
    let n = params.n;
    
    // Load into shared memory
    if (tid < n) {
        shared_a[tid] = a[tid];
        shared_b[tid] = b[tid];
        shared_c[tid] = c[tid];
        shared_d[tid] = d[tid];
    }
    workgroupBarrier();
    
    // Reduction phase
    var stride = 1u;
    for (var step = 0u; step < 8u; step = step + 1u) {  // log2(256) = 8
        if (stride >= n) { break; }
        
        let half_stride = stride;
        stride = stride << 1u;
        
        let i = tid * stride + half_stride;
        if (i < n) {
            let i_prev = i - half_stride;
            let i_next = i + half_stride;
            
            if (i_prev < n && i_next < n && shared_b[i_prev] != 0.0 && shared_b[i_next] != 0.0) {
                let alpha = -shared_a[i] / shared_b[i_prev];
                let gamma = -shared_c[i] / shared_b[i_next];
                
                shared_b[i] = shared_b[i] + alpha * shared_c[i_prev] + gamma * shared_a[i_next];
                shared_d[i] = shared_d[i] + alpha * shared_d[i_prev] + gamma * shared_d[i_next];
                shared_a[i] = alpha * shared_a[i_prev];
                shared_c[i] = gamma * shared_c[i_next];
            }
        }
        workgroupBarrier();
    }
    
    // Solve the 1-element system at the center
    if (tid == n / 2u - 1u || (n == 1u && tid == 0u)) {
        if (shared_b[tid] != 0.0) {
            shared_d[tid] = shared_d[tid] / shared_b[tid];
        }
    }
    workgroupBarrier();
    
    // Substitution phase (reverse order)
    stride = n;
    for (var step = 0u; step < 8u; step = step + 1u) {
        if (stride <= 1u) { break; }
        
        stride = stride >> 1u;
        let half_stride = stride >> 1u;
        if (half_stride == 0u) { break; }
        
        let i = tid * stride + half_stride;
        if (i < n && i > 0u) {
            let i_prev = i - half_stride;
            let i_next = i + half_stride;
            
            var x_prev: f32 = 0.0;
            var x_next: f32 = 0.0;
            if (i_prev < n) { x_prev = shared_d[i_prev]; }
            if (i_next < n) { x_next = shared_d[i_next]; }
            
            if (shared_b[i] != 0.0) {
                shared_d[i] = (shared_d[i] - shared_a[i] * x_prev - shared_c[i] * x_next) / shared_b[i];
            }
        }
        workgroupBarrier();
    }
    
    // Write back solution
    if (tid < n) {
        d[tid] = shared_d[tid];
    }
}

// =============================================================================
// BATCHED SOLVER: True 2D dispatch for multiple independent systems
// =============================================================================
//
// Each workgroup Y handles one system in the batch.
// Workgroup X threads cooperate on cyclic reduction within that system.
//
// Buffer layout: [batch_size × n_padded] row-major
// - System i data at offset: i * n_padded
//
// This achieves:
// - Zero CPU↔GPU round-trips per system (all batched)
// - Full parallelism across batch AND within each system
// - Efficient memory coalescing

struct BatchParams {
    n: u32,           // System size per batch element
    n_padded: u32,    // Padded to power of 2
    batch_size: u32,  // Number of systems
    step: u32,        // Current reduction step (for multi-pass)
}

@group(1) @binding(0) var<uniform> batch_params: BatchParams;

// Batched solve for small systems (n <= 256)
// Uses 2D dispatch: workgroup Y = batch index, workgroup X threads = element index
@compute @workgroup_size(256, 1, 1)
fn solve_batch_small(@builtin(local_invocation_id) local_id: vec3<u32>,
                     @builtin(workgroup_id) wg_id: vec3<u32>) {
    let tid = local_id.x;
    let batch_idx = wg_id.y;
    let n = batch_params.n;
    let n_padded = batch_params.n_padded;
    
    // Early exit if batch index is out of range
    if (batch_idx >= batch_params.batch_size) {
        return;
    }
    
    // Calculate offset into the flattened buffers
    let offset = batch_idx * n_padded;
    
    // Load this system's data into shared memory
    if (tid < n) {
        shared_a[tid] = a[offset + tid];
        shared_b[tid] = b[offset + tid];
        shared_c[tid] = c[offset + tid];
        shared_d[tid] = d[offset + tid];
    } else if (tid < n_padded) {
        // Pad with identity (b=1, others=0)
        shared_a[tid] = 0.0;
        shared_b[tid] = 1.0;
        shared_c[tid] = 0.0;
        shared_d[tid] = 0.0;
    }
    workgroupBarrier();
    
    // Reduction phase
    var stride = 1u;
    for (var step = 0u; step < 8u; step = step + 1u) {  // log2(256) = 8
        if (stride >= n_padded) { break; }
        
        let half_stride = stride;
        stride = stride << 1u;
        
        let i = tid * stride + half_stride;
        if (i < n_padded) {
            let i_prev = i - half_stride;
            let i_next = i + half_stride;
            
            if (i_prev < n_padded && i_next < n_padded && shared_b[i_prev] != 0.0 && shared_b[i_next] != 0.0) {
                let alpha = -shared_a[i] / shared_b[i_prev];
                let gamma = -shared_c[i] / shared_b[i_next];
                
                shared_b[i] = shared_b[i] + alpha * shared_c[i_prev] + gamma * shared_a[i_next];
                shared_d[i] = shared_d[i] + alpha * shared_d[i_prev] + gamma * shared_d[i_next];
                shared_a[i] = alpha * shared_a[i_prev];
                shared_c[i] = gamma * shared_c[i_next];
            }
        }
        workgroupBarrier();
    }
    
    // Solve the 1-element system at the center
    let center = n_padded / 2u - 1u;
    if (tid == center || (n_padded == 1u && tid == 0u)) {
        if (shared_b[tid] != 0.0) {
            shared_d[tid] = shared_d[tid] / shared_b[tid];
        }
    }
    workgroupBarrier();
    
    // Substitution phase (reverse order)
    stride = n_padded;
    for (var step = 0u; step < 8u; step = step + 1u) {
        if (stride <= 1u) { break; }
        
        stride = stride >> 1u;
        let half_stride = stride >> 1u;
        if (half_stride == 0u) { break; }
        
        let i = tid * stride + half_stride;
        if (i < n_padded && i > 0u) {
            let i_prev = i - half_stride;
            let i_next = i + half_stride;
            
            var x_prev: f32 = 0.0;
            var x_next: f32 = 0.0;
            if (i_prev < n_padded) { x_prev = shared_d[i_prev]; }
            if (i_next < n_padded) { x_next = shared_d[i_next]; }
            
            if (shared_b[i] != 0.0) {
                shared_d[i] = (shared_d[i] - shared_a[i] * x_prev - shared_c[i] * x_next) / shared_b[i];
            }
        }
        workgroupBarrier();
    }
    
    // Write back solution (only original n elements)
    if (tid < n) {
        d[offset + tid] = shared_d[tid];
    }
}

// Batched reduction step for large systems
// 2D dispatch: X = element threads, Y = batch index
@compute @workgroup_size(256, 1, 1)
fn reduction_batch(@builtin(global_invocation_id) global_id: vec3<u32>,
                   @builtin(workgroup_id) wg_id: vec3<u32>) {
    let batch_idx = wg_id.y;
    let n_padded = batch_params.n_padded;
    let step = batch_params.step;
    
    if (batch_idx >= batch_params.batch_size) {
        return;
    }
    
    let offset = batch_idx * n_padded;
    let stride = 1u << (step + 1u);
    let half_stride = stride >> 1u;
    
    let i = global_id.x * stride + half_stride;
    
    if (i >= n_padded) {
        return;
    }
    
    let i_prev = i - half_stride;
    let i_next = i + half_stride;
    
    if (i_prev >= n_padded || i_next >= n_padded) {
        return;
    }
    
    let idx = offset + i;
    let idx_prev = offset + i_prev;
    let idx_next = offset + i_next;
    
    // Compute elimination factors
    let alpha = -a[idx] / b[idx_prev];
    let gamma = -c[idx] / b[idx_next];
    
    // Update coefficients
    b[idx] = b[idx] + alpha * c[idx_prev] + gamma * a[idx_next];
    d[idx] = d[idx] + alpha * d[idx_prev] + gamma * d[idx_next];
    a[idx] = alpha * a[idx_prev];
    c[idx] = gamma * c[idx_next];
}

// Batched substitution step for large systems
@compute @workgroup_size(256, 1, 1)
fn substitution_batch(@builtin(global_invocation_id) global_id: vec3<u32>,
                      @builtin(workgroup_id) wg_id: vec3<u32>) {
    let batch_idx = wg_id.y;
    let n_padded = batch_params.n_padded;
    let step = batch_params.step;
    
    if (batch_idx >= batch_params.batch_size) {
        return;
    }
    
    let offset = batch_idx * n_padded;
    let stride = 1u << (step + 1u);
    let half_stride = stride >> 1u;
    
    let i = global_id.x * stride + half_stride;
    
    if (i >= n_padded) {
        return;
    }
    
    let i_prev = i - half_stride;
    let i_next = i + half_stride;
    let idx = offset + i;
    
    var x_prev: f32 = 0.0;
    var x_next: f32 = 0.0;
    
    if (i_prev < n_padded) {
        x_prev = d[offset + i_prev];
    }
    if (i_next < n_padded) {
        x_next = d[offset + i_next];
    }
    
    d[idx] = (d[idx] - a[idx] * x_prev - c[idx] * x_next) / b[idx];
}