CN107832150B - 一种计算任务动态分区策略 - Google Patents

Abstract

本发明一种计算任务动态分区策略，属于互联网技术领域，针对移动增强现实，在周边设备协作环境下，根据实际的网络情况及两端设备的资源利用情况动态决定计算分区，将部分任务上传到资源有限的周边设备进行处理，处理结果根据后继任务的所有位置决定是否将数据进行网络传输，最终，所有结果返回移动设备端进行显示，从而有效降低移动应用MAR的时延，本发明将动态决定计算分区的方法形式化为M2CP问题，针对链状数据结构和并行数据结构的任务，分别采用多项式时间CP算法和EFS2算法求解，对一般结构数据，采用多项式时间DPA算法，将任务动态地分隔成链状结构和并行结构，然后分别调用CP算法和EFS2算法完成最终的动态分区。

Description

一种计算任务动态分区策略

技术领域

本发明属于互联网技术领域，特别适用于手机增强应用等新型体系架构环境，具体涉及一种计算任务动态分区策略。

背景技术

移动增强现实(Mobile Augmented Reality,简称MAR)越来越受到人们的关注，成为最近几年智能手机和穿戴应用设备的重要技术之一。然而，移动增强现实应用面临着巨大挑战。一方面，这些应用是时间敏感的。一些虚拟物体是与上下文相关的。较长的建模时间及渲染虚拟物体所需要的时间使得对时间敏感的增加现实应用变得不可用。另一方面，建造虚拟物体经常会用到机器学习等算法。由于这些算法需要从传感器处析取挖掘大量信息，使得应用成为计算密集型程序。由于MAR时间敏感的应用程序，这就造成了时间敏感与计算密集的巨大矛盾。

计算卸载到云端或局部边缘设备是普遍使用的解决方案。主要存在以下三种方式。一、将整个应用下载到云端，仅在手机移动端或可穿戴设备上显示返回的增加现实结果。二、静态分区，是将应用程序静态的分成几个模块，然后由开发者决定哪些模块可以上传到云端进行处理。三、动态分区，是根据当前网络情况针对不同的目标进行动态分区，这些目标可以是最小化时延，最大化带宽，最小化能耗，或者几个目标的组合。

计算卸载到云端或局部边缘设备是普遍使用的解决方案。然而，许多应用直接把整个应用下载到云端，然后只在手机端或可穿戴设备上显示返回的结果。虽然这种方式可以有效的降低智能设备的负载，然而当网络实际情况变得比较糟时，这种粗粒度的方式仍然会使用应用延时变得很大，甚至导致应用不可用。有些研究则采用了静态应用任务分区的方式。不过情况与第一类整个应用迁移的方式类似，并没有根据实际网络情况进行合理的分区，仍然会导致应用时延的变长。

采用计算任务动态分区的方式可以有效解决以上面临的问题。然而，这里面临着巨大的挑战。一是对端服务设备资源仍然是有限的。这意味着不可能把所有的计算分区任务上传到服务设备中进行计算。必须考虑到任务的负载均衡，以求达到最终的时间最短的目标。二是计算分区任务相互关联，即后面的任务必须要在前面的任务完成之后才能开始。这种情况不仅限于链状结构，还应用于并行结构或任意的有向无环图中。

发明内容

为了克服上述现有技术的缺点，本发明的目的在于提供一种计算任务动态分区策略，针对移动增强现实，在周边设备协作环境下，根据实际的网络情况及两端设备的资源利用情况动态地决定计算分区，将部分任务上传到资源有限的周边设备进行处理，处理结果根据后继任务的所在的位置(或者在手机设备端或者在周边服务设备)决定是否将数据进行网络传输。最终，所有结果返回移动设备端进行显示。该策略可以有效降低移动应用MAR的时延。

为了实现上述目的，本发明将所述动态决定计算分区的方法形式化为如下的M2CP问题：

x_Input＝0,x_Display＝0

式中，

分别为任务i的开始处理时间、处理结束时间、所需处理时间以及任务i和任务j间的数据传输时间，所有任务形成有向无环图G＝(V,A)，V为结点集合，A为任务关系弧，τ为每一帧数据的处理时限，i∈V，代表一个计算分区任务，其需求被定义为p_i，弧a＝<i,j>代表一条从任务i到任务j的数据路径，{a|i,j∈V,a∈A}，如果任务i和任务j属于不同的设备端，则两者之间数据通信被定义为c_i,j,<i,j>∈A，

和

分别为任务i的前趋任务集和后继任务集，x_i为任务i的分区决定，x_i仅包含两个值0和1，0表明计算分区在本地执行，1则表明在远端执行，f_L,f_R分别为本地和远端有效的CPU频率，一般情况下，f_L<f_R，即本地CPU处理速率低于远端服务端处理速率；b为带宽，y_i(t)为任务i在时刻t的CPU资源的分配情况，z_i,j(t)为时刻t在任务i和任务j之间带宽的分配情况，x_input和x_Display为两个虚拟节点，分别表示应用数据的输入与显示。由于数据采集的传感器与用于显示的屏幕都在本地端，因此两个任务分区都为1。

针对链状数据结构的任务，采用多项式时间CP算法求解所述M2CP问题。

针对并行数据结构的任务，采用常数近似度

时间的EFS2算法求解所述M2CP问题。

针对一般结构数据，采用多项式时间DPA算法，将任务动态地分隔成链状结构和并行结构，然后分别调用CP算法和EFS2算法完成最终的动态分区。

与现有技术相比，本发明的有益效果是：

(1)动态性。相对于现有分区技术，DPA算法针对真实环境变量动态调整任务的分区，能够自适应当前实际情况，适用于具有适时变化的手机无线网络环境、不断变化的手机及周边设备的负载的MAR架构。

(2)完成时间最小化。相对于现有技术，DPA算法针对完成时间为目标进行优化。该算法通过环境信息动态的进行分区，从而实现了最优的性调度时间。

(3)低时间复杂度。该发明具有多项式时间复杂度O(n²)，无论是链状结构，并行结构，还是一般结构。相对于大多数现有技术，具有高效的特点。

(4)常数近似度。该发明比大多数无任何界的近似算法来说，最坏结果可以控制在一个常数

里，因此更具可靠性。

附图说明

图1是M2CP系统架构示意图。

图2是针对链状数据流程计算任务动态分区的CP算法示意图。

图3是针对并行数据流程计算任务动态分区的EFS2算法示意图。

图4是针对一般有向无环结构动态分隔示意图。

具体实施方式

下面结合附图和实施例详细说明本发明的实施方式。

本发明首先进行建模，称为M2CP，其系统架构如图1所示。然后针对两种特殊分区任务结构——链状结构和并行结构分别提出了CP算法和EFS2算法，最后针对一般无向无环结构的任务提出DPA算法，该算法对任务进行动态划分，形成链状结构和并行结构，并分别调用各自算法完成任务计算。

1.M2CP建模

假设所有任务形成有向无环图G＝(V,A)，其中V定义为结点集合，A定义为任务关系弧。每个结点i∈V。每个i∈V代表一个计算分区任务，其需求被定义为p_i,i∈V。一个弧a＝<i,j>({a|i,j∈V,a∈A})代表一条从任务i到任务j的数据路径。如果任务i和任务j属于不同的设备端，则两者之间数据通信被定义为c_i,j,<i,j>∈A。方便描述任务间的关系，

和

分别用于定义任务i的前趋任务集和后继任务集。此外，针对移动设备输入和显示都必须在本机上执行的特点，引入两虚似节点，这两个节点无任务计算需求，仅可能存在数据传输。

为了方便描述分区，这里定义x_i为任务i的分区决定。x_i仅包含两个值0和1，0表明该计算分区在本地执行，1则表明在远端执行。同时还定义

分别为任务i的开始处理时间、处理结束时间、所需处理时间以及任务i和任务j间的数据传输时间。显然，

f_L,f_R分别为本地和远端有效的CPU频率。一般情况下，假定f_L<f_R，即本地CPU处理速率低于远端服务端处理速率。带宽被定义为b。除了分区相关的定义之外，还需要决定：

(1)y_i(t)，用于定义任务i在时刻t的CPU资源的分配情况；

(2)z_i,j(t)，用于定义时刻t在任务i和任务j之间带宽的分配情况。

对于每一帧数据，定义处理时限为τ。则满足：

在本地端和远端CPU资源的限制分别为：

及

上两式中y_i(t)满足，

进一步地，对任务i的CPU资源需求总量满足，

类似于CPU的限制，带宽限制条件也满足以下限制条件，

最后，任务之间具有相互关联关系，因此，任务开始时间被限制为，

针对上述动态分区建模的限制，本发明的问题可以形式化为一个M2CP问题：

很容易看出，M2CP问题是一个混合整数规划问题，它因此是一个NP-hard问题，即使数据流程图被简化成并行任务时也是NP-hard的。

2.链状数据流程求解算法—CP算法

本发明给出针对链状数据结构的任务的一种计算任务动态分区算法，CP算法，如图2所示。

假设该结构的结点数有n个。该算法基于一个事实，存在两个任务i和任务j，如果这两个任务是允许放置到边缘设备上执行，则在两者之间的任务将全部在远端边缘设备上执行。因此，整个过程仅需扫描两个端点的传输情况，即可确定全部任务的分区情况。进一步地，计算哪种分区时间最短，需要将两端点任务的所有时间全部计算一遍，判断本身将达到O(n)时间复杂度，再加上遍历两个端点需要O(n²)时间复杂度，O(n³)仍然比较高。因此，CP算法采用了增量遍历的方式，可以有将判断变成O(1)，使整体复杂度变为O(n²)时间复杂度。具体步骤如下：

步骤1：设置初始值。假设所有计算分区都执行在本地，得到初始时间InitTime，并设置总时间为completion＝InitTime；

步骤2：遍历起始端点i＝1 to n。

步骤2.1：设置临时时间变量time＝InitTime；

步骤2.2：遍历结束端点j＝i to n

步骤2.2.1：计算任务j的增量值△_j，

其中，

以及，

步骤2.2.2：更新临时时间time＝time+△_j；

步骤2.2.3：判断time是否比当前completion还要小，是的话，则记录当前的端点任务序号i和j，并设置completion为time；

步骤3：返回端点任务序号i和j及最终时间completion。

3.并行数据流程求解算法—EFS2算法

本发明给出针对并行数据结构的任务的一种计算任务动态分区算法，EFS2算法，如图3所示。

与链状结构类似，同样假设并行结构的结点数有n个。该算法的基本原则是按照任务被各机器的执行效率由高到低的顺序，将下一个未分配的任务分配给任务负载轻效率高于下限的设备执行。该算法优势在于其时间复杂度仍为O(n²)，并且当设置效率下限阈值为

时，具有常数近似度

EFS2的算法具体实现步骤如下：

步骤1：计算两个终端对所有任务的效率e_i,L和e_i,R，其中符号“L”和“R”分别表示任务是在本地手机或可穿戴设置还是远端周边设备。其计算方法为，

其中

步骤2：分别按e_i,L和e_i,R倒序排序；

步骤3：初始化所有任务为“未分配”，两终端为“激活”状态，并设置两终端负载w_L和w_R初始值为0，设置阈值；

步骤4：针对所有“未分配”的任务，

步骤4.1：找到当前“未分配”任务i的待分配的终端M(“M”代表“L”或“R”中的一个)，有如下几种情况，

(1)如果仅一端设备是“激活”的，则将它设置为待分配终端；

(2)如果两端都为“激活”状态，且负载最小的终端对该任务效率低于阈值η时，设置该设备为“未激活”状态，并设置另一台设备为待分配终端；

(3)否则，设置该设备为待分配终端；

步骤4.2：设置该任务的分区为待分配终端M，设置任务i为“分配”状态；

步骤4.3：对于更新终端M的负载，

其中，Assigned表明所有已“分配”的任务。

步骤5：令最终时间completion为负载w_L和w_R中最大值；

步骤6：返回分区值及最终时间completion。

4.一般有向无环数据流程求解算法—DPA算法

针对M2CP建模，本发明中涉及的DPA算法用于将任务动态地分隔成链状结构和并行结构，然后分别调用CP算法和EFS2算法完成最终的动态分区。图4为一个动态分隔示意图。

直觉上，任务7-任务9应该作为并行任务一同进行处理，但事实上可能有多种并行处理的情况。图4所示的为一种可能性。例如，任务5和6执行在远端周边设备，任务4则并行执行在本地手机端。假设任务5和任务6先于任务4完成。此时，远端周边设备则动态的决定接下来的可执行任务的类型(链还是并行任务)以及相应任务。在示意中，只能任务8和任务9能并行执行，而任务7由于任务4未完成则无法被调度。DPA算法具体的步骤如下所示：

步骤1：广度优先遍历任务；

步骤1.1：对于所有未确定类型的任务，假设均无任何通信代价的情况下计算当前深度所有任务的估计开始时间

步骤1.2：如果仅有一个任务拥有最小的

即当前仅有一个任务，则该任务为链中的一员，则返回步骤1，继续寻找链表成员；

步骤1.3：如果有多个任务拥有最小的

即当前有多个任务，说明这些任务应为并行任务，则停止遍历；

步骤2：如果链中不为空，则调用CP算法，并需要返回端点任务标记及相应的completion；

步骤3：如果链为空，说明当前任务为并行任务，则调用EFS2算法，并需要返回并行任务分区及相应的completion；

步骤4：如果链和并行任务集合均为空，任务处理完成，进行收尾处理；

步骤4.1：综合两个类型的分区值，并将所有completion的和作为最终完成时间makespan。

步骤5：返回任务计算任务动态分区及makespan。

Claims (7)

1.一种计算任务动态分区策略，针对移动增强现实，在周边设备协作环境下，根据实际的网络情况及两端设备的资源利用情况动态决定计算分区，将部分任务上传到资源有限的周边设备进行处理，处理结果根据后继任务的所在位置决定是否将数据进行网络传输，最终，所有结果返回移动设备端进行显示，从而有效降低移动应用MAR的时延，其特征在于，所述动态决定计算分区的方法形式化为如下的M2CP问题：

x_Input＝0,x_Display＝0

式中，

分别为任务i的开始处理时间、处理结束时间、所需处理时间以及任务i和任务j间的数据传输时间，所有任务形成有向无环图G＝(V,A)，V为结点集合，A为任务关系弧，τ为每一帧数据的处理时限，i∈V，代表一个计算分区任务，其需求被定义为p_i，弧a＝<i,j>代表一条从任务i到任务j的数据路径，{a|i,j∈V,a∈A}，如果任务i和任务j属于不同的设备端，则两者之间数据通信被定义为c_i,j,<i,j>∈A，

和

分别为任务i的前趋任务集和后继任务集，x_i为任务i的分区决定，x_i仅包含两个值0和1，0表明计算分区在本地执行，1则表明在远端执行，f_L,f_R分别为本地和远端有效的CPU频率，b为带宽，y_i(t)为任务i在时刻t的CPU资源的分配情况，z_i,j(t)为时刻t在任务i和任务j之间带宽的分配情况，x_input和x_Display为两个虚拟节点，分别表示应用数据的输入与显示。

2.根据权利要求1所述计算任务动态分区策略，其特征在于，所述后继任务的所在位置指在手机设备端或者在周边服务设备。

3.根据权利要求1所述计算任务动态分区策略，其特征在于，所述f_L<f_R，即本地CPU处理速率低于远端服务端处理速率。

4.根据权利要求1所述计算任务动态分区策略，其特征在于，针对链状数据结构的任务，采用多项式时间CP算法求解所述M2CP问题，算法基本步骤如下：

步骤1：设置初始值，假设所有计算分区都执行在本地，得到初始时间InitTime，并设置总时间为completion＝InitTime；

步骤2：遍历起始端点i∈V；

步骤2.1：设置临时时间变量time＝InitTime；

步骤2.2：遍历结束端点j＝i to|V|，其中|V|表示集合V的个数；

步骤2.2.1：计算任务j的增量值Δ_j，

其中，

以及，

步骤2.2.2：更新临时时间time＝time+Δ_j；

步骤2.2.3：判断time是否比当前completion还要小，是的话，则记录当前的端点任务序号i和j，并设置completion为time；

步骤3：返回端点任务序号i和j及最终时间completion。

5.根据权利要求1所述计算任务动态分区策略，其特征在于，针对并行数据结构的任务，采用常数近似度

时间的EFS2算法求解所述M2CP问题，算法基本步骤如下：

步骤1：计算两个终端对所有任务的效率e_i,L和e_i,R，

其中

步骤2：分别按e_i,L和e_i,R倒序排序；

步骤3：初始化所有任务为“未分配”，两终端为“激活”状态，并设置两终端负载w_L和w_R初始值为0，设置阈值；

步骤4：针对所有“未分配”的任务：

步骤4.1：找到当前“未分配”任务i的待分配的终端M，M代表终端L或终端R中的一个，有如下几种情况，

(1)如果仅一端设备是“激活”的，则将它设置为待分配终端；

(2)如果两端都为“激活”状态，且负载最小的终端对该任务效率低于阈值η时，设置该设备为“未激活”状态，并设置另一台设备为待分配终端；

(3)否则，设置该设备为待分配终端；

步骤4.2：设置该任务的分区为待分配终端M，设置任务i为“分配”状态；

步骤4.3：更新终端M的负载

其中，w_L为M代表终端L时的负载，w_R为M代表终端R时的负载，Assigned表明所有已“分配”的任务；

骤5：令最终时间completion为负载w_L和w_R中最大值；

步骤6：返回分区值及最终时间completion。

6.根据权利要求1所述计算任务动态分区策略，其特征在于，针对一般结构数据，采用多项式时间DPA算法，将任务动态地分隔成链状结构和并行结构，然后分别调用CP算法和EFS2算法完成最终的动态分区。

7.根据权利要求6所述计算任务动态分区策略，其特征在于，所述多项式时间DPA算法的基本步骤如下：

步骤1：广度优先遍历任务；

步骤1.1：对于所有未确定类型的任务，假设均无任何通信代价的情况下计算当前深度所有任务的估计开始时间

步骤1.2：如果仅有一个任务拥有最小的

即当前仅有一个任务，则该任务为链中的一员，则返回步骤1，继续寻找链表成员；

步骤1.3：如果有多个任务拥有最小的

即当前有多个任务，说明这些任务应为并行任务，则停止遍历；

步骤2：如果链中不为空，则调用CP算法，并需要返回端点任务标记及相应的completion；

步骤3：如果链为空，说明当前任务为并行任务，则调用EFS2算法，并需要返回并行任务分区及相应的completion；

步骤4：如果链和并行任务集合均为空，任务处理完成，进行收尾处理；

步骤4.1：综合两个类型的分区值，并将所有completion的和作为最终完成时间makespan。

步骤5：返回任务计算任务动态分区及makespan。

Images