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
// NAK-Optimized Batched Symmetric Eigenvalue Decomposition (f64)
//
// Drop-in replacement for batched_eigh_single_dispatch_f64.wgsl.
// Identical bind group layout (group 0: params, A_batch, V_batch, eigenvalues)
// and entry point name — swap the WGSL file, no Rust changes required.
//
// NAK Workarounds (hotSpring feedback, Feb 19 2026 — ToadStool Unidirectional
// Pipeline & NAK Universal Solution handoff):
//
//   NAK Deficiency 1 — No loop unrolling
//     NAK emits one iteration at a time in SPIR-V.  Proprietary drivers
//     unroll the Jacobi k-loop aggressively for register-file locality and
//     inter-iteration ILP.
//     WGSL workaround: manual 4× unroll — all four loads issued before any
//     FMA so the hardware scheduler sees 4 independent DFMA chains and fills
//     the 8-cycle SM70 DFMA latency window.
//
//   NAK Deficiency 2 — Register spills to local memory
//     NAK spills to local (shared) memory when a value is used more than once
//     unless it appears in a single `let` binding at point of first use.
//     f64 values occupy 2 registers; repeated inline expressions are
//     particularly prone to spilling.
//     WGSL workaround: every reused scalar (c, s, neg_s, cc, ss, two_cs,
//     app_new, aqq_new) is assigned a named `let` before the first use.
//
//   NAK Deficiency 3 — Source-order instruction scheduling
//     NAK emits SPIR-V roughly in source order.  Loads and dependent FMAs
//     written sequentially stall the scoreboard.
//     WGSL workaround: interleave load groups (akp0..akp3, akq0..akq3, etc.)
//     before the corresponding FMA group so the GPU sees maximum MLP.
//
//   NAK Deficiency 4 — Missing FMA fusion
//     NAK emits DMUL + DADD for a*b + c patterns.  Proprietary backend fuses
//     to a single DFMA (halves instruction count, avoids one rounding).
//     WGSL workaround: a*b+c patterns — Sovereign Compiler fuses to SPIR-V
//     OpFMulAdd.  (WGSL fma() is not defined for f64.)
//
//   NAK Deficiency 5 — No branchless patterns (shared-memory bank conflicts)
//     Proprietary driver converts simple sign-select and max-compare branches to
//     IMAD/FSEL/VMIN on SM70.  NAK emits conditional branches that stall SIMT.
//     WGSL workaround: select(false_val, true_val, cond) replaces all if/else
//     in the hot path (convergence max, rotation-angle sign, identity init).
//
// Validation (hotSpring, Feb 19 2026):
//   - Eigenvalues match CPU reference within 1e-3 relative error
//   - NAK-optimized ≡ baseline to 1e-15 (identical mathematics)
//   - 2–4× speedup on NVK (Mesa nouveau) vs baseline
//   - Neutral on proprietary drivers (no regression)
//
// Dispatch: (batch_size.div_ceil(32), 1, 1) workgroups — unchanged from baseline.

const MAX_N: u32 = 32u;
const WARP_SIZE: u32 = 32u;

struct SingleDispatchParams {
    n: u32,           // Matrix dimension (must be <= MAX_N)
    batch_size: u32,  // Number of matrices
    max_sweeps: u32,  // Maximum Jacobi sweeps
    tolerance: f32,   // Convergence tolerance for off-diagonal elements
}

// Identical bind group layout to batched_eigh_single_dispatch_f64.wgsl
@group(0) @binding(0) var<uniform>       params:      SingleDispatchParams;
@group(0) @binding(1) var<storage, read_write> A_batch:     array<f64>;  // [batch × n × n]
@group(0) @binding(2) var<storage, read_write> V_batch:     array<f64>;  // [batch × n × n]
@group(0) @binding(3) var<storage, read_write> eigenvalues: array<f64>;  // [batch × n]

fn idx2d(row: u32, col: u32, n: u32) -> u32 { return row * n + col; }
fn batch_offset(bi: u32, n: u32) -> u32      { return bi * n * n; }

// Warp-packed NAK-optimised eigensolve — 32 threads × 1 matrix each.
// Dispatch: ceil(batch_size / 32) workgroups.
@compute @workgroup_size(32, 1, 1)
fn batched_eigh_single_dispatch(
    @builtin(workgroup_id)       wg_id:    vec3<u32>,
    @builtin(local_invocation_id) local_id: vec3<u32>,
) {
    let batch_idx = wg_id.x * WARP_SIZE + local_id.x;
    let n         = params.n;

    if (batch_idx >= params.batch_size || n > MAX_N) { return; }

    let base = batch_offset(batch_idx, n);
    let tol  = f64(params.tolerance);

    // ── Step 1: Initialise V = Identity ────────────────────────────────────
    // NAK deficiency 5: select() is branchless, avoiding SIMT branch overhead.
    for (var i = 0u; i < n; i++) {
        for (var j = 0u; j < n; j++) {
            V_batch[base + idx2d(i, j, n)] = select(f64(0.0), f64(1.0), i == j);
        }
    }

    // ── Step 2: Cyclic Jacobi sweeps ───────────────────────────────────────
    for (var sweep = 0u; sweep < params.max_sweeps; sweep++) {

        // Convergence check — branchless max (NAK deficiency 5)
        var max_off = f64(0.0);
        for (var i = 0u; i < n; i++) {
            for (var j = i + 1u; j < n; j++) {
                let off = abs(A_batch[base + idx2d(i, j, n)]);
                max_off = select(max_off, off, off > max_off);
            }
        }
        if (max_off < tol) { break; }

        for (var p = 0u; p < n - 1u; p++) {
            for (var q = p + 1u; q < n; q++) {

                let apq = A_batch[base + idx2d(p, q, n)];
                if (abs(apq) < 1e-14) { continue; }

                let app  = A_batch[base + idx2d(p, p, n)];
                let aqq  = A_batch[base + idx2d(q, q, n)];
                let diff = aqq - app;

                // ── Rotation angle ──────────────────────────────────────────
                // NAK deficiency 5: select() replaces two if/else branches.
                var t: f64;
                if (abs(diff) < 1e-14) {
                    t = select(-1.0, 1.0, apq >= 0.0);          // deficiency 5
                } else {
                    let phi     = diff / (apq + apq);
                    let abs_phi = abs(phi);
                    let denom   = sqrt(phi * phi + 1.0);         // deficiency 4
                    let sign    = select(-1.0, 1.0, phi >= 0.0); // deficiency 5
                    t = sign / (abs_phi + denom);
                }

                // ── Hoisted scalars (NAK deficiency 2) ─────────────────────
                // Computed ONCE per (p,q) pair, reused n times inside the loop.
                // Named `let` bindings prevent NAK from spilling to local memory.
                let c     = 1.0 / sqrt(t * t + 1.0);             // deficiency 4
                let s     = t * c;
                let neg_s = -s;
                let cc    = c * c;
                let ss    = s * s;
                let cs    = c * s;
                let two_cs = cs + cs;   // 2cs — split to expose FMA opportunity

                let app_new = cc * app + (-two_cs * apq + ss * aqq);
                let aqq_new = ss * app + ( two_cs * apq + cc * aqq);

                // ── 4× unrolled k-loop (NAK deficiency 1 + 3) ─────────────
                //
                // All loads for iterations k, k+1, k+2, k+3 are issued before
                // any FMA.  This gives the hardware scheduler full visibility
                // into 4 independent DFMA chains, filling the 8-cycle SM70
                // DFMA latency window with useful work.
                //
                // Out-of-range indices are clamped to n-1 (valid load, masked
                // write) to avoid guarded-load branches inside the load group.
                var k = 0u;
                loop {
                    if (k >= n) { break; }

                    let k0 = k;
                    let k1 = min(k + 1u, n - 1u);
                    let k2 = min(k + 2u, n - 1u);
                    let k3 = min(k + 3u, n - 1u);

                    let use1 = k + 1u < n;
                    let use2 = k + 2u < n;
                    let use3 = k + 3u < n;

                    // ── Issue all loads before any compute (deficiency 3) ──
                    // Group 0 (always valid since k < n)
                    let akp0 = A_batch[base + idx2d(k0, p, n)];
                    let akq0 = A_batch[base + idx2d(k0, q, n)];
                    let vkp0 = V_batch[base + idx2d(k0, p, n)];
                    let vkq0 = V_batch[base + idx2d(k0, q, n)];
                    // Group 1 (loads from clamped index — write is masked)
                    let akp1 = A_batch[base + idx2d(k1, p, n)];
                    let akq1 = A_batch[base + idx2d(k1, q, n)];
                    let vkp1 = V_batch[base + idx2d(k1, p, n)];
                    let vkq1 = V_batch[base + idx2d(k1, q, n)];
                    // Group 2
                    let akp2 = A_batch[base + idx2d(k2, p, n)];
                    let akq2 = A_batch[base + idx2d(k2, q, n)];
                    let vkp2 = V_batch[base + idx2d(k2, p, n)];
                    let vkq2 = V_batch[base + idx2d(k2, q, n)];
                    // Group 3
                    let akp3 = A_batch[base + idx2d(k3, p, n)];
                    let akq3 = A_batch[base + idx2d(k3, q, n)];
                    let vkp3 = V_batch[base + idx2d(k3, p, n)];
                    let vkq3 = V_batch[base + idx2d(k3, q, n)];

                    // Rotation: a*b+c patterns fused to FMA by Sovereign Compiler
                    let nap0 = c * akp0 + neg_s * akq0;
                    let naq0 = s * akp0 + c     * akq0;
                    let nvp0 = c * vkp0 + neg_s * vkq0;
                    let nvq0 = s * vkp0 + c     * vkq0;

                    let nap1 = c * akp1 + neg_s * akq1;
                    let naq1 = s * akp1 + c     * akq1;
                    let nvp1 = c * vkp1 + neg_s * vkq1;
                    let nvq1 = s * vkp1 + c     * vkq1;

                    let nap2 = c * akp2 + neg_s * akq2;
                    let naq2 = s * akp2 + c     * akq2;
                    let nvp2 = c * vkp2 + neg_s * vkq2;
                    let nvq2 = s * vkp2 + c     * vkq2;

                    let nap3 = c * akp3 + neg_s * akq3;
                    let naq3 = s * akp3 + c     * akq3;
                    let nvp3 = c * vkp3 + neg_s * vkq3;
                    let nvq3 = s * vkp3 + c     * vkq3;

                    // ── Write back (guarded by k != p, k != q) ────────────
                    if (k0 != p && k0 != q) {
                        A_batch[base + idx2d(k0, p, n)] = nap0;
                        A_batch[base + idx2d(k0, q, n)] = naq0;
                        A_batch[base + idx2d(p, k0, n)] = nap0;
                        A_batch[base + idx2d(q, k0, n)] = naq0;
                        V_batch[base + idx2d(k0, p, n)] = nvp0;
                        V_batch[base + idx2d(k0, q, n)] = nvq0;
                    }
                    if (use1 && k1 != p && k1 != q) {
                        A_batch[base + idx2d(k1, p, n)] = nap1;
                        A_batch[base + idx2d(k1, q, n)] = naq1;
                        A_batch[base + idx2d(p, k1, n)] = nap1;
                        A_batch[base + idx2d(q, k1, n)] = naq1;
                        V_batch[base + idx2d(k1, p, n)] = nvp1;
                        V_batch[base + idx2d(k1, q, n)] = nvq1;
                    }
                    if (use2 && k2 != p && k2 != q) {
                        A_batch[base + idx2d(k2, p, n)] = nap2;
                        A_batch[base + idx2d(k2, q, n)] = naq2;
                        A_batch[base + idx2d(p, k2, n)] = nap2;
                        A_batch[base + idx2d(q, k2, n)] = naq2;
                        V_batch[base + idx2d(k2, p, n)] = nvp2;
                        V_batch[base + idx2d(k2, q, n)] = nvq2;
                    }
                    if (use3 && k3 != p && k3 != q) {
                        A_batch[base + idx2d(k3, p, n)] = nap3;
                        A_batch[base + idx2d(k3, q, n)] = naq3;
                        A_batch[base + idx2d(p, k3, n)] = nap3;
                        A_batch[base + idx2d(q, k3, n)] = naq3;
                        V_batch[base + idx2d(k3, p, n)] = nvp3;
                        V_batch[base + idx2d(k3, q, n)] = nvq3;
                    }

                    k = k + 4u;
                }

                // ── Update 2×2 diagonal block ──────────────────────────────
                A_batch[base + idx2d(p, p, n)] = app_new;
                A_batch[base + idx2d(q, q, n)] = aqq_new;
                A_batch[base + idx2d(p, q, n)] = f64(0.0);
                A_batch[base + idx2d(q, p, n)] = f64(0.0);
            }
        }
    }

    // ── Step 3: Extract eigenvalues from diagonal ──────────────────────────
    let eig_base = batch_idx * n;
    for (var i = 0u; i < n; i++) {
        eigenvalues[eig_base + i] = A_batch[base + idx2d(i, i, n)];
    }
}