A Pragmatic Approach for Predicting the Scalability of Parallel Applications

Aleksandar Dragojević, Rachid GuerraouiInfoscience 2012

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 PreSca methodology: using measured points and checkpoints to select the best predictive model.

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:

  1. Interpolation: Using just 8 measurements, the 90th percentile of error was lower than 15%.
  2. 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.
  3. Dynamic Scheduling: OPreSca determined optimal thread counts in fewer than 7 steps, with errors lower than 3% on average.
Scalability curves for Kmeans and Vacation benchmarks, illustrating the variance and non-linear behavior PreSca aims to model.

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

Abstract

Predicting the scalability of parallel applications is becoming crucial now that the number of cores in modern CPUs doubles roughly every two years. Traditional ways to get some understanding of the scalability of a parallel application rely on extensive experiments or detailed application models. Both are very time consuming and often hard to use. This paper presents PreSca, a pragmatic system for predicting the scalability of parallel applications. PreSca uses function approximation techniques to model scalability with an analytical performance function extracted from a set of measurements. By considering the application as a black-box without requiring any knowledge about its internals, PreSca can be applied with little effort to any parallel application. We show how PreSca can be used statically to predict the scalability of a given application and decide which synchronization primitive scales best for it as well as how it can be used on-line to dynamically assist scheduling decisions and adjust core assignment. In some sense, PreSca shows, for the first time, how function approximation can be used to predict the scalability of parallel applications in a completely general way. We extensively evaluated PreSca using a large number of parallel benchmarks, including some that use locks and some that use transactional memory. We also consider two different multicore systems. Our evaluation shows that PreSca produces accurate results. More specifically: (1) PreSca’s interpolations based on only 8 measurements have 90th percentile of error lower than 15%, (2) PreSca’s extrapolations using measurements with up to m cores predict the performance for n ≤ 2m cores with errors lower than 20 % in most cases, and (3) PreSca’s on-line scheduler determines the optimal thread count using fewer than 7 measurements with errors lower than 3 % on average. 1.
BibTeX
@inproceedings{dragojevic2012pragmatic,
  author = {Aleksandar Dragojević and Rachid Guerraoui},
  title = {{A Pragmatic Approach for Predicting the Scalability of Parallel Applications}},
  booktitle = {Infoscience},
  year = {2012},
}
Figure