Overview

A minimal, high-performance WebGPU library implementing an in-place exclusive prefix sum (scan). Designed for GPU-accelerated rendering and compute pipelines, it leverages hardware subgroup operations to maximize throughput, minimize global memory roundtrips, and efficiently process contiguous arrays of 32-bit unsigned integers (Uint32Array).

Requirements: WebGPU-enabled browser with subgroups feature and required WGSL extensions (linear_indexing, subgroup_uniformity, subgroup_id).

Installation: npm install @zeitfall/webgpu-exclusive-scan

Mathematical & Algorithmic Properties

| Operation / Metric | WebGPUExclusiveScanner | | --- | --- | | Work Complexity | O(n) | | Step (Time) Complexity | O(log n) | | Auxiliary Space | O(n / k) |

Note 1: n represents the total number of scalar elements within the dataset buffer.

Note 2: k represents the data processed per workgroup block (4 * workgroupSize). Auxiliary space is dynamically allocated for intermediate block sums across hierarchical compute passes.

API Reference

WebGPUExclusiveScanner

The primary controller class managing the compute pipelines and dispatch configurations for the parallel scan.

• Constructor constructor(gpuDevice: GPUDevice, workgroupSize = 64) Initializes the internal compute pipelines and shader modules. The gpuDevice must be instantiated with the subgroups feature enabled. Throws an error if subgroups are unsupported.
• scan(encoder: GPUCommandEncoder, dataBuffer: GPUBuffer, dataLength: number): void Dispatches the scan and uniform-add compute passes. Mutates the dataBuffer in-place. The target buffer must be created with the GPUBufferUsage.STORAGE flag.
• dispose(dataBuffer: GPUBuffer): void Frees the internally cached intermediate block buffers associated with a specific dataBuffer. Must be called to prevent memory leaks when the primary data buffer is destroyed by the host.

Operational Context (Behavioral Notes)

• Subgroup Intrinsics: Bypasses workgroup shared memory overhead by utilizing subgroupExclusiveAdd and subgroupAdd for intra-wavefront reductions, drastically reducing shared memory synchronization barriers and increasing execution speed.
• In-Place Mutation: The algorithm updates the input GPUBuffer directly without requiring a secondary destination buffer. This eliminates the need for VRAM-heavy Ping-Pong buffer allocations during the main scan passes.
• Zero-Allocation Execution: Intermediate block sum buffers are dynamically allocated upon the first scan and retained in an internal WeakMap. Subsequent scans on the same GPUBuffer execute with zero allocation overhead.
• Vectorized Loads/Stores: Memory access is strictly optimized via 128-bit vec4u coalesced reads and writes (array<vec4u>), saturating memory bandwidth and minimizing cache misses across the global invocation grid.

Usage Example

import { WebGPUExclusiveScanner } from '@zeitfall/webgpu-exclusive-scan';

const gpuDevice = await initGPUDevice();
const scanner = new WebGPUExclusiveScanner(gpuDevice);

// Generate mock data for the scan
const inputData = new Uint32Array(8_000_000).map(() => Math.ceil(16 * Math.random()));

const inputBuffer = gpuDevice.createBuffer({
    size: inputData.byteLength,
    usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_SRC | GPUBufferUsage.COPY_DST
});

const resultBuffer = gpuDevice.createBuffer({
    size: inputData.byteLength,
    usage: GPUBufferUsage.MAP_READ | GPUBufferUsage.COPY_DST
});

// Upload data to VRAM
gpuDevice.queue.writeBuffer(inputBuffer, 0, inputData);

const commandEncoder = gpuDevice.createCommandEncoder();

// Perform the exclusive scan in-place
scanner.scan(commandEncoder, inputBuffer, inputData.length);
commandEncoder.copyBufferToBuffer(inputBuffer, resultBuffer);

gpuDevice.queue.submit([commandEncoder.finish()]);
await gpuDevice.queue.onSubmittedWorkDone();

// Read back the results
const resultArrayBuffer = await mapBuffer(resultBuffer);
const resultArray = new Uint32Array(resultArrayBuffer);

console.log('Input data:', inputData);
console.log('Prefix scan:', resultArray);

// --- Utility Functions ---

async function mapBuffer(buffer: GPUBuffer) {
    await buffer.mapAsync(GPUMapMode.READ);
    const arrayBuffer = buffer.getMappedRange().slice(0);
    buffer.unmap();
    return arrayBuffer;
}

async function initGPUDevice() {
    if (!navigator.gpu) throw new TypeError('WebGPU is not supported.');

    const gpuWGSLFeatues = navigator.gpu.wgslLanguageFeatures;
    const requiredFeatures = ['linear_indexing', 'subgroup_uniformity', 'subgroup_id'];

    requiredFeatures.forEach((feature) => {
        if (!gpuWGSLFeatues.has(feature)) {
            throw new TypeError(`GPU lacks required WGSL feature: "${feature}"`);
        }
    });

    const adapter = await navigator.gpu.requestAdapter();
    if (!adapter) throw new TypeError('No GPU adapter found.');
    if (!adapter.features.has('subgroups')) throw new TypeError('GPU lacks "subgroups" support.');

    return adapter.requestDevice({
        requiredFeatures: ['subgroups'],
        requiredLimits: {
            maxBufferSize: adapter.limits.maxBufferSize,
            maxComputeWorkgroupsPerDimension: adapter.limits.maxComputeWorkgroupsPerDimension
        }
    });
}

References

[1] Harris, M., Sengupta, S., & Owens, J. D. (2007). Parallel Prefix Sum (Scan) with CUDA. GPU Gems 3, Part VI, Chapter 39. NVIDIA Developer

[2] Yayo1. (2024). WebGPU Prefix Sum. yayo1.com