(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210730454.9 (22)申请日 2022.06.24 (71)申请人 西安电子科技大 学 地址 710071 陕西省西安市太白南路2号 (72)发明人 马英红　吝李婉　焦毅　李红艳　 刘伟　刘勤　张琰　 (74)专利代理 机构 陕西电子 工业专利中心 61205 专利代理师 王品华 (51)Int.Cl. G06F 9/50(2006.01) G06F 9/455(2006.01) G06F 16/901(2019.01) (54)发明名称 基于图分割的工作流部署方法 (57)摘要 本发明公开了一种基于图分割的工作流部 署方法， 主要解决现有基于分簇的工作流部署算 法以牺牲工作流中任务并行执行效率为代价实 现通信开销的最小化， 导致任务并行执行效率较 低的问题。 其实现方案是： 1)建立工作流有向无 环图DAG模型G； 2)计算工作流中任务执行时间和 任务间的数据传输时间； 3)对工作流模型G中的 串行结构进行合并， 得到新工作流模型图G'； 4) 对新工作流模型图G'进行分割， 得到最佳任务分 区； 5)以执行时间最小为依据， 将最佳任务分区 映射到虚拟机上， 完成对工作流的部署。 本发明 减小了工作流完成时间， 提高了工作流的执行效 率， 可用于工作流执行过程中数据开销与任务并 行执行效率的联合优化。 权利要求书3页 说明书8页 附图3页 CN 115080236 A 2022.09.20 CN 115080236 A 1.一种基于图分割的工作流部署方法， 其特 征在于， 包括如下步骤： (1)根据工作 流中的任务集T、 任务之间的数据依赖及时序关系E、 任务复杂度集合L、 数 据传输量 集合D， 建立工作流有向无环图DAG模型： G＝{T,E,L,D}； (2)为工作流分配一组虚拟机S＝{sk|k＝1,2,3,...,q}， q表示虚拟机 数量， 每个虚拟机 所对应的物理机各不相同； 计算工作流中任务在不同虚拟机上的执行时间wi,k和有数据依 赖关系任务之间的数据传输时间ci,j， 以及任务在所有虚拟机上的平均执行时间 和任务 之间的平均数据传输时间 (3)确定工作流模型G中具有串行结构的两个任务， 并对其进行合并， 得到新工作流模 型图G'： 在工作流模型图中， 如果一个任务中只有一个子任务且该子任务仅有一个父任务， 则 该子任务与其父任务构成串行 结构； 将拥有串行结构的任务ti和任务ti+1之间的数据传输 取消， 并将这两个任务相加合并为 一个新任务t ′i； (4)对串行 结构合并后形成的新工作流模型图G'进行分割： (4a)将工作流模型图G'划分为 n个子图， 每 个子图中包 含一个顶点； (4b)依次搜索并尝试合并有边连接的两个子图， 根据各子图中所包含的任务和任务之 间的连接关系， 计算每次合并后的模块度增量ΔQ： 如果两个子图中存在相同层的任务， 计算这两个子图合并后的新子图内同层任务平均 执行时间之和sum， 并将其与该层所有任务平均执 行时间的最大值maxW进行比较： 若sum＞maxW*α， 则ΔQ ＝‑(ei,j+ej,i‑2aia)j＝‑2(ei,j‑aiaj)； 否则， ΔQ＝ei,j+ej,i‑2aiaj＝2(ei,j‑aiaj)； 其中α 为比较系数， 取值为小于1的数， ei,j表 示第i个子图和第j个子图之间的连边权重占图G中总连边权重之和的比例， ai表示第i个子 图中所有任务的连边权 重之和占图G中总连边权 重之和的比例。 如果两个子图中不存在相同层的任务， 则ΔQ ＝ei,j+ej,i‑2aiaj＝2(ei,j‑aiaj)； (4c)将ΔQ 值最大的两个子图进行合并， 并更新模块度Q ＝Q+maxΔQ； (4d)重复(4a)至(4c)， 直至整个图G'合并为一个子图， 找到模块度值最大时对应 的图 划分结果， 即为最佳的任务分区P＝{p1,p2,...px,...,ph}， 其中px表示第x个任务分区， h表 示分区数量； (5)将最佳任务分区映射到虚拟机上， 完成对工作流的部署： (5a)根据任 务平均执行时间 和任务之间的平均数据传输时间 计算每个任 务的优 先级rank(ti)： 其中， suc c(ti)表示任务ti的子任务 集合； (5b)根据各任务的优先级ran k(ti)计算任务分区的优先级： rank(px)＝max(ran k(ti)， ti∈px) (5c)按rank(px)将所有分区降序排列， 每次选取rank(px)值最大且未部署的任务分区， 遍历所有虚拟机并计算该任务分区在当前虚拟机上的总执行时间与该虚拟上已部署任务权　利　要　求　书 1/3 页 2 CN 115080236 A 2的执行时间之和， 找到该值 最小的虚拟机sk； (5d)将任务分区中的所有任务作为一个整体一起部署到虚拟机sk上， 将分区内的多个 任务按照ran k(ti)值降序排列， 虚拟机将按照顺序依次执 行这些任务。 2.根据权利 要求1所述的方法， 其特征在于： 步骤(1)中， 建立工作流有向无环图模型G， 实现如下： (1a)将工作流中的任务集T表示为： T＝{ti|i＝1,2,...,n}， 其中ti表示第i个任务， n为 工作流包 含的任务数； (1b)将任务之 间的数据依赖及时序关系E表示为： E＝{ei,j|ti,tj∈T}， 其中ei,j取值为0 或1， 当ei,j取值为0时， 表示任务ti和任务tj之间无依赖关系/ 不存在边， 当ei,j取值为1时， 则 表示任务ti与任务tj之间有依赖关系 /存在边， 有向边ei,j连接两个任务ti和tj， 称ti为tj的 父任务， tj为ti的子任务， 将没有任何父任务的任务称为入口任务； (1c)将任务复杂度集 合L表示为： L＝{li|ti∈T}， 其中li表示任务ti的计算复杂度； (1d)将数据传输量集合D表示为： D＝{di,j|ti,tj∈T}， 其中di,j表示任务ti和任务tj之间 的数据传输量； (1e)将上述四个元 素组合， 得到 工作流有向无环图模型G＝{T,E,L,D}。 3.根据权利要求1所述的方法， 其特征在于： 步骤(2)中计算工作流中任务在不同虚拟 机上的执 行时间wi,k及任务在所有虚拟机上的平均执 行时间 公式如下： 其中， wi,k表示任务ti在虚拟机sk上的执行时间， 表示任务ti在所有虚拟机上的平均 执行时间， li表示任务ti的计算复杂度， vk表示虚拟机sk的处理能力， q表示可用虚拟机数 量。 4.根据权利要求1所述的方法， 其特征在于： 步骤(2)中计算有数据依赖关系任务之间 的数据传输时间ci,j任务之间的平均数据传输时间 公式如下： 其中， ci,j表示任务ti和任务tj之间的数据传输时间， 任 务ti和任务tj分别部署至虚拟机 sk1和虚拟机sk2上执行， di,j表示任务ti和任务tj之间的数据传输量， rk1,k2表示虚拟机sk1与 虚拟机sk2之间的数据传输速率； 表示第i个任务ti与第j个任务tj之间的平均数据传输 时间， 表示所有虚拟机之间的平均数据传输速率； 当两个有先后依赖关系的任务放在同 一个虚拟机时， 其之间的数据传输开销可忽略不计， 即ci,j为0。 5.根据权利要求1所述的方法， 其特征在于： 步骤(4b)中， 每个任务所处的层数由节点 与入口任务之间的最大距离决定 。 6.根据权利要求1所述的方法， 其特征在于： 步骤(4b)计算模块度增量ΔQ公式中所涉权　利　要　求　书 2/3 页 3 CN 115080236 A 3