A dynamic scheduling algorithm for divisible loads in grid environments

被引:0
作者
Loc, Nguyen The [1 ]
Elnaffar, Said [2 ]
机构
[1] Hanoi National University of Education, Hanoi
[2] College of IT, UAE University, Al-Ain
来源
Journal of Communications | 2007年 / 2卷 / 04期
关键词
CPU power prediction; Divisible loads; Grid scheduling;
D O I
10.4304/jcm.2.4.57-64
中图分类号
学科分类号
摘要
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. © 2006 ACADEMY PUBLISHER.
引用
收藏
页码:57 / 64
页数:7
相关论文
共 14 条
[1]  
Bharadwaj V., Ghose D., Mani V., Robertazzi T.G., Scheduling Divisible Loads in Parallel and Distributed Systems, (1996)
[2]  
Foster I., Kesselman C., Grid2: Blueprint for a New Computing Infrastructure, (2003)
[3]  
Nguyen T.L., Elnaffar S., Katayama T., Ho T.B., MRRS: A More Efficient Algorithm for Scheduling Divisible Loads of Grid Applications, IEEE/ACM International Conference on Signal-Image Technology and Internet-based Systems (SITIS'06), (2006)
[4]  
Nguyen T.L., Elnaffar S., Katayama T., Ho T.B., UMR2: A Better and More Realistic Scheduling Algorithm for the Grid, International Conference on Parallel and Distributed Computing and Systems (PDCS'06), pp. 432-437, (2006)
[5]  
Beaumont O., Legrand A., Robert Y., Scheduling Divisible Workloads on Heterogeneous Platforms, Parallel Computing, 9, (2003)
[6]  
Yang Y., Raart K.V., Casanova H., Multiround Algorithms for Scheduling Divisible Loads, IEEE Transaction on Parallel and Distributed Systems, 16, (2005)
[7]  
Yang Y., Casanova H., RUMR: Robust Scheduling for Divisible Workloads, HPDC'03, (2003)
[8]  
Nguyen T.L., Elnaffar S., Katayama T., Bao H.T., A Scheduling Method for Divisible Workload Problem in Grid Environments, PDCAT'05, (2005)
[9]  
Yang L., Schopf J., Foster I., Homeostatic and Tendency-based CPU Load Predictions, IPDPS'03, (2003)
[10]  
Yang L., Schopf J., Foster I., Conservative Scheduling: Using Predicted Variance to Improve Scheduling Decision in Dynamic Environments, SuperComputing, (2003)