全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

多云环境下基于代价驱动的科学工作流调度策略*

DOI: 10.16451/j.cnki.issn1003-6059.201510001, PP. 865-875

Keywords: 云计算,科学工作流,代价驱动,优化调度,多云环境

Full-Text   Cite this paper   Add to My Lib

Abstract:

针对多云环境下带截止日期约束的科学工作流调度问题,引入局部关键路径算法思想,提出基于代价驱动的科学工作流调度策略,目的是在满足科学工作流截止日期约束的同时,尽可能降低执行代价.该策略充分考虑多云环境和科学工作流的独有特性,首先根据工作流自身结构合并存在有向割边的相邻任务;再基于关键父任务迭代机制寻找带局部截止日期的局部关键路径;最后为局部关键路径分配最适合实例,并执行所有任务.实验表明,文中策略有效提高现有真实科学工作流的执行效率,并大幅减少执行代价.

References

[1]  Bittencourt L F, Madeira E R M, da Fonseca N L S. Scheduling in Hybrid Clouds. IEEE Communications Magazine, 2012, 50(9): 42-47
[2]  Tindell K W, Burns A, Wellings A J. Allocating Hard Real-Time Tasks: An NP-Hard Problem Made Easy. Real-Time Systems, 1992, 4(2): 145-165
[3]  Armbrust M, Fox A, Griffith R, et al. A View of Cloud Computing. Communications of the ACM, 2010, 53(4): 50-58
[4]  Wang Q, Li X F, Wang J. A Data Placement and Task Scheduling Algorithm in Cloud Computing. Journal of Computer Research and Development, 2014, 51(11): 2416-2426 (in Chinese)(王 强,李雄飞,王 婧.云计算中的数据放置与任务调度算法.计算机研究与发展, 2014, 51(11): 2416-2426)
[5]  Song Y J, Yang X Z, Li D Y, et al. The Cloud Scheduler Politics of Multiprocessor Multitask Real Time Systems. Chinese Journal of Computers, 2000, 23(10): 1107-1113 (in Chinese) (宋远骏,杨孝宗,李德毅,等.多机多任务实时系统云调度策略.计算机学报, 2000, 23(10): 1107-1113)
[6]  Cao H J, Jin H, Wu X X, et al. DAGMap: Efficient and Depend-able Scheduling of DAG Workflow Job in Grid. The Journal of Supercomputing, 2010, 51(2): 201-223
[7]  Chen W N, Zhang J. An Ant Colony Optimization Approach to a Grid Workflow Scheduling Problem with Various QoS Requirements. IEEE Trans on Systems, Man, and Cybernetics: Applications and Reviews, 2008, 39(1): 29-43
[8]  Abrishami S, Naghibzadeh M, Epema D H J. Deadline-Constrained Workflow Scheduling Algorithms for Infrastructure as a Service Clouds. Future Generation Computer Systems, 2013, 29(1): 158-169
[9]  Pandey S, Wu L L, Guru S M, et al. A Particle Swarm Optimization-Based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments // Proc of the 24th IEEE International Conference on Advanced Information Networking and Applications. Perth, USA, 2010: 400-407
[10]  Wu Z J, Ni Z W, Gu L C, et al. A Revised Discrete Particle Swarm Optimization for Cloud Workflow Scheduling // Proc of the International Conference on Computational Intelligence and Security. Nanning, China, 2010: 184-188
[11]  Li J Y, Qiu M K, Ming Z, et al. Online Optimization for Scheduling Preemptable Tasks on IaaS Cloud Systems. Journal of Parallel and Distributed Computing, 2012, 72(5): 666-677
[12]  Lin X Y, Wu C Q. On Scientific Workflow Scheduling in Clouds under Budget Constraint // Proc of the 42nd International Confe-rence on Parallel Processing. Lyon, France, 2013: 90-99
[13]  Liu S W, Kong L M, Ren K J, et al. A Two-Step Data Placement and Task Scheduling Strategy for Optimizing Scientific Workflow Performance on Cloud Computing Platform. Chinese Journal of Computers, 2011, 34(11): 2121-2130 (in Chinese) (刘少伟,孔令梅,任开军,等.云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略.计算机学报, 2011, 34(11): 2121-2130)
[14]  Abrishami S, Naghibzadeh M, Epema D H J. Cost-Driven Scheduling of Grid Workflows Using Partial Critical Paths. IEEE Trans on Parallel and Distributed Systems, 2012, 23(8): 1400-1414
[15]  Bharathi S, Chervenak A, Deelman E, et al. Characterization of Scientific Workflows // Proc of the 3rd Workshop on Workflows in Support of Large-Scale Science. Austin, USA, 2008. DOI: 10.1109/WORKS.2008.4723958
[16]  Van den Bossche R, Vanmechelen K, Broeckhove J. Online Cost-Efficient Scheduling of Deadline-Constrained Workloads on Hybrid Clouds. Future Generation Computer Systems, 2013, 29(4): 973-985
[17]  Wang X D. Data Structures and Algorithm Design. Beijing, China: China Machine Press, 2012 (in Chinese) (王晓东.数据结构与算法设计.北京:机械工业出版社, 2012)
[18]  Kwok Y K, Ahmad I. Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors. ACM Computing Surveys, 1999, 31(4): 406-471
[19]  Zhao F, Wang B S, Lu Z X, et al. Impact of Non-cut Link Fai-lures on Network Traffic. Journal on Communications, 2006, 27(11A): 184-188 (in Chinese) (赵 锋,王宝生,卢泽新,等.非割边链路故障对网络流量的影响分析.通信学报, 2006, 27(11A): 184-188)
[20]  Yi S, Andrzejak A, Kondo D. Monetary Cost-Aware Checkpointing and Migration on Amazon Cloud Spot Instances. IEEE Trans on Services Computing , 2012, 5(4): 512-524
[21]  Topcuoglu H, Hariri S, Wu M Y. Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing. IEEE Trans on Parallel and Distributed Systems, 2002, 13(3): 260-274

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133