允许违反局部时间约束的科学工作流调度策略

计算机工程与科学

• 论文 • 下一篇

允许违反局部时间约束的科学工作流调度策略

陈旺虎,段菊，俞茂义

（西北师范大学计算机科学与工程学院,甘肃兰州 730070）

收稿日期:2015-07-21 修回日期:2015-11-27 出版日期:2016-11-25 发布日期:2016-11-25
基金资助:
国家自然科学基金（61462076）；甘肃省自然科学基金（1208RJZA134）；甘肃省科技支撑计划（1104GKCA023）；西北师范大学青年教师科研提升计划（NWNULKQN1230）

A scheduling policy of scientific workflows allowing

the violation of local time constraints

CHEN Wanghu，DUAN Ju,YU Maoyi

（College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China）

Received:2015-07-21 Revised:2015-11-27 Online:2016-11-25 Published:2016-11-25

摘要/Abstract

摘要：

提高科学工作流在云环境中的执行效率、降低执行费用受到广泛关注。用户期望的局部QoS约束与工作流的总体执行效率之间往往存在矛盾。针对该现象，在前期的研究基础上提出一种允许违反局部时间约束的科学工作流调度策略。通过对已聚簇的工作流任务集使用任务后向优先合并的方法，可实现任务间空闲时间片的合理利用，进而优化科学工作流的执行时间；另外，为充分利用任务的松弛时间，提高工作流的整体执行效率，允许部分任务的调度违反局部最晚完成时间的约束。实验结果表明，该策略能提前科学工作流的最早完成时间，提高处理机的利用率，并最终降低工作流的执行费用。

关键词: 科学工作流, 任务调度, 任务聚簇, 松弛时间, 局部约束

Abstract:

Improving the execution efficiency as well as reducing the execution cost of the scientific workflows in cloud is important. Focused on the conflict between userdesired local QoS constraints and the overall execution efficiency of the workflow，we propose a scheduling policy of scientific workflows allowing the violation of local time constraints. Based on backward merging of task clusters, free time spans between workflow task executions can be exploited, and the whole execution time of the workflow can be optimized. Furthermore，in order to make full use of the slack time during task execution and improve the overall efficiency of the workflow, some workflow tasks are permitted to violate the local constraint of the latest finish time. Experimental results show that the policy can bring forward the earliest finish time of the workflow and improve the utilization ratio of processors, and eventually lower the execution cost of the workflow.

Key words:

scientific workflow, task scheduling, cluster aggregation, slack time, local constraint

陈旺虎,段菊，俞茂义. 允许违反局部时间约束的科学工作流调度策略[J]. 计算机工程与科学.

CHEN Wanghu，DUAN Ju,YU Maoyi.

A scheduling policy of scientific workflows allowing

the violation of local time constraints

[J]. Computer Engineering & Science.

参考文献

［1］Goble C,Roure D D.The impact of workflow tools on datacentric research［C］∥Proc of the 4th Paradigm:DataIntensive Scientific Discovery,2009:137145.

［2］Chen Wanghu, Altintas I, Wang Jianwu, et al.Enhancing smart rerun of kepler scientific workflows based on near optimum provenance caching in cloud［C］∥Proc of

2014 IEEE World Congress on Services (SERVICES),2014:378384.

［3］Vaquero L M,RoderoMerino L,Caceres J,et al.A break in the clouds:Towards a cloud definition［J］.ACM SIGCOMM Computer Communication Review,2008,39(1):5055.

［4］He Kun,Zhao Yong,Huang Wenqi.A clustering and scheduling algorithm based on task duplication［J］.Chinese Journal of Computers,2008,31(5):733740.(in Chinese)

［5］Bazoobandi H A, Khorashadizadeh M, Eftekhari M.Solving task scheduling problem in multiprocessors with genetic algorithm and task duplication［C］∥
Proc of 2014 IEEE Iranian Conference on Intelligent Systems (ICIS),2014:14.

［6］Park C I,Choe T Y.An optimal scheduling algorithm based on task duplication［C］∥
.Proc of IEEE 8th International Conference on Parallel and Distributed Systems,2001:914.

［7］Zhang Jianjun, Li Qinghua, Qu Yong. Task duplication based scheduling algorithm［J］.Computer Engineering and Design,2009,30(8):19861899.(in Chinese)

［8］Xie Zhiqiang,Han Yingjie,Qi Yonghong,et al.A scheduling algorithm for multicore based on critical path and task duplication［J］.Journal of National University of Defense Technology,2014,36(1):172177.(in Chinese)

［9］Duan Ju,Chen Wanghu,Wang Runping,et al.Execution optimization policy of scientific workflow based on cluster aggregation under cloud environment［J］.Journal of Computer Applications,2015,35(6):15801584.(in Chinese)

［10］Li Huifang, Fan Yushun. Overview on managing time in workflow systems［J］.Journal of Software,2002,13(8):15521558.(in Chinese)

［11］Abrishami S,Naghibzadeh M,Epema D H J.Deadlineconstrained workflow scheduling algorithms for infrastructure as a service clouds［J］.Future Generation Computer Systems,2013,29(1):158169.

［12］Rodriguez M A,Buyya R.Deadline based resource provisioning and scheduling algorithm for scientific workflows on clouds［J］.Cloud Computing IEEE Transactions on,2014,2(2):11.

［13］Calheiros R N, Buyya R. Meeting deadlines of scientific workflows in public clouds with tasks replication［J］.IEEE Transactions on Parallel & Distributed Systems,2014,25(7):1.

［14］Chopra N,Singh S.Deadline and cost based workflow scheduling in hybrid cloud［C］∥Proc of
2013 International Conference on Advances in Computing,Communications and Informatics (ICACCI),2013:840846.

［15］Byun E K,Kee Y S,Kim J S,et al.BTS:Resource capacity estimate for timetargeted science workflows［J］.Journal of Parallel & Distributed Computing,2011,71(6):848862.

［16］Liu X,Yang Y,Yuan D,et al.Do we need to handle every temporal violation in scientific workflow systems［J］.ACM Transactions on Software Engineering & Methodology,2014,23(1):510.

附中文参考文献：

［4］何琨,赵勇,黄文奇.基于任务复制的分簇与调度算法［J］.计算机学报,2008,31(5):733740.

［7］张建军,李庆华,瞿勇.基于任务复制的调度算法［J］.计算机工程与设计,2009,30(8):18961899.

［8］谢志强,韩英杰,齐永红,等.基于关键路径和任务复制的多核调度算法［J］.国防科技大学学报,2014,36(1):172177.

［9］段菊,陈旺虎,王润平,等.云环境下基于聚簇的科学工作流执行优化策略［J］.计算机应用,2015,35(6):15801584.

［10］李慧芳,范玉顺.工作流系统时间管理［J］.软件学报,2002,13(8):15521558.

[1]	温瑞林, 樊春, 马银萍 , 王政丹, 向广宇 , 付振新. SlurmX：基于Slurm使用面向对象设计方法重构的任务调度系统[J]. 计算机工程与科学, 2022, 44(09): 1532-1541.
[2]	李文佳, 史岚, 季航旭, 罗意彭. 面向Flink的负载均衡任务调度算法的研究与实现[J]. 计算机工程与科学, 2022, 44(07): 1141-1151.
[3]	罗磊, 陈照云, 王俪璇. 用户QoS感知的GPU集群深度学习任务动态调度[J]. 计算机工程与科学, 2021, 43(08): 1331-1340.
[4]	杨坚伟, 孟敏, 黄家乐, 武继刚. 分布式训练异构任务调度算法研究[J]. 计算机工程与科学, 2021, 43(07): 1160-1167.
[5]	黄山, 房六一, 徐浩桐, 段晓东, . 面向容器环境的Flink的任务调度优化研究[J]. 计算机工程与科学, 2021, 43(07): 1173-1184.
[6]	邢红星, 魏叶华, 乐懿. 硬件成本缩减的异构分布式嵌入式系统调度算法[J]. 计算机工程与科学, 2021, 43(02): 258-265.
[7]	胡亚红1，盛夏2，毛家发1. 资源不均衡Spark环境任务调度优化算法研究[J]. 计算机工程与科学, 2020, 42(02): 203-209.
[8]	朱永超1，周川1，崔玉伟2，郭健1，吴益飞1. 基于模拟退火算法的改进主/副版本调度算法[J]. 计算机工程与科学, 2019, 41(09): 1534-1540.
[9]	王宇新，王飞，王冠，郭禾. 一种基于两级DAG模型的MapReduce工作流异构调度算法[J]. 计算机工程与科学, 2019, 41(08): 1353-1359.
[10]	郭宏乐，陈旺虎，马生俊，李新田，乔保民. 一种云环境下科学工作流执行计划的优化方法[J]. 计算机工程与科学, 2019, 41(03): 433-439.
[11]	吉慧，周磊. 面向温度优化的片上网络任务调度方法[J]. 计算机工程与科学, 2018, 40(09): 1527-1533.
[12]	孙小涓1,2,3,石涛2,3,李冰2,3,杨晓艳2,3,雷斌1,2,3,胡玉新1,2,3 . 空间科学卫星数据快速处理方法[J]. 计算机工程与科学, 2018, 40(08): 1351-1357.
[13]	童钊1,2，陈洪剑1,2，陈明1,2，梅晶1,2，刘宏1,2. 一种云环境下基于混合型BBO的任务调度算法[J]. 计算机工程与科学, 2018, 40(05): 765-772.
[14]	贺智明，刘敏. 云环境下基于偏好的资源公平分配策略[J]. 计算机工程与科学, 2017, 39(11): 1991-1999.
[15]	莫文导1，利业鞑2，温昂展3，林伟伟3. 面向移动设备的温度感知的任务调度算法[J]. 计算机工程与科学, 2017, 39(04): 627-633.

允许违反局部时间约束的科学工作流调度策略

A scheduling policy of scientific workflows allowing

the violation of local time constraints

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价