西安电子科技大学学报（自然科学版）2024，Vol.51Issue(2)：13-27,15.DOI:10.19665/j.issn1001-2400.20231206
通信计算联合优化的图分割工作流部署方法
Workflow deployment method based on graph segmentation with communication and computation jointly optimized
摘要
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分类
信息技术与安全科学引用本文复制引用
马英红,吝李婉,焦毅,李秦尧..通信计算联合优化的图分割工作流部署方法[J].西安电子科技大学学报（自然科学版）,2024,51(2):13-27,15.基金项目
"十四五"国防基础科研计划(JCKY2020203XXXX) （JCKY2020203XXXX）
中央高校基本科研业务费专项资金(JB210106) （JB210106）
