Predicting the Scalability of an STM: A Pragmatic Approach

Aleksandar Dragojević, Rachid GuerraouiInfoscience 2010

Abstract

Conducting a thorough performance evaluation of a Software Transactional Memory (STM) system is time-consuming and often fails to predict performance on different hardware configurations. We propose a pragmatic approach using classical engineering approximation techniques to extract analytical performance functions from a limited set of measurements. We demonstrate that polynomial and rational functions provide excellent interpolations, with average errors of 1-2%. Furthermore, rational functions enable reasonably precise extrapolation, predicting performance up to $2m$ threads using data from only $m$ threads with approximately 10% error. This approach facilitates static decisions on STM usage and dynamic thread adjustment for optimal concurrency.

Introduction: The Performance Wall

Software Transactional Memory (STM) promises to simplify parallel programming by allowing code blocks to run atomically. However, its performance is a moving target. An application might scale linearly up to 16 threads but then suffer from severe contention at 32 threads. Currently, developers face a "performance wall": to understand how an STM application will behave on new hardware, they typically must run exhaustive, time-consuming experiments on that exact machine. Theoretical models often focus on worst-case scenarios, which are too pessimistic for real-world use. There is a dire need for a way to predict scalability without profiling every possible thread count.

Methodology: A Black-Box Approach

Rather than building complex analytical models based on source code analysis, we treat the STM and hardware as a "black box." We apply classical engineering curve-fitting techniques:

  1. Profiling: Measure speedup at a small number of thread counts (e.g., 1, 8, 16, 32).
  2. Approximation: Fit the data to mathematical functions, including polynomials and rational functions (ratios of two polynomials).
  3. Prediction: Use the resulting function $f(n)$ to estimate performance for any thread count $n$.

A key finding is that rational functions (specifically degree 3/3) are superior for extrapolation. Unlike polynomials, which can oscillate at the boundaries, rational functions naturally model the "peak and decline" behavior common in high-contention parallel workloads.

We evaluated our approach using the STAMP benchmark suite and STMBench7 on a Sun UltraSPARC T2 CPU supporting up to 64 hardware threads.

Speedup trends for STAMP and STMBench7 benchmarks across varying thread counts.

As shown in the figure above, different workloads exhibit vastly different scaling characteristics. Some, like Vacation Low, scale significantly, while others, like Intruder, plateau early. This diversity makes a one-size-fits-all analytical model difficult to construct.

Key Insights: Modeling Diversity and Hardware Thresholds

The primary challenge in STM performance prediction is the diversity of scaling behaviors across different workloads.

Diverse speedup curves across the STAMP benchmark suite, illustrating monotonic growth, peaking, and noisy behavior.

As illustrated in the grid above, workloads like Genome (b) show smooth asymptotic growth, while Yada (j) and Intruder (c) exhibit a distinct peak followed by a decline as contention increases. The Bayes benchmark (a) represents a significant outlier; its non-deterministic nature introduces "noise" that makes curve-fitting more difficult.

Additionally, we observed that prediction errors often spiked at multiples of 16 threads. This corresponds to the 16 execution units of our test CPU; crossing these hardware thresholds changes the underlying system behavior in ways that pure mathematical functions cannot foresee without local data points.

Results and Applications

Our results demonstrate high accuracy and practical utility:

  • Interpolation Accuracy: Using 9 data points to model up to 64 threads yielded an average error of only 1-2%.
  • Extrapolation Accuracy: Predicting 64-thread performance from 32-thread data resulted in ~10% error in the best cases.
  • Dynamic Optimization: We implemented an algorithm that profiles a few thread counts at runtime and automatically adjusts to the optimal concurrency level, typically converging in 6 to 8 steps.

This pragmatic approach requires no source code access or internal STM knowledge, making it a versatile tool for both static deployment decisions and dynamic runtime management.

Summary updated

Abstract

Conducting a thorough performance evaluation of an STM is very time consuming. Depressingly, even with all this effort, and even with the same application, it can still be hard to predict the performance if the number of underlying threads on which the application needs to be deployed is different than those of the experiment. Basically, one might have to conduct an entire set of new experiments to get some understanding of the performance of the STM with the new number of threads. We propose a pragmatic approach to contribute to changing this state of affairs. Using classical engineering approximation techniques, we extract from a set of STM performance measurements, analytical performance functions to model the scalability of the STM. We show, more specifically, that polynomial and rational functions provide good interpolations of STM performance: even with only a handful of measurements, the average error in most cases is around 1-2%. Further, we show that we can perform reasonably precise extrapolation using rational functions: basically, using measurements with up to m threads, we can predict the performance up to roughly 2m threads with a relatively low error (around 10% in best cases). We discuss two possible applications of our approach: (1) statically deciding whether to use an STM for a given workload and a given number of threads, and (2) dynamically adjusting the number of threads that execute in parallel to match the optimal concurrency level of a given workload.
BibTeX
@inproceedings{dragojevic2010predicting,
  author = {Aleksandar Dragojević and Rachid Guerraoui},
  title = {{Predicting the Scalability of an STM: A Pragmatic Approach}},
  booktitle = {Infoscience},
  year = {2010},
}
Figure