A prefix sum (or scan) takes an input array [a0, a1, a2, ...] and produces an output array where each element is the sum of all preceding elements. While trivial to compute sequentially on a CPU in O(N) time, parallelizing it across thousands of GPU SIMD lanes requires a tree-based algorithm. The Blelloch scan is an optimal, work-efficient parallel algorithm that performs 2(N - 1) additions and O(log N) parallel steps. It consists of an Up-Sweep (reduce) phase building partial sums up a binary tree, followed by a Down-Sweep phase distributing cumulative sums back down. It powers parallel radix sort, stream compaction, octree building, and particle systems.

Radix sort sorts integer or floating-point keys by processing them digit-by-digit from least significant to most significant. In WebGPU, a 4-bit radix (radix 16) or 8-bit radix (radix 256) is typically used. For each 4-bit pass, three compute shaders execute: 1) Histogram pass: each workgroup counts occurrences of each 4-bit digit in its partition; 2) Global Prefix Sum pass: a Blelloch scan is run across all histogram bins to determine global destination memory offsets; 3) Reorder/Scatter pass: threads read keys and write them to their globally sorted partition using the scanned offsets. For 32-bit keys, 8 passes of 4 bits produce a 100% sorted array.

WebGPU workgroup memory (shared memory on NVIDIA/AMD GPUs) is split into 32 memory banks. When multiple threads within the same SIMD wavefront (warp/subgroup) access different addresses within the same memory bank simultaneously, a bank conflict occurs, serializing access and degrading performance by up to 16x. In Blelloch scan implementations, padding array indices by (index + (index >> 5)) offsets memory accesses across banks, ensuring conflict-free shared memory reads and writes at maximum hardware bandwidth.

A single WebGPU workgroup can typically coordinate 256 to 1024 threads, handling up to 2048 elements using local shared memory. For datasets with millions of elements (such as 3D Gaussian Splatting with 2,000,000 splats), a hierarchical multi-dispatch scan (Block-Scan & Sum-Scan) or decoupled look-back scan is used. Workgroups scan local tiles of 2048 elements and write out their tile block sums into an auxiliary buffer. A secondary single-workgroup shader scans the block sums, and a final pass adds the scanned block sums back into the individual tile elements.