计算机科学 ›› 2015, Vol. 42 ›› Issue (3): 233-236.doi: 10.11896/j.issn.1002-137X.2015.03.048

• 人工智能 • 上一篇    下一篇

网格原子化作业的二分图调度方法

李建勋,郭建华,李维乾,曹茂生   

  1. 西安理工大学经济与管理学院 西安710048,西安理工大学经济与管理学院 西安710048,西安工程大学计算机科学学院 西安710048,西安理工大学经济与管理学院 西安710048
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受“十二五”国家水体污染控制与治理重大专项课题:基于水环境风险防控的松花江水文过程调控技术及示范(2012ZX07201-006),国家自然科学基金:基于数字地球和复杂性理论的水污染模拟仿真研究(51109177),陕西省自然科学基础研究计划项目:3S下的水利工程移民辅助决策技术研究与实现(2014JM9365)资助

Bipartite Graph Scheduling Method for Grid Task Atomized

LI Jian-xun, GUO Jian-hua, LI Wei-qian and CAO Mao-sheng   

  • Online:2018-11-14 Published:2018-11-14

摘要: 对于网格系统中计算力调度等问题,结合有向无环作业图DATG和无向节点图UNG,采用并行集APS建立了一种基于二分图的网格调度算法BGS,并在惩罚策略、负载均衡、复活机制的引导下,使系统的调度动态地逐步趋向优化。实验结果表明:该算法能够更加适应网格资源的变化,降低作业负载,提高作业的并行化程度,并能根据系统负载合理地利用节点资源。

关键词: 网格,原子操作,网格调度

Abstract: Focusing on the scheduling problems in grid system,adopting directed acyclic task graph and undirected node graph,the paper proposed a grid scheduling algorithm based on bipartite graph (BGS) by using atom parallel set,and made the dynamic grid scheduling gradually optimized by introducing punishment strategies,load balancing and revived mechanism.The results show that the BGS algorithm can adapt to the changes in grid resources better,reduce the load of tasks,improve the degree of parallel operations and reasonably use the node resources in accordance with system load.

Key words: Grid,Atom operation,Grid scheduling

[1] 王勇,胡春明,杜宗霞.服务质量感知的网格工作流调度[J].软件学报,2006,7(11):2341-2351
[2] Bharadwaj V,Ghose D,Robertazzi T G.Divisible Load Theory:A New Paradigm for Load Scheduling in Distributed Systems[J].Cluster Computing,2003,6(1):7-17
[3] Beaumont O,Legrand A,Robert Y.Scheduling divisible work-loads on heterogeneous platforms[J].Parallel Computing,2003,9(9):1121-1152
[4] Beaumont O,Boudet V,Petitet A,et al.A proposal for a heterogeneous cluster Scalapack (dense linear solvers)[J].IEEE Transaction on Computers,2001,0(10):1050-1070
[5] Bajaj R,Agrawal D P.Improving scheduling of tasks in a heterogeneous environment[J].IEEE Transactions on parallel and distributed systems,2004,5(2):107-118
[6] Radulescu A,Gemund A J C van.On the complexity of listscheduling algorithms for distributed-memory systems[C]∥Proceeding ICS ’99 Proceedings of the 13th international confe-rence on Supercomputing,1999.New York:ACM,1999:68-75
[7] Radulescu A,Arjan J C.Low-cost task scheduling for distributed-memory machines[J].IEEE Transactions on Parallel and Distributed Systems,2002,3(6):648-658
[8] 林伟伟,齐德昱,李拥军,等.树型网格计算环境下的独立任务调度[J].软件学报,2006,7(11):2352-2361
[9] Sih G C,Lee E A.A compile-time scheduling heuristic for interconnection constrained heterogeneous processor architectures[J].IEEE Trans.on Parallel and Distributed Systems,1993,4(2):75-87
[10] 杜晓丽,蒋昌俊,徐国荣,等.一种基于模糊聚类的网格DAG任务图调度算法[J].软件学报,2006,7(11):2277-2288
[11] Cao Hai-jun,Jin Hai,Wu Xiao-xin,et al.DAGMap:Efficientscheduling for DAG grid workflow job[C]∥Proceedings of the 2008 9th IEEE/ACM International Conference on Grid Computing,2008.Tsukuba,IEEE,2008:17-24
[12] Mourad H,Franck B.Dynamic Critical Path Scheduling Parallel Programs onto MultiProcessors[C]∥IEEE Computer Society Proceeding of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05),2005.Washington,2005:203-209
[13] 李建勋,解建仓,陈田庆,等.计算网格下的高性能MODIS蒸散发反演研究[J].西安交通大学学报,2010,4(10):36-41
[14] Kwok Y K,Ahmad I.Benchmarking the task graph scheduling algorithms[J].Journal of Parallel and Distributed Computing,1999,9:381-422
[15] Freund R F,Siegel H J.Heterogeneous processing[J].IEEE Computer,1993,6(6):13-17

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!