Home > Published Issues > 2007 > Volume 2, No. 4, June 2007 >

A Dynamic Scheduling Algorithm for Divisible Loads in Grid Environments

Nguyen The Loc1 and Said Elnaffar2
1. Hanoi National University of Education, Hanoi, VietNam
2. College of IT, UAE University, Al-Ain, UAE

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.