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.

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), andbind(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).

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-scenesdataset 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