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
//
// grid_fit_2d_f64.wgsl — 2D least-squares surface fit on a structured grid
//
// Fits polynomial surface z = a + bx + cy + dxy to observed data.
// Single-workgroup reduction computes sums for normal equations,
// then solves the 4x4 system X'X β = X'z.
//
// Design matrix row per point: [1, x, y, xy]
//
// Provenance: groundSpring → ToadStool absorption

struct GridFitParams {
    nx: u32,
    ny: u32,
    _pad0: u32,
    _pad1: u32,
}

@group(0) @binding(0) var<storage, read> data: array<f64>;              // [NX*NY]
@group(0) @binding(1) var<storage, read> x_coords: array<f64>;          // [NX]
@group(0) @binding(2) var<storage, read> y_coords: array<f64>;          // [NY]
@group(0) @binding(3) var<storage, read_write> out_coefficients: array<f64>;  // [4] -> a,b,c,d
@group(0) @binding(4) var<uniform> params: GridFitParams;

var<workgroup> shared_sums: array<f64, 64>;  // Scratch for reduction

@compute @workgroup_size(64)
fn main(
    @builtin(global_invocation_id) gid: vec3<u32>,
    @builtin(local_invocation_id) lid: vec3<u32>,
) {
    let nx = params.nx;
    let ny = params.ny;
    let n_total = nx * ny;
    let tid = lid.x;

    // Each thread accumulates partial sums over its chunk
    var s0: f64 = 0.0;   // sum(1)
    var s1: f64 = 0.0;   // sum(x)
    var s2: f64 = 0.0;   // sum(y)
    var s3: f64 = 0.0;   // sum(xy)
    var s4: f64 = 0.0;   // sum(x^2)
    var s5: f64 = 0.0;   // sum(y^2)
    var s6: f64 = 0.0;   // sum(x^2 y)
    var s7: f64 = 0.0;   // sum(xy^2)
    var s8: f64 = 0.0;   // sum(x^2 y^2)
    var sz: f64 = 0.0;   // sum(z)
    var sxz: f64 = 0.0;  // sum(xz)
    var syz: f64 = 0.0;  // sum(yz)
    var sxyz: f64 = 0.0; // sum(xyz)

    let num_threads = 64u;
    for (var idx = tid; idx < n_total; idx = idx + num_threads) {
        let ix = idx / ny;
        let iy = idx % ny;
        let x = x_coords[ix];
        let y = y_coords[iy];
        let z = data[idx];
        let xy = x * y;
        let x2 = x * x;
        let y2 = y * y;

        s0 += 1.0;
        s1 += x;
        s2 += y;
        s3 += xy;
        s4 += x2;
        s5 += y2;
        s6 += x2 * y;
        s7 += x * y2;
        s8 += x2 * y2;
        sz += z;
        sxz += x * z;
        syz += y * z;
        sxyz += xy * z;
    }

    // Tree reduction across threads: 14 passes, one per sum
    shared_sums[tid] = s0;
    workgroupBarrier();
    for (var stride = 32u; stride > 0u; stride = stride / 2u) {
        if tid < stride {
            shared_sums[tid] = shared_sums[tid] + shared_sums[tid + stride];
        }
        workgroupBarrier();
    }
    let sum0 = shared_sums[0u];

    shared_sums[tid] = s1;
    workgroupBarrier();
    for (var stride = 32u; stride > 0u; stride = stride / 2u) {
        if tid < stride {
            shared_sums[tid] = shared_sums[tid] + shared_sums[tid + stride];
        }
        workgroupBarrier();
    }
    let sum1 = shared_sums[0u];

    shared_sums[tid] = s2;
    workgroupBarrier();
    for (var stride = 32u; stride > 0u; stride = stride / 2u) {
        if tid < stride {
            shared_sums[tid] = shared_sums[tid] + shared_sums[tid + stride];
        }
        workgroupBarrier();
    }
    let sum2 = shared_sums[0u];

    shared_sums[tid] = s3;
    workgroupBarrier();
    for (var stride = 32u; stride > 0u; stride = stride / 2u) {
        if tid < stride {
            shared_sums[tid] = shared_sums[tid] + shared_sums[tid + stride];
        }
        workgroupBarrier();
    }
    let sum3 = shared_sums[0u];

    shared_sums[tid] = s4;
    workgroupBarrier();
    for (var stride = 32u; stride > 0u; stride = stride / 2u) {
        if tid < stride {
            shared_sums[tid] = shared_sums[tid] + shared_sums[tid + stride];
        }
        workgroupBarrier();
    }
    let sum4 = shared_sums[0u];

    shared_sums[tid] = s5;
    workgroupBarrier();
    for (var stride = 32u; stride > 0u; stride = stride / 2u) {
        if tid < stride {
            shared_sums[tid] = shared_sums[tid] + shared_sums[tid + stride];
        }
        workgroupBarrier();
    }
    let sum5 = shared_sums[0u];

    shared_sums[tid] = s6;
    workgroupBarrier();
    for (var stride = 32u; stride > 0u; stride = stride / 2u) {
        if tid < stride {
            shared_sums[tid] = shared_sums[tid] + shared_sums[tid + stride];
        }
        workgroupBarrier();
    }
    let sum6 = shared_sums[0u];

    shared_sums[tid] = s7;
    workgroupBarrier();
    for (var stride = 32u; stride > 0u; stride = stride / 2u) {
        if tid < stride {
            shared_sums[tid] = shared_sums[tid] + shared_sums[tid + stride];
        }
        workgroupBarrier();
    }
    let sum7 = shared_sums[0u];

    shared_sums[tid] = s8;
    workgroupBarrier();
    for (var stride = 32u; stride > 0u; stride = stride / 2u) {
        if tid < stride {
            shared_sums[tid] = shared_sums[tid] + shared_sums[tid + stride];
        }
        workgroupBarrier();
    }
    let sum8 = shared_sums[0u];

    shared_sums[tid] = sz;
    workgroupBarrier();
    for (var stride = 32u; stride > 0u; stride = stride / 2u) {
        if tid < stride {
            shared_sums[tid] = shared_sums[tid] + shared_sums[tid + stride];
        }
        workgroupBarrier();
    }
    let sumz = shared_sums[0u];

    shared_sums[tid] = sxz;
    workgroupBarrier();
    for (var stride = 32u; stride > 0u; stride = stride / 2u) {
        if tid < stride {
            shared_sums[tid] = shared_sums[tid] + shared_sums[tid + stride];
        }
        workgroupBarrier();
    }
    let sumxz = shared_sums[0u];

    shared_sums[tid] = syz;
    workgroupBarrier();
    for (var stride = 32u; stride > 0u; stride = stride / 2u) {
        if tid < stride {
            shared_sums[tid] = shared_sums[tid] + shared_sums[tid + stride];
        }
        workgroupBarrier();
    }
    let sumyz = shared_sums[0u];

    shared_sums[tid] = sxyz;
    workgroupBarrier();
    for (var stride = 32u; stride > 0u; stride = stride / 2u) {
        if tid < stride {
            shared_sums[tid] = shared_sums[tid] + shared_sums[tid + stride];
        }
        workgroupBarrier();
    }
    let sumxyz = shared_sums[0u];

    // Solve 4x4 system: X'X * [a,b,c,d]' = [sumz, sumxz, sumyz, sumxyz]'
    // X'X = [[sum0, sum1, sum2, sum3], [sum1, sum4, sum3, sum6], [sum2, sum3, sum5, sum7], [sum3, sum6, sum7, sum8]]
    if tid == 0u {
        let m = array<f64, 16>(
            sum0, sum1, sum2, sum3,
            sum1, sum4, sum3, sum6,
            sum2, sum3, sum5, sum7,
            sum3, sum6, sum7, sum8
        );
        let rhs = array<f64, 4>(sumz, sumxz, sumyz, sumxyz);

        // 4x4 determinant and inverse (Cramer-style)
        let s0_m = m[0]*m[5] - m[1]*m[4];
        let s1_m = m[0]*m[6] - m[2]*m[4];
        let s2_m = m[0]*m[7] - m[3]*m[4];
        let s3_m = m[1]*m[6] - m[2]*m[5];
        let s4_m = m[1]*m[7] - m[3]*m[5];
        let s5_m = m[2]*m[7] - m[3]*m[6];
        let c5 = s0_m*m[10] - s1_m*m[9] + s3_m*m[8];
        let c4 = s0_m*m[11] - s2_m*m[9] + s4_m*m[8];
        let c3 = s1_m*m[11] - s2_m*m[10] + s5_m*m[8];
        let c2 = s3_m*m[11] - s4_m*m[10] + s5_m*m[9];
        let det = c5*m[15] - c4*m[14] + c3*m[13] - c2*m[12];

        if abs(det) > 1e-15 {
            let inv_det = 1.0 / det;
            for (var col: u32 = 0u; col < 4u; col = col + 1u) {
                var cof: f64 = 0.0;
                for (var row: u32 = 0u; row < 4u; row = row + 1u) {
                    let sign = select(-1.0, 1.0, (row + col) % 2u == 0u);
                    var minor: array<f64, 9>;
                    var mi: u32 = 0u;
                    for (var i: u32 = 0u; i < 4u; i = i + 1u) {
                        for (var j: u32 = 0u; j < 4u; j = j + 1u) {
                            if i != row && j != col {
                                minor[mi] = m[i*4u+j];
                                mi = mi + 1u;
                            }
                        }
                    }
                    let d = minor[0]*(minor[4]*minor[8]-minor[5]*minor[7])
                          - minor[1]*(minor[3]*minor[8]-minor[5]*minor[6])
                          + minor[2]*(minor[3]*minor[7]-minor[4]*minor[6]);
                    cof += sign * d * rhs[row];
                }
                out_coefficients[col] = cof * inv_det;
            }
        } else {
            out_coefficients[0u] = 0.0;
            out_coefficients[1u] = 0.0;
            out_coefficients[2u] = 0.0;
            out_coefficients[3u] = 0.0;
        }
    }
}