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
// L-BFGS Two-Loop Recursion — f64 canonical
//
// Implements the Nocedal (1980) two-loop recursion on GPU:
//   d = -H_k · g_k
//
// where H_k is the limited-memory BFGS inverse Hessian approximation
// stored implicitly via m correction pairs (s_i, y_i).
//
// Operates on batched problems: `batch_size` independent L-BFGS instances
// each with `n` dimensions and `m_used` stored pairs.

struct Params {
    n: u32,
    m_capacity: u32,
    m_used: u32,
    batch_size: u32,
}

@group(0) @binding(0) var<uniform> params: Params;
// gradient: [batch_size * n]
@group(0) @binding(1) var<storage, read> gradient: array<f64>;
// s_history: [m_capacity * batch_size * n] — position differences
@group(0) @binding(2) var<storage, read> s_history: array<f64>;
// y_history: [m_capacity * batch_size * n] — gradient differences
@group(0) @binding(3) var<storage, read> y_history: array<f64>;
// rho: [m_capacity * batch_size]
@group(0) @binding(4) var<storage, read> rho: array<f64>;
// alpha_buf: [m_capacity * batch_size] — scratch for backward loop
@group(0) @binding(5) var<storage, read_write> alpha_buf: array<f64>;
// direction: [batch_size * n] — output descent direction
@group(0) @binding(6) var<storage, read_write> direction: array<f64>;

@compute @workgroup_size(64, 1, 1)
fn two_loop_recursion(@builtin(global_invocation_id) gid: vec3<u32>) {
    let b = gid.x;
    if (b >= params.batch_size) {
        return;
    }
    let n = params.n;
    let m = params.m_used;
    let mc = params.m_capacity;
    let b_off = b * n;

    // q = gradient[b]
    for (var j = 0u; j < n; j = j + 1u) {
        direction[b_off + j] = gradient[b_off + j];
    }

    // Backward loop: i = m-1 .. 0
    for (var ii = 0u; ii < m; ii = ii + 1u) {
        let i = m - 1u - ii;
        let s_off = (i * params.batch_size + b) * n;
        let rho_idx = i * params.batch_size + b;
        var dot: f64 = 0.0;
        for (var j = 0u; j < n; j = j + 1u) {
            dot = dot + s_history[s_off + j] * direction[b_off + j];
        }
        let alpha_i = rho[rho_idx] * dot;
        alpha_buf[i * params.batch_size + b] = alpha_i;
        let y_off = (i * params.batch_size + b) * n;
        for (var j = 0u; j < n; j = j + 1u) {
            direction[b_off + j] = direction[b_off + j] - alpha_i * y_history[y_off + j];
        }
    }

    // Scale by initial Hessian: H_0 = gamma * I
    if (m > 0u) {
        let last = m - 1u;
        let s_off = (last * params.batch_size + b) * n;
        let y_off = (last * params.batch_size + b) * n;
        var sy: f64 = 0.0;
        var yy: f64 = 0.0;
        for (var j = 0u; j < n; j = j + 1u) {
            sy = sy + s_history[s_off + j] * y_history[y_off + j];
            yy = yy + y_history[y_off + j] * y_history[y_off + j];
        }
        var gamma: f64 = 1.0;
        if (yy > 1e-30) {
            gamma = sy / yy;
        }
        for (var j = 0u; j < n; j = j + 1u) {
            direction[b_off + j] = direction[b_off + j] * gamma;
        }
    }

    // Forward loop: i = 0 .. m-1
    for (var i = 0u; i < m; i = i + 1u) {
        let y_off = (i * params.batch_size + b) * n;
        let rho_idx = i * params.batch_size + b;
        var dot: f64 = 0.0;
        for (var j = 0u; j < n; j = j + 1u) {
            dot = dot + y_history[y_off + j] * direction[b_off + j];
        }
        let beta = rho[rho_idx] * dot;
        let alpha_i = alpha_buf[i * params.batch_size + b];
        let s_off = (i * params.batch_size + b) * n;
        for (var j = 0u; j < n; j = j + 1u) {
            direction[b_off + j] = direction[b_off + j] + (alpha_i - beta) * s_history[s_off + j];
        }
    }

    // Negate for descent: d = -H * g
    for (var j = 0u; j < n; j = j + 1u) {
        direction[b_off + j] = -direction[b_off + j];
    }
}

// Line search step update: x_new = x + alpha * d
struct StepParams {
    n: u32,
    batch_size: u32,
    _pad0: u32,
    _pad1: u32,
}

@group(0) @binding(0) var<uniform> step_params: StepParams;
@group(0) @binding(1) var<storage, read> x_current: array<f64>;
@group(0) @binding(2) var<storage, read> dir: array<f64>;
@group(0) @binding(3) var<storage, read> alphas: array<f64>;
@group(0) @binding(4) var<storage, read_write> x_next: array<f64>;

@compute @workgroup_size(256, 1, 1)
fn apply_step(@builtin(global_invocation_id) gid: vec3<u32>) {
    let idx = gid.x;
    let n = step_params.n;
    let total = n * step_params.batch_size;
    if (idx >= total) {
        return;
    }
    let b = idx / n;
    x_next[idx] = x_current[idx] + alphas[b] * dir[idx];
}