GPU-Driven Anything

There is a pattern underneath some of the most interesting graphics techniques. Culling, level of detail, light clusters, particle systems, marching squares, Gaussian splatting: they look like different problems, but in each one a hundred thousand GPU threads want to write into one list, in order, with no gaps, and none of them knows where its place is.

On the CPU that is one line: if the object is visible, push_back it. On the GPU every object gets its own thread, and that line is gone. This video is about the pattern that replaces it, so that next time you run into it you recognize it right away and know exactly what to do.

Chapters

• 0:00 The pattern
• 2:35 Prefix sum
• 4:19 Expansion
• 4:53 Compaction
• 5:12 Compaction + expansion
• 6:19 Binning
• 8:06 Push vs. pull
• 10:40 Atomics

Play with it

Every animation in the video comes from this page. Pick an example, step through count, prefix sum and write, drag the camera, and open Where it’s used for the papers and talks each example comes from.

InteractiveGPU-Driven AnythingOpen full screen

The pattern in one paragraph

Each thread counts how much it wants to write: 0 or 1 for a cull, a triangle count for a level of detail, one per cluster a light touches. A prefix sum over the counts turns them into offsets, and the offset is where that thread starts writing. The sum itself runs in parallel; plenty of good algorithms do that, and a few are linked below.

Three shapes of the same idea:

• Compaction: every input makes 0 or 1 outputs. Fewer outputs than inputs. Culling.
• Expansion: every input makes a different number of outputs, decided at run time. Level of detail, particles, curves.
• Binning: every input goes into one or more of several lists, and the prefix sum runs over the lists, not the inputs. Light clusters, material tiles.

The two chain: compact first, expand only what survived, and the second pass can pull straight from the first pass’s result.

Two nuances

Push or pull. Push has a thread per input write its outputs at its offset, which needs the whole output buffer and leaves a wave waiting for its longest thread. Pull has a thread per output find its input with a binary search over the prefix sums, technically an upper bound. More work per thread, less memory, balanced work, and a natural fit for the expansion half of the chain.

Atomics instead? One counter, every visible thread adds to it and writes at the value it gets back. Perfectly compact, but in the order the threads happened to reach the counter, which changes from frame to frame. When order matters, the prefix sum gives the same output every frame.

Prefix sum resources

Roughly in the order I would read them:

• Prefix sum on Wikipedia: the serial version and the two classic parallel ones.
• GPU Gems 3, chapter 39: Parallel Prefix Sum (Scan) with CUDA (Harris, Sengupta, Owens, 2007): the classic work-efficient scan, with code, and compaction as an application.
• Prefix Sums and Their Applications (Blelloch, 1990): where the all-prefix-sums idea and its many uses come from.
• Data Parallel Algorithms (Hillis and Steele, 1986): the simple log-step scan.
• Scan Primitives for GPU Computing (Sengupta, Harris, Zhang, Owens, 2007): scan and segmented scan as GPU building blocks.
• Single-pass Parallel Prefix Scan with Decoupled Look-back (Merrill and Garland, 2016): the state of the art, the one inside CUB.
• Prefix sum on Vulkan (Raph Levien, 2020) and Prefix sum on portable compute shaders (2021): decoupled look-back in a compute shader, and what it takes to run it everywhere.
• GPUPrefixSums (Thomas Smith): a survey of implementations in HLSL, CUDA and WGSL, from the wave to the whole device.
• Efficient Stream Compaction on Wide SIMD Many-Core Architectures (Billeter, Olsson, Assarsson, 2009): compaction built on a scan.
• WavePrefixSum in HLSL: the scan within one wave, one intrinsic.
• The pull side of expansion is the load-balancing search in ModernGPU.

Find more on my YouTube channel.