Computer Science ›› 2015, Vol. 42 ›› Issue (3): 233-236.doi: 10.11896/j.issn.1002-137X.2015.03.048

Previous Articles     Next Articles

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

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!