收稿日期: 2010-03-05
修回日期: 2010-05-10
网络出版日期: 2011-01-20
基金资助
国家863项目(2006AA01A110)和国家自然科学基金(60273041)资助
A quality-driven algorithm for task scheduling in grid market
Received date: 2010-03-05
Revised date: 2010-05-10
Online published: 2011-01-20
宋浒 , 杨寿保 , 刘晓茜 , 郭良敏 . 网格市场中服务质量驱动下的任务调度算法[J]. 中国科学院大学学报, 2011 , 28(1) : 86 -93 . DOI: 10.7523/j.issn.2095-6134.2011.1.013
We propose a quality-driven algorithm for task scheduling in grid market, which is deadline- and budget-constrained and maximizes number of completed tasks (DBCN). This algorithm combines the high throughput advantage of Min-min algorithm and the global optimization advantage of linear programming. Meanwhile the algorithm considers not only all the tasks but also those prior ones. Compared with the Min-min and DBCT classical algorithms, DBCN completes about 10.6% and 22.0% more tasks and about 20% and 40% more prior tasks, respectively.
Key words： grid market; QoS; deadline and budget; scheduling algorithm
[1] Buyya R, Abramson D, Giddy J. Economy driven resource management architecture for computational power Grids //PDPTA ’00: Proceedings of the 7th International Conference on Parallel and Distributed Processing Techniques and Applications. 2000.
[2] Ravi B, Sanjukta D, Robert G, et al. A market design for grid computing
[J]. INFORMS Journal on Computing, Forthcoming, 2007, 20(1):100-111.
[3] Stuer G, Vanmechelen K, Broeckhove J. A commodity market algorithm for pricing substitutable grid resources
[J]. Future Generation Computer Systems, 2007, 23(5):688-701.
[4] Buyya R, Murshe M, Abramson D. A deadline and budget constrained cost-time optimization algorithm for scheduling task farming applications on global grids //ICPDP ’02: The 2002 International Conference on Parallel and Distributed Processing Techniques and Applications. Las Vegas, Nevada, USA, 2002.
[5] Buyya R, Abramson D, Giddy J. Nimrod/G: An architecture for a resource management and scheduling System in a Global Computational Grid //HPC ASIA 2000: 4th International Conference and Exhibition on High Performance Computing in Asia-Pacific Region. Beijing, 2000.
[6] Armstrong R, Hensgen D, Kidd T. The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions //HCW ’98: the 7th IEEE Heterogeneous Computing Workshop. 1998:79- 87.
[7] Freund R, Gherrity M, Ambrosius S, et al. Scheduling resources in multi-user, heterogeneous, computing environments with SmartNet //HCW ’98: the 7th IEEE Heterogeneous Computing Workshop. 1998: 184-199.
[8] Ibarra O, Kim C. Heuristic algorithms for scheduling independent tasks on nonidentical processors
[J]. Journal of the ACM, 1997, 77(2): 280-289.
[9] Buyya R, Giddy J, Abramson D. An evaluation of economy-based resource trading and scheduling on computational power grids for parameter sweep applications //AMS ’00: The Second Workshop on Active Middleware Services, Pittsburgh, USA, 2000.
[10] Garg S, Konugurthi P, Buyya R. A linear programming driven genetic algorithm for meta-scheduling on utility grids //ADCOM’ 08: The 16th International Conference on Advanced Computing and Communications, Chennai, India, 2008: 19-26.
[11] Wang Z, Cao J W. Committee-based evaluation and selection of grid resources for QoS improvement //Grid’ 09: The 10th IEEE/ACM International Conference on Grid Computing. Canada, 2009: 138-144.
[12] Vanmechelen K, Depoorter W, Broeckhove J. Economic grid resource management for CPU Bound Applications with hard deadlines //CCGrid’ 08: The 8th International Conference on Cluster Computing and the Grid. Lyon, France, 2008.
[13] Sundaram V, Chandra A, Weissman J. Exploring the throughput-fairness tradeoff of deadline scheduling in heterogeneous computing environments //ACM SIGMETRICS’ 08: The 2008 International Conference on Measurement and Modeling of Computer Systems. Annapolis, Maryland, USA, 2008.
[14] Buyya R, Murshed M. GridSim: A Toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing
[J]. The Journal of Concurrency and Computation: Practice and Experience, 2002, 14(13): 1175-1220.
[15] Land A, Doig A. An automatic method of solving discrete programming problems
[J]. Econometrica, 1960, 28: 497-520.
/
| 〈 |
|
〉 |
