ISSN : 1796-2021
Volume : 2    Issue : 4    Date : June 2007

A Dynamic Scheduling Algorithm for Divisible Loads in Grid Environments
Nguyen The Loc and Said Elnaffar
Page(s): 57-64
Full Text:
PDF (389 KB)

Divisible loads are those workloads that can be partitioned by a scheduler into any arbitrary chunks.
The problem of scheduling divisible loads has been defined for a long time, however, a handful of
solutions have been proposed. Furthermore, almost all proposed approaches attempt to perform
scheduling in dedicated environments such as LANs, whereas scheduling in non-dedicated
environments such as Grids remains an open problem. In Grids, the incessant variation of a
worker's computing power is a chief difficulty of splitting and distributing workloads to Grid workers
efficiently. In this paper, we first introduce a computation model that explains the impact of local
(internal) tasks and Grid (external) tasks that arrive at a given worker. This model helps estimate the
available computing power of a worker under the fluctuation of the number of local and Grid
applications. Based on this model, we propose the CPU power prediction strategy. Additionally, we
build a new dynamic scheduling algorithm by incorporating the prediction strategy into a static
scheduling algorithm. Lastly we demonstrate that the proposed dynamic algorithm is superior to the
existing dynamic and static algorithms by a comprehensive set of simulations.

Index Terms
CPU power prediction, divisible loads, Grid scheduling.