Automatically batching control-intensive programs for modern accelerators

Alexey Radul, Brian Patton, Dougal Maclaurin, Matthew D. Hoffman, Rif A. Saurous

TL;DR

Researchers at Google have developed a method to automatically "batch" complex, recursive programs—like the No U-Turn Sampler (NUTS) used in Bayesian statistics—so they can run efficiently on modern accelerators like GPUs. By mechanically transforming standard Python code into a form that explicitly tracks program counters and stacks for every item in a batch, they achieved orders-of-magnitude speedups over traditional CPU-based implementations.

What Problem Does This Paper Address?

Modern accelerators (GPUs and TPUs) are built for SIMD (Single Instruction, Multiple Data) parallelism. They are incredibly fast at performing the same operation (like a matrix multiplication) on a massive block of data simultaneously. This works perfectly for standard deep learning models, which are mostly "straight-line" math.

However, many powerful algorithms—especially in probabilistic programming and Bayesian statistics—are control-intensive. They rely heavily on if/else statements, variable-length loops, and recursion. In these cases, different data points in a batch might want to take different paths through the code. Traditionally, this "divergence" makes batching nearly impossible to do by hand, forcing researchers to run these algorithms on CPUs or in "eager" modes that suffer from massive communication overhead.

Methods

The authors propose two primary strategies for "autobatching" these difficult programs:

  1. Local Static Autobatching: This approach keeps the original program structure but wraps every operation. It uses a "mask" to track which members of a batch are currently active. 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 the results for the inactive ones.
  2. Program-Counter (PC) Autobatching: This is the paper's more novel contribution. Instead of relying on the host language (Python) to handle recursion, the system materializes its own explicit stack for every variable and the program counter itself.
  3. The runtime maintains a "pool" of batch members at different points in the code.
  4. At each step, it picks a "program point" (a specific line of code) where several batch members are waiting and executes that block for all of them at once.
  5. This allows the system to batch computations even if batch members are at different recursion depths or in different subroutines.

The system is implemented as a program transformation on Python source code and is integrated into the TensorFlow Probability ecosystem.

Datasets (Test Problems)

The authors evaluated their method using the No U-Turn Sampler (NUTS), a notoriously difficult algorithm to vectorize due to its recursive nature and data-dependent stopping criteria. They tested it on two benchmarks:

  • Correlated Gaussian: A 100-dimensional synthetic problem used to measure how well the system handles varying trajectory lengths.
  • Bayesian Logistic Regression: A more "real-world" problem involving 10,000 synthetic data points and 100 regressors.

Key Insights and Ideas

  • Recursion is the Bottleneck: Standard machine learning frameworks (like XLA or TensorFlow Graph mode) cannot natively represent recursion. By moving the stack management into the data arrays themselves, the authors allow recursive programs to run entirely within high-performance graph modes.
  • Convergence vs. Divergence: In PC autobatching, threads that diverge (take different branches) can eventually "re-converge" when they hit the same subroutine later, even if they arrived there through different paths. This maximizes the number of items being processed in a single GPU kernel call.
  • The "Earliest Block" Heuristic: To decide which part of the code to run next for a batch, the authors found that simply running the "earliest" available block in the program order is surprisingly effective at keeping the batch synchronized.

Key Results

  • Linear Scaling: On GPUs, the throughput (gradients evaluated per second) scaled almost linearly with batch size.
  • Massive Speedups: The autobatched NUTS implementation on a single GPU outperformed the highly optimized, C++-based Stan (running on a CPU) by significant margins once the batch size reached into the hundreds or thousands.
  • Utilization Gains: PC autobatching recovered roughly 2x more utilization than local static batching on the Gaussian problem. It successfully synchronized gradients across different NUTS trajectories, which local methods cannot do.

Limitations and Future Work

  • Memory Overhead: Managing explicit stacks for every variable increases memory pressure. The authors implemented several compiler optimizations (like "caller-saves" disciplines) to mitigate this, but it remains a constraint for very deep recursion.
  • Gather/Scatter Costs: To batch divergent items, the system often has to "gather" data into a contiguous block and "scatter" it back. On some hardware (like TPUs), these operations can be more expensive than simply "masking" and doing extra work.
  • Static Shapes: The current implementation struggles with platforms like XLA that require all array shapes to be known statically, as the number of "active" batch members fluctuates dynamically. Future work could involve better scheduling to fit these dynamic workloads into static hardware constraints.

Summary updated

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.
BibTeX
@inproceedings{radul2020automatically,
  author = {Alexey Radul and Brian Patton and Dougal Maclaurin and Matthew D. Hoffman and Rif A. Saurous},
  title = {{Automatically batching control-intensive programs for modern accelerators}},
  booktitle = {MLSys},
  year = {2020},
  url = {https://openreview.net/forum?id=SdhqngJhGRj},
}

Loading related content...

Figure