Abstract
We present a general approach to batching arbitrary computations for accelerators such as GPUs. We show orders-of-magnitude speedups using our method on the No U-Turn Sampler (NUTS), a workhorse algorithm in Bayesian statistics. The central challenge of batching NUTS and other Markov chain Monte Carlo algorithms is data-dependent control flow and recursion. We overcome this by mechanically transforming a single-example implementation into a form that explicitly tracks the current program point for each batch member, and only steps forward those in the same place. We present two different batching algorithms: a simpler, previously published one that inherits recursion from the host Python, and a more complex, novel one that implemenents recursion directly and can batch across it. We implement these batching methods as a general program transformation on Python source. Both the batching system and the NUTS implementation presented here are available as part of the popular TensorFlow Probability software package.
Introduction
Modern accelerators like GPUs and TPUs are designed for high-throughput SIMD (Single Instruction, Multiple Data) parallelism. They excel at performing uniform operations on large data blocks, a characteristic that has fueled the deep learning revolution. However, many sophisticated algorithms—particularly in probabilistic programming and Bayesian statistics—are control-intensive. These algorithms rely on complex if/else logic, variable-length loops, and recursion.
When different data points in a batch take different execution paths, they "diverge," making traditional batching nearly impossible to implement manually. This often forces researchers to run these algorithms on CPUs, missing out on the massive parallel potential of modern hardware.
Methodology: Autobatching Strategies
The researchers developed a system to automatically transform standard Python code into a batched version. They propose two primary strategies:
1. Local Static Autobatching
This approach maintains the original program structure but wraps operations with a "mask." The mask tracks which batch members are active for a given branch. If an if statement splits the batch, the system executes the "true" branch for some members and then the "false" branch for others, masking out results for inactive members at each step.
2. Program-Counter (PC) Autobatching
PC autobatching is the more advanced contribution, designed to handle recursion and complex divergence more efficiently. Instead of relying on Python's native stack, the system materializes an explicit stack for every variable and the program counter (PC) itself.
As illustrated in Figure 1, the runtime maintains a pool of batch members at different program points. At each execution step, it selects a specific line of code where multiple members are waiting and executes that block for all of them simultaneously. This allows the system to batch computations even when members are at different recursion depths, maximizing hardware utilization.
Implementation and Stack Management
To enable recursive programs to run entirely within high-performance graph modes (like XLA or TensorFlow Graph), which typically do not support recursion, the system embeds stack management directly into the data arrays.
Figure 2 shows how the system tracks recursion depth using stack pointers for each variable. This explicit representation allows the runtime to manage complex control flow dynamically. By moving the stack into the data, the system can perform "re-convergence," where threads that diverged earlier can be processed together again when they reach the same subroutine.
Experimental Evaluation: The NUTS Benchmark
The system was tested using the No U-Turn Sampler (NUTS), a notoriously difficult algorithm to vectorize due to its recursive nature and data-dependent stopping criteria. Benchmarks included a 100-dimensional Correlated Gaussian problem and a Bayesian Logistic Regression problem with 10,000 data points.
Key Results
- Linear Scaling: Throughput (gradients evaluated per second) on GPUs scaled almost linearly with batch size.
- Significant Speedups: The autobatched NUTS implementation on a single GPU significantly outperformed the highly optimized, C++-based Stan running on a CPU once batch sizes reached the hundreds.
- Utilization Gains: PC autobatching recovered approximately 2x more utilization than local static batching on the Gaussian problem by successfully synchronizing gradients across divergent trajectories.
Limitations and Future Work
Despite its success, the method has constraints. Managing explicit stacks increases memory pressure, requiring optimizations like "caller-saves" disciplines. Additionally, the gather/scatter costs associated with grouping divergent items can be high on some hardware, such as TPUs. Future research will focus on better scheduling heuristics to handle the dynamic nature of these workloads within the static shape constraints of compilers like XLA.
Summary updated