Predicting Running Time of Grid Tasks based on CPU Load Predictions

The ability to accurately predict task running time is of great importance for interactive applications and scheduling algorithms which need to determine how to use time-shared resources in a dynamic grid environment. In this paper we present and evaluate a new method to predict the running time of tasks in a grid. The prediction of task running time is based on a novel CPU load prediction method and is calculated from predictions of CPU load. We conducted evaluations using more than 10,000 randomized testcases run on load traces sampled from 39 heterogeneous machines. Our experimental results demonstrate that both our CPU load prediction method and task running time prediction strategy outperform significantly the widely used AR(16) load prediction model and the task running-time prediction method based on this model