Runtime Prediction of Parallel Programs

Abstract

Applications today are presented with the difficulty of performing growingly complex, intensive computations on increasingly large datasets. Modern machines are developing in the trend of having more and more processors per machine to allow for efficient executions of these demanding applications. Parallelization allows programs to take advantage of multicore machines and generate execution time speedups. For one parallel application, the scheduler's job is simple. However, on multi-tenanted machines with complex execution deadlines, it can be very difficult to schedule parallel programs for maximum resource utilization. A key component of this challenge is the difficulty of knowing how long it takes a program to run on any given number of cores, and how much speedup is gained when the core allocation amount is increased.In this paper we present a method of predicting parallel program runtime using a minimal number of sample executions. Our key insight is that all parallel programs exhibit similar, predictable speedup behavior and thus can be utilized to predict runtime of other programs. We use training runs of a set of benchmark programs to construct a model that predicts the runtime of new programs on different numbers of cores. The model built uses a combination of machine learning and equation fitting, and with just two sample runs of the new program, we can achieve runtime predictions with less than 15% error from real values for the majority of programs tested. Additionally, the combined approach model yields average percentage error within 5% of predictions using more sample runs for 10 of the 17 applications.