TL;DR
This paper introduces ESTIMA, a tool that predicts how well in-memory applications will scale to more CPU cores. By analyzing "stalled cycles" – processor cycles spent waiting for resources – ESTIMA can forecast performance on larger machines with minimal user input, offering a simpler alternative to extensive performance testing.
What Problem Does This Paper Address?
Modern applications increasingly rely on in-memory data storage, enabling faster processing by avoiding slow disk I/O. However, as the number of CPU cores on servers continues to grow rapidly, predicting how these applications will perform on future hardware becomes challenging. Traditional methods for assessing scalability, like exhaustive performance testing or complex modeling, are time-consuming, error-prone, and require deep system knowledge. This leaves a gap for a more accessible and efficient way to forecast application performance as core counts increase.
Methods
ESTIMA's core innovation lies in its use of "stalled cycles" to predict scalability. Stalled cycles are processor cycles that aren't spent doing useful work, often due to waiting for data from memory (cache misses) or contention for shared resources (like locks). The tool works in three main stages:
- Stalled Cycles Collection: ESTIMA runs the application on a small number of cores, collecting hardware performance counter data for "backend stalls" (cycles spent waiting during instruction execution). Optionally, it can also collect software-level stalls (e.g., from transactional memory aborts or spinlock contention).
- Stalled Cycles Approximation: It uses regression analysis with predefined function kernels to model the collected stall data. This allows ESTIMA to extrapolate stall behavior to higher core counts.
- Translating Stalled Cycles to Execution Time: ESTIMA calculates the total stalled cycles per core and then uses a scaling factor, derived from both stall data and measured execution times, to predict the application's execution time on larger core configurations.
A key aspect is ESTIMA's focus on fine-grained hardware stall events rather than aggregate ones, which are found to be more sensitive to early scalability changes.
Datasets
The paper evaluates ESTIMA using a variety of benchmarks and real-world applications, including:
- Production Applications: memcached and SQLite (with a TPC-C workload).
- Benchmark Suites: STAMP (e.g., intruder, genome, yada, kmeans, streamcluster), PARSEC (e.g., blackscholes, raytrace), and standard STM micro-benchmarks.
- Custom Kernel: A k-nearest neighbors (KNN) calculation kernel.
These benchmarks cover diverse workloads, critical section lengths, and synchronization techniques, including Software Transactional Memory (STM). The evaluation involves cross-machine predictions (e.g., desktop to server) and scaling experiments on different hardware platforms.
Key Insights and Ideas
- Stalled Cycles as a Scalability Predictor: The central idea is that the behavior of stalled cycles, particularly backend stalls, directly correlates with an application's scalability. As core counts increase, contention for resources often leads to more stalls, which in turn degrades performance.
- Fine-Grained Stalls are Crucial: Using detailed hardware stall events (e.g., specific pipeline stalls) provides earlier indicators of scalability issues than aggregate stall counters or simply measuring execution time. This allows ESTIMA to predict slowdowns before they become significant in actual execution time.
- Software Stalls Enhance Accuracy: While hardware stalls are sufficient, incorporating software stall information (like STM aborts or synchronization overheads) can significantly improve prediction accuracy, especially for applications with complex concurrency.
- Beyond Time Extrapolation: Directly extrapolating execution time can be misleading, especially when scalability changes are not yet evident in measurements on a small number of cores. ESTIMA's stall-based approach offers a more robust alternative.
- Bottleneck Identification: The detailed stall information collected by ESTIMA can also help pinpoint the root causes of scalability limitations, guiding developers towards specific optimization targets.
Key Results
- Accurate Predictions: ESTIMA achieved low prediction errors across a wide range of benchmarks. For predictions on machines with up to four times more cores than used for measurements, errors were below 15% for over half of the applications.
- Cross-Machine Prediction Success: ESTIMA accurately predicted the scalability of memcached and SQLite on server machines based on measurements from desktop machines, with errors generally below 30%.
- Capturing Scalability Trends: ESTIMA successfully predicted when applications would stop scaling, even when these trends were not apparent in the initial measurements. This was particularly evident in applications like
intruderandyada. - Software Stall Improvement: Incorporating software stall data improved prediction accuracy by an average of 57%, and up to 87% for specific cases.
- Bottleneck Identification Impact: By identifying bottlenecks, ESTIMA helped developers optimize
streamclusterandintruder, leading to performance improvements of up to 74% and 70%, respectively.
Limitations and Future Work
- Architecture Similarity: ESTIMA performs best when predicting scalability between machines with similar architectures. Cross-platform predictions with significant architectural differences may yield less accurate results.
- Workload Configuration: ESTIMA is not designed to predict performance for drastically different workload configurations, as it doesn't perform static or dynamic analysis of the target application's behavior.
- NUMA Effects: While ESTIMA can capture NUMA effects if they are present in the measurement machine (like the Opteron), it might not inherently account for them if they are absent in the measurement setup but present in the target machine (like some Intel Xeon configurations).
- Future Work: The authors suggest that ESTIMA's core functionality can be extended to support more complex scenarios, and its generality and ease of use make it a valuable tool for developers and users alike. The potential for further integration of application-specific inputs to enhance accuracy is also highlighted.
Summary updated