基于DDPG 算法的云数据中心任务节能调度研究①

王立红 张延华 孟德彬 李萌

(北京工业大学信息学部 北京 100124)

0 引言

云计算是近年来兴起的一种新的商业模式,通过构建具有强大计算能力的计算资源池,为企业、组织和个人提供按需、低成本的计算、带宽等共享资源服务[1]。云计算技术的快速发展也使得数据中心在工业互联网和物联网技术中的核心地位越来越高[2]。随着云数据中心数量和规模的增长,大量的电力消耗和能源消耗无疑成为各国面临的严峻挑战。根据自然资源保护委员会的报告,数据中心目前消耗了全球约7% 的电力,能耗预计每年将超过1400 亿千瓦时。

云数据中心的能源消耗主要来自2 部分,即信息技术服务系统和基础设施系统[3]。其中,物理服务器在数据中心的能耗中占比最大。值得注意的是,服务器的能源效率很大程度上取决于计算资源的使用情况,例如处理器的利用率[4]。另外,云环境中工作负载是随机且高度动态变化的,这些大批量的任务需要被分配给合适的节点处理。因此,进行有效的任务调度是提高服务器资源利用率的一种较为合适的方法。它可以提高服务器的能效,减少服务器的空闲运行,避免能源浪费,从而进一步降低数据中心的最终能耗。

近来许多研究集中在云调度上。为了灵活管理大量的服务器资源和海量的任务,数据中心采用虚拟化技术,构建多个虚拟机(virtual machine,VM)来执行这些计算任务。云计算数据中心可以通过迁移和整合处理大量和短期工作的虚拟机来分配计算[5-6]。但是,这些方法不适合长期和计算密集型任务,因为迁移会中断任务执行并导致移动数据的开销。传统上,各种元启发式算法可以在一定条件下提供可行解。文献[7]采用模拟退火方法实现云数据中心资源调度,以降低能耗。文献[8]提出了一种改进的粒子群优化算法,该算法在平衡能源效率方面取得了良好的效果。为了考虑异构资源,文献[9]结合遗传算法和粒子群算法的优势找到最优资源调度方案,从而进行能源优化。然而,基于启发式的方法只能处理相对稳定的工作负载,且随着工作负载的增加,该算法会导致高复杂度,从而增加了计算时间。

近年来,深度强化学习(deep reinforcement learning,DRL)作为传统强化学习(reinforcement learning,RL)[10-12]方法的重要延伸,已广泛应用于解空间大的决策优化和控制问题,包括数据中心的能耗优化问题和资源调度问题。在传统的RL 系统中,代理通过迭代向环境发送动作、监控环境状态以及评估标量奖励以指导下一步动作来与环境交互。代理的目标是最大化累积奖励。在交互过程中,代理会构建一个查找表,之后可以使用该查找表来根据环境状态选择一个动作。但是,对于状态空间和动作空间大的优化问题,查找表的大小会非常大,不利于学习过程和模型性能。DRL 通过将表格替换为称为深度Q 网络(deep Q network,DQN) 的深度神经网络来解决此问题。文献[13]提出了一种深度强化学习方法实现了分布式数据中心的优化选择,有效降低了整体用户成本。文献[14]基于深度Q 学习的系统,通过使用资源供应和任务调度决策来最大限度地降低能源成本。文献[15]提出DRL 模型来适应服务级别协议目标,学习不同类型任务的固有特征,从而降低集群VM 的总使用成本和平均任务持续时间。这些方法都试图利用DQN 卓越的在线和自主能力来解决云计算系统中的资源分配问题,然而它们始终专注于提高DQN 的效率,而不是扩展对不同工作负载变化的适应性。当这种变化持续发生时,DQN 类型的方法是不够的,这是因为需要对所有可能的动作生成Q 值。

为此,本文将在线任务调度表述为一个有约束的动态优化问题,然后采用深度确定性策略梯度(deep deterministic policy gradient,DDPG)算法将连续的任务请求调度到合适的VM。具体来说,动态变化的工作负载到达数据中心后,经准入控制策略进入任务队列;并在队列中进行优先级排序之后,调度器采用DDPG 网络,将任务和VM 的信息作为代理的状态;将给任务分配的VM 作为动作,任务的响应时间和云数据中心能耗作为奖励函数,自适应地为实时任务分配VM。

本文的结构安排如下。第1 节介绍本文的系统模型;第2 节详细介绍本文所采用的在线任务调度策略;第3 节评估了所提出的算法并对仿真结果进行讨论和分析;第4 节对本文工作进行了总结。

1 系统模型及问题表述

如图1 所示,本文研究的系统模型包含3 部分,分别为用户工作负载模型、云环境模型和任务调度模型。根据系统模型,将在线任务调度问题表述为一个有约束的多目标优化问题。

图1 系统模型

1.1 用户工作负载模型

工作负载即用户向数据中心提交包括中央处理器(central processing unit,CPU)、内存、存储、带宽等资源需求。假设用户提交的请求是相互独立的,并且有以下特点:(1)每个请求都被视为一个完整的任务,不能进一步拆分为更小的任务;(2)每项任务仅可由一台VM 完全完成;(3)在任何时候,每个VM 要么空闲,要么只执行一项任务;(4)任务间没有通信或依赖关系。具体来说,用户任务由其到达时间、计算能力和服务质量(quality of service,QoS)(例如用户请求截止时间)定义。通过这种方式,可以将任务形式化为六元组:

其中,Taskj指代到达的第j个任务,是任务j到达时间,lenj是任务j的长度,uj是处理任务j对CPU 的需求,mij是计算任务j需要的指令数,dj是任务j硬截止时间,Ttypej是任务j类型(即I/O 或计算密集型)。

1.2 云环境模型

本文云环境模型简化为由VM 的建立、云能耗模型和VM 的释放组成。构建VM 模型,实现计算资源的提供;不同的VM,处理任务所需的能耗也不同,采用云能耗公式实现总能源成本的定量计算;最后,VM 空闲时及时释放资源以达到节能的目的。

1.2.1 VM 模型

云数据中心的基础设施依赖于资源虚拟化。映射虚拟化技术将许多物理服务器的计算资源划分为独立的隔离虚拟资源,从而实现资源池化。不同的VM 计算能力不同,功耗也不尽相同。因此,在本文的模型中,将每个VM 的属性定义为一个四元组:

其中,VMi指代云数据中心的第i个VM,mipsi是VMi每秒执行的指令数,speedi是VMi接收用户请求的速度,是VMi的静态功耗,Vtypei是VMi的类型(即高I/O 或高计算型)。

1.2.2 云能耗公式

云计算环境中的VM 在任务到达之间存在一定的间隔,因此云环境的能量消耗会有一定的概率空闲。设是空闲概率,而1-则是VM 运行的概率。因此,云环境的能量消耗是所有VM 的能耗之和,可以表示为

其中,Ui是VM 的CPU 利用率;ci是利用率的影响因素;bi是一个常数,这意味着无论VM 有没有任务运行,都具有静态功耗,取bi=,因为,当Ui=0时,

此外,式(3)还表明了能耗取决于任务在云环境中停留的时间,因此可以通过减少任务的响应时间和提高CPU 的利用率来减少云数据中心的能源消耗。

1.2.3 VM 释放

每个任务的运行时间占用CPU 和内存等资源的时间不是无限的,现实中会在进程结束后自动释放。本文假设只有在任务完成后才能释放VM。

1.3 任务调度模型

任务调度模块由任务队列(task queue,TQ)、状态监视器(status monitor,SM)和基于DDPG 的任务调度器构成。

TQ 的功能主要是存储用户提交的请求并对其进行优先级排序。在每个时间窗口,用户请求经准入控制策略被推送到队列中,过度消耗资源或超过截止时间的任务会被拒绝。SM 分为任务监视器和VM 监视器,分别用来获取任务和VM 的状态信息,包括VM 的CPU 利用率、任务等待时间等。之后,这些状态信息作为输入发送到基于DRL 的任务调度器,输出是任务-VM 分配方案。最后,任务调度器将TQ 中的任务推送到与该VM 关联的缓冲队列,将其分配给特定的VM 执行。每轮分配后,TQ中的任务会被清空,为下一个时间窗口做准备。

1.4 问题表述

本文研究在保证服务质量(QoS)的情况下减少云数据中心的能耗,为用户提供服务。因此可将调度问题表述为一个有约束的多目标优化问题。

一旦任务开始,任务的执行就不能被中断,即分配给忙碌VM 的任务将需要等待,直到所有先前分配的任务都已执行。因此,任务j的响应时间可以定义为

其中,Ttypej是任务j类型;Vtypei是VMi的类型;⊕是异或符号,表示当VM 类型和任务类型不同时,CPU 处理速度会更低;mipsi是VMi每秒执行的指令数。

由此,所有任务分配给VM 的平均响应时间为

根据能耗模型可知,所有任务的能耗平均值为

基于上述公式,多目标函数及其约束可以表述为

评估函数采用加权和的方法[16]来将多目标优化问题转换为具有权重的单个目标,该权重代表用户在目标之间的偏好。考虑到任务的响应时间和VM 的能源消耗在数据规模上不统一,使用取对数的方法进行标准化数据处理,最终定义任务调度评估函数为

其中,δ∈[0,1],为加权值系数,表示用户对响应时间和能耗的关注度。

2 基于DDPG 的准入动态任务调度策略

针对云计算环境中工作负载的高度动态性和多样性的特点,本文基于联合优化目标函数,提出DRL 方法对系统的任务调度进行优化,以获取最小能源消耗。

2.1 准入控制策略

基于准入控制策略[17],调度器根据用户的截止日期筛选任务,只选择可实现的任务,而拒绝其他任务。具体来说,用户提交任务之后,假设将其分配给云数据中心类型匹配的计算能力最强的VM 且无等待立即被执行,若它仍不能在硬截止日期前完成,则请求应被拒绝。根据服务级别协议,应该满足:

2.2 动态任务优先级

在大多数现有的基于DRL 的云任务调度策略中,用户任务通常以先到先服务(first come first served,FCFS)的方式处理。但任务的顺序不同,系统选择的VM 就会不同,QoS 和能耗都会受到影响;另外,训练过程中探索阶段对初始动作的选择会影响调度策略的收敛速度,为提高DRL 调度策略的运行效率,可以在任务队列对任务进行动态的优先级排序。

仅仅依据某一方面的特征参数来排序是不够的,本文综合考虑了任务长度和任务截止时间来设计优先级。当任务的长度很短时,优先执行可以尽快释放VM 资源;离任务的截止时间很近时,优先执行可以提高任务成功率。由此,任务的排序优先级函数定义为

其中,lenj是任务的长度;dj是任务j硬截止时间;ω∈[0,1],为加权值系数,表示任务长度和硬截止时间对优先级的影响程度。当ω取值很大且越接近于1 时,任务长度对优先级的影响越大;ω越接近于0 时,硬截止时间对优先级影响越大,本文ω取值为0.5。

2.3 基于DDPG 的任务调度

2.3.1 DRL 学习机制

RL 通常是基于马尔可夫决策过程(Markov decision process,MDP)定义的,具有潜在的马尔可夫性,即RL 决策仅依赖于直接从其经验中学习而无需任何先验知识。然而,传统的RL 算法无法处理高维的复杂状态和动作空间,因此作为深度学习(deep learning,DL)和RL 的结合,DRL 应运而生。DRL 的基本思想是在环境中设置一个代理,通过执行动作与环境进行交互。代理将从环境中获得奖励,根据奖励改进其行动策略,并期望在下一步中获得更多奖励[18]。代理的目标是通过与环境交互来学习最优策略π以最大化预期回报。

在时间t,代理观察当前系统的状态st,采取行动at,然后从环境反馈获得即时奖励rt,之后系统进入下一个状态st+1。预期累计收益为

其中,γ∈[0,1]是折扣因子,表示对未来获得奖励的重视程度,决定未来奖励如何转换为当前收益。

基于策略π,在状态st的动作at获得的t时刻的最大期望奖励函数定义为动作-价值函数Q,定义为

其中,Eπ[*] 表示数学期望,是针对环境中的所有随机策略执行的。

如果基于策略π的动作-价值函数大于基于其他策略的Q 函数,则策略π是最优策略,对应的Q函数是最优动作价值函数。

DRL 的最终目标就是找到这个最优策略:

据此,代理不断通过下式迭代动作-状态值,表达式为

其中,α∈[0,1]为学习率,为下一状态的最大动作-状态值。

在众多DRL 算法中,应用最广泛的为DQN。尽管DQN 可以成功解决高维状态空间中的问题,但它只能处理离散和低维动作空间。此外,DQN 还存在估计过高的缺陷,而Actor-Critic 方法存在收敛速度慢的问题。为了解决上述问题,本文提出了DDPG算法[19-20]。它的确定性策略可以提高效率,并且与DQN 的结合使训练过程易于收敛。因此,本文的在线任务调度算法是基于DDPG 的。

2.3.2 算法设计

基于DRL,分别设计和部署状态空间、动作空间、奖励设计、网络结构和网络训练。

(1)状态空间

状态空间是代理从当前环境中观测到的信息。在本文中,环境xt的状态观测由状态监视器提供,分为2 部分:对用户任务的观测和对VM 资源的观测。假设环境是完全观测的,则st=xt。此时,任意时隙t的系统状态定义为

(2)动作空间

DRL 代理根据观测的环境状态信息以固定的间隔做出决策,从待处理的任务队列中选择合适的任务分配给某个VM。因此,动作空间在时隙t处定义为

其中,ai,j(t)={0,1},如果ai,j(t)=1,则taskj分配给VMi。

(3)奖励设计

根据云系统模型和响应时间与能耗最小化目标,并结合任务调度评估函数,本文奖励函数设计为

其中,δ∈[0,1],和Ei,j(t) 分别是将taskj分配给VMi的任务响应时间和在该VM 上的能量消耗。

(4)网络结构

在DDPG 中,因为采用Actor-Critic 架构,所以其由Actor 和Critic 2 个部分组成。此外,对于具有高维状态和动作空间的系统,维护如此庞大的转换表所消耗的计算量和存储空间是无法接受的。因此,为从高维数据中获取低维特征,DDPG 借鉴DQN的思想,采用深度神经网络(deep neural networks,DNN)通过调整网络中的参数来逼近函数。Actor 网络μ(s|θμ) ≈μ(s) 逼近策略函数μ,Critic 网络Q(s,a|θQ) ≈Q(s,a) 逼近Q 函数,其中,θ是神经网络的权重参数。最终DDPG 有Actor eval、Critic eval、Actor target 和Critic target 4 个神经网络,网络架构如图2,主要由评估网络、目标网络和回放缓冲区3 个模块组成。

图2 DDPG 网络架构

代理从环境记忆库中随机抽取〈st,at,rt,st+1〉 存入回放缓冲区中,目的是打破训练时经验学习的时间相关性。目标网络的输出值分别为Q′ 和μ′,相应函数的神经网络权重以如下方式缓慢更新。

其中,τ∈(0,1)是目标网络的学习率,通常τ ＜＜1。

本文的目标是基于TD-error 最小化损失函数,因此Critic eval 网络的损失函数为

评估网络中Actor 使用策略梯度函数进行更新动作:

(5)网络训练

训练时,为了增加探索的随机性,增加策略函数的决策范围,防止陷入局部最优,设置贪婪系数ε,根据概率ε随机选择动作at。代理执行动作at并获取即时奖励rt后,观察下一状态st+1,将经验〈st,at,rt,st+1〉 存入环境记忆库中,然后随机抽取样本容量B大小的经验存放入回放缓冲区,作为输入传进行评估网络和目标网络计算Q 值,最后根据策略梯度函数和损失函数迭代更新,每隔一定训练步数,降低贪婪系数ε,直至Q 值和损失函数曲线收敛,停止训练。在训练过程完全完成后,基于DRL 的调度方案在计算上将是轻量级的。

2.3.3 伪代码

综上,基于DDPG 的任务调度算法的伪代码如算法1 所示。

算法中第(5)～(7)行为环境与代理的交互过程;第(8)～(9)行为利用经验回放机制抽取样本的训练过程;第(10)～(12)行为评估网络的训练过程和目标网络参数的更新过程;第(5)行和第(13)行为利用贪婪系数ε经固定训练步数平衡动作偏好的选择过程。

3 仿真实验及结果分析

本节首先介绍了仿真实验的环境和设置参数,之后展示并比较分析了不同工作负载和不同调度策略下的仿真结果。

3.1 仿真环境与实验设置

本文仿真实验的硬件配置和软件环境为@Intel Core i5 CPU 2.20 GHz,8 GB 内存,Python3.8 和Py-Torch 1.0。

在云数据中心设置中,VM 数量设置为20,5 种类型,用于处理不同类型的任务,包括计算密集型和I/O 密集型任务。任务数量设置为500 000,每个作业任务的长度由正态分布控制。分布的均值和方差分别设置为150 和10。作业的到达时间由泊松分布控制,平均到达率λ选自{8,10,12,14,16}。在所提出DDPG 网络中,2 个Actor 网络的输入层函数为tanh,输出层利用ReLU 函数。Critic 网络使用ReLU作为输入激活函数并在输出层采用线性激活函数。另外,在评估网络中,使用自适应矩估计(Adam)方法优化网络。Actor 和Critic 网络的学习率分别设置为0.006 和0.008。在目标网络中,学习率τ设置为0.001。经验回放缓冲区容量大小设置为1000。云环境中其他参数具体如表1 所示。

最后,通过大量实验来评估本文提出的任务调度策略。实验中选择了5 种方法作为对比,包括随机调度、轮循算法、贪婪算法、DQN 算法和DDPG 算法。并使用平均响应时间、能耗和CPU 利用率标准差3 个指标来评估调度策略的性能。

3.2 收敛性分析

为了验证DDPG 算法能够更好更快地得到最优解,本文通过观察Actor 网络的Q 值和Critic 网络的Loss 值是否达到收敛来确定。

图3 和图4 分别展示了在不同到达率的条件下,训练期间评估网络中Actor 网络的Q 值和目标网络中Critic 网络的Loss 值随训练步数的变化曲线。对于Actor_Q_Value 来说,如果选择的是一个正确的行为,则Q 值会不断增加直至收敛不变。对于Critic_Q_loss 来说,损失代表了神经网络的学习空间。当它变小时,意味着神经网络在学习,收敛代表学习完成。由图3 和图4 可看出,随着迭代次数的增加,不同任务到达率的Q 值和Loss 值都在约5000 步的迭代次数时达到稳定的收敛,表明训练结束且网络输出为最优策略。

图3 不同到达率下的Actor_Q_Value 值

图4 不同到达率下的Critic_Q_Loss 值

图5 展示了在相同到达率下DQN 算法和DDPG算法随着训练步数的增加,其损失函数变化曲线对比图。由图5 可知,DDPG 算法比DQN 算法的Loss值更迅速地收敛。并且在这2 种算法都采用均方误差计算损失函数的条件下,DDPG 算法的Loss 值更小,综上说明本文采用的DDPG 算法可以更快更准确地找到最优解。

图5 DQN 和DDPG 算法的Q_Loss 值对比

3.3 结果对比分析

由于实验的随机性,本文对不同到达率的每种算法进行了10 次重复实验,最后记录了平均结果。

图6 展示了用户任务的到达率从8/s 增加到16/s 的5 种调度算法的平均响应时间对比图。由图可知,各种算法的平均任务响应时间随到达率的增加都有不同程度的增加,这是因为更高的到达率意味着更多的用户任务将在系统中排队等待服务。

图6 5 种调度算法的平均响应时间对比

由图6 的5 种算法的平均响应时间对比可以看出,随机任务算法产生的平均响应时间最长并且随着到达率增加增长得最快,原因是它将用户提交的任务随机分配给VM 而不考虑匹配性,可能会导致任务等待时间和处理时间都比较长。同理,轮询算法将任务依次分配给VM,响应时间会因任务类型和VM 类型不匹配问题而拉长。贪婪算法的主要思想是根据任务的到达时间将任务分配给第一个空闲的VM,但过分强调每个单独的任务可能不会导致所有任务的总体完成时间最短。相比之下,本文采用的DDPG 算法平均任务响应时间最短。图5 中,在到达率为16/s 时,采用随机算法的平均响应时间为1.66 s,DQN 算法平均响应时间为0.78 s,而DDPG 算法的平均响应时间约为0.66 s,比随机算法缩短了60%,比DQN 算法缩短了15%。这得益于将任务响应时间作为奖励函数去训练和DDPG 算法处理高维度连续动作空间问题的优越性。

图7 展示了5 种调度算法在不同任务到达率下的系统总能耗对比图。随着到达率的增加,使用5种调度算法的系统总能耗都随之增加。这是由于工作负载的增大,需要系统更多的资源和时间去处理任务,根据能耗模型,系统能耗会随之增加。观察图7可知,随机调度算法和轮询调度算法的总能耗最高且相差不大,这是由算法无需考虑任何因素快速将任务分配给VM 的特性决定的。显然,基于DRL 调度的2 种算法总能耗最低。只有到达率为8/s 时,DQN 的能耗低于DDPG 算法,之后的到达率,DDPG 能耗皆低于DQN,这表明DQN 更适合低负载的系统而DDPG 算法则更适合高负载的系统,并且,工作负载越高,节能效果越显著。

图7 5 种调度算法的总能耗对比

图8 展示了不同到达率、不同调度算法下系统VM 的CPU 利用率标准差。本文利用CPU 利用率的标准差来表征VM 之间的负载平衡。当多个任务被频繁地调度到同一VM 上,会导致其过度使用而其他VM 长时间空闲,资源利用率低下。因此负载平衡也是评估调度策略好坏的一个重要指标。由图8可知,DDPG 算法的CPU 利用率标准差低于其他4 种算法,表明本文采用的DDPG 算法可以优化系统的负载平衡。

图8 5 种调度算法的CPU 利用率标准差对比

4 结论

本文研究了如何在满足所有用户的QoS 指标下最大限度地减少云数据中心的能耗。为了解决这个问题,提出了一种基于DDPG 的节能任务调度策略,所提出的策略分为3 个过程,即准入控制、动态优先级排序和基于DDPG 网络的任务调度。采用DDPG 网络寻找最优任务分配解决方案,将用户提交的任务和VM 关键信息作为状态输入,联合考虑任务的响应时间和系统能耗2 大指标作为奖励函数训练网络,动态地适应不确定性和高度波动的工作负载。仿真结果证明,相比于现有调度方法,本文所提策略不仅具有更快更稳定的收敛性,还能有效地减少平均任务响应时间,节省系统整体能耗,并在保证系统负载均衡方面有很好的优越性。