面向数据密集型工作流的QoS-aware调度算法

摘要/Abstract

摘要： 随着技术的发展,人们可以从不同的数据中心获得资源。跨数据中心的数据密集型工作流任务调度成为了一个热点问题。提出了一个在多数据中心环境下的数据密集型工作流任务调度算法。多数据中心环境中的数据密集型工作流计算有2个特点：(1)数据量大,而且分布在不同的地理位置,数据迁移的过程会消耗大量的时间和带宽;(2)数据中心具有异构性,提供资源的数量、种类和价格不同。针对这些特点,算法将数据迁移的过程映射为一个数据迁移任务,使用有向无环图(DAG)对工作流进行建模,对DAG进行了化简。算法利用模拟退火算法,将工作流执行时间和花费作为优化目标,计算出一个优化的调度方案。分别使用CloudSim平台和Hadoop平台对算法进行了验证。

关键词: 工作流, 云计算, 大数据, 调度

Abstract: The development of technology enables people to access resources from different data centers. Resource management and scheduling of applications, such as workflow, that are deployed on the cloud computing environment have already become a hot spot. A QoS-aware scheduling algorithm for data intensive workflow on multiple data center environment was proposed. Scheduling data intensive workflow on multiple data center environment has two characteristics: A large amount of data is distributed in different geographical locations, the process of data migration will consume a large amount of time and bandwidth; secondly, the data centers have different price and resources. Data migration between data centers was mapped to a task of workflow, models workflow with DAG, simplifying the DAG, and scheduling all the tasks of workflow using Simulated Annealing. The experiment using CloudSim platform and Hadoop platform shows that this scheduling algorithm is effective.

Key words: workflow, big data, cloud computing, schedule

中图分类号:

TP391

万聪, 王翠荣, 王聪. 面向数据密集型工作流的QoS-aware调度算法[J]. 系统仿真学报, 2016, 28(3): 549-558.

Wan Cong, Wang Cuirong, Wang Cong. QoS-aware Scheduling for Data Intensive Workflow[J]. Journal of System Simulation, 2016, 28(3): 549-558.

参考文献

[1] 杨来, 史忠植, 梁帆, 等. 基于Hadoop 云平台的并行数据挖掘方法[J]. 系统仿真学报, 2013, 25(5): 936-944.
(Yang Lai, Shi Zhongzhi, Liang Fan.Parallel Approach in Data Mining Based on Hadoop Cloud Platform[J]. Journal of System Simulation (S1004-731X), 2013, 25(5): 936-944.)
[2] 李伯虎, 柴旭东, 侯宝存, 等. 一种基于云计算理念的网络化建模与仿真平台-“云仿真平台”[J]. 系统仿真学报, 2009, 21(17): 5292-5299.
(Li Bohu, Chai Xudong, Hou Baocun, et al.Networked Modeling & Simulation Platform Based on Concept of Cloud Computing-Cloud Simulation Platform[J]. Journal of System Simulation (S1004-731X), 2009, 21(17): 5292-5299.)
[3] 黄安祥, 冯晓文, 李劲松, 等. 基于云计算平台的航空兵训练仿真体系结构[J]. 系统仿真学报, 2011, 23(增1): 106-109.
(Huang Anxiang, Feng Xiaowen, Li Jinsong, et al.Aviation Simulation Architecture Based on Cloud Computing Platform[J]. Journal of System Simulation (S1004-731X), 2011, 23(S1): 106-109.)
[4] Olston C, Chiou G, Chitnis L, et al.Nova: Continuous Pig/Hadoop Workflows[C]// Proceedings of the SIGMOD’2011, Athens, Greece. USA: ACM, 2011: 1081-1090.
[5] Mao Y, Wu W, Zhang H, et al.GreenPipe: A Hadoop Based Workflow System on Energy-Efficient Clouds[C]// Proceedings of the IPDPSW’2012, Shanghai, China. USA: IEEE, 2012: 2211-2219.
[6] Wang L, Tao J, Ranjan R, et al.G-Hadoop: MapReduce Across Distributed Data Centers for Data-Intensive Computing[J]. Future Generation Computer Systems (S0167-739X), 2013, 29(3): 739-750.
[7] Ahmed R, DeSmedt P, Kent W, et al. Pegasus: A System for Seamless Integration of Heterogeneous Information Sources[C]// Compcon Spring'91. Digest of Papers. USA: IEEE, 1991: 128-136.
[8] Du Z, Hu J, Chen Y.Optimized QoS-aware Replica Placement Heuristics and Applications in Astronomy Data Grid[J]. Journal of Systems and Software (S0164-1212), 2011, 84(7): 1224-1232.
[9] Fedak G, He H, Cappello F.BitDew: A Programmable Environment for Large-Scale Data Management and Distribution[J]. Journal of Network and Computer Applications (S1084-8045), 2009, 32(5): 961-975.
[10] Gu Y, Grossman R.Toward Efficient and Simplified Distributed Data Intensive Computing[J]. IEEE Transactions on Parallel and Distributed Systems (S1045-9219). 2011, 22(6): 974-984.
[11] Jayalath C, Stephen J, Eugster P.From The Cloud to The Atmosphere: Running MapReduce Across Data Centers[J]. IEEE Transactions on Computers (S0018-9340), 2014, 63(1): 74-87.
[12] Dean J, Ghemawat S, MapReduce: Simplified Data Processing on Large Clusters[J]. Communications of The ACM (S0001-0782). 2008, 51(1): 107-113.
[13] Sakellariou R, Zhao H, Tsiakkouri E, et al.Scheduling Workflows with Budget Constraints[C]// Integrated Research in GRID Computing. USA: Springer, 2007: 189-202.
[14] Fard M, Prodan R, Fahringer T.Multi-objective List Scheduling of Workflow Applications in Distributed Computing Infrastructures[J]. Journal of Parallel and Distributed Computing (S0743-7315), 2014, 73(3): 2152-2165.
[15] Adabi S, Movaghar A, Rahmani M.Bi-level Fuzzy Based Advanced Reservation of Cloud Workflow Applications on Distributed Grid Resources[J]. The Journal of Supercomputing (S0920-8542), 2014, 63(1): 175-218.
[16] Benoit A, Hakem M, Robert Y.Multi-criteria Scheduling of Precedence Task Graphs on Heterogeneous Platforms[J]. The Computer Journal (S0010-4620), 2010, 53(6): 772-785.
[17] Blythe J, Jain S, Deelman E, et al.Task Scheduling Strategies for Workflow-Based Applications in Grids[C]// Proceedings of the IEEE International Symposium on Cluster Computing and the Grid, 2005. USA: IEEE, 2005.
[18] Yu J, Buyya R.QoS-based Scheduling of Workflow Applications on Service Grids[C]// Proceedings of the 1st IEEE International Conference on e-Science and Grid Computing, 2005. USA: IEEE, 2005.
[19] 王凌, 郑大钟. 多目标优化的一类模拟退火算法[J]. 计算机工程与应用, 2002, 38(8): 4-5.
(Wang Ling, Zheng Dazhong.A Class of Simulated Annealing Approach for Multi-objective Optimization[J]. Computer Engineering and Applications (S1002-8331), 2002, 38(8): 4-5.)
[20] 谢涛, 陈火旺. 多目标优化与决策问题的演化算法[J]. 中国工程科学, 2002, 4(2): 59-69
[21] Calheiros R N, Ranjan R, Beloglazov A, et al. CloudSim: A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms [J]. Software: Practice and Experience (S1097-024X), 2011, 41(1): 23-50. ?
[22] 刘少伟, 孔令梅, 任开军, 等. 云环境下优化科学工作流执行性能的两阶段数据放置与任务调度策略[J]. 计算机学报, 2011, 34(11): 2121-2130.
(Liu Shaowei, Kong Lingmei, Ren Kaijun, et al.A Two-step Data Placement and Task Scheduling Strategy for Optimizing Scientific Workflow Performance on Cloud Computing Platform[J]. Chinese Journal of Computer (S0254-4164), 2011, 34(11): 2121-2130.)