Abstract—Divisible loads are those workloads that can bepartitioned by a scheduler into any arbitrary chunks. Theproblem of scheduling divisible loads has been defined for along time, however, a handful of solutions have beenproposed. Furthermore, almost all proposed approachesattempt to perform scheduling in dedicated environmentssuch as LANs, whereas scheduling in non-dedicatedenvironments such as Grids remains an open problem. InGrids, the incessant variation of a worker's computingpower is a chief difficulty of splitting and distributingworkloads to Grid workers efficiently. In this paper, wefirst introduce a computation model that explains theimpact of local (internal) tasks and Grid (external) tasksthat arrive at a given worker. This model helps estimate theavailable computing power of a worker under thefluctuation of the number of local and Grid applications.Based on this model, we propose the CPU power predictionstrategy. Additionally, we build a new dynamic schedulingalgorithm by incorporating the prediction strategy into astatic scheduling algorithm. Lastly we demonstrate that theproposed dynamic algorithm is superior to the existingdynamic and static algorithms by a comprehensive set ofsimulations.

Index Terms—CPU power prediction, divisible loads, Gridscheduling.

Cite: Nguyen The Loc and Said Elnaffar, "A Dynamic Scheduling Algorithm for Divisible Loads in Grid Environments," Journal of Communications, vol. 2, no. 4, pp. 57-64, 2007.