通信计算联合优化的图分割工作流部署方法

doi:10.19665/j.issn1001-2400.20231206

摘要/Abstract

摘要：

为提高计算效率,将复杂的大规模任务分解为简单任务并建模为工作流,交由并行分布式计算集群来完成,已成为云中心处理持续增长的计算和网络任务的重要手段。然而,分布式计算的任务间数据传输所带来的通信带宽占用却容易造成云中心的网络拥塞。如何兼顾计算效率和通信开销,科学地部署工作流意义重大。两类典型的工作流部署算法为基于列表的部署算法和基于分簇的部署算法。然而,前者致力于提高计算效率,未关注工作流中任务之间的通信开销,大规模工作流的部署易带来较重的网络负荷;后者关注通信开销的最小化,但牺牲了工作流中任务的并行计算效率,导致工作流完成时间较长。文中从图论的角度出发,充分挖掘工作流中各任务之间的依赖性和并行性,通过对经典图分割算法进行改进,实现了工作流任务分区过程中通信开销最小化和计算并行性最大化之间的平衡。仿真结果表明,在不同的工作流规模下,所提算法的通信开销比列表部署算法平均减少约35%~50%,工作流完成时间比分簇部署算法平均降低约50%~65%,且对于具有不同通信计算比的工作流均具有良好的稳定性。

关键词: 云计算, 数据中心, 工作流, 任务部署, 图论

Abstract:

For the purpose of improving computing efficiency,it becomes an important way for cloud data centers to deal with the continuous growth of computing and network tasks by decomposes complex large-scale tasks into simple tasks and modeling them into workflows,which are then completed by parallel distributed computing clusters.However,the communication bandwidth consumption caused by inter-task transmission can easily cause network congestion in data center.It is of great significance to deploy workflow scientifically,taking into account both computing efficiency and communication overhead.There are two typical types of workflow deployment algorithms:list-based workflow deployment algorithm and cluster-based workflow deployment algorithm.However,the former focuses on improving the computing efficiency while does not pay attention to the inter-task communication cost,so the deployment of large-scale workflow is easy to bring heavy network load.The latter focuses on minimizing the communication cost,but sacrifices the parallel computing efficiency of the tasks in the workflow,which results in a long workflow completion time.This work fully explores the dependency and parallelism between tasks in workflow,from the perspective of graph theory.By improving the classic graph segmentation algorithm,community discovery algorithm,the balance between minimizing communication cost and maximizing computation parallelism was achieved in the process of workflow task partitioning.Simulation results show that,under different workflow scales,the proposed algorithm reduces the communication cost by 35%~50%,compared with the typical list-based deployment algorithm,and the workflow completion time by 50%~65%,compared with the typical cluster-based deployment algorithm.Moreover,its performance has good stability for workflows with different communication-calculation ratios.

Key words: cloud computing, data center, workflow, task deployment, graph theory

中图分类号:

TP393

马英红, 吝李婉, 焦毅, 李秦尧. 通信计算联合优化的图分割工作流部署方法[J]. 西安电子科技大学学报, 2024, 51(2): 13-27.

MA Yinghong, LIN Liwan, JIAO Yi, LI Qinyao. Workflow deployment method based on graph segmentation with communication and computation jointly optimized[J]. Journal of Xidian University, 2024, 51(2): 13-27.

图/表 12

图1

图2

图3

图4

图5

图6

表1

表2

表3

图9

图10

图11

参考文献 26

[1]	张可涵, 李红艳, 刘文慧, 等. 面向流量预测的时间相关图卷积网络构建方法[J]. 西安电子科技大学学报, 2023, 50(5):11-20.
	ZHANG Kehan, LI Hongyan, LIU Wenhui, et al. Construction Method of Temporal Correlation Graph Convolution Network for Traffic Prediction[J]. Journal of Xidian University, 2023, 50(5):11-20.
[2]	TOPCUOGLU H, HARIRI S, WU M Y. Task Scheduling Algorithms for Heterogeneous Processors[C]//Proceedings of the 8th Heterogeneous Computing Workshop(HCW'99). Piscataway:IEEE,1999:3-14.
[3]	王雪. 基于异构多核处理器的依赖任务调度策略研究[D]. 哈尔滨: 哈尔滨工程大学, 2014.
[4]	邵侠. 云计算环境下工作流任务调度算法研究[D]. 哈尔滨: 哈尔滨理工大学, 2019.
[5]	BITTENCOURT L F, SAKELLARIOU R, MADEIRA E. Dag Scheduling Using a Lookahead Variant of the Heterogeneous Earliest Finish Time Algorithm[C]// 2010 18th Euromicro Conference on Parallel,Distributed and Network-based Processing.Piscataway:IEEE, 2010: 27-34.
[6]	DJIGAL H, FENG J, LU J, et al. IPPTS:An Efficient Algorithm for Scientific Workflow Scheduling in Heterogeneous Computing Systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2020, 32(5):1057-1071.
[7]	ARABNEJAD H, BARBOSA J G. List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 25(3):682-694.
[8]	AHMAD S G, LIEW C S, RAFIQUE M M, et al. Data-Intensive Workflow Optimization Based on Application Task Graph Partitioning in Heterogeneous Computing Systems[C]//Proceedings of the IEEE Fourth International Conference on Big Data and Cloud Computing. Piscataway:IEEE,2014:129-136.
[9]	张庆根. 基于图分割强化学习的数据密集型科学工作流调度算法研究[D]. 哈尔滨: 哈尔滨理工大学, 2021.
[10]	KHAN M A. Scheduling for Heterogeneous Systems Using Constrained Critical Paths[J]. Parallel Computing, 2012, 38(4-5):175-193.
[11]	ZHOU Y, TIAN L, LIU L, et al. Fog Computing Enabled Future Mobile Communication Networks:A Convergence of Communication and Computing[J]. IEEE Communications Magazine, 2019, 57(5):20-27.
[12]	QI Y, TIAN L, ZHOU Y, et al. Mobile Edge Computing-Assisted Admission Control in Vehicular Networks:The Convergence of Communication and Computation[J]. IEEE Vehicular Technology Magazine, 2019, 14(1):37-44.
[13]	LI A, SUN J, ZENG X, et al. FedMask:Joint Computation and Communication-Efficient Personalized Federated Learning via Heterogeneous Masking[C]//Proceedings of the 19th ACM Conference on Embedded Networked Sensor Systems(SenSys '21). New York: ACM,2021:42-55.
[14]	蒋卓伽, 王瑾伟, 徐炜, 等. 云数据中心环境下NFV虚拟资源计算算法研究[J]. 信息技术, 2022,8:53-58.
	JIANG Zhuojia, WANG Jinwei, XU Wei, et al. Research on NFV Virtual Resource Computing Algorithm in Cloud Data Center Environment[J]. Information Technology, 2022,8:53-58.
[15]	孙凤杰, 王克俭, 何振学, 等. 基于烟花算法的云计算任务调度研究[J]. 计算机仿真, 2022, 39(3):340-343.
	SUN Fengjie, WANG Kejian, HE Zhenxue, et al. Research on Cloud Computing Task Scheduling Based on Fireworks Algorithm[J]. Computer Simulation, 2022, 39(3):340-343.
[16]	韦昊典. 基于OpenStack的云计算资源分层调度系统[D]. 西安: 西安电子科技大学, 2022.
[17]	LU S, SHI W. Vehicle Computing:Vision and Challenges[J]. Journal of Information and Intelligence, 2023, 1(1):23-35.
[18]	LIU H, YANG M, WANG T, et al. A Heuristic Mixed Real-Time Task Allocation of Virtual Utilization in Multi-Core Processor[J]. Journal of Information and Intelligence, 2023, 1(2):156-177.
[19]	MOHAMED E, AGOUTI T, TIKNIOUINE A, et al. A Comprehensive Literature Review on Community Detection:Approaches and Applications[J]. Procedia Computer Science, 2019,151:295-302.
[20]	杨煜, 段威威. 基于谱聚类的社交网络动态社区发现算法[J]. 计算机应用, 2023, 43(10):3129-3135. doi: 10.11772/j.issn.1001-9081.2022101517
	YANG Yi, DUAN Weiwei. Spectral Clustering Based Dynamic Community Discovery Algorithm in Social Network[J]. Journal of Computer Applications, 2023, 43(10):3129-3135. doi: 10.11772/j.issn.1001-9081.2022101517
[21]	周锐, 王桂娟, 邓皓天, 等. 复杂网络聚类特征层次布局算法[J]. 计算机应用研究, 2022, 39(2):479-484.
	ZHOU Rui, WANG Guijuan, DENG Haotian, et al. Complex Network Clustering Feature Multi-Level Layout Algorithm[J]. Application Research of Computers, 2022, 39(2):479-484.
[22]	NEWMAN M. Modularity and Community Structure in Networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(23):8577-8582.
[23]	XIA C, LUO Y, WANG L, et al. A Fast Community Detection Algorithm Based on Reconstructing Signed Networks[J]. IEEE Systems Journal, 2022, 16(1):614-625
[24]	ZHOU J, CHEN Z, DU M, et al. RobustECD:Enhancement of Network Structure for Robust Community Detection[J]. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(1):842-856.
[25]	甘雨. 面向云计算平台的任务调度算法研究[D]. 武汉: 武汉科技大学, 2022.
[26]	DEVARAJ R, SARKAR A. Comments on “IPPTS:An Efficient Algorithm for Scientific Workflow Scheduling in Heterogeneous Computing Systems”[J]. IEEE Transactions on Parallel and Distributed Systems:A Publication of the IEEE Computer Society, 2023, 34(3):810-811.

参数	固定值(变化值)
N/个	50(20,40,60,80,100)
K/个	5(1,2,3,4,5,6)
CCR	0.5(0.4,0.8,1.2,1.6,2.0)