随着人工智能与移动互联网的不断发展，远程智能监控^[1]、自动驾驶^[2]等为代表的新型业务应用大量涌现，这些应用通常需要消耗大量的计算资源^[3]. 同时，随着应用越来越复杂，通常以微服务^[4]的形式进行开发部署，此时一个应用往往可拆分成多个具有数据依赖与时序依赖关系的子任务集合，通常可表示为工作流结构^[5]. 图1展示了2种典型的工作流结构：链式工作流应用和有向无环图（directed acyclic graph，DAG）式工作流应用. 链式工作流应用为一系列顺序执行的子任务，如：采用深度神经网络（deep neural network，DNN）模型（如VGG^[6]）对图像进行识别，其神经网络模型可表示为若干顺序执行的不同模型层次（如卷积层、池化层、全连接层等）^[6-8]，并可按层进行任务划分与卸载；而DAG式工作流^[5,9-10]则通常由多个分支与汇聚结构组成，比如：智能道路监控需要并行执行多项子任务，可以用DAG图来描述.

图  1  算力网络（CPN）环境下工作流执行场景

Figure  1.  Workflow execution scenario in CPN environment

下载: 全尺寸图片 幻灯片

目前终端设备由于计算能力有限，难以支撑工作流应用的执行^[11]，而云服务器虽然具有丰富的计算资源，但端云间较大的网络通信延迟^[9]将极大降低工作流应用的执行性能. 边缘计算^[12]通过将边缘服务器部署在靠近用户的网络边缘侧为用户提供计算资源，一方面补齐了终端算力不足的短板，另一方面降低了任务上云所带来的通信开销. 近年来已有不少相关工作^{[1,6-7,12-16]}关注边缘计算场景下的任务卸载与执行优化问题，然而这种端边云之间的垂直协同模式通常仅考虑终端和相邻边缘计算资源的协同与卸载，无法有效融合广域范围内的算力资源，因此仍然难以满足复杂工作流的高效能、低延迟需求.

近年来，边缘服务器在网络中的广泛部署，使得算力从集中走向分布，计算从“点”到“网”逐渐成为网络基础设施的重要组成部分. 算力网络^[17]通过无处不在的网络感知并连接分布式的算力节点，基于软件定义网络（software defined network，SDN）^[18]的思想将路由层分为控制面和转发面，综合考虑网络和计算资源状况，将业务调度到合适的计算资源节点上.

然而，面对算力网络中网络环境高复杂强动态、算力资源高异构泛分布的特点，实现广域算网融合环境下的资源高效融合和协同是一项挑战. 具体表现在2个方面：

1）计算模式方面. 许多新兴应用其源与目的不一定相同^[8]，如图1中的智能道路监控，橙色实线表示数据的传输路径，道路图像由路边的摄像头采集（源），而分析的结果需要传到监控中心（目的）. 若采用传统侧重于靠近终端用户的边缘计算模式，将会在源端附近完成所有计算，然后再通过广域网络进行远距离传输. 由于无法有效融合广域范围内的算力与网络资源，将导致较差的任务执行性能. 因此算力网络环境中的工作流调度需要同时考虑任务在多边缘节点间的计算与传输开销的协同分配模式，实现边传边算，传算协同.

2）问题求解方面. 广域算力网络环境和传统边缘计算环境相比，具有算力资源高异构、泛分布的特点，因此相较传统端边云间的任务卸载问题，算力网络下的任务卸载问题具有更高的复杂性（不仅需要考虑任务的卸载还要决策数据的传输路径）. 除此之外，应用的复杂性和环境的动态性将进一步增加任务卸载与资源分配的求解难度.

目前针对算力网络环境下的复杂工作流任务，协同优化的工作还很少，而传统边缘计算环境下的工作流卸载的工作^[9-10,19-20]无法直接适用. 为此，本文研究了算力网络环境下工作流任务的卸载与资源分配优化问题，主要贡献有3个方面：

1）分析了算力网络下的工作流任务卸载与执行模式，并提出了算力网络环境下工作流任务卸载与资源分配问题. 综合考虑了算力网络中的网络环境、计算资源以及工作流任务的拓扑信息，建立时延模型，为工作流任务卸载与资源分配问题提供优化目标.

2）针对链式工作流任务，设计并实现了一种基于势博弈^[21]的分布式工作流卸载（decentralized workload offloading，DWO）算法. 首先根据卸载决策通过凸优化^[22]方法得到最优资源分配方案；然后将卸载决策建模为一个加权拥塞博弈问题，并证明了该博弈是一种势博弈（至少存在一个纳什均衡解）和无政府代价^[21]（price of anarchy，PoA）值. 另外，针对DAG工作流任务，设计并实现了一种基于动态资源权重的启发式工作流卸载（heuristic workflow offloading, Heu-WO）算法. 该算法将每个资源的占有情况记作资源权重，每个子任务基于资源权重选择完成时间最少的节点进行卸载，并动态更新资源权重.

3）针对算力网络环境下工作流任务卸载和资源分配问题，为了验证本文所提算法的有效性，设计并实现了仿真实验. 相比较最优解，本文所提算法DWO降低了一个维度（用户维度）的时间复杂度，解的近似比高达94.6%，相比其他算法可以获得最高3.2x的加速比；本文所提算法Heu-WO的时间复杂度为多项式级别，相比其他算法可以获得最高2.8x的加速比. 从而验证了本文所提算法的有效性.

1.   相关工作

为了解决终端计算能力的限制，文献[6, 13-15]从模型切分和卸载的角度出发，研究了将任务部分卸载到边缘服务器上处理来降低任务的计算时延. 其中LEIME^[6]提出了一种基于多出口DNN的低延迟边缘智能方案来解决传统多出口DNN无法提供快速且一致的推理. 首先它在模型级别，提出了一种提前退出算法，以自动构建具有较低时间复杂度的最优 ME-DNN；在计算层面，提出了一种分布式卸载机制，在运行时微调任务调度，以维持动态环境中的高性能，具有接近最优性能保证的特性. Neurosurgeon^[13]所考虑的计算任务是基于AlexNet，VGG这样的链式深度神经网络模型，并按照层来考虑切分点位置，综合网络环境和终端设备算力及边缘服务器的算力，找到一个最佳的切分位置使得总体的计算时延最低或者能量开销最低. 文献[14]提出了一种将 DNN 划分为多个分区的技术，这些分区可以在本地处理或卸载到一个或多个强大的节点. 通过设计自适应 DNN 分区方案和基于匹配游戏方法卸载计算的分布式算法来加快推理速度. 文献[15]在基于正交频分多址（orthogonal frequency division multiple access，OFDMA）的协同边缘计算场景下考虑了卸载决策、协作决策、计算资源分配和通信资源分配问题. 用户的延迟敏感任务可以在本地计算，或卸载到协作设备、MEC服务器. 目标是在延迟约束下最小化所有移动用户的总能量消耗，并提出了一种两级交替方法来解决公式化的混合整数非线性规划（mixed-integer nonlinear programming，MINLP）问题. 在上层，使用启发式算法来处理初始设置下的协作决策和卸载决策；在下层，基于当前卸载决策，通过深度强化学习更新功率、子载波和计算资源的分配. 但是由于启发式算法和深度强化学习的联合算法的算法复杂度会比较高，上述工作^[6,13-15]基于传统深度学习模型具有链式的特点，在研究模型切分时对于链式任务的切分难以表达现在复杂工作流任务，呈现DAG的依赖关系.

针对日益复杂的应用，文献[9-10, 19-20]研究了工作流任务的卸载问题. 其中，文献[9]研究了具有预算约束下最小化工作流任务完成时间问题，即每个移动设备的预算都是有限的，并且必须确定哪些子任务应该在本地计算或者应该发送到边缘服务器或云服务器，针对2种合作模式（单边缘服务器与云服务器协同和多边缘服务器协同），分别设计了基于贪心策略的任务卸载算法. 文献[10]研究了MEC 在依赖和服务缓存约束下的任务卸载问题，提出了一种基于表的启发式任务卸载算法，该算法能够预测卸载决策的影响. 通过使用时间消耗表来预测卸载某个子任务的影响力，从而做出卸载决策. 文献[19]研究了具有通信延迟和应用程序完成截止日期的异构处理器上的工作流任务调度，提出了一种启发式算法ITAGS，首先通过松弛原问题中的二元约束，转化成凸问题，并获得原问题最优目标的下界；然后为每个单独子任务分配截止时间；最后贪婪地优化每一子任务调度. 文献[20]提出了一种联合工作流任务卸载和流调度的启发式算法，利用每个任务图的知识和流程的开始时间来做出任务卸载决策. 文献[9-10, 19-20] 工作默认卸载是单跳的，没有考虑到算力网络环境中任务可以通过多跳的方式卸载到原本访问不到的算力节点上，即算力路由问题，难以有效利用网络中的算力资源.

为了有效利用网络中的算力资源，文献[8, 23-25]研究了任务在多跳网络环境下的卸载问题. 其中，文献[8]介绍了一种低延迟自适应工作负载分配框架，首先通过一种自适应任务划分和放置算法来利用计算网络资源. 其次，为了解决复杂的 DAG 拓扑，设计了一种分区和放置的最优寻路算法用于联合优化计算寻路和工作负载分配. 文献[23]研究了工业物联网场景下多跳计算卸载中的计算卸载和通信路由问题，以最小化每个任务的计算时间和能量消耗为目标，将联合优化问题制定成一个势博弈问题；通过一种自由约束机制来确保有限的改进路径可以达到纳什均衡，提出了一种多跳协作消息传递机制并开发了2种可以实现纳什均衡的服务质量（quality of service，QoS）感知分布式算法. 文献[24]研究了联合多任务部分计算卸载和网络流调度问题，目标是最小化所有任务的平均完成时间，提出了一种联合部分卸载和流调度的启发式算法，通过考虑设备的等待时间和网络流的开始时间来决定部分卸载率；同时使用McCormick包络将公式化的MINLP问题松弛成线性规划（linear programming，LP）问题，以提供下界. 文献[25]提出了一种避免分割网络的启发式方法和一种可以优化多跳协作网络中计算任务分配的迭代任务分配算法，来评估多跳网络中计算卸载的效果. 上述工作^{[8, 23-25]}聚焦卸载问题，没有考虑资源分配的问题，而是事先声明一个子任务需要多少的计算资源或者考虑排队、均匀分配资源，然而对于不同任务，适当的资源分配算法对满足延迟要求是至关重要的.

综上，现有的研究工作难以适用于算力网络环境下的工作流卸载问题，因此本文以最小化平均工作流任务完成时间为目标，研究了算力网络环境下工作流任务卸载与资源分配问题.

2.   问题定义和建模

2.1   问题分析

本文旨在研究一种算力网络环境下的通用工作流任务的执行优化机制，对于许多新兴业务应用其源与目的不一定相同^[8]，例如：智能安防、远程控制、增强现实应用等. 图2展示了算力网络环境下算力节点协作处理工作流任务的场景. 在这一场景中，算力节点高效协同，为低延时的工作流任务提供更好的性能保障. 如图2中任务执行路径所示，数据在终端设备（摄像头）上产生，需要经过多个算力节点协同分析处理，最终将数据的识别结果发送至远端的智能监控中心. 在这种执行模式下，数据源和目的之间的路径选择、工作流任务的卸载位置以及算力节点的资源分配情况都将影响应用的执行性能. 因此，本文研究的问题是在算力网络环境下联合任务卸载和资源分配优化问题，以最小化工作流任务的端到端延迟.

图  2  整体框架

Figure  2.  Overall framework

下载: 全尺寸图片 幻灯片

2.2   问题建模

1）系统建模. 我们把算力网络建模成一个有向无环图^[5]（DAG）：$GE = (M,ER)$，其中$M$表示算力节点的集合，$ER$表示算力节点之间物理链路的集合. 我们用${F_m}$表示算力节点$m \in M$的计算能力（以FLOPS来衡量）；${B_{m,n}}$表示算力节点$m$到算力节点$n$之间的带宽.

2）任务建模. $U$表示用户的集合，由于工作流任务由多个具有依赖关系的子任务构成，将任务建模成一个有向无环图：$GT = (S,S R)$，其中$S$表示工作流任务中子任务的集合，$S R$表示子任务之间依赖关系集合. ${c_{u,s}}$表示用户$u$中子任务$s$所需的计算量，${d_{u,s}}$表示子任务$s$的中间数据/输出结果所需的数据传输量. 本文中主要符号及含义如表1所示.

表  1  主要符号的含义

Table  1.  Meaning of the Main Symbols

符号	含义
${F_m}$	算力节点$m$的算力
${B_{m,n}}$	算力节点$m$和$n$之间的带宽
${c_{u,s}}$	用户$u$的子任务$s$的计算量
${d_{u,s}}$	用户$u$的子任务$s$的数据量
${A_{u,s}}$	用户$u$的子任务$s$的卸载位置
$A_{u,t}$	用户$u$的子任务$t$的卸载位置
${P_{u,s}}$	分配给用户$u$的子任务$s$的算力比例
${Q_{u,s,t}}$	分配给用户$u$的子任务$s$到子任务$t$的带宽比例

下载: 导出CSV 

| 显示表格

基于上述问题建模，本文研究的问题包含二维影响工作流任务执行性能的决策变量：卸载决策和资源分配决策. 卸载决策决定将工作流任务中的子任务提交到哪个算力节点${A_{u,s}}$上进行执行；资源分配决策决定工作流任务中提交的子任务分配计算资源的比例${P_{u,s}}$，以及分配的带宽资源的比例${Q_{u,s,t}}$.

2.3   问题定义

工作流任务的处理延迟包括计算延时和中间数据/结果的传输时延2部分. 对于任意用户$u$的子任务$s$，其计算延时$T_{u,s}^{{\rm{comp}}}$可以通过其计算量和所分配的计算资源${F_{{A_{u,s}}}}\times{P_{u,s}}$表示：

本文用$K$表示子任务间的传输路径集合，${K_{u,s,t}}$则表示用户$u$的子任务$s$到子任务$t$的传输路径，由卸载决策$A$决定，如式（2）所示：

则子任务$s$到子任务$t$的传输时延$T_{u,s,t}^{{\rm{comm}}}$如式（3）所示，其中${d_s}$表示子任务${B_{{K_{u,s,t}}}}\times{Q_{u,s,t}}$的中间数据量/输出结果数据量，${B_{{K_{u,s,t}}}}\times{Q_{u,s,t}}$表示所分配的带宽资源.

结合式（1）和式（3）可以得出工作流任务的子任务$s$的完成时间为：

其中，$s. pre$表示子任务$s$的前驱子任务集合.

因此，工作流任务的完成时间即为最后一个子任务$(s\_last)$的完成时间：

本文的研究问题，即联合优化工作流任务的卸载决策、资源分配决策来最小化所有用户的平均完成时间，该问题$P$可以表示的数学模型为：

目标函数：

约束条件：

其中，$A,P,Q$分别表示卸载位置决策、算力比例决策和带宽比例决策. $I( · )$表示指示函数，当括号里等式成立时值为1，反之则为0. 约束式（7）和式（8）分别保证分配给用户的算力资源和带宽资源大于0，是连续性变量；约束式（9）（10）保证分配的资源比例之和小于或等于1；约束式（11）表示卸载位置变量的取值范围，是离散型变量. 在有M个算力节点、N个用户，每个用户的工作流应用含有S个子任务的场景下，卸载决策的空间为${M^{NS}}$，因此，该问题是一个混合整数非线性规划问题，同时也是一个NP难问题.

3.   工作流卸载算法

本文研究了2种典型的工作流结构：链式工作流任务和DAG式工作流任务. 针对链式工作流任务，本文提出了一种基于势博弈的分布式工作流卸载算法DWO来最小化工作流任务的完成时间；针对DAG式的工作流任务，本文提出了一种基于动态资源权重的启发式工作流卸载算法Heu-WO来减小工作流任务的完成时间.

3.1   链式工作流卸载算法

通过对链式工作流结构进行分析，可以将原问题$P$分解成2个子问题：子问题$P1$根据卸载策略和路径选择策略决定最优的资源分配方案；子问题$P2$根据最优分配策略决定卸载位置和传输路径，该问题基于势博弈进行求解.

3.1.1   最优资源分配策略

子问题$P1$目标是在给定卸载策略和路径选择策略的前提下，决定最优的资源分配策略使得工作流任务完成时间最小.

目标函数：

约束条件：

在$P1$中，式（12）表示的目标函数是凸函数，式（13）和式（14）表示的定义域为凸集，式（15）和式（16）表示的也是凸函数，因此$P1$是一个凸优化问题，且最优解满足KKT（Karush-Kuhn-Tucker）条件. 首先给出$P1$的拉格朗日函数：

其中，$\alpha$和$\beta$分别表示2个约束项的参数. 从而获得拉格朗日对偶问题和KKT条件，通过求解KKT条件，得到最优的资源分配策略，资源分配的表达式为

其中，${D_{u,s}}(A)$表示卸载决策$A$中与用户$u$的子任务卸载到同一节点的用户和子任务集合，${R_{u,s,t}}(A)$表示卸载决策$A$中与用户$u$的子任务$s$到子任务$t$占有相同链路的用户和子任务集合. 根据最优资源分配策略，将式（17）中的$P_{u,s}^*(A)$和式（18）中的$Q_{u,s,t}^*(A)$代入到式（12）中，可以获得在卸载策略$A$下的各个用户的工作流任务完成时间${\bar C_u}$.

因此，原问题$P$可以表示为$P2$问题：

目标函数：

约束条件：

子问题$P2$的2种变量均为离散型，本文考虑工作流子任务的个数为$S$，故可行的解空间大小为${\left| M \right|^{\left| U \right|S}}$. 解空间是指数级的. 本文采用基于势博弈的方法来解决子问题$P2$.

3.1.2   多用户卸载博弈（multi-user offloading game，MOG）

基于3.1.1节的分析，本文设计了一种基于势博弈的方法来解决工作流卸载问题. 首先将子问题$P2$建模为一个多用户卸载博弈$G = \{ U,{A_u},{V_u}\}$，其中$U$表示用户集合，${A_u}$表示用户$u$的卸载决策，${V_u}$表示用户$u$的效用函数.

定理1. 在最优资源分配条件下，用户间的相互作用可以被建模为一个资源依赖加权的拥塞博弈，每个用户的代价函数为

证明. 用$x$表示用户$u$的子任务$s$的卸载位置${A_{u,s}}$，$y$表示用户$u$的子任务$s$到子任务$t$的传输路径${K_{u,s,t}}$. 首先定义$w_{u,s}^x({A_u}) = \sqrt {\dfrac{{{c_{u,s}}}}{{{F_x}}}}$表示用户$u$的子任务$s$在算力节点$x$上处理，$w_{u,s}^y({A_u}) = \sqrt {\dfrac{{{d_{u,s}}}}{{{B_y}}}}$表示用户$u$的子任务$s$到子任务$t$的中间数据在路径$y$上传输. 那么${w_x}(A) = \displaystyle\sum_{(v,s) \in D(x)} {\sqrt {\dfrac{{{c_{v,s}}}}{{{F_x}}}} }$，${w_y}(A) = \displaystyle\sum_{(v,s,t) \in R(y)} {\sqrt {\dfrac{{{d_{v,s}}}}{{{B_y}}}} }$. 其中$D(x)$表示卸载到算力节点$x$上的子任务集合，$R(y)$表示占用链路$y$的子任务传输集合. 因此，用户间的相互作用可以被建模为一个资源依赖加权的拥塞博弈. 证毕.

本文将用户的效用函数${V_u}$定义为该用户工作流的完成时间，即

其中，${A_{ - u}}$表示不包含用户$u$的决策集，${\bar C_u}({A_u},{A_{ - u}})$表示用户$u$的工作流任务完成时间.

定义1. 纳什均衡^[21]. MOG的策略${A^*}$是纳什均衡解当且仅当任意用户无法通过改变自身策略降低自己的效用值${V_u}$.

接下来，本文分析了MOG的纳什均衡的存在性，关键在于证明MOG是一个严格势博弈^[7].

定义2. （严格势博弈^[21]） 博弈$G = \{ U,{A_u},{V_u}\}$是严格博弈需满足式（24）：

其中$\varPhi ({A_u},{A_{ - u}})$表示为势函数.

为了证明MOG是一个严格势博弈，本文将势函数定义为

其中，${\varPhi _u}({A_u},{A_{ - u}}) = \displaystyle\sum_{h \in H} {w_u^h({A_j})\displaystyle\sum_{j \leqslant u} {w_j^h({A_j})} }$，$H = \{ A \cup K\}$表示资源的集合.

定理2. MOG是严格势博弈.

证明. 假设某一时刻用户$g$将决策$\left( {{A_g},{A_{ - g}}} \right)$改变为$\left( {A_g',{A_{ - g}}} \right)$，此时该用户的效用差值为

下面分3种情况讨论：

1）对于用户$i < g$：${\varPhi _i}(A) - {\varPhi _i}(A') = 0$.

2）对于用户$i > g$：${\varPhi _i}(A) - {\varPhi _i}(A') = \displaystyle\sum_{h \in H} (w_i^h(A)w_g^h(A) - w_i^h(A)w_g^h(A'))$.

3）对于用户$i = g$：${\varPhi _i}(A) - {\varPhi _i}(A') = \displaystyle\sum_{h \in H} (w_g^h(A) \displaystyle\sum_{j \leqslant g} w_j^h(A) - w_g^h(A')\displaystyle\sum_{j \leqslant g} {w_j^h(A')} )$.

综上，

证毕.

3.1.3   基于势博弈的分布式工作流卸载算法

针对链式工作流应用，本文提出了基于势博弈的分布式工作流卸载算法，该算法的设计依据是基于博弈论的有限改进性质（在有限迭代轮次下可以获得一个纳什均衡解^[26]）. 伪代码如算法1所示.

算法1. DWO算法

①每个用户$u$随意选择一个可行策略，记为${A_u}$；

② repeat

③按序选择一个用户$u$；

④ ${A'_u} = \left\{ {\begin{array}{*{20}{c}} {{{\hat A}_u},{V_u}({A_u},{A_{ - u}}) > {V_u}({{\hat A}_u},{A_{ - u}})} ,\\ {{A_u},{V_u}({A_u},{A_{ - u}}) \leqslant {V_u}({{\hat A}_u},{A_{ - u}})}; \end{array}} \right.$

/ *${\hat A_u}$表示从可行解中选择的一个解，${A'_u}$表示用　　　　户$u$新的策略. */

⑤更新策略集为$A = ({A'_u},{A_{ - u}})$；

⑥ until所有用户都不再更新策略.

算法DWO根据MOG的有限改进性质，且一次只允许一个用户对它的策略进行改善. 首先，每个用户随机地选择一个可行策略；然后，在每一轮迭代过程中按序选择一个用户对它的策略进行改善，并更新到总的策略集上，直到所有的用户都不再更新策略，即算法达到纳什均衡.

3.1.4   时间复杂度分析

假设算力节点的数量为$M$，用户数量为$U$，工作流任务拓扑中的节点数为$S$，根据式（17）和式（18）可知资源分配策略的时间复杂度为$O(US)$. 在每一轮迭代过程中，用户进行决策的时间复杂度为$O({M^S}US)$. 假设算法DWO经过$C$轮达到收敛，因此算法DWO的时间复杂度为$O(C{M^S}US)$. 当子任务数量较少时可以有效进行求解；而针对子任务数量较多的场景，一种可行的优化思路是先筛选若干个子任务切分点，将子任务数量降低，从而降低时间复杂度.

3.1.5   PoA分析

本文探讨算法DWO的纳什均衡解的有效性. 算法DWO可能有多个纳什均衡解，根据博弈论中的PoA的定义，本文将最差的纳什均衡解和最优解的比值定义为算法DWO的PoA值.

其中：$\cal A$表示算法DWO的纳什均衡解集，${A^*}$表示最优策略. 显然可以得到PoA值的下界：

本文将介绍PoA值的一个上界.

定理3. DWO的PoA值的上界为：$PoA \leqslant \dfrac{{3 + \sqrt 5 }}{2}$.

证明. 根据式（21），将总的效用表述为

根据纳什均衡的定义，可得：

将所有用户合成一个不等式，可得：

重新排序并重写式（31），可得：

其中，${O_h}(A)$表示卸载决策$A$占用资源$h$的用户与子任务集合. 因为总的权重$\displaystyle\sum_{i \in {O_h}(A)} {w_i^h({A_i}){w_h}} (A) - w_h^2(A)$与资源$h$相关，根据$\displaystyle\sum_{i \in {O_h}(A)} {w_i^h{{({A_i})}^2}} \leqslant w_h^2(A)$，由式（32）推出：

通过柯西-施瓦茨不等式，可得：

对于式（34），两边同除$\displaystyle\sum_{h \in H} {w_h^2({A^*})}$，可得：

因为式（35）包含了DWO的所有纳什均衡解，同样包含了最差的纳什均衡解，因此：

通过求解式（36），即证：$PoA \leqslant \dfrac{{3 + \sqrt 5 }}{2}$.

3.2   DAG式工作流卸载算法

针对DAG式工作流，本文同样将资源分配和任务卸载分开. 由于目标函数中含有不可微函数$\max ( · )$，本文基于松弛的资源分配策略进行资源分配；由于算法DWO在子任务数量大的场景下其时间复杂度较高，难以在可接受的计算时间内获得一个可行解. 因此，本文设计了一种基于动态资源权重的启发式工作流卸载算法Heu-WO.

3.2.1   松弛的资源分配策略

针对DAG式的工作流应用进行分析，由于DAG式工作流的完成时间中含有函数$\mathrm{m}\mathrm{a}\mathrm{x}(·)$，故其目标函数不能像链式的工作流转化成式（12）. 而函数$\mathrm{m}\mathrm{a}\mathrm{x}(·)$也是凸函数^[22]，所以该问题的目标函数式（6）仍然是凸函数；且定义域和约束函数与$P1$问题中的一致，故原问题的定义域为凸集，约束函数也是凸函数，所以该问题也是凸优化问题. 但是因为函数 $\max ( · )$不可微，求解比较困难. 所以本文将函数 $\max ( · )$松弛为求和函数$\sum {( · )}$，即，将目标函数从式（6）松弛成式（12），这样便可以通过3.1.1节中的式（17）和式（18）求解得到该问题的资源分配方案.

3.2.2   基于动态资源权重的启发式工作流卸载算法

针对DAG式工作流应用，本文提出了一种基于动态资源权重的启发式工作流卸载算法Heu-WO，它将每个资源的占有情况记作资源权重，对每个子任务基于资源权重选择完成时间最少的节点进行卸载，并动态更新资源权重. 伪代码如算法2所示.

算法2. 基于动态资源权重的启发式工作流卸载算法Heu-WO

①初始化每个算力节点$m$的算力资源占用量$c{o_m}$

②初始化每条链路$(m,n)$的带宽资源占用量$d{o_{m,n}}$

③ for 每个用户$u$

④　 for 每个子任务$s$

⑤　　 $l = \mathop {\arg \min }\limits_m \left(\left(\mathop {\max }\limits_{i \in s. pre} \dfrac{{{d_s}d{o_{{A_{u,i}},m}}}}{{{B_{{A_{u,i}},m}}}}\right) + \dfrac{{{c_s}c{o_m}}}{{{F_m}}}\right)$；

/* $s. pre$；表示子任务$s$的前驱子任务集合，　　　　　寻找子任务$s$完成时间最短的卸载位置*/

⑥　　 ${A_{u,s}} = l$；

/*记录用户$u$子任务$s$的卸载位置*/

/*${A_{u,s}}$，记录子任务$s$的卸载位置为$l$，更新　　　　　　所占用资源的占用量*/

⑦ 　　$c{o_l} + = \sqrt {{c_s}}$；

/*更新算力资源的占用情况*/

⑧　　 $d{o_{{A_{u,i}},l}} + = \sqrt {{d_s}} ,\forall i \in s. pre$；

/*更新带宽资源的占用情况*/

⑨　 end for

⑩ end for

⑪ ${P_{u,s}} = \dfrac{{\sqrt {{c_{u,s}}} }}{{c{o_{{A_{u,s}}}}}}$, ${Q_{u,s,t}} = \dfrac{{\sqrt {{d_{u,s}}} }}{{d{o_{{K_{u,s,t}}}}}}$；

/*进行资源分配*/

⑫ return$A,P,Q$.

/*输出卸载与资源分配方案*/

根据公平性原则，每个用户对其子任务$s$选择最佳的卸载方案，如算法2行⑤表示选择最小化子任务$s$的完成时间的卸载位置，行⑥~⑧更新策略和环境中的占用情况，以供其他用户做出决策.

3.2.3   时间复杂度分析

假设算力节点的数量为$M$，用户数量为$U$，工作流任务拓扑中的节点数为$S$. 由算法2，外部（行③，④）是双层循环，故时间复杂度为$O(US)$；内部（行⑤）是对所有算力节点的一次遍历，故时间复杂度为$O(M)$. 综上，本文所提算法Heu-WO的时间复杂度为$O(USM)$.

4.   实验结果与分析

本文进行了算力网络环境下工作流任务的执行优化实验，首先对实验环境与参数进行说明，然后展示仿真结果并对其进行分析.

4.1   实验环境与参数设置

本文使用拥有i7-12700K CPU，32GB RAM的服务器作为算力网络环境工作流任务执行优化的硬件平台，软件平台采用Ubuntu 20.04 x86_64操作系统，Visual Studio Code 1.73.1版本以及Python3. 8版本的编程环境，并采用了DAG生成器^[27]生成DAG拓扑数据，以此代表具有依赖关系的工作流任务. 通过控制参数n和参数density来随机生成不同的工作流任务，其中参数n控制DAG的节点个数，即子任务数量；参数density表示DAG密度，是边数与节点数的比值，用于控制DAG中节点间的边数，即子任务间的依赖关系，density值越大，DAG中的边数越多，子任务之间的数据交互就越多. 为了便于理解，图3展示了DAG生成器在不同参数下所生成的DAG结构. 同时，本文的网络拓扑也采用了DAG生成器用于生成复杂的网络环境.

图  3  DAG生成器

Figure  3.  DAG generator

下载: 全尺寸图片 幻灯片

本文实验环境参数如表2所示.

表  2  实验环境参数

Table  2.  Experimental environment Parameters

环境参数	设置值
算力节点个数	[10, 50]
用户数	[100, 500]
算力节点计算资源/ TFLOPS	[1.0, 3.0]
算力节点间带宽/ Mbps	[40, 80]
DAG节点数量	[1, 100]
DAG密度	[1, 1.5]
子任务计算量/ GFLOPs	[0.2, 1.2]
子任务传输数据量/ KB	[100, 800]

下载: 导出CSV 

| 显示表格

4.2   对比算法

为了验证本文所提算法DWO和算法Heu-WO的有效性，将DWO和Heu-WO与其他4种算法进行对比实验. 具体描述为：

1）低延迟自适应工作负载分配（low-latency adaptive workload allocation，LAWA）^[8]. 该算法在已知一条最优传输路径的前提下，通过联合优化计算寻路和工作负载分配来降低工作流应用的完成时间. 但是LAWA没有考虑如何寻找到最优路径. 因此，本文先通过最短路径算法获得传输路径.

2）最佳卸载（Optimal）. 该算法通过暴力求解方法遍历卸载空间以获取最优解. 但该方法的复杂度太高，难以在大规模场景下进行求解.

3）最近卸载（Nearest）. 该算法先根据任务的原数据量和结果数据量决策卸载到靠近发送方的算力节点或靠近接受方的算力节点上进行处理，用户独立选择最短传输路径，然后基于凸优化方法求得的最优的资源分配方案.

4）随机卸载（Random）. 该算法指的是用户将每个子任务随机卸载到算力节点上，子任务传输独立选择最短路径，然后基于凸优化方法求得最优的资源分配方案.

4.3   DWO算法性能分析

验证算法的性能以及收敛性. 本节在小规模链式工作流场景下进行了500次独立实验，然后将结果按照Optimal的值进行规格化处理，最后取平均值.

如图4所示，DWO算法可以很快达到收敛，与Optimal相比，DWO解的近似比高达94.6%，与其他算法相比，加速比最高达3.2x，Heu-WO次之，然后依次是LAWA，Nearest，Random. LAWA考虑了在最优传输路径上进行卸载，有效利用了传输路径上的计算资源，但是没有联合计算路径和传输路径，其最优传输路径上的算力节点相比较其他算力节点未必是最优的. Nearest是一种0/1卸载，传输成本低，但是无法利用其他节点上的资源，导致计算时延大. Random随机地选择卸载位置会导致传输开销大，在网络带宽小的情况下尤为突出.

图  4  算法性能

Figure  4.  The performance of algorithms

下载: 全尺寸图片 幻灯片

4.4   Heu-WO算法性能分析

4.4.1   算法效率分析

为了验证Heu-WO算法的效率，本节通过改变节点数量、用户数量和子任务数量进行了3组实验.

图5展示了算法完成时间与算力节点数量之间的关系，用户数量越多，算法的完成时间也就越长；随着算力节点的增加，算法的完成时间呈现出线性增长的趋势. 本文通过最小二乘法对各曲线进行线性拟合，得到的4条近似直线，其斜率由上到下依次是0.044，0.087，0.122，0.169. 可以看出，算法完成时间与相应的节点数之间存在线性关系.

图  5  算力节点数量对算法完成时间的影响

Figure  5.  Impact of the quantity of computing nodes on completion time of algorithm

下载: 全尺寸图片 幻灯片

图6展示了算法完成时间与用户数量之间的关系，算力节点数量越多，算法的完成时间也就越多；随着用户数量的增加，算法的完成时间同样呈现出线性增长的趋势. 同样通过最小二乘法对各曲线进行线性拟合，得到的4条近似直线，其斜率由上到下依次是0.048，0.090，0.128，0.169. 可以看出，完成时间与相应的用户数量之间也存在线性关系.

图  6  用户数量对算法完成时间的影响

Figure  6.  Impact of the quantity of users on completion time of algorithm

下载: 全尺寸图片 幻灯片

图7展示了算法完成时间与子任务数量之间的关系，其中：Cx_Ny表示在用户数为x、算力节点数为y的情况下，随着用户数量与节点数量的增加，算法的完成时间相应地增加；子任务数量越多，算法的完成时间也就越大，同样呈现出线性增长的趋势. 本文通过最小二乘法对各曲线进行线性拟合，得到的4条近似直线，其斜率由上到下依次是0.20，0.40，0.41，0.79. 可以看出，完成时间与用户数量和节点数量的乘积存在正比关系.

图  7  子任务数量对算法完成时间的影响

Figure  7.  Impact of the quantity of sub-tasks on completion time of algorithm

下载: 全尺寸图片 幻灯片

综上，图5，6，7共同体现出该算法的完成时间与算力节点数量、用户数量以及子任务数量均呈现出正比关系，从而验证了3.2.3节中所分析的Heu-WO的时间复杂度为$O(USM)$.

4.4.2   验证算力网络环境资源的影响

本节验证算力网络环境资源对算法性能的影响，通过实验分析平均时延与算力网络环境资源（节点计算能力和带宽资源）的关系.

图8展示了不同算法在不同算力节点计算能力下的平均时延. 随着算力节点计算能力的增加，各个算法的平均时延均有所降低. 这是因为算力节点的计算资源越多，可以分配给用户的计算资源相应地增加了，降低了计算带来的时间开销. 与其他算法相比， Heu-WO算法实现了最低平均时延（加速比最高达2.7x）.

图  8  平均时延与计算能力的关系

Figure  8.  Relationship of average latency and computing capability

下载: 全尺寸图片 幻灯片

图9展示了不同算法在不同网络带宽下的平均时延. 随着网络带宽的增加，各个算法的平均时延也均有所降低. 这是因为网络带宽越大，传输数据则越快，降低了数据传输的时间开销. 与其他算法相比， Heu-WO算法实现了最低平均时延（加速比最高达2. 4x）.

图  9  平均时延与网络带宽的关系

Figure  9.  Relationship of average latency and bandwidth of network

下载: 全尺寸图片 幻灯片

4.4.3   验证节点数量和用户数量的影响

本节验证节点数量和用户数量对算法性能的影响. 通过控制变量，分析平均时延与节点数量和用户数量的关系.

图10展示了不同算法在不同节点数量下的平均时延，随着节点数量的增加，各个算法的平均时延均有所降低. 这是由于资源增加使得用户之间的资源竞争减弱，用户可以分配更多的资源，从而降低了平均时延. 与其他算法相比， Heu-WO保持最优（加速比最高达2.8x）.

图  10  平均时延与节点数量的关系

Figure  10.  Relationship of average latency and quantity of nodes

下载: 全尺寸图片 幻灯片

图11展示了不同算法在不同用户数量下的平均时延，随着用户数量的增加，各个算法的平均时延均有所上升. 这是由于用户数量增加加剧了用户之间的资源竞争，从而增加了平均时延. 与其他算法相比， Heu-WO仍保持最优（加速比最高达1.9x）.

图  11  平均时延与用户数量的关系

Figure  11.  Relationship of average latency and quantity of users

下载: 全尺寸图片 幻灯片

4.4.4   验证子任务数量的影响

图12展示了不同算法在不同子任务数量下的平均时延. 随着子任务数量的成倍增加，各个算法的平均时延也呈现出线性上升的趋势. 这是因为虽然子任务数量增加，而资源没发生变化，子任务分配到的资源相应降低，从而导致平均时延的增加. 与其他算法相比， Heu-WO保持最优（加速比最高达1.7x）.

图  12  平均时延与子任务数量的关系

Figure  12.  Relationship of average latency and quantity of subtasks

下载: 全尺寸图片 幻灯片

5.   结论与展望

本文研究了算力网络环境下工作流任务卸载与资源分配问题. 根据工作流应用的特点，针对链式工作流任务，本文提出了一种基于势博弈的分布式工作流卸载算法DWO，首先已知卸载决策下的资源分配问题是一个凸优化问题，通过凸优化方法得到最优资源分配方案，基于凸优化求解的资源分配方案，将卸载问题建模成一个加权拥塞博弈. 本文证明了该博弈是一种势博弈（至少存在一个纳什均衡解）和PoA值；针对DAG工作流任务，本文提出了一种基于动态资源权重的启发式工作流卸载算法Heu-WO，每个子任务基于资源权重选择完成时间最少的节点进行卸载. 数值仿真实验表明，在子任务数较小场景下，DWO可以有效地取得高近似比的解（94.6%），相比其他算法可以获得最高3.2x的加速比；Heu-WO可以在较低多项式时间内进行求解，与现有算法相比，最高可以获得2.8x的加速比. 从而验证了本文所提算法DWO和Heu-WO的有效性.

未来的工作包括3个方面：

1）本文为了简化问题，在考虑子任务间传输时只考虑了单跳的传输路径（见式（2）），然而子任务间的传输可以是多跳的. 因此，下一步我们将对子任务多跳传输的路径选择问题做进一步研究.

2）DWO具有一定的理论性，但是针对子任务数量大的场景，时间复杂度较高（见3.1.4节），且难以适用于DAG式工作流任务；而Heu-WO虽然时间复杂度低，但是缺乏理论保证. 因此，下一步我们将考虑对DAG式工作流任务的卸载问题进行松弛，采用势博弈方法求解，并进行理论分析.

3）本文研究的工作流任务卸载问题只考虑了算力资源同构的场景. 事实上，在大规模算力网络环境下存在大量的异构算力节点，如中央处理器（central processing unit，CPU）、图形处理器（graphics processing unit，GPU）. 因此，异构算力网络场景下的工作流任务卸载问题将是我们未来要进一步研究的工作.

作者贡献声明：姜玉龙负责算法设计、仿真与论文撰写；东方负责提出论文整体架构与论文修订指导；郭晓琳负责算法指导与文字把关；罗军舟负责总体思路指导.