Fast Algorithms for Scheduling Many-body Correlation Functions on Accelerators

Oguz Selvitopi, M. Emin Ozturk, Jie Chen, Ponnuswamy Sadayappan, Robert G. Edwards, Aydin Buluç

Introduction

In nuclear physics, Lattice Quantum Chromodynamics (LQCD) simulations are essential for understanding the interactions of quarks and gluons within hadrons. These simulations involve calculating complex "correlation functions" through thousands of tensor contractions. However, a significant hardware bottleneck exists: the memory capacity of modern GPUs (typically 32–80 GB) is often insufficient to hold the massive tensors required for a single baryon node calculation (up to 2 GB each). This disparity necessitates frequent data transfers between fast GPU memory and slower CPU host memory via the PCIe bus. Poor scheduling of these contractions leads to excessive "evictions," where tensors are moved out of memory only to be reloaded shortly after, creating a substantial I/O bottleneck.

The Contraction Problem

The computational workload in LQCD can be modeled as a Directed Acyclic Graph (DAG) composed of multiple contraction trees. Each node represents a tensor, and edges represent dependencies where child tensors are contracted to form a parent tensor. Efficiently navigating this DAG is critical for minimizing the peak memory footprint and reducing data traffic.

Contraction trees and the resulting Directed Acyclic Graph (DAG) representing tensor dependencies.

Proposed Scheduling Strategies

To address the memory bottleneck, this research introduces two novel scheduling algorithms designed to improve temporal locality by keeping data on the GPU for as long as it is needed.

1. Sibling Scheduler

The Sibling Scheduler is a computationally efficient, bottom-up approach. It prioritizes completing "sibling" nodes—tensors that share the same parent. By finishing all children of a specific parent node quickly, the parent contraction can be executed, allowing the child tensors to be released from memory immediately. While effective for smaller, shallower graphs, its local focus means it does not account for varying tensor sizes, which can limit its effectiveness in more complex physics problems.

2. Tree Scheduler

The Tree Scheduler adopts a more sophisticated global perspective. Rather than focusing on individual nodes, it treats entire contraction trees as the primary units of scheduling. It utilizes a dynamic "gain" metric to decide the processing order.

The Tree Scheduler uses a 'tgain' metric to prioritize trees that free the most memory upon completion.

A "high gain" tree is one that, once fully processed, allows the maximum amount of memory to be freed across the entire DAG. This global awareness allows the Tree Scheduler to make smarter decisions for massive datasets, such as those involving three-baryon systems (e.g., tritium), where memory management is most critical.

Experimental Evaluation

The algorithms were integrated into the Redstar LQCD analysis suite and tested against six hadronic correlation functions of varying complexity, from simple mesons (a0-111) to complex three-baryon systems (tritium).

Compared to the default sorting-based scheduler (RS-GS), the proposed methods achieved significant performance improvements:

  • Peak Memory Reduction: Up to 2.1x improvement.
  • Eviction Reduction: Data evictions dropped by up to 4.2x.
  • Data Traffic: Total PCIe data movement was reduced by up to 1.8x.
  • Total Runtime: These optimizations resulted in a nearly 2x speedup in total computation time.

Conclusion

As computational power continues to outpace memory bandwidth, algorithmic scheduling becomes a primary lever for performance in high-performance computing. The Sibling and Tree schedulers demonstrate that intelligent reordering of operations can effectively mitigate the I/O bottleneck in LQCD simulations. Future work will explore more granular node-based scheduling and multi-GPU partitioning to further scale these simulations for even larger physical systems.

Summary updated

BibTeX
@inproceedings{selvitopi2026fast,
  author = {Oguz Selvitopi and M. Emin Ozturk and Jie Chen and Ponnuswamy Sadayappan and Robert G. Edwards and Aydin Buluç},
  title = {{Fast Algorithms for Scheduling Many-body Correlation Functions on Accelerators}},
  booktitle = {IPDPS},
  year = {2026},
  doi = {10.1109/ipdps65963.2026.00036},
}
Figure