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

马英红; 吝李婉; 焦毅; 李秦尧

doi:10.19665/j.issn1001-2400.20231206

您当前的位置：

首页 >

文章列表页 >

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

信息与通信工程 | 更新时间：2024-06-03

- 通信计算联合优化的图分割工作流部署方法
- Workflow deployment method based on graph segmentation with communication and computation jointly optimized
- 西安电子科技大学学报 2024年51卷第2期页码：13-27
- 作者机构：
  
  1. 西安电子科技大学通信工程学院,陕西西安 710071
  2. 润建股份有限公司,陕西西安 710075
  3. 中国航天空气动力技术研究院创新与应用中心,北京 100074
- 作者简介：
  
  [ "马英红(1981—),女,副教授,E-mail:[email protected]; " ]
  [ "吝李婉(1995—),女,西安电子科技大学硕士研究生,E-mail:[email protected]; " ]
  [ "焦毅(1980—),男,讲师,E-mail:[email protected]; " ]
  [ "李秦尧(1993—),男,助理工程师,E-mail:[email protected]" ]
- 基金信息：
  
  “十四五”国防基础科研计划(JCKY2020203XXXX);中央高校基本科研业务费专项资金(JB210106)
- DOI：10.19665/j.issn1001-2400.20231206
  中图分类号： TP393
- 纸质出版日期：2024-4-20，
  
  网络出版日期：2024-1-4，
  
  收稿日期：2022-11-29，
扫描看全文
马英红, 吝李婉, 焦毅, 等. 通信计算联合优化的图分割工作流部署方法[J]. 西安电子科技大学学报, 2024,51(2):13-27.

Yinghong MA, Liwan LIN, Yi JIAO, et al. Workflow deployment method based on graph segmentation with communication and computation jointly optimized[J]. Journal of Xidian University, 2024,51(2):13-27.
马英红, 吝李婉, 焦毅, 等. 通信计算联合优化的图分割工作流部署方法[J]. 西安电子科技大学学报, 2024,51(2):13-27. DOI： 10.19665/j.issn1001-2400.20231206.

Yinghong MA, Liwan LIN, Yi JIAO, et al. Workflow deployment method based on graph segmentation with communication and computation jointly optimized[J]. Journal of Xidian University, 2024,51(2):13-27. DOI： 10.19665/j.issn1001-2400.20231206.

摘要

为提高计算效率

将复杂的大规模任务分解为简单任务并建模为工作流

交由并行分布式计算集群来完成

已成为云中心处理持续增长的计算和网络任务的重要手段。然而

分布式计算的任务间数据传输所带来的通信带宽占用却容易造成云中心的网络拥塞。如何兼顾计算效率和通信开销

科学地部署工作流意义重大。两类典型的工作流部署算法为基于列表的部署算法和基于分簇的部署算法。然而

前者致力于提高计算效率

未关注工作流中任务之间的通信开销

大规模工作流的部署易带来较重的网络负荷;后者关注通信开销的最小化

但牺牲了工作流中任务的并行计算效率

导致工作流完成时间较长。文中从图论的角度出发

充分挖掘工作流中各任务之间的依赖性和并行性

通过对经典图分割算法进行改进

实现了工作流任务分区过程中通信开销最小化和计算并行性最大化之间的平衡。仿真结果表明

在不同的工作流规模下

所提算法的通信开销比列表部署算法平均减少约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.

关键词

云计算数据中心工作流任务部署图论

Keywords

cloud computingdata centerworkflowtask deploymentgraph theory

references

张可涵, 李红艳, 刘文慧, 等. 面向流量预测的时间相关图卷积网络构建方法[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.

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.

王雪. 基于异构多核处理器的依赖任务调度策略研究[D]. 哈尔滨: 哈尔滨工程大学, 2014.

邵侠. 云计算环境下工作流任务调度算法研究[D]. 哈尔滨: 哈尔滨理工大学, 2019.

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.

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.

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.

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.

张庆根. 基于图分割强化学习的数据密集型科学工作流调度算法研究[D]. 哈尔滨: 哈尔滨理工大学, 2021.

KHAN M A. Scheduling for Heterogeneous Systems Using Constrained Critical Paths[J]. Parallel Computing, 2012, 38(4-5):175-193.

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.

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.

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.

蒋卓伽, 王瑾伟, 徐炜, 等. 云数据中心环境下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.

孙凤杰, 王克俭, 何振学, 等. 基于烟花算法的云计算任务调度研究[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.

韦昊典. 基于OpenStack的云计算资源分层调度系统[D]. 西安: 西安电子科技大学, 2022.

LU S, SHI W. Vehicle Computing:Vision and Challenges[J]. Journal of Information and Intelligence, 2023, 1(1):23-35.

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.

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.

杨煜, 段威威. 基于谱聚类的社交网络动态社区发现算法[J]. 计算机应用, 2023, 43(10):3129-3135. DOI:10.11772/j.issn.1001-9081.2022101517http://doi.org/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.2022101517http://doi.org/10.11772/j.issn.1001-9081.2022101517

周锐, 王桂娟, 邓皓天, 等. 复杂网络聚类特征层次布局算法[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.

NEWMAN M. Modularity and Community Structure in Networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(23):8577-8582.

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

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.

甘雨. 面向云计算平台的任务调度算法研究[D]. 武汉: 武汉科技大学, 2022.

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.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

灾后无人机自组网高动态多信道TDMA调度算法

面向云存储的数据流行度去重方案

面向数据质量的隐私保护多分类LR方案

面向ASPE的抗合谋攻击图像检索隐私保护方案

一种面向数据中心的能耗感知虚拟机放置策略