Clustering Based Job Runtime Prediction for Backfilling Using Classification

An underestimation of job runtime causes rescheduling, which has a large impact on the scheduling performance. Most of the previous studies use regression algorithms to predict the job runtime, which do not consider the difference in performance impact between underestimation and overestimation. As a result, researchers have to use additional approaches to avoid underestimation. We propose a machine learning based method that predicts the job runtime while avoiding underestimation at the same time. Instead of regression, we treat the runtime prediction problem as a classification problem to classify jobs into clusters, each of which has a predicted runtime plus a statistically reasonable offset value. To organize those clusters, past jobs recorded in log data are clustered based on their recorded runtimes, and then the standard deviation of runtimes within the cluster is also calculated so that two sigma is used as the reasonable offset for the cluster. As a result, the runtime prediction with a statistically reasonable offset value can avoid underestimation more effectively than the existing approaches, which combine regressions with additional underestimation avoidance methods. The evaluation results show that the proposed mechanism has a lower underestimation rate than the existing mechanism used with regression algorithms. Due to the lower underestimation rate, the average wait time and makespan of all the scheduled jobs using the runtime predicted by the proposed mechanism are shorter than those of the existing mechanism used with regression algorithms. Furthermore, the proposed mechanism outperforms the others in the evaluation also from a viewpoint of bounded slowdown.