A Compilation Model for Divergent Parallel Workloads

Alexander J Root, Christophe Gyurgyik, Devanshu Ladsaria, Rohan Sawhney, Jonathan Ragan-Kelley, Andrew Adams, Matt Pharr, Kayvon Fatahalian, Fredrik KjolstadarXiv 2026 · arXiv

TL;DR

The Grove compiler introduces Parallel Dispatch Graphs (PDGs), a novel abstraction that decouples the high-level logic of divergent programs (like ray tracers) from their low-level execution strategies. By using a composable scheduling language, Grove automatically generates code that matches or outperforms hand-optimized expert implementations, achieving speedups of up to 13× by tailoring execution to specific hardware and data.

What Problem Does This Paper Address?

Modern CPUs and GPUs are built for "coherence." They reach peak performance when every lane in a SIMD unit executes the same instruction on contiguous memory. However, many important workloads—such as Monte Carlo path tracing and spatial PDE solvers—are inherently divergent. In these programs, one thread might hit a mirror while its neighbor hits a diffuse wall, or one might finish its work in two steps while another takes twenty.

To make these programs run fast, experts manually restructure them using complex techniques like "wavefront" processing (queuing up similar work) or "persistent threads" (manual load balancing). The problem is that these optimizations are incredibly difficult to write, hard to debug, and completely non-portable. If you tune a renderer for an NVIDIA GPU, you often have to rewrite the core loop to make it run efficiently on an Intel CPU. There is currently no unified way to explore this optimization space without starting from scratch.

Methods

The authors propose a new compilation pipeline called Grove. Its core innovation is the Parallel Dispatch Graph (PDG), an intermediate representation that treats control flow, data flow (queues), and parallel loops as a single, transformable abstraction.

![Fig.

  1. Parallel dispatch graphs (PDGs) representing divergence in a simple path tracer.](/figures/art_621ad772f1be47b2b5fdca7a58c54906)

Key components of the Grove system include:

  • The PDG Abstraction: It models programs as a hierarchy of loops. Crucially, it introduces "deferred" edges—instead of executing a function immediately, the program can push the "continuation" (the remaining work) onto a queue to be drained later when more similar work is available.
  • A Push-Based Scheduling Language: Inspired by Halide, Grove provides a set of commands to transform the PDG. These include tile (loop optimization), defer (turning control flow into data flow), specialize (splitting queues by material type), and bind (mapping work to specific hardware like NVIDIA’s RT Cores).
  • The Grove Compiler: This tool lowers high-level, machine-agnostic code into PDGs, applies the user-defined schedule, and generates optimized LLVM IR for various backends (x86 and NVPTX).

![Fig.

  1. A complex "Wavefront" PDG generated by applying scheduling transformations to the simple graph in Fig 1.](/figures/art_79d54b3088464636b7b2e7dcc23dc9a4)

Datasets

The authors evaluated Grove against state-of-the-art hand-optimized libraries and applications:

  • Tree Traversals: Compared against Embree (Intel) and FCPW.
  • Path Tracing: Compared against PBRT-v4, a gold-standard research renderer.
  • PDE Solvers: Compared against WoSX (Walk on Spheres/Stars).
  • Scenes: Evaluation used standard graphics benchmarks including the pbrt-v4-scenes dataset and various complex meshes (e.g., the "San Miguel" courtyard and "Dragon").

Key Insights and Ideas

  • Optimization as Composition: The authors realized that complex "expert" optimizations are actually just compositions of well-known functional programming concepts (like CPS conversion) and loop transformations. By formalizing this, they turned a "black art" into a searchable design space.
  • The "Useful Lie" of SPMD: Programmers prefer writing "Single Program, Multiple Data" (SPMD) code where they describe what one thread does. Grove preserves this "lie" at the frontend while giving the compiler the tools to "shatter" that abstraction for performance at the backend.
  • Data-Dependent Scheduling: A major finding was that the "best" schedule isn't just hardware-dependent—it's data-dependent. A schedule that works for a scene with simple geometry might be terrible for one with complex materials. Grove’s language allows for rapid per-scene tuning that manual rewriting never could.

Key Results

Grove demonstrates that high-level abstractions don't have to come at the cost of performance:

  • Matching Experts: Grove-generated code matched or outperformed hand-optimized baselines with geomean speedups of 1.02× to 2.95×.
  • Beating Experts: Through manual exploration of the scheduling space, the authors found path-tracing schedules that beat expert-written ones by 1.3× on CPUs and 1.6× on GPUs (geomean), with peak speedups reaching 13× on specific scenes.
  • Expressiveness: Grove successfully reproduced the complex GPU wavefront architecture of PBRT—which took months of expert effort to build manually—using just 64 scheduling commands.

Limitations and Future Work

  • Manual Scheduling: Currently, a human must still decide which scheduling commands to use. The authors note that an autoscheduler (similar to those for Halide) is a natural next step.
  • Loop Nest Constraints: Grove does not yet support irregular parallel loop nests.
  • Layout Co-optimization: While Grove handles execution schedules, it doesn't yet automatically co-optimize the memory layout of the queues with the schedule, which is a known bottleneck in high-performance rendering.
  • Safety: The compiler relies on user-provided parallelism annotations and does not currently verify if those loops are actually independent.

Summary updated

Abstract

Efficient execution on modern parallel machines requires more than abundant parallelism; it demands instruction coherence, memory coherence, and load balance to maximize SIMD utilization and memory bandwidth. Efficiently mapping \textit{divergent} parallel workloads to modern machines, where control flow, memory accesses, and unbounded iteration depend on per-thread runtime values, often requires global program restructuring that trades off increased coherence with reduced locality, parallelism, or extra work. We observe that the key optimizations used to accelerate divergent parallel programs can be expressed as compositions of well-known program transformations from the functional programming and loop optimization communities. We operationalize this insight through \textit{parallel dispatch graphs}: a compilation model that represents divergent programs by representing control flow, data flow between logical stages, and parallel loops within a single abstraction. To facilitate rapid exploration of points in the optimization space, we provide a scheduling language that includes composable transformations of data-dependent control flow and data flow, together with standard loop transformations and hardware bindings. This separation of concerns allows the core algorithm to remain portable, while the execution schedule can be specialized to the specifics of target hardware and input data values. We evaluate our system using popular applications from the domain of spatial computing, and show that the optimization strategies of hand-optimized parallel tree traversals, path tracers, and Monte Carlo PDE solvers can be reproduced as schedules in our system. Our generated code matches or outperforms the hand-optimized implementations (geomeans $1.02$--$2.95\times$ faster). Additionally, we demonstrate empirically that the best schedule varies across programs, machines, and inputs.
BibTeX
@misc{root2026compilation,
  author = {Alexander J Root and Christophe Gyurgyik and Devanshu Ladsaria and Rohan Sawhney and Jonathan Ragan-Kelley and Andrew Adams and Matt Pharr and Kayvon Fatahalian and Fredrik Kjolstad},
  title = {{A Compilation Model for Divergent Parallel Workloads}},
  year = {2026},
  eprint = {2611.22183},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22183},
}
Figure