ESTIMA

Georgios Chatzopoulos, Aleksandar Dragojević, Rachid Guerraoui

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:

  1. 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).
  2. 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.
  3. 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 intruder and yada.
  • 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 streamcluster and intruder, 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

Abstract

This paper presents ESTIMA, an easy-to-use tool for extrapolating the scalability of in-memory applications. ESTIMA is designed to perform a simple, yet important task: given the performance of an application on a small machine with a handful of cores, ESTIMA extrapolates its scalability to a larger machine with more cores, while requiring minimum input from the user. The key idea underlying ESTIMA is the use of stalled cycles (e.g. cycles that the processor spends waiting for various events, such as cache misses or waiting on a lock). ESTIMA measures stalled cycles on a few cores and extrapolates them to more cores, estimating the amount of waiting in the system. ESTIMA can be effectively used to predict the scalability of in-memory applications. For instance, using measurements of memcached and SQLite on a desktop machine, we obtain accurate predictions of their scalability on a server. Our extensive evaluation on a large number of in-memory benchmarks shows that ESTIMA has generally low prediction errors.
BibTeX
@inproceedings{chatzopoulos2016estima,
  author = {Georgios Chatzopoulos and Aleksandar Dragojević and Rachid Guerraoui},
  title = {{ESTIMA}},
  booktitle = {PPoPP},
  year = {2016},
  doi = {10.1145/2851141.2851159},
}

Loading related content...

Figure