Astro: Scaling the Unscalable - Auto-Generating Synthetic Traces for Massive MPI Workloads

TL;DR

Performance modeling for High-Performance Computing (HPC) often hits a wall: you need large-scale traces to model large-scale systems, but you can't get those traces without already having a large-scale system. Astro breaks this cycle. It uses machine learning to recognize scaling patterns in small-scale MPI traces and synthetically extrapolates them to thousands of ranks with less than 15% error, even for proprietary codebases.

The Bottleneck of Modern HPC Modeling

As we push toward exascale computing, two traditional methods dominate workload representation:

1. Trace-driven simulation: Accurate but requires massive disk space and access to the very clusters the architect is trying to design.
2. Workload Skeletons: Efficient but requires weeks of manual source-code instrumentation and is useless for "black-box" proprietary software.

The authors of Astro identified a crucial insight: most well-written MPI programs exhibit structured scaling patterns. Whether it is a 3D stencil or an algebraic multigrid solver, the way computation and communication grow as you add more ranks follows mathematical rules.

Methodology: The Divide-and-Conquer Approach

Astro doesn't try to model the entire workload as a single block. Instead, it builds a Call Transition Graph (CTG). Each vertex is an MPI call site, and each edge represents the computation (instruction count) between calls.

1. Scaling Pattern Classification

Astro classifies scaling into four categories to apply the right mathematical tool for the job:

• Constant: Values remain the same regardless of scale.
• Cluster Value Scaling: Uses regression to see how a value (like message size) grows with rank count ($C_r$).
• Pattern Scaling with Rank Count: Handles cases where the communication topology changes complexity as the system grows.
• Compound Scaling: Uses Decision Trees to handle complex if-else logic that depends on rank ID ($R_{id}$) and iteration count ($C_{it}$).

2. The "Split-and-Merge" Algorithm

To handle non-linear scaling, Astro introduces a sequence segmentation algorithm. It divides the value distribution into segments that demonstrate consistent behavior (like replication or insertion) across scales. This allows Astro to "see" how a communication pattern expands.

Experimental Results: Benchmarking the Future

The authors tested Astro against the CORAL workload suite, including complex codes like AMG (Algebraic MultiGrid) and HACC (Cosmology simulation).

Fidelity across Metrics

Astro maintained impressive accuracy even when extrapolating from 512 ranks up to 8,192 ranks:

• Instruction Count: Error rates were stable, generally remaining well below 10% after adjusting for sequence displacement.
• Message Size: Even with the load imbalance inherent in AMG, Astro captured the scaling trends effectively.
• Destination Ranks: For point-to-point communication, the predicted destination ranks matched original traces with high density at zero error.

Comparison with ScalaExtrap

A critical win for Astro is its ability to handle non-linear and non-stencil patterns. Previous SOTA tools like ScalaExtrap often fail when communication periods change or when iteration counts follow staircase functions. Astro’s use of autocorrelation and decision trees allows it to thrive where previous tools broke.

Critical Analysis & Conclusion

Astro represents a significant shift from "collecting data" to "learning patterns."

Strengths:

• Zero Source Code Requirement: Works on binary-intercepted traces.
• Resource Efficiency: Generates 8K-rank traces on a single node.
• Versatility: Handles complex patterns (FFT, Master-Worker) that stymied previous efforts.

Limitations:

• Pattern Coverage: If a scaling pattern only emerges at very high ranks (not present in the small training set), Astro cannot predict it.
• Determinism: Highly non-deterministic workloads (e.g., using random numbers for communication targets) remain a challenge for any trace-based tool.

In conclusion, Astro provides a robust bridge between local experimentation and large-scale performance projection, making it an essential framework for the next generation of HPC architects.