Skip to main content

GRAPH_RADIX_SCATTER_WGSL

Constant GRAPH_RADIX_SCATTER_WGSL 

Source
pub const GRAPH_RADIX_SCATTER_WGSL: &str = "// Target: c:\\github\\qualiaDB\\crates\\qualia-core-db\\src\\shaders\\graph_radix_scatter.wgsl\n// Stable intra-workgroup rank scatter for LSD radix sort.\n\nstruct Params {\n    n: u32,\n    shift: u32,\n    num_wgs: u32,\n    _pad1: u32,\n}\n\n@group(0) @binding(0) var<storage, read> keys_in: array<u32>;\n@group(0) @binding(1) var<storage, read> idx_in: array<u32>;\n@group(0) @binding(2) var<storage, read_write> keys_out: array<u32>;\n@group(0) @binding(3) var<storage, read_write> idx_out: array<u32>;\n@group(0) @binding(4) var<storage, read> wg_offsets: array<u32>;\n@group(0) @binding(5) var<uniform> params: Params;\n\nvar<workgroup> wg_digits: array<u32, 256>;\n\nfn digit_at(i: u32, shift: u32) -> u32 {\n    let lo = keys_in[i * 2u];\n    let hi = keys_in[i * 2u + 1u];\n    if (shift < 32u) {\n        return (lo >> shift) & 255u;\n    }\n    return (hi >> (shift - 32u)) & 255u;\n}\n\n@compute @workgroup_size(256)\nfn main(\n    @builtin(global_invocation_id) gid: vec3<u32>,\n    @builtin(local_invocation_id) lid: vec3<u32>,\n    @builtin(workgroup_id) wid: vec3<u32>,\n) {\n    let i = gid.x;\n    let t = lid.x;\n    let valid = i < params.n;\n    let d = select(0xFFFFFFFFu, digit_at(i, params.shift), valid);\n    wg_digits[t] = d;\n    workgroupBarrier();\n\n    if (!valid) {\n        return;\n    }\n\n    // Deterministic intra-workgroup rank: count threads u < t with identical digit d.\n    var local_rank: u32 = 0u;\n    for (var u: u32 = 0u; u < t; u = u + 1u) {\n        local_rank = local_rank + select(0u, 1u, wg_digits[u] == d);\n    }\n\n    let base_offset = wg_offsets[d * params.num_wgs + wid.x];\n    let pos = base_offset + local_rank;\n    keys_out[pos * 2u] = keys_in[i * 2u];\n    keys_out[pos * 2u + 1u] = keys_in[i * 2u + 1u];\n    idx_out[pos] = idx_in[i];\n}\n";
Expand description

Canonical graph radix scatter compute shader.