Abstract
Predicting the scalability of parallel applications is becoming crucial as CPU core counts continue to double every few years. Traditional methods for understanding scalability rely on exhaustive experimentation or complex application-specific models, both of which are time-consuming and difficult to implement. This paper presents PreSca, a pragmatic system that uses function approximation to model scalability via an analytical performance function extracted from a small set of measurements. By treating applications as black boxes, PreSca can be applied to any parallel workload with minimal effort. Our evaluation shows that PreSca achieves high accuracy, with 90th percentile errors below 15% using only eight measurements, and can effectively assist in both static design decisions and dynamic runtime scheduling.
The Scalability Wall
Parallel programming is inherently difficult, but predicting how a program will behave on future hardware is even harder. A developer might write an application on an 8-core machine today, but in two years, that same code might run on a 32- or 64-core server. Ideally, adding more cores should make an application faster; in reality, performance often plateaus or even crashes due to synchronization bottlenecks (like locks) or hardware contention.
Traditionally, understanding this "scalability curve" required either exhaustive testing on expensive hardware or building complex mathematical models. PreSca offers a pragmatic middle ground: treating the application as a black box and using curve-fitting to forecast future performance.
Methodology: Function Approximation
PreSca operates on the principle of function approximation rather than assuming a single model (like Amdahl’s Law) fits every scenario. The system maintains a "kernel" of diverse analytical functions, including rational functions, cubic logs, and exponential ratios.
The system mimics a human "eyeballing" a graph to draw a line of best fit. It takes a small set of measurements (e.g., performance at 2, 4, and 8 threads) and uses them as training data to fit various functions. It then utilizes "checkpoints" to validate which function is the most accurate. To ensure realistic results, PreSca employs heuristic filtering to discard functions that predict impossible outcomes, such as negative execution times or physically improbable performance jumps.
Beyond static prediction, the researchers introduced OPreSca, a dynamic version for online scheduling. OPreSca runs alongside an application, measuring performance at different thread counts in short intervals to quickly converge on the optimal number of threads for maximum throughput.
Evaluation and Key Insights
The authors evaluated PreSca across two hardware architectures (a 64-thread UltraSparc T2 and a 48-thread AMD Opteron) using major benchmark suites like STAMP, PARSEC, and STMBench7. Several key insights emerged:
- The Black-Box Advantage: Because PreSca does not need to understand why a synchronization primitive is slow, it is highly portable across different languages and techniques.
- Kernel Diversity: No single mathematical function was a universal winner. The strength of the approach lies in trying multiple models and selecting the one that fits the specific workload's scalability "flavor."
- Less is More: Surprisingly, using fewer measurement points sometimes led to better predictions. High-thread measurements can be noisy; by focusing on the trend of the initial points, the model often avoids being steered in the wrong direction by outliers.
Results and Limitations
PreSca demonstrated remarkable accuracy across various scenarios:
- Interpolation: Using just 8 measurements, the 90th percentile of error was lower than 15%.
- Extrapolation: When predicting performance for double the number of measured cores (e.g., using 16-core data to predict 32-core performance), errors remained under 20% in most cases.
- Dynamic Scheduling: OPreSca determined optimal thread counts in fewer than 7 steps, with errors lower than 3% on average.
Despite its success, PreSca faces challenges with "performance cliffs"—abrupt, non-linear drops caused by hardware limits (like cache capacity) that are not visible in early measurements. Additionally, in applications with high performance variance, such as the kmeans benchmark, noisy checkpoints can lead the system to select sub-optimal models. While PreSca is a powerful predictive tool, it remains a black-box system; it can tell a developer that an application will not scale, but it cannot diagnose the specific line of code causing the bottleneck.
Summary updated