Performance Prediction of Parallel Applications

Accurate estimates of parallel application runtimes are useful for better job scheduling and utilization of high performance computing resources, application code fine-tuning, power consumption, and improved response time. Current approaches to predict runtimes of parallel applications rely on application code analyses or construction of elaborate skeleton execution models that mimic the applications' characteristics. These approaches require expertise in the application domain and significant manual work. In this work, we develop newer runtime prediction techniques based on statistical analyses, the fractal theory, and curve fitting techniques, using currently available tools for profiling and a few pre-runs of the application for small input sizes.

For scientific Central Processing Unit (CPU) and Graphics Processing Unit (GPU) applications, we present prediction methods that use small input executions to identify the execution trends of major execution phases of an application and predict phase runtimes for the target input size using statistical analysis and execution profiles of a database of kernels or using fractal models. The overall runtimes are estimated by aggregating the phase runtimes and non-phase runtimes.

For parallel iterative machine learning applications that train classifiers and use gradient descent optimization, we predict runtimes using curve-fitting techniques to predict the number of iterations and time to complete. We implemented these runtime prediction models on a cluster of 288 CPU cores and multiple GPUs and evaluated their accuracy. Our results show that the proposed runtime prediction techniques can provide accurate runtime estimates with errors of less than 15% in most cases.

In addition, we designed and developed a tool that leverage our prediction techniques to automate the prediction of runtimes for a wide variety of applications. Our techniques, which avoid manual analyses of application codes, are particularly suitable to be used in our automated tool. Our tool delivers accurate predictions with little user intervention by automatically analyzing the characteristics of the application whose runtime is to be predicted and selecting an appropriate technique for the prediction. This is the first tool to automate the prediction of runtimes for a wide variety of CPU and GPU applications.