一种基于V-TGRU模型的资源调度算法

doi:10.3785/j.issn.1008-9497.2022.04.010

一种基于V-TGRU模型的资源调度算法

常晓洁^,^,, 张华

浙江大学信息技术中心，浙江杭州 310058

A resource scheduling algorithm based on V-TGRU model

CHANG Xiaojie^,^,, ZHANG Hua

Information Technology Center，Zhejiang University，Hangzhou 310058，China

收稿日期: 2021-11-26

Received: 2021-11-26

作者简介 About authors

常晓洁（1988—），ORCID：https：//orcid.org/0000-0002-9461-3670，女，硕士，工程师，主要从事计算机应用及云计算研究，E-mail：changxj@zju.edu.cn. , E-mail：changxj@zju.edu.cn

摘要

提出了一种在私有云计算环境下基于机器学习V-TGRU模型进行资源预测的算法。通过统计历史记录，将其与当前工作负载下不同任务的先验资源使用情况相结合，同时考虑工作负载特性、主机特征和同一资源池中任务之间的亲和性等因素，动态预测多任务的资源占用情况，并根据预测结果和任务运行现状进行多目标任务优化调度。实验证明，此算法能有效完成对资源的预判选择、减少调度次数、节约调度时间、节省云计算资源和带宽，保障应用任务稳定运行。

关键词： 机器学习 ; 资源预测 ; 任务调度 ; 云计算

Abstract

This paper presents a new algorithm for resource prediction based on machine learning model V-TGRU in private cloud computing environment. The algorithm makes statistics of historical records and combines the prior resource usage of different tasks under the current workload, at the same time, considering the workload characteristics, host characteristics, the affinity between tasks in the same resource pool and other factors. The multi factor data matrix is further standardized and coded. The standardized coded data are modeled by V-TGRU to dynamically predict the resource occupation of multi tasks, and carry out multi-objective task optimal scheduling. Experimental results show that this method can effectively complete the pre-judgment and selection of resources, reduce the scheduling time and times, save cloud resources and bandwidth, and ensure the stable operation of application tasks.

Keywords： machine learning ; resource prediction ; task scheduling ; cloud computing

PDF (1291KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

常晓洁, 张华. 一种基于V-TGRU模型的资源调度算法. 浙江大学学报(理学版)[J], 2022, 49(4): 467-473 doi:10.3785/j.issn.1008-9497.2022.04.010

CHANG Xiaojie, ZHANG Hua. A resource scheduling algorithm based on V-TGRU model. Journal of Zhejiang University(Science Edition)[J], 2022, 49(4): 467-473 doi:10.3785/j.issn.1008-9497.2022.04.010

云计算是一种基于可配置网络、存储、服务器、应用软件等计算资源共享池进行计算并按需分配和付费的服务模型^［1-4］。云计算环境下的资源分配和调度是云计算服务领域的核心问题。随着云计算技术的不断发展和应用需求的持续提高，云计算环境的复杂性日益加剧，机器选择过程中基于任务应用行为^［5］、故障表现^［6］、能源效率^［7］、亲和性^［8］等最优调度算法的影响因素研究正吸引越来越多学者的兴趣。机器学习是依靠过去的经验数据创建模型的能力^［9-10］，调度算法的优化需通过机器学习组件提高复杂决策的准确性和有效性^［11］。文献［12-13］提出了基于决策树、支持向量机、神经网络等经典模型的机器学习算法在云计算场景中的应用。文献［14-15］讨论了应用强化的机器学习算法进行权限管理和资源分配。文献［16-20］分别介绍了针对单一资源变量，如CPU或资源请求输入门控循环单元（gate recurrent unit，GRU）、长短期记忆（long short term memory，LSTM）网络以及改进离散检测GRU（IGRU-SD）算法进行资源预测。上述研究均基于单变量环境下的优化策略，在实际应用过程中则需考虑精度、训练时间、参数量、特性数量和变量之间的关系等。

文献［21］研究了虚拟化服务器集群中电源优化的动态配置方法；文献［22］研究了基于信任驱动和服务质量需求的工作流聚类分析调度方法；文献［23］研究了云计算环境下基于分簇的资源调度算法；文献［24］研究了基于分布式深度学习的多个异构神经网络调度模型。这些方法对云资源的充分调度具有一定借鉴意义，但在任务调度过程中，尚存在大量闲散的、未被利用的计算资源以及任务的反复调度所造成的资源浪费。

针对上述云计算环境下资源调度算法的问题，提出在私有云计算环境下基于机器学习变量传输控制GRU（V-TGRU）模型的资源预测算法。

1　资源预测模型

1.1　数据预处理

以用户提交的每个实例为单位进行云计算资源匹配，用户提交的 $n$ 个实例组成应用集 $X = {X_{1} ， X_{2} ， \dots ， X_{n}}$ ，每个实例要求采集 $p$ 个参数组成向量矩阵： $X = {X_{1} ， X_{2} ， \dots ， X_{p}}$ ，其中 $X \in R^{n T / t \times p}$ 。

云环境有 $n$ 个虚拟资源组成，第 $i$ 个虚拟资源池状态可表示为 $Y = {Y_{1} ， \dots ， Y_{i} ， \dots ， Y_{q}}$ 的向量矩阵， $Y \in R^{m T / t \times q}$ 。

利用云计算环境中虚拟资源的各项属性值、均值以及标准差对采集到的原始应用实例数据和资源池数据进行标准化处理，标准化迭代公式为

r_{i j}^{''} = \frac{r_{i j} - S_{j} r_{j m i n}^{'} - {\bar{r}}_{j}}{S_{j} r_{j m a x}^{'} - S_{j} r_{j m i n}^{'}}

，（1）

其中， $r_{i j}$ 表示第 $i$ 个资源池的第 $j$ 个参数， $r_{j m i n}^{'}$ 表示第 $j$ 个参数标准化的最小值， $r_{j m a x}^{'}$ 表示第 $j$ 个参数标准化的最大值， $\bar{r_{j}}$ 表示第 $j$ 个参数的平均值， $S_{j}$ 表示第 $j$ 个参数的标准差。

1.2　V-TGRU算法模型

GRU算法的记忆较循环神经网络（recurrent neural network，RNN）算法更长，训练速度较LSTM网络算法更快，但仍存在需要预处理数据包和内存使用率高等问题。为此，引入变量门控递归单元，包括1个调整新输入与前内存合并的重置器、1个控制前内存保存的更新门Z。

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 V-TGRU模型结构

Fig.1 V-TGRU model structure

在V-TGRU模型框架中，提出了一种具有双向结构和门控递归单元变量w的增强型V-TGRU网络。首先，将双向结构应用于捕获输出，从而提高GRU模型的表达能力。所采用的加权特征平均法简单地导出了每个时间点带中心双加权方案的平均向量。其由两部分组成：双向GRU输出和加权平均特征。变量w和变量激活指变量w中的权重和激活功能与GRU相同，但V-TGRU中的权重w和激活功能采用二值化表征。此外，V-TGRU用编码器自动进行预处理。编码器中输入的为压缩数据，通常比原始输入数据更规整，从而降低内存占用率，解决GRU算法需要预处理数据包和内存使用率高的问题。

V-TGRU预测模型^［25］的算法流程：

输入：采集到的N个实例资源占用情况矢量包 $X_{i} = {X_{I D}, X_{l e n}, X_{i n}, X_{o u t}, X_{c p u}, X_{m e m}, X_{n e t}, X_{t k}}$ 。

输出：测试数据集的评估结果。

步骤1　创建编码器模型。

（1）添加第一个编码器层e1单元的tanh触发；

（2）添加第二个编码器层e2单元的tanh触发。

步骤2　创建V-TGRU模型。

（1）添加第一个V-TGRU层l1单元，退出dropout为d1且循环退出dropout为r1；

（2）添加第一个V-TGRU层l2单元，退出dropout为d2且循环退出dropout为r2。

步骤3　训练和验证模型。

（1）当训练模型验证集上的误差不满足早停法条件时；

（2）当训练数据集不为空时；

（3）将计算周期数据集作为模型输入；

（4）计算H（p，q）分类交叉熵损失函数；

（5）用随机梯度下降优化算法更新权重和偏差；

（6）用验证集验证输出的训练模型。

步骤4　测试模型。

（1）用测试数据集测试已优化的超参数；

（2）返回测试数据集的评估结果。

编码器编码： $X = [x_{1}, x_{2}, \dots ， x_{p}]^{T}$ 为编码器的输入数据矢量， $X = [x_{1}^{'}, x_{2}^{'}, \dots ， x_{p}^{'}]$ 为编码器的输出数据矢量。利用tanh激活功能，最终接收的节点值为

X^{'} = f (x) = t a n h (W X + b)

。（2）

用编码器对标准化后的矩阵 X 和 Y 编码，得到历史时段占用资源的时间序列矩阵 $X^{'} = [x_{1}^{'}, \dots, x_{i}^{'}, \dots, x_{p}]$ 和资源池的性能时间序列矩阵 $Y^{'} = [y_{1}^{'}, \dots, y_{i}^{'}, \dots, y_{q}]$ ，其中p>q。

为提高训练过程的稳定性和收敛速度，采用批量梯度下降法进行训练，同时，采用误差反向传播法调整参数。对于GRU模型，有2种反向传播方式：用最后一个时刻的值作为输出和用各时刻的平均值作为输出，参数更新式为

∆ w (t) = - η \frac{\partial J}{\partial w} + α ∆ w (t - 1)

，（3）

其中， $Δ w (t)$ 为第t次迭代的加权更新，η为算法的学习率，0≤α<1为动量项，J为成本函数。

V-TGRU在最后一个时间点的隐藏输出可代表任务资源的占用情况，但在V-TGRU中，序列中间区域的信息可能会丢失。考虑序列的起始和结束区域对后向GRU和前向GRU的输出贡献很大，因此，引入加权特征平均提供局部特征序列 $t_{k}$ 的另一种观点。平均特征序列向量 $\bar{t}$ 为

\bar{t} = \sum_{k = 1}^{N} w_{k} t_{k} ，

（4）

其中， $w_{k}$ 表示迭代权值，k表示随机时间步长索引。为突出中间局部特征的影响，迭代权值设计为

w_{k} = \frac{e x p (m i n (k - 1, T - k))}{\sum_{j = 1}^{T} e x p (m i n (j - 1, T - j))}

，（5）

其中， $j$ 表示随机时间步长参数量， $T$ 表示参数总量。

2　基于预测结果的调度模型

本文提出的基于预测结果的调度模型将在调度过程中结合多实例的现在及未来状态值和资源池的现在及未来状态值、实例调度的网络传输时间以及CPU资源计算时间，以实例调度次数最少化、调度总时间最小以及资源预测调度最精确为调度标准。因此先对资源池和实例进行数据预处理，并将预处理数据输入V-TGRU预测模型，得到预测结果；然后按照矢量参数优先级对实例进行排序，同时将预测后的资源池进行聚类分级，优先调度优先级更高的实例至更优的资源池聚类。调度算法流程如下：

输入： $X_{i} = {X_{I D}, X_{l e n}, X_{i n}, X_{o u t}, X_{c p u}, X_{m e m}, X_{n e t}, t_{t k}}$ ，

其中， $X_{I D}$ 为实例编号； $X_{l e n}$ 为实例计算量，用实例中运行的进程数表示； $X_{i n}$ 为实例需要处理的输入数据量； $X_{o u t}$ 为实例在所有进程运行过程中产生的输出数据量； $X_{c p u}$ 为实例运行占用CPU的核比数； $X_{m e m}$ 为实例运行占用的内存； $X_{n e t}$ 为实例间交互所需的带宽； $X_{t k}$ 为与第k个实例的亲和度，根据相互调用情况统计。

Y_{j} = {Y_{I D}, Y_{c p u s}, Y_{m e m s}, Y_{m i p s}, Y_{b n e t}}

，

其中， $Y_{I D}$ 为资源池编号； $Y_{c p u s}$ 为资源含有CPU的个数； $Y_{m e m s}$ 为资源的存储能力； $Y_{m i p s}$ 为资源的计算能力； $Y_{b n e t}$ 为资源的网络传输能力。

x_{i} = {x_{I D}, x_{l e n}, x_{i n}, x_{o u t}, x_{c p u}, x_{m e m}, x_{n e t}, x_{t j}}

为模拟预测实例使用资源情况的输出结果。

y_{j} = {y_{I D}, y_{c p u s}, y_{m e m s}, y_{m i p s}, y_{b n e t}}

为模拟预测资源池占用情况的输出结果。

输出： $〈X_{i}, Y_{j}, C_{i - j}〉。$

实例 $X_{i}$ 调度至资源池 $Y_{j}$ 上执行， $C_{j}$ 属于第i个实例调度到第j个资源池的映射关系。

（1） FunClustering（ $Y_{r j}$ ） //构建资源池聚类 $Y_{r j}$ 函数，分类计算调度资源，减少调度计算量。

（2） FunClustering（ $y_{r j}$ ） //构建预测资源池聚类 $y_{r j}$ 函数。

（3） SortCluster（ $y_{j}$ ） //按预处理后的整体情况对资源池聚类进行排序。

（4） SortEarlyDeadlineFirst（ $X_{i}$ ）//按实例的运行截止时间进行排序。

（5） Sort（ $X_{i}$ ） //对实例资源占用情况逐一排序。

（6） Sort （ $x_{i}$ ）//对实例资源预测占用情况逐一排序。

（7） $I N S_r u n t i m e_{（ i ， j ）} = \frac{N_{x c p u s j}}{N_{y r j c p u s j}}$ // 实例 $X_{i}$ 在资源池 $Y_{j}$ 的运行时间取决于实例对CPU的占用需求以及资源池的处理时间。

（8） $S c h e d u l_t i m e_{（ i ， j ）} = \frac{x_{i l e n i}}{y_{r j m i p s}}$ // 实例 $X_{i}$ 的调度预测时间取决于 $X_{i}$ 的计算量及资源池 $Y_{j}$ 的计算能力。

（9） $T R A N_t i m e_{（ i ， j ）} = \frac{x_{i n i} + x_{o u t i}}{y_{b n e t}}$ // 根据预测结果计算第i个实例调度到第j个资源聚类上的传输时间。

（10） $W A I T_t i m e_{（ i ， j ）} = \frac{x_{i t k}}{X_{i - 1}} X_{t k} + \sum_{1}^{i - 1} \frac{x_{i l e n i}}{y_{r j m i p s}}$ //实例 $X_{i}$ 等待调度时长取决于排序在 $X_{i}$ 前的实例调度时间以及与之前调度实例的亲和度 $X_{t k}$ 。

（11）Sort （ $x_{i} ， I N S_r u n t i m e_{（ i ， j ）} ， S c h e d u l_t i m e_{（ i ， j ）} ，$ $T R A N_t i m e_{（ i ， j ）}$ ） //对实例的资源预测占用情况及调度情况逐一排序。

（12） $C_{i - j} \leftarrow G e t C l u s t e r T y p e (D e a d l i n e_{t i m e_X_{i}} ，$ $S c h e d u l_t i m e_{（ i ， j ）})$ //根据截止时间和资源调度排序情况，将排序后的实例映射至最接近截止时间且任务负载最少的资源池。

算法（1）~（3），通过聚类方法对资源池进行预处理。（4）~（6），按照截止时间、现在和预测情况对实例进行排序，首先处理截止时间较近、资源情况紧缺的实例。（7）~（10），根据预测的实例运行情况和资源池占用情况，预判传输、调度及运行情况。（11）和（12），汇总预判情况，对实例运行情况进行排序，将最接近截止时间、最急需的实例优先调度到任务负载最少的资源池。

3　实验结果分析

3.1　实验环境

硬件环境：华为RH2288V3，CPU规格E5－2680V4×2，56核，内存128 GB和384 GB，硬盘规格800 G［ssd］×12和6 T［sata，7 200 r·min^-1］×12，共100个虚拟节点，200个实例，通过观察多个实例的24 h历史数据，整理得到每个实例对应资源需求的时间曲线，描述每个实例每天每个采样点所需的对应资源数量。每隔5 min采集一次，每天288个采集点，连续采集30 d。

3.2　结果分析

3.2.1　预测结果对比

对采集到的数据进行训练和建模，预测数据曲线的走势，并根据预测结果进行资源调度，通过调度实例的精度和F-测量^［26］，判断V-TGRU、GRU、LSTM及IGRU-SD模型预判的准确度。

表1中，“正”表示需要调度的实例；“负”表示不需要调度的实例，TP为实际需要调度，预测也需要调度的实例数；FN为实际需要调度而预测不需要调度的实例数；FP为实际不需要调度而预测需要调度的实例数；TN为实际不需要调度，预测也不需要调度的实例数。

精 度 = \frac{T P + T N}{T P + T N + F P + F N} ，

R = \frac{T P}{T P + F N} ，

P = \frac{T P}{T P + F P} ，

F - 测 量 = \frac{2 P R}{P + R} 。

表1 混淆矩阵

Table 1 Confusion matrix

	预测-正	预测-负
实际-正	TP	FN
实际-负	FP	TN

新窗口打开| 下载CSV

4个模型最优、平均及最差状态对比见表2。由表2可知，基于变量门控编码的双向V-TGRU模型较另外3种资源预测模型更准确，也更稳定。

表2 精度与F-测量对比

Table 2 Accuracy vs. F-measure

标准	模型
	V-TGRU		GRU
	精度	F-测量	精度	F-测量
最优	98.7	90.8	90.5	83.2
平均	97.5	89.6	87.8	81.7
最差	96.9	89.5	86.9	80.7
标准	模型
	LSTM		IGRU-SD
	精度	F-测量	精度	F-测量
最优	88.9	82.2	96.9	91.3
平均	87.7	80.7	96.2	89.5
最差	84.1	78.5	95.7	88.3

新窗口打开| 下载CSV

3.2.2　调度结果对比

V-TGRU与GRU、LSTM、IGRU-SD三种资源模型预测下的调度以及不进行预测的自适应调度算法（adaptive scheduling algorithm，ASQ）的对比见图2~图4。通过对比多任务下的调度执行时间、调度等待时间和调度次数，综合评价调度算法的效率。

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 多任务实例调度执行时间

Fig.2 Execution time of multi instance task scheduling

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 多任务实例调度等待时间

Fig.3 Waiting time of multi instance task scheduling

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 多任务实例调度次数

Fig.4 Times of multi instance task scheduling

由图2~图4可知，随着实例数的逐渐增多，4种预测调度算法和ASQ的调度执行时间呈增加趋势，但每个任务的平均调度执行时间均呈不同程度的下降趋势，这是因为当需要调度的实例数在一定范围内增多时，并发处理能力令调度执行时间缩短。由于V-TGRU预测的准确率更高，使无用的调度大大减少，降低了调度过程中的资源浪费，同时由于更及时地调度了所在虚拟计算节点资源相对紧张的实例，提高了实例的稳定性和运行性能，保障了云平台资源的利用率和可靠性。

4　结语

经实验测试，证明本文算法能更精确预测未来时效内实例占用资源的状况、运行状态以及资源池被占用情况，通过将更准确的预测结果和实时采集到的状态数据相结合进行综合分析调度，能更有效地完成实例对资源的预判选择，减少调度时间，避免实例的反复调度，节省因云资源的强制占用和反复调度消耗的资源及带宽，保证实例更稳定运行，提升用户满意度。下一步工作重点将积累并整合大量运维数据，研究更加高效的调度策略，进一步降低资源浪费，提升调度性能。

http://dx.doi.org/10.3785/j.issn.1008-9497.2022.04.010

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

ARMBRUST

， FOX A， GRIFFITH

， et al.

A view of cloud computing

［J］. Communications of the ACM， 2010，53（4）：50-58. DOI：10.1145/1721654. 1721672