Skip to main content

GRAPH_RADIX_HIST_WGSL

Constant GRAPH_RADIX_HIST_WGSL 

Source
pub const GRAPH_RADIX_HIST_WGSL: &str = "// Target: c:\\github\\qualiaDB\\crates\\qualia-core-db\\src\\shaders\\graph_radix_hist.wgsl\n// Stable LSD radix histogram: workgroup-local histogram to eliminate global atomic contention.\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_write> wg_hist: array<u32>;\n@group(0) @binding(2) var<uniform> params: Params;\n\nvar<workgroup> local_hist: array<atomic<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 t = lid.x;\n    atomicStore(&local_hist[t], 0u);\n    workgroupBarrier();\n\n    let i = gid.x;\n    if (i < params.n) {\n        let d = digit_at(i, params.shift);\n        atomicAdd(&local_hist[d], 1u);\n    }\n    workgroupBarrier();\n\n    // Column-major by digit d so device prefix sum is contiguous:\n    wg_hist[t * params.num_wgs + wid.x] = atomicLoad(&local_hist[t]);\n}\n";
Expand description

Canonical graph radix histogram compute shader.