Enabling dynamic scheduling in computational grids by predicting CPU utilization

Scheduling divisible workloads in Grids is one of the active topics in the literature nowadays. However, most of the scheduling algorithms are static, that is, they presume that Grid resources such as CPU power and network bandwidth are constant. This assumption is plausible in a dedicated distributed system but not in a dynamic, non-dedicated environment such as the Grid where distributed computers (workers) are supposed to process local applications in addition to any incoming Grid tasks. Dynamic scheduling algorithms should divide the workload into chunks and dispatch them to Grid workers in light of their currently available resources. In this paper, we propose a methodology that can render a static scheduling algorithm dynamic by incorporating a prediction module that performs short-term prediction of the CPU utilization. To illustrate this methodology we show how to integrate the UMR, a static scheduling algorithm, with the tendency-based method, a prediction mechanism used to predict CPU loads. We believe that augmenting a static scheduling algorithm with an appropriate prediction mechanism can produce a dynamic scheduling algorithm that can handle the constantly changing properties of Grid resources.