Multi-dimensional Feature Fusion-based Runtime Prediction Approach for Cloud Workflow Tasks
-
摘要: 任务执行时间估计是云数据中心环境下工作流调度的前提. 针对现有工作流任务执行时间预测方法缺乏类别型和数值型数据特征的有效提取问题, 提出了基于多维度特征融合的预测方法. 首先, 通过构建具有注意力机制的堆叠残差循环网络, 将类别型数据从高维稀疏的特征空间映射到低维稠密的特征空间, 以增强类别型数据的解析能力, 有效提取类别型特征; 其次, 采用极限梯度提升算法对数值型数据进行离散化编码, 通过对稠密空间的输入向量进行稀疏化处理, 提高了数值型特征的非线性表达能力; 在此基础上, 设计多维异质特征融合策略, 将所提取的类别型、数值型特征与样本的原始输入特征进行融合, 建立基于多维融合特征的预测模型, 实现了云工作流任务执行时间的精准预测; 最后, 在真实云数据中心集群数据集上进行了仿真实验. 实验结果表明, 相对于已有的基准算法, 该方法具有较高的预测精度, 可用于大数据驱动的云工作流任务执行时间预测.Abstract: Task runtime estimation is a prerequisite for workflow scheduling in cloud data centers. However, the existing runtime prediction methods for workflow activities fail to effectively extract categorical and numerical features. In this paper, we propose a multi-dimensional feature fusion-based runtime prediction approach for workflow tasks. Firstly, we construct a stacked residual recurrent neural network with an attention mechanism for mapping categorical data from high-dimensional sparse space to low-dimensional dense space so as to enlarge its capability of parsing categorical data for categorical feature extraction. Secondly, extreme gradient boosting is introduced to discretize the numerical data and enhance the nonlinear representation capability for numerical features through sparsely processing the input vectors within dense space. Thirdly, we design a heterogeneous multi-dimensional feature fusion strategy, and then blend the extracted features with original inputs to mine comprehensive knowledge for runtime prediction. Finally, based on the resulting multi-dimensional fused features, a prediction model is developed to fully utilize these features as well as its corresponding hidden knowledge and then to forecast the runtimes accurately for cloud workflow tasks. To verify the effectiveness and superiority of the proposed method, we conduct extensive experiments on a cluster dataset from a real cloud data center. The experimental results show that, our approach outperforms the existing algorithms and can be applied in big data-driven runtime prediction for workflow activities in the cloud.
-
Key words:
- Cloud data centers /
- workflows /
- ensemble learning /
- feature fusion /
- execution time prediction
-
图 1 基于多维度特征融合的云工作流任务执行时间预测模型
Fig. 1 The multi-dimensional feature fusion-based runtime prediction model for cloud workflow tasks
表 1 预测精度的差值
Table 1 The difference of prediction performance
i $ \delta _i^{MAE}$ $\delta _i^{RMSE} $ $ \delta _i^{RMSLE}$ $\delta _i^{R2} $ DIN 1.439 1.825 0.679 0.006 DCN 0.286 4.043 0.048 0.014 DeepFM 0.373 1.811 0.043 0.009 W&D 0.810 3.576 0.141 0.012 TSA 0.942 6.408 0.030 0.025 GBDT + LR 1.257 2.143 0.117 0.007 
下载: 导出CSV
表 2 预测精度提升的比例(%)
Table 2 The proportion of performance improvement (%)
i $ \eta _i^{MAE}$ $\eta _i^{RMSE} $ $ \eta _i^{RMSLE}$ $\eta _i^{R2} $ DIN 36.94 22.06 82.60 0.61 DCN 10.43 36.95 16.49 1.43 DeepFM 13.18 18.85 15.03 0.92 W&D 24.80 34.14 36.72 1.22 TSA 27.72 48.16 10.99 2.59 GBDT + LR 33.85 23.70 32.50 0.71
下载: 导出CSV
-
[1] Versluis L, Iosup A. A survey of domains in workflow scheduling in computing infrastructures: Community and keyword analysis, emerging trends, and taxonomies. Future Generation Computer Systems, 2021, 123: 156-177 doi: 10.1016/j.future.2021.04.009 [2] Paknejad P, Khorsand R, Ramezanpour M. Chaotic improved PICEA-g-based multi-objective optimization for workflow scheduling in cloud environment. Future Generation Computer Systems, 2021, 117: 12-28 doi: 10.1016/j.future.2020.11.002 [3] Mohammadzadeh A, Masdari M, Gharehchopogh F S, Jafarian A. A hybrid multi-objective metaheuristic optimization algorithm for scientific workflow scheduling. Cluster Computing, 2021, 24(2): 1479-1503 doi: 10.1007/s10586-020-03205-z [4] Chu Z, Yu J, Hamdulla A. A novel deep learning method for query task execution time prediction in graph database. Future Generation Computer Systems, 2020, 112: 534-548 doi: 10.1016/j.future.2020.06.006 [5] Pham T, Durillo J J, Fahringer T. Predicting workflow task execution time in the cloud using a two-stage machine learning approach. IEEE Transactions on Cloud Computing, 2020, 8(1): 256-268 doi: 10.1109/TCC.2017.2732344 [6] Chirkin A M, Belloum A S Z, Kovalchuk S V, Makkes M X, Melnik M A, Visheratin A A, et al. Execution time estimation for workflow scheduling. Future Generation Computer Systems, 2017, 75(10): 376-387 [7] Moreno C, Fischmeister S. Accurate measurement of small execution times-getting around measurement errors. IEEE Embedded Systems Letters, 2017, 9(1): 17-20 doi: 10.1109/LES.2017.2654160 [8] Pietri I, Juve G, Deelman E, Sakellariou R. A performance model to estimate execution time of scientific workflows on the cloud. In: Proceedings of the 9th Workshop on Workflows in Support of Large-scale Science. New Orleans, USA: IEEE, 2014. 11−19 [9] 许伦凡, 熊敏, 肖永浩. 基于调度历史数据在线预测作业执行时间. 计算机应用研究, 2018, 37(3): 1-6Xu Lun-Fan, Xiong Min, Xiao Yong-Hao. On-line prediction of application runtime using schedule historical data. Application Research of Computers, 2018, 37(3): 1-6 [10] Chirkinab A M, Kovalchuka S V. Towards better workflow execution time estimation. IERI Procedia. 2014, 10: 216-223 doi: 10.1016/j.ieri.2014.09.080 [11] Xu H, Li X. Methods for virtual machine scheduling with uncertain execution times in cloud computing. International Journal of Machine Learning and Cybernetics, 2017, 10(6): 325-335 [12] Nouri A, Poplavko P, Angelis L, Zerzelidis A, Bensalem S, Katsaros P. Maximal software execution time: A regression-based approach. Innovations in Systems & Software Engineering, 2018, 14(2): 101-116 [13] Tahvili S, Afzal W, Saadatmand M, Bohlin M, Ameerjan S H. ESPRET: A tool for execution time estimation of manual test cases. Journal of Systems and Software, 2018, 146: 26-41 doi: 10.1016/j.jss.2018.09.003 [14] Park J W, Kim E. Runtime prediction of parallel applications with workload-aware clustering. Journal of Supercomputing, 2017, 73(3): 1-17 [15] 郑婷婷, 陈洁璇, 许洋, 余阳, 潘茂林. 业务流程中一种个性化的任务完成时间预测方法. 计算机集成制造系统, 2019, 25(4): 207-214Zheng Ting-Ting, Chen Jie-Xuan, Xu Yang, Yu Yang, Pan Mao-Lin. Approach for individual task completion time prediction in business processes. Computer Integrated Manufacturing Systems, 2019, 25(4): 207-214 [16] 夏元清, 闫策, 王笑京, 宋向辉. 智能交通信息物理融合云控制系统. 自动化学报, 2019, 45(1): 132-142Xia Yuan-Qing, Yan Ce, Wang Xiao-Jing, Song Xiang-Hui. Intelligent transportation cyber-physical cloud control systems. Acta Automatica Sinica, 2019, 45(1): 132-142 [17] 范苍宁, 刘鹏, 肖婷, 赵巍, 唐降龙. 深度域适应综述: 一般情况与复杂情况. 自动化学报, 2021, 47(3): 515−548Fan Cang-Ning, Liu Peng, Xiao Ting, Zhao Wei, Tang Xiang-Long. A review of deep domain adaptation: general situation and complex situation. Acta Automatica Sinica, 2021, 47(3): 515−548 [18] 伍章俊, 刘晓, 倪志伟. 基于混沌时间序列的云工作流活动运行时间预测模型. 计算机集成制造系统, 2013, 19(8): 1920-1927Wu Zhang-Jun, Liu Xiao, Ni Zhi-Wei. Forecasting model for activity durations in cloud workflow based on chaotic time series. Computer Integrated Manufacturing Systems, 2013, 19(8): 1920-1927 [19] Nadeem F, Alghazzawi D, Mashat A, Fakeeh K, Almalaise A, Hagras H. Modeling and predicting execution time of scientific workflows in the grid using radial basis function neural network. Cluster Computing, 2017, 20(3): 2805–2819 doi: 10.1007/s10586-017-1018-x [20] Rehse J R, Fettke P. A deep learning approach for predicting process behavior at runtime. In: Proceedings of the 12th International Conference on Business Process Management. Barcelona, Spain: 2017. 327−338 [21] Zhu Z, Fan P. Machine learning based prediction and classification of computational jobs in cloud computing centers. In: Proceedings of the 15th International Wireless Communications & Mobile Computing Conference. Tangier, Morocco: IEEE, 2019. 1482−1487 [22] Bi J, Li S, Yuan H, Zhao Z, Liu H. Deep neural networks for predicting task time series in cloud computing systems. In: Proceedings of the 16th International Conference on Networking, Sensing and Control. Banff, Canada: 2019. IEEE, 86−91 [23] Dong X, Yu Z, Cao W, Shi Y, Ma Q. A survey on ensemble learning. Frontiers of Computer Science, 2020, 14(2): 241-258 doi: 10.1007/s11704-019-8208-z [24] 郑顾平, 王秋萍. 基于参数变化的云应用程序执行时间预估方法. 计算机工程与应用, 2017, 53(11): 95-99 doi: 10.3778/j.issn.1002-8331.1605-0047Zheng Gu-Ping, Wang Qiu-Ping. Method for predicting execution time of cloud application based on parametric variation. Computer Engineering and Applications, 2017, 53(11): 95-99 doi: 10.3778/j.issn.1002-8331.1605-0047 [25] 李帅标, 赵海燕, 陈庆奎, 曹健. 基于Stacking策略的过程剩余执行时间预测. 小型微型计算机系统, 2019, 40(12): 2481-2486 doi: 10.3969/j.issn.1000-1220.2019.12.001Li Shuai-Biao, Zhao Hai-Yan, Chen Qing-Kui, Cao Jian. Process remaining execution time prediction based on stacking strategy. Journal of Chinese Computer Systems, 2019, 40(12): 2481-2486 doi: 10.3969/j.issn.1000-1220.2019.12.001 [26] Nadeem F, Daniyal A, Mashat A, Faqeeh K, Almalaise A. Using machine learning ensemble methods to predict execution time of e-science workflows in heterogeneous distributed systems. IEEE Access, 2019, 7: 25138–25149 doi: 10.1109/ACCESS.2019.2899985 [27] Hilman M H, Rodriguez M A, Buyya R. Task runtime prediction in scientific workflows using an online incremental learning approach. In: Proceedings of the 11th IEEE/ACM International Conference on Utility and Cloud Computing. Zurich, Switzerland: IEEE, 2018. 1−8 [28] Gao Y, Zhang B, Wang S, Ma A. DBN based cloud service response time prediction method. In: Proceedings of the International Conference on Advanced Communication Technology. Bongpyeong, South Korea: IEEE, 2019. 42−46 [29] Pham T P, Durillo J J, Fahringer T. Predicting workflow task execution time in the cloud using a two-stage machine learning approach. IEEE Transactions on Cloud Computing, 2017, 8(1): 1-13 [30] Li H, Cao Y, Li S, Zhao J, Sun Y. XGBoost model and its application to personal credit evaluation. IEEE Intelligent Systems, 2020, 35(3): 52-61 doi: 10.1109/MIS.2020.2972533 [31] Weng T, Liu W, Xiao J. Supply chain sales forecasting based on lightGBM and LSTM combination model. Industrial Management & Data Systems, 2020, 120(2): 265-279 [32] Guo J, Chang Z, Wang S, Ding H, Feng Y, Mao L, Bao Y. Who limits the resource efficiency of my datacenter: an analysis of Alibaba datacenter traces. In: Proceedings of the International Symposium on Quality of Service. New York, USA: 2019. 1–10 [33] Zhou G, Fan Y, Yan Y, Zhu X, Zhu H, Group A, et al. Deep interest network for click-through rate prediction. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. London, UK: 2018. 1059–1068 [34] Wang R, Fu B, Fu G, Wang M. Deep & cross network for ad click predictions. In: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Halifax, Canada: 2017. 1–7 [35] Li L, Hong J, Min S, Xue Y. A novel CTR prediction model based on DeepFM for taobao data. In: Proceedings of the IEEE International Conference on Artificial Intelligence and Industrial Design. Guangzhou, China: IEEE, 2021. 184−187 [36] Kim M, Lee S, Kim J. A wide & deep learning sharing input data for regression analysis. In: Proceedings of IEEE International Conference on Big Data and Smart Computing. Busan, South Korea: IEEE, 2020. 8−12 [37] Christakopoulou K, Beutel A, Li R, Jain S, Chi E H. Q&R: A two-stage approach toward interactive recommendation. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. London, UK: 2018. 139–148 [38] He X, Pan J, Jin O, Xu T, Liu B, Xu T, et al. Practical lessons from predicting clicks on ads at Facebook. In: Proceedings of the 8th International Workshop on Data Mining for Online Advertising. New York, USA: 2014. 1–9 [39] 赵文迪, 陈德旺, 卓永强, 黄允浒. 深度神经模糊系统算法及其回归应用. 自动化学报, 2020, 46(11): 2350−2358Zhao Wen-Di, Chen De-Wang, Zhuo Yong-Qiang, Huang Yun-Hu. Deep neural fuzzy system algorithm and its regression application. Acta Automatica Sinica, 2020, 46(11): 2350−2358 [40] Gupta R, Pandey G, Chaudhary P, Pal S K. Machine learning models for government to predict COVID-19 outbreak. Digital Government Research and Practice, 2020, 1(4): 1-6 -
图(7) / 表(2)
计量
- 文章访问数: 1142
- HTML全文浏览量: 846
- PDF下载量: 275
- 被引次数: 0
