CN116991555A - 一种面向异构设备协作网络的群智计算在线任务调度方法 - Google Patents

Abstract

本发明公开了一种面向异构设备协作网络的群智计算在线任务调度方法，首先构建异构设备协作的群智计算网络；然后构建异构设备资源与用户任务的关系模型、用户任务的特征模型以及建立群智计算网络调度的目标函数；接下来通过离散化时间放缩目标函数得到队列状态决策控制模型，并通过队列状态决策控制模型计算出等待队列的流量状态、进入调度周期的时刻和持续时间以及需要调度的重流量任务类型；最终创建调度周期内关于资源和重流量任务新的二分图，并使用改进后的匈牙利算法对处于调度周期内的重流量任务进行计算，得到此阶段内群智计算网络的调度策略。本发明使每次分配任务时达到最高任务匹配数量，减少网络系统的高频任务负荷。

Description

一种面向异构设备协作网络的群智计算在线任务调度方法

技术领域

本发明属于任务规划技术领域，具体涉及一种群智计算在线任务调度。

背景技术

群智计算是人机物三者融合互联的新型协同计算范式。人类群体、信息空间及万物实体正在实现广泛和深度的互联，人类进入人机物三元融合的万物智能互联时代。群智计算在利用人机物异质智能体资源的互补性、能力的差异性、彼此间的协作性和竞争性，来能够支持计算密集型和延迟敏感型的应用任务，例如增强现实、图像处理和短视频缓存等近年来5G/6G网络下新兴的人工智能应用任务以及常见的集群任务。

资源分配和任务调度优化策略是对群智计算网络系统提高资源利用率和减少任务服务延迟的重要技术之一。在群智计算网络资源中，由于异构设备之间存在系统结构差异、计算能力多样以及资源有限等问题，从原来移动边缘计算中云边端构成的简单网络，逐渐演变成由多异构设备构成的随机性强、资源泛在有限以及不稳定节点连接性的异构设备协作复杂网络。因此，研究异构设备间高效协作的隐含关联和数学映射模型，发掘异构设备之间高效协同理论，来提出针对异构设备协作网络的资源分配和任务调度高效优化策略。

现有的工作无法满足群智计算的非确定性、可演化性和可保障性，特别是在对群智计算网络进行资源调度和任务分配时，往往其优化目标忽略了群智计算网络本身的异构资源利用情况以及系统容量损失。另外随着出现越来越多的集群任务或者人工智能大规模应用任务，对不同异构设备协作处理的需求在增加，因此需要针对异构设备协作网络提出高效调度策略算法来满足现实应用场景。

发明内容

为了克服现有技术的不足，本发明提供了一种面向异构设备协作网络的群智计算在线任务调度方法，首先构建异构设备协作的群智计算网络；然后构建异构设备资源与用户任务的关系模型、用户任务的特征模型以及建立群智计算网络调度的目标函数；接下来通过离散化时间放缩目标函数得到队列状态决策控制模型，并通过队列状态决策控制模型计算出等待队列的流量状态、进入调度周期的时刻和持续时间以及需要调度的重流量任务类型；最终创建调度周期内关于资源和重流量任务新的二分图，并使用改进后的匈牙利算法对处于调度周期内的重流量任务进行计算，得到此阶段内群智计算网络的调度策略。本发明使每次分配任务时达到最高任务匹配数量，减少网络系统的高频任务负荷。

本发明解决其技术问题所采用的技术方案包括如下步骤：

步骤1：构建异构设备协作的群智计算网络；

步骤2：构建异构设备资源与用户任务的关系模型、用户任务的特征模型以及建立群智计算网络调度的目标函数；

步骤3：通过离散化时间放缩目标函数得到队列状态决策控制模型，并通过队列状态决策控制模型计算出等待队列的流量状态、进入调度周期的时刻和持续时间以及需要调度的重流量任务类型；

步骤4：创建调度周期内关于资源和重流量任务新的二分图并使用改进后的匈牙利算法对处于调度周期内的重流量任务进行计算，得到此阶段内群智计算网络的调度策略。

进一步地，所述步骤1具体为：

所述群智计算网络包括发布任务的用户、多个异构设备资源和一个任务等待队列；用户随时间发布在线任务，如果任务所需的资源被占用，则进入等待队列等待被服务；如果所需资源空闲，则所需资源共同协作处理该任务；在任务进入系统或者资源服务完成的时刻，即系统状态改变时刻，计算系统的流量状态来调度任务。

进一步地，所述步骤2具体为：

步骤2-1：在群智计算网络中，用户随时间在线发布任务到达等待队列；用 表示任务类型的集合，用/>表示设备资源的集合；其中任务-资源关系矩阵用一个I×J维的A表示；如果资源i协作参与类型j任务的服务过程，则A_ij＝1，否则A_ij＝0；对所有任务j有/>对所有任务i有其中/>表示类型j任务服务过程中所需的资源集，/>表示由资源i协作处理的任务类型集；

步骤2-2：让v_jn表示类型j任务的服务时间，且是一个独立同分布的随机变量序列，其均值为/>变异系数为σ_j；对于每种类型j任务的服务时间，有：

V_j(0)＝0

其中V_j(n)是连续被服务n个类型j任务的时间和；S_j(t)表示为在[0,t]时间内始终处理类型j任务，直到时刻t为止处理的类型j任务数量；

步骤2-3：用表示j任务的到达间隔序列，其均值为1/λ_j；对于每种类型j任务的到达时间，有：

U_j(0)＝0

其中U_j(n)是第n个类型j任务到达系统的时刻；E_j(t)表示为直到t时刻，经用户发布任务后到达系统的类型j任务数量；

λ_j是类型j任务到达间隔符合的分布参数，是类型j任务服务时间符合的分布参数；ρ_i表示为资源i上的负载，其计算公式为/>则对于资源i的流量状态定义为：

如果θ_i＝-∞，则资源i处于轻流量状态；如果则资源i处于重流量状态。

对于资源的流量状态表示，表示轻流量状态的资源，/>表示重流量状态的资源：

对于任务的分类，包括三种任务类型集合：仅由重流量状态资源处理的任务类型集合仅由轻流量状态资源处理的任务类型集合/>由轻流量和重流量两种状态处理的任务类型集合/>

对于全部的类型j任务，用Q_j(t)表示在时刻t时系统中类型j任务的数量，包括正在被服务的任务:

Q_j(t)＝Q_j(0)+E_j(t)-S_j(T_j(t))

其中Q_j(t)是系统中任务的初始数量状态，Q_j(0)＝0，T_j(t)表示在[0,t]期间处理类型j任务的累积时间；

步骤2-4：群智计算网络的目标函数为最小化系统中等待任务的数量，即最小化系统容量损失：

进一步地，所述步骤3具体为：

步骤3-1：通过增加与资源相关联的任务负载约束，将连续时间下的目标函数离散为每一时刻的队列状态决策控制模型，其与资源i相关联的任务负载定义为：

步骤3-2：利用队列模型中流体和扩散缩放过程，即通过增加任务负载约束将连续时间离散化间隔的时间点，建立的队列状态决策控制模型为：

步骤3-3：对于每一个时刻t，群智计算系统的队列流量状态是一个确定的值，即决策控制模型在数学模型上是一个线性规划模型：

利用二次规划模型找到上面线性规划模型具有最小欧几里得范数的最优解，并且因为该二次规划模型是凸的，所以在多项式时间内是可解的：

其中z(w)表示线性规划模型的最优目标函数值；

步骤3-4：通过在时刻t求解出的队列状态决策控制模型，得到此时队列状态接近最优解的所有任务类型数量对于重流量任务和轻流量任务的定义有：

则相应的处理重流量任务资源和处理轻流量任务的资源，两者分别定义为：

如果则此时t时刻进入调度周期，调度周期的持续时间是实现资源之间最优工作负载分配所需的预期时间，计算公式为：

在[t,t+L(t)]时间内对内的重流量任务数量从Q_j(t)降低至/>值以下，在调度周期结束后，重新根据此时系统流量状态计算队列状态决策控制模型，并重复步骤3-2到步骤3-4；

进一步地，所述步骤4具体为：

步骤4-1：将每次进入调度周期的t时刻计算出内的重流量任务类型，所有资源和重流量任务-资源的关系矩阵作为新的二分图/>进行匹配；

步骤4-2：对于二分图先匹配第一个节点，将第一个节点所需资源标记为该任务节点的占用，最大匹配任务数量加1；

步骤4-3：对于下一个节点，如果所需资源空闲，重复步骤4-2，即将该节点标记为该任务节点的占用，最大匹配任务数量加1；如果存在所需资源被占用的情况，查询被占资源的任务节点，然后解除该任务节点所占用的所有资源；如果解除的所有资源能让匹配的任务数量大于1，那么将这些资源匹配，标记这些资源为相应任务的占用，记录这步操作后的任务匹配数量X，然后最大任务匹配数量加X减1；如果解除的所有资源让匹配的任务数量小于等于1，那么回溯到接触占用资源节点的情况前，目前匹配的任务节点所需的资源被占用无法匹配，跳过该节点；

步骤4-4：重复步骤4-3，直至没有属于重流量任务节点可以被匹配，最后将匹配到的类型任务进入所需资源设备；

步骤4-5：对于轻流量任务，寻找剩余的空闲设备资源，分配给相应的轻流量任务去服务。

本发明的有益效果如下：

(1)本发明针对异构设备协作处理任务的网络架构提出优化策略，符合现实中异构设备和集群任务的真实场景。

(2)本发明提出了一种基于离散化时间放缩的队列状态决策控制模型，用来计算得出此时等待队列的流量状态、进入调度周期的时间以及需要调度的重流量任务类型。

(3)本发明改进了匈牙利算法来对调度周期内的重流量任务进行资源分配，使每次分配任务时达到最高任务匹配数量，减少网络系统的高频任务负荷。

附图说明

图1为本发明场景图。

图2为本发明解决方案图。

具体实施方式

下面结合附图和实施例对本发明进一步说明。

本发明针对现有技术问题，提出了一种异构设备协作网络中基于离散化时间放缩的群智计算在线任务调度方案，用于群智计算场景下计算集群的多服务器任务如深度神经网络的分布式训练或者大规模图像处理任务，即多服务器任务同时请求多个计算设备的场景，如CPU、GPU和FGPA等计算资源。

本发明的目的可以通过采取如下技术方案达到：

一种基于离散化时间放缩的群智计算在线调度方法，包括以下步骤：

步骤一：构建异构设备协作的群智计算网络；

步骤二：构建异构设备资源与用户任务的关系模型、用户任务的特征模型以及建立群智计算网络调度的目标函数；

步骤三：通过离散化时间来放缩目标函数得到易于计算的队列状态决策控制模型，并通过队列状态决策控制模型计算出此时等待队列的流量状态、进入调度周期的时刻和持续时间以及需要调度的重流量任务类型；

步骤四：创建了调度周期内关于资源和重流量任务新的二分图并使用改进后的匈牙利算法对处于调度周期内的重流量任务进行计算，得到此阶段内群智计算网络的调度策略。

具体实施例：

所述步骤一具体为：构建异构设备协作的群智计算网络，网络包含发布任务的用户、多个异构设备资源和一个任务等待队列。用户随时间发布在线任务，如果任务所需的资源被占用，则进入等待队列等待被服务；如果所需资源空闲，则所需资源共同协作处理该任务。在任务进入系统或者资源服务完成的时刻，即系统状态改变时刻，计算系统的流量状态来调度任务。

所述步骤二，在群智计算网络中，用户随时间在线发布任务到达等待队列，用 表示任务类型的集合，用/>表示设备资源类型的集合。其中任务-资源关系矩阵用一个I×J维的A来表示，如果资源i协作参与类型j任务的服务过程，则A_ij＝1，否则A_ij＝0。对所有任务j有/>对所有任务i有其中/>表示类型j任务服务过程中所需的资源集，/>表示由资源i协作处理的任务类型集。

让v_jn表示j类型任务的服务时间，且是一个严格独立同分布的随机变量序列，其均值为/>变异系数为σ_j。对于每种类型j任务的服务时间，有

V_j(0)＝0

其中V_j(n)是连续被服务n个类型j任务的时间和。S_j(t)表示为在[0,t]时间内始终处理类型j任务，直到时刻t为止处理的类型j任务数量。

类似的，用表示j任务的到达间隔序列，其均值为1/λ_j。对于每种类型j任务的到达时间，有

U_j(0)＝0

其中U_j(n)是第n个j类型任务到达系统的时刻。E_j(t)表示为直到t时刻，经用户发布任务后到达系统的类型j任务数量。

λ_j是任务j到达间隔符合的分布参数，是任务j服务时间符合的分布参数。ρ_i表示为资源i上的负载，其计算公式为/>则对于资源i的流量状态定义为

如果θ_i＝-∞，则资源i处于轻流量状态；如果则资源i处于重流量状态。

对于资源的流量状态表示，表示轻流量状态的资源，/>表示重流量状态的资源

对于任务的分类：是由重流量状态资源处理的任务类型集合，是仅由轻流量状态资源处理的任务类型集合，而是由轻流量和重流量两种状态处理的任务类型集合。

对于全部的任务j，用Q_j(t)表示在时刻t时系统中j类任务的数量，包括正在被服务的任务

Q_j(t)＝Q_j(0)+E_j(t)-S_j(T_j(t))

其中Q_j(t)是系统中任务的初始数量状态，一般Q_j(0)＝0，T_j(t)表示在[0,t]期间处理类型j任务的累积时间。

群智计算网络的目标函数为最小化系统中等待任务的数量，即最小化系统容量损失

所述步骤三，通过增加与资源相关联的任务负载约束，将连续时间下的目标函数离散为每一时刻的队列状态决策控制模型。其与资源i相关联的任务负载定义为

在系统中不再有任务到达并且协作所需的所有其他资源可用的情况下，W(t)是资源i为了处理所有相关任务而应该花费的预期时间。

利用队列模型中流体和扩散缩放过程，即通过增加任务负载约束将连续时间离散化间隔的时间点，建立的队列状态决策控制模型为

对于每一个时刻t，群智计算系统的队列流量状态是一个确定的值，即决策控制模型在数学模型上是一个线性规划模型

为了求解上述线性规划模型，利用二次规划模型来找到它具有最小欧几里得范数的最优解，并且因为该二次规划模型是凸的，所以在多项式时间内是可解的

其中z(w)表示线性规划模型的最优目标函数值。

通过在时刻t求解出的队列状态决策控制模型，得到此时队列状态接近最优解的所有任务类型数量对于重流量任务和轻流量任务的定义有

则相应的处理重流量任务资源和处理轻流量任务的资源，两者分别定义为

如果则此时t时刻进入调度周期，调度周期的持续时间是实现资源之间最优工作负载分配所需的预期时间，计算公式为

在[t,t+L(t)]时间内对内的重流量任务数量从Q_j(t)降至到接近/>的水平，在调度周期结束后，重新根据此时系统流量状态计算队列状态决策控制模型，并重复相同的过程。

所述步骤四，在每个调度周期内，由于异构设备协作处理任务，会出现某个任务所需资源被其他类型占用的情况，因此为达到最大的任务匹配数量，改进了匈牙利算法。

将每次进入调度周期的t时刻计算出内的重流量任务类型，所有资源和重流量任务-资源的关系矩阵作为新的二分图/>进行匹配。

对于二分图先匹配第一个节点，它相关联的资源节点必定是空闲的，于是将第一个节点所需资源标记为该任务节点的占用，最大匹配任务数量加1。

对于下一个节点，如果所需资源空闲，重复上述操作；如果存在所需资源被占用的情况，查询被占资源的任务节点，然后解除该任务节点所占用的所有资源。如果解除的所有资源可以让匹配的任务数量大于1，那么将这些资源匹配，标记这些资源为相应任务的占用，记录这步操作后的任务匹配数量X，然后最大任务匹配数量加X减1；如果解除的所有资源让匹配的任务数量小于等于1，那么回溯到接触占用资源节点的情况前，目前匹配的任务节点所需的资源被占用无法匹配，跳过该节点。

重复上述节点操作，直至没有属于重流量任务节点可以被匹配，最后将匹配到的类型任务进入所需资源设备；

对于轻流量任务，在上面步骤结束后，寻找剩余的空闲设备资源，分配给相应的轻流量任务去服务。

Claims (5)

1.一种面向异构设备协作网络的群智计算在线任务调度方法，其特征在于，包括如下步骤：

步骤1：构建异构设备协作的群智计算网络；

步骤2：构建异构设备资源与用户任务的关系模型、用户任务的特征模型以及建立群智计算网络调度的目标函数；

步骤3：通过离散化时间放缩目标函数得到队列状态决策控制模型，并通过队列状态决策控制模型计算出等待队列的流量状态、进入调度周期的时刻和持续时间以及需要调度的重流量任务类型；

步骤4：创建调度周期内关于资源和重流量任务新的二分图并使用改进后的匈牙利算法对处于调度周期内的重流量任务进行计算，得到此阶段内群智计算网络的调度策略。

2.根据权利要求1所述的一种面向异构设备协作网络的群智计算在线任务调度方法，其特征在于，所述步骤1具体为：

所述群智计算网络包括发布任务的用户、多个异构设备资源和一个任务等待队列；用户随时间发布在线任务，如果任务所需的资源被占用，则进入等待队列等待被服务；如果所需资源空闲，则所需资源共同协作处理该任务；在任务进入系统或者资源服务完成的时刻，即系统状态改变时刻，计算系统的流量状态来调度任务。

3.根据权利要求2所述的一种面向异构设备协作网络的群智计算在线任务调度方法，其特征在于，所述步骤2具体为：

步骤2-1：在群智计算网络中，用户随时间在线发布任务到达等待队列；用 表示任务类型的集合，用/>表示设备资源的集合；其中任务-资源关系矩阵用一个I×J维的A表示；如果资源i协作参与类型j任务的服务过程，则A_ij＝1，否则A_ij＝0；对所有任务j有/>对所有任务i有其中/>表示类型j任务服务过程中所需的资源集，/>表示由资源i协作处理的任务类型集；

步骤2-2：让v_jn表示类型j任务的服务时间，且是一个独立同分布的随机变量序列，其均值为/>变异系数为σ_j；对于每种类型j任务的服务时间，有：

V_j(0)＝0

其中V_j(n)是连续被服务n个类型j任务的时间和；S_j(t)表示为在[0,t]时间内始终处理类型j任务，直到时刻t为止处理的类型j任务数量；

步骤2-3：用表示j任务的到达间隔序列，其均值为1/λ_j；对于每种类型j任务的到达时间，有：

U_j(0)＝0

其中U_j(n)是第n个类型j任务到达系统的时刻；E_j(t)表示为直到t时刻，经用户发布任务后到达系统的类型j任务数量；

λ_j是类型j任务到达间隔符合的分布参数，是类型j任务服务时间符合的分布参数；ρ_i表示为资源i上的负载，其计算公式为/>则对于资源i的流量状态定义为：

如果θ_i＝-∞，则资源i处于轻流量状态；如果则资源i处于重流量状态；

对于资源的流量状态表示，表示轻流量状态的资源，/>表示重流量状态的资源：

对于任务的分类，包括三种任务类型集合：仅由重流量状态资源处理的任务类型集合仅由轻流量状态资源处理的任务类型集合/>由轻流量和重流量两种状态处理的任务类型集合/>

对于全部的类型j任务，用Q_j(t)表示在时刻t时系统中类型j任务的数量，包括正在被服务的任务:

Q_j(t)＝Q_j(0)+E_j(t)-S_j(T_j(t))

其中Q_j(t)是系统中任务的初始数量状态，Q_j(0)＝0，T_j(t)表示在[0,t]期间处理类型j任务的累积时间；

步骤2-4：群智计算网络的目标函数为最小化系统中等待任务的数量，即最小化系统容量损失：

4.根据权利要求3所述的一种面向异构设备协作网络的群智计算在线任务调度方法，其特征在于，所述步骤3具体为：

步骤3-1：通过增加与资源相关联的任务负载约束，将连续时间下的目标函数离散为每一时刻的队列状态决策控制模型，其与资源i相关联的任务负载定义为：

步骤3-2：利用队列模型中流体和扩散缩放过程，即通过增加任务负载约束将连续时间离散化间隔的时间点，建立的队列状态决策控制模型为：

步骤3-3：对于每一个时刻t，群智计算系统的队列流量状态是一个确定的值，即决策控制模型在数学模型上是一个线性规划模型：

利用二次规划模型找到上面线性规划模型具有最小欧几里得范数的最优解，并且因为该二次规划模型是凸的，所以在多项式时间内是可解的：

其中z(w)表示线性规划模型的最优目标函数值；

步骤3-4：通过在时刻t求解出的队列状态决策控制模型，得到此时队列状态接近最优解的所有任务类型数量对于重流量任务和轻流量任务的定义有：

则相应的处理重流量任务资源和处理轻流量任务的资源，两者分别定义为：

如果则此时t时刻进入调度周期，调度周期的持续时间是实现资源之间最优工作负载分配所需的预期时间，计算公式为：

在[t,t+L(t)]时间内对内的重流量任务数量从Q_j(t)降低至/>值以下，在调度周期结束后，重新根据此时系统流量状态计算队列状态决策控制模型，并重复步骤3-2到步骤3-4。

5.根据权利要求4所述的一种面向异构设备协作网络的群智计算在线任务调度方法，其特征在于，所述步骤4具体为：

步骤4-1：将每次进入调度周期的t时刻计算出内的重流量任务类型，所有资源和重流量任务-资源的关系矩阵作为新的二分图/>进行匹配；

步骤4-2：对于二分图先匹配第一个节点，将第一个节点所需资源标记为该任务节点的占用，最大匹配任务数量加1；

步骤4-3：对于下一个节点，如果所需资源空闲，重复步骤4-2，即将该节点标记为该任务节点的占用，最大匹配任务数量加1；如果存在所需资源被占用的情况，查询被占资源的任务节点，然后解除该任务节点所占用的所有资源；如果解除的所有资源能让匹配的任务数量大于1，那么将这些资源匹配，标记这些资源为相应任务的占用，记录这步操作后的任务匹配数量X，然后最大任务匹配数量加X减1；如果解除的所有资源让匹配的任务数量小于等于1，那么回溯到接触占用资源节点的情况前，目前匹配的任务节点所需的资源被占用无法匹配，跳过该节点；

步骤4-4：重复步骤4-3，直至没有属于重流量任务节点可以被匹配，最后将匹配到的类型任务进入所需资源设备；

步骤4-5：对于轻流量任务，寻找剩余的空闲设备资源，分配给相应的轻流量任务去服务。