A prediction method for job runtimes on shared processors: Survey, statistical analysis and new avenues

Grid computing is an emerging technology by which huge numbers of processors over the world create a global source of processing power. Their collaboration makes it possible to perform computations that are too extensive to perform on a single processor. On a grid, processors may connect and disconnect at any time, and the load on the computers can be highly bursty. These characteristics raise the need for the development of techniques that make grid applications robust against the dynamics of the grid environment. In particular, applications that use significant amounts of processor power for running jobs need effective predictions of the expected computation times of those jobs on remote hosts. Currently, there are no effective prediction methods available that cope with the ever-changing running times of jobs on a grid environment. Motivated by this, we develop the Dynamic Exponential Smoothing (DES) method to predict running times in a grid environment. The main idea behind DES is that it dynamically adapts its prediction strategy to the height of the fluctuations in those running times. We have performed extensive experiments in a real global-scale grid environment to compare the effectiveness of DES. The results demonstrate that DES strongly and consistently outperforms existing prediction methods.