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:
- Profiling: Measure speedup at a small number of thread counts (e.g., 1, 8, 16, 32).
- Approximation: Fit the data to mathematical functions, including polynomials and rational functions (ratios of two polynomials).
- 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.
Datasets and Scaling Trends
We evaluated our approach using the STAMP benchmark suite and STMBench7 on a Sun UltraSPARC T2 CPU supporting up to 64 hardware threads.
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.
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