TL;DR
This paper introduces two novel scheduling algorithms—the Sibling Scheduler and the Tree Scheduler—designed to manage massive tensor contractions in Lattice QCD simulations. By optimizing the order of operations to minimize peak memory usage on GPUs, these algorithms reduce slow data transfers (evictions) by up to 4.2x and speed up total computation time by nearly 2x.
What Problem Does This Paper Address?
In the world of nuclear physics, researchers use Lattice Quantum Chromodynamics (LQCD) to simulate how quarks and gluons interact to form hadrons (like protons and neutrons). These simulations require calculating "correlation functions," which involve thousands of complex tensor contractions.
The challenge is a classic hardware bottleneck: memory. A single baryon node can require 2 GB of memory, while a high-end GPU might only have 32–80 GB. Because these tensors are too large to fit all at once, the system must constantly move data between the fast GPU memory and the slower CPU (host) memory via the PCIe bus. If the contractions are scheduled poorly, the system "evicts" tensors prematurely, only to reload them moments later, creating a massive data traffic jam that slows down the entire simulation.
Methods
The authors propose two distinct scheduling strategies to reorder these contractions and improve "temporal locality" (keeping data on the GPU as long as it's needed):
- Sibling Scheduler: This is a fast, "bottom-up" approach. It exploits the fact that most contractions in this field are binary (two inputs, one output). It prioritizes completing "sibling" nodes—tensors that share the same parent—so that the parent contraction can be performed and the children tensors can be released from memory as quickly as possible.
- Tree Scheduler: This is a more sophisticated, "global" approach. Instead of looking at individual contractions, it treats entire contraction trees as units. It uses a "gain" metric to dynamically decide which tree to process next based on the current state of GPU memory. A "high gain" tree is one that, once processed, allows the most memory to be freed.
Both schedulers were integrated into Redstar, a widely used LQCD analysis software suite, allowing for real-world performance testing.
Datasets
The algorithms were evaluated using six different hadronic correlation functions that represent various physical systems, ranging from simple mesons to complex three-baryon systems:
- Meson-Meson:
a0-111,a0-d3 - Three-Meson:
f0 - Baryon-Meson:
roper - Baryon-Baryon:
deuteron - Three-Baryon:
tritium(the most complex, involving $O(N^5)$ complexity)
These datasets vary in the number of contraction trees (from ~4,000 to over 100,000) and the size of the tensors involved.
Key Insights and Ideas
- Local vs. Global Trade-offs: The Sibling scheduler is computationally "cheap" and works best for smaller, shallower graphs. However, because it doesn't consider the actual size of the tensors, it can struggle with larger, more complex physics problems.
- The Power of "Gain": The Tree scheduler’s ability to look at the "global state" of memory is its secret weapon. By calculating how much memory a specific sequence will free up across the entire DAG (Directed Acyclic Graph), it makes much smarter decisions for massive datasets like
tritium. - Data Movement is the Real Enemy: The results confirm a growing trend in high-performance computing: as processors get faster, the time spent moving data (the "IO bottleneck") becomes the primary limiting factor. Algorithmic scheduling is often more effective than raw hardware upgrades for these workloads.
Key Results
The proposed schedulers significantly outperformed the default "RS-GS" (sorting-based) scheduler used in Redstar:
- Peak Memory Reduction: Improved by up to 2.1x.
- Eviction Reduction: The number of times data had to be kicked out of GPU memory dropped by up to 4.2x.
- Data Traffic: Total data moved over the PCIe bus was reduced by up to 1.8x.
- Total Runtime: These memory optimizations led to a 1.9x speedup in the actual time-to-solution for correlation function computations.
Limitations and Future Work
While the Tree scheduler is highly effective, it has a higher "scheduling overhead" (the time the CPU spends planning the order) than the Sibling scheduler. Although this overhead is currently negligible compared to the hours-long physics simulations, it could grow with even larger datasets.
The authors suggest two main paths for future research:
- General Node-Based Scheduling: Moving beyond "trees" to a more granular scheduler that applies the "gain" concept to every individual node in the graph.
- Multi-GPU Support: Developing partitioning models to intelligently split these massive contraction graphs across multiple GPUs to further scale the simulations.
Summary updated