Communication aware multiple directed acyclic graph scheduling considering cost and fairness

doi:10.11772/j.issn.1001-9081.2015.11.3017

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (11): 3017-3020.DOI: 10.11772/j.issn.1001-9081.2015.11.3017

• DPCS 2015 Paper • Next Articles

Communication aware multiple directed acyclic graph scheduling considering cost and fairness

WANG Yuxin¹, CAO Shijie¹, GUO He², CHEN Zheng², CHEN Xin²

1. College of Computer Science and Technology, Dalian University of Technology, Dalian Liaoning 116024, China;
2. College of Software, Dalian University of Technology, Dalian Liaoning 116620, China

Received:2015-06-17 Revised:2015-07-09 Online:2015-11-10 Published:2015-11-13

兼顾费用与公平的带通信开销的多有向无环图调度

王宇新¹, 曹仕杰¹, 郭禾², 陈征², 陈鑫²

1. 大连理工大学计算机科学与技术学院, 辽宁大连 116024;
2. 大连理工大学软件学院, 辽宁大连 116024

通讯作者: 王宇新(1973-),男,辽宁大连人,副教授,博士,CCF会员,主要研究方向:计算机系统结构、并行计算.
作者简介:曹仕杰(1992-),男,陕西汉中人,硕士研究生,主要研究方向:计算机系统结构、工作流调度; 郭禾(1955-),男,辽宁大连人,教授,主要研究方向:高性能计算、系统结构; 陈征(1989-),女,河南安阳人,硕士研究生,主要研究方向:计算机系统结构; 陈鑫(1983-),男,辽宁锦州人,讲师,博士,主要研究方向:组合优化与调度.
基金资助:
国家自然科学基金资助项目(11372067,61300016).

Abstract

Abstract: Multiple Directed Acyclic Graphic (DAG) scheduling algorithms are supposed to take many factors into account, such as execution time, communication overhead, cost and fairness of all DAG. Therefore, in order to increase fairness and reduce cost, a new scheduling strategy CAFS (Communication Aware Fair Scheduling), based on CA-DAG (Communication Aware-DAG), was proposed. Also, a BD (Backward Difference) rule was introduced to optimize finish time of all DAGs. CAFS is consisted of two parts: the pre-scheduling part adopts CACO (Communication Aware Cost Optimization) to optimize the total cost, and utilizes the classical fairness algorithm to decide the sequence for scheduling. Based on the sequence the second part schedules all the DAGs using BD rule to reduce the finish time. The simulation results show that CAFS can reduce the finish time without increasing cost and guarantee the fairness, and the average execution time has been reduced by 19.82%.

Key words: multiple directed acyclic graph scheduling, communication overhead, cost, fairness, workflow

摘要： 针对云环境下多有向无环图(DAG)工作流的调度算法应考虑执行时间、费用开销、通信开销、公平性等多个指标的问题,在模型带通信开销的DAG(CA-DAG)的基础上结合公平性算法提出一种优化完成时间的后向求异(BD)原则与兼顾费用和公平的多DAG调度策略CAFS.CAFS调度策略分为两个阶段:预调度阶段利用带通信开销的工作流费用优化(CACO)算法在考虑通信开销的同时求解所有任务的最优服务并优化费用,采用fairness算法得到较公平的调度顺序;调度阶段采用BD原则,根据在预调度阶段得出的调度顺序进一步优化整体的完成时间并执行调度.实验结果表明,CAFS调度算法具有较好的公平性,在不提高费用的基础上时间减少19.82%.

关键词: 多有向无环图调度, 通信开销, 费用, 公平, 工作流

CLC Number:

TP393

WANG Yuxin, CAO Shijie, GUO He, CHEN Zheng, CHEN Xin. Communication aware multiple directed acyclic graph scheduling considering cost and fairness[J]. Journal of Computer Applications, 2015, 35(11): 3017-3020.

王宇新, 曹仕杰, 郭禾, 陈征, 陈鑫. 兼顾费用与公平的带通信开销的多有向无环图调度[J]. 计算机应用, 2015, 35(11): 3017-3020.

References

[1] GONZALEZ L M V, RODERO-MERINO L, CACERES J, et al. A break in the clouds: towards a cloud definition[J]. ACM SIGCOMM Computer Communication Review, 2009, 39(1):50-55.
[2] YUAN Y, LI X, WANG Q,et al. Bottom level based heuristic for workflow scheduling in grids [J]. Chinese Journal of Computers, 2008, 31(2): 283-290. (苑迎春,李小平,王茜,等. 基于逆向分层的网格工作流调度算法[J]. 计算机学报,2008,31(2): 282-290.)
[3] YUAN Y, LI X, WANG Q. Cost optimization heuristics for grid workflows scheduling based on serial reduction[J]. Journal of Computer Research and Development, 2008, 45(2): 246-253.(苑迎春,李小平,王茜. 基于串规约的网格工作流费用优化方法[J]. 计算机研究与发展,2008,45(2): 246-253.)
[4] YUAN Y, LI X, WANG Q, et al. Grid workflows schedule based on priority rules[J]. Acta Electronica Sinica, 2009,37(7): 1458-1462.(苑迎春,李小平,王茜等. 基于优先级规则的网格工作流调度[J]. 电子学报, 2009,37(7):1458-1462.)
[5] LIU C, ZHANG W, LUO Z, et al. Temporal consistency based heuristics for cost optimization in workflow scheduling[J]. Journal of Computer Research and Development, 2012, 49(6): 1323-1331.(刘灿灿,张卫民,骆志刚,等. 基于时序一致的工作流费用优化方法[J]. 计算机研究与发展,2012,49(6): 1323-1331.)
[6] LIU C, ZHANG W, LUO Z, et al. Workflow cost optimization heuristics based on advanced priority rule[J]. Journal of Computer Research and Development, 2012, 49(7): 1593-1600. (刘灿灿,张卫民,骆志刚,等. 基于改进优先级规则的工作流费用优化方法[J]. 计算机研究与发展,2012,49(7): 1593-1600.)
[7] CHEN S, NEPAL S, LIU R. Secure connectivity for intra-cloud and inter-cloud communication[C]// Proceedings of the 40th International Conference on Parallel Processing Workshops. Piscataway: IEEE, 2011: 154-159.
[8] GUO H, CHEN Z, YU Y, et al. A communication aware DAG workflow cost optimization model and algorithm[J]. Journal of Computer Research and Development, 2015, 52(6): 1400-1408. (郭禾,陈征,于玉龙,等. 带通信开销的DAG工作流费用优化模型与算法[J]. 计算机研究与发展,2015,52(6): 1400-1408.)
[9] TIAN G. Research on several problems of scheduling multiple DAGs sharing resources[D]. Beijing: Beijing University of Technology, 2014: 36-45. (田国忠.多DAG共享资源调度的若干问题研究[D].北京: 北京工业大学,2014: 36-45.)
[10] ZHAO H, SAKELLARIOU R. Scheduling multiple DAGs onto heterogeneous systems[C]// Proceedings of the 20th International Parallel and Distributed Processing Symposium. Washington, DC: IEEE Computer Society, 2006: 1-14.
[11] TIAN G, XIAO C, XIE J. An cost optimization methods for scheduling concurrent multiple DAGs sharing heterogeneous resource[J]. Acta Electronica Sinica, 2014, 42(9): 1-6. (田国忠,肖创柏,谢军奇. 一种多DAG任务共享异构资源调度的费用优化方法[J]. 电子学报,2014,42(9): 1-6.)
[12] HONIG U, SCHIFFMANN W. A meta-algorithm for scheduling multiple DAGs in homogeneous system environments[C]// Proceedings of the IEEE 18th IA STED International Conference on Parallel and Distributed of Computing and System. Piscataway: IEEE, 2006: 147-152.

[1]	MENG Fan, CHEN Guang, WANG Yong, GAO Yang, GAO Dequn, JIA Wenlong. Multi-granularity temporal structure representation based outlier detection method for prediction of oil reservoir [J]. Journal of Computer Applications, 2021, 41(8): 2453-2459.
[2]	YAO Jie, CHENG Chunling, HAN Jing, LIU Zheng. Anomaly detection method based on multi-task temporal convolutional network in cloud workflow [J]. Journal of Computer Applications, 2021, 41(6): 1701-1708.
[3]	WANG Junhong, YAN Jiarong. Classification algorithm based on undersampling and cost-sensitiveness for unbalanced data [J]. Journal of Computer Applications, 2021, 41(1): 48-52.
[4]	ZHAO Zhixue, LI Xiamiao, ZHOU Xiancheng. Green vehicle routing problem optimization for multi-type vehicles considering traffic congestion areas [J]. Journal of Computer Applications, 2020, 40(3): 883-890.
[5]	DUAN Yujun, WANG Yaoli, CHANG Qing, LIU Xing. Wireless sensor deployment optimization based on improved IHACA-CpSPIEL algorithm [J]. Journal of Computer Applications, 2020, 40(3): 793-798.
[6]	ZHANG Qing, ZHENG Yan. Civil aviation engine module maintenance level decision-making and cost optimization based on annealing frog leaping particle swarm algorithm [J]. Journal of Computer Applications, 2020, 40(12): 3541-3549.
[7]	ZHANG Hang, LIU Shanzheng, TANG Dan, CAI Hongliang. Erasure code with low recovery-overhead in distributed storage systems [J]. Journal of Computer Applications, 2020, 40(10): 2942-2950.
[8]	YIN Shengnan, LI Yinzhen, ZHANG Changze. High-speed railway fare adjustment strategy based on passenger flow assignment [J]. Journal of Computer Applications, 2020, 40(1): 278-283.
[9]	YANG Zhengqing, ZHOU Zhaorong, YUAN Shu. Task assignment based on discrete cuckoo search algorithm in mobile crowd sensing system [J]. Journal of Computer Applications, 2019, 39(9): 2778-2783.
[10]	LI Yefei, XU Chao, XU Daoqiang, ZOU Yunfeng, ZHANG Xiaoda, QIAN Zhuzhong. Online task scheduling algorithm for big data analytics based on cumulative running work [J]. Journal of Computer Applications, 2019, 39(8): 2431-2437.
[11]	WANG Shouhua, LI Yunke, SUN Xiyan, JI Yuanfa. Dual-antenna attitude determination algorithm based on low-cost receiver [J]. Journal of Computer Applications, 2019, 39(8): 2381-2385.
[12]	YANG Hao, WANG Yu, ZHANG Zhongyuan. Integration of cost-sensitive algorithms based on average distance of K-nearest neighbor samples [J]. Journal of Computer Applications, 2019, 39(7): 1883-1887.
[13]	ZHAO Shicao, XIAO Yonghao, DUAN Bowen, LI Yufeng. HSWAP: numerical simulation workflow management platform suitable for high performance computing environment [J]. Journal of Computer Applications, 2019, 39(6): 1569-1576.
[14]	FU Shucun, FU Zhangjie, XING Guowen, LIU Qingxiang, XU Xiaolong. Computation offloading method for workflow management in mobile edge computing [J]. Journal of Computer Applications, 2019, 39(5): 1523-1527.
[15]	ZHAO Wei, LIN Yuming, HUANG Taoyi, LI You. User opinion extraction based on adaptive crowd labeling with cost constrain [J]. Journal of Computer Applications, 2019, 39(5): 1351-1356.

Communication aware multiple directed acyclic graph scheduling considering cost and fairness

兼顾费用与公平的带通信开销的多有向无环图调度

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics