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
//
// groundSpring — Batched multinomial sampling for rarefaction
//
// Each invocation runs one replicate: draws `depth` reads from a
// community described by cumulative abundance probabilities, counting
// how many reads land in each taxon.
//
// Binding layout:
//   @group(0) @binding(0) params:      Params          {n_taxa, depth, n_reps, cumulative_probs, seed_lo, seed_hi, _pad}
//   @group(0) @binding(1) cumulative:  array<f64>      cumulative probabilities [n_taxa]
//   @group(0) @binding(2) seeds:       array<u32>      xoshiro state (4 × u32 per replicate)
//   @group(0) @binding(3) counts:      array<u32>      output [n_reps × n_taxa]
//
// Dispatch: (ceil(n_reps / 64), 1, 1)
//
// CPU reference: groundspring::rarefaction::multinomial_sample()
//
// For absorption into barracuda as ops::batched_multinomial_f64.
// Uses xoshiro128** matching barracuda::ops::prng_xoshiro_wgsl.

struct Params {
    n_taxa:          u32,
    depth:            u32,
    n_reps:           u32,
    cumulative_probs: u32,
    seed_lo:          u32,
    seed_hi:          u32,
    _pad0:            u32,
    _pad1:            u32,
}

@group(0) @binding(0) var<uniform>             params:     Params;
@group(0) @binding(1) var<storage, read>       cumulative: array<f64>;
@group(0) @binding(2) var<storage, read_write> seeds:      array<u32>;
@group(0) @binding(3) var<storage, read_write> counts:     array<u32>;

// ── Xoshiro128** (matches barracuda prng_xoshiro_wgsl) ──────────────

fn rotl(x: u32, k: u32) -> u32 {
    return (x << k) | (x >> (32u - k));
}

fn xoshiro_next(s: ptr<function, vec4<u32>>) -> u32 {
    let result = rotl((*s).y * 5u, 7u) * 9u;
    let t = (*s).y << 9u;
    (*s).z ^= (*s).x;
    (*s).w ^= (*s).y;
    (*s).y ^= (*s).z;
    (*s).x ^= (*s).w;
    (*s).z ^= t;
    (*s).w = rotl((*s).w, 11u);
    return result;
}

fn xoshiro_next_f64(s: ptr<function, vec4<u32>>) -> f64 {
    let hi = xoshiro_next(s);
    let lo = xoshiro_next(s);
    let combined = (f64(hi) * 4294967296.0 + f64(lo));
    return combined / 18446744073709551616.0;
}

// ── Binary search over cumulative probabilities ─────────────────────

fn find_taxon(u: f64) -> u32 {
    var lo = 0u;
    var hi = params.n_taxa;
    loop {
        if lo >= hi { break; }
        let mid = (lo + hi) / 2u;
        if cumulative[mid] < u {
            lo = mid + 1u;
        } else {
            hi = mid;
        }
    }
    return min(lo, params.n_taxa - 1u);
}

// ── Main ────────────────────────────────────────────────────────────

@compute @workgroup_size(64, 1, 1)
fn main(@builtin(global_invocation_id) gid: vec3<u32>) {
    let rep = gid.x;
    if rep >= params.n_reps { return; }

    let base = rep * params.n_taxa;
    let seed_base = rep * 4u;

    // Load per-replicate PRNG state
    var state = vec4<u32>(
        seeds[seed_base],
        seeds[seed_base + 1u],
        seeds[seed_base + 2u],
        seeds[seed_base + 3u],
    );

    // Zero output counts
    for (var t = 0u; t < params.n_taxa; t++) {
        counts[base + t] = 0u;
    }

    // Multinomial sampling: depth draws with binary-search assignment
    for (var d = 0u; d < params.depth; d++) {
        let u = xoshiro_next_f64(&state);
        let taxon = find_taxon(u);
        counts[base + taxon] += 1u;
    }

    // Write back PRNG state for potential multi-pass usage
    seeds[seed_base]      = state.x;
    seeds[seed_base + 1u] = state.y;
    seeds[seed_base + 2u] = state.z;
    seeds[seed_base + 3u] = state.w;
}