JEDERL：一种异构计算平台任务调度优化算法

吕文凯，杨鹏飞，丁韵青，张鹤于，郑天洋

(西安电子科技大学 计算机科学与技术学院，陕西 西安 710071)

由图形处理器(Graphics Prdessing Unit，GPU)、数字信号处理器(Digital Signal Processpr，DSP)、现场可编程门阵列(Field Programmable Gate Array，FPGA)等计算资源构建的异构计算平台[1]，通过将不同属性的计算任务调度到对应的专用处理单元上来保证高性能计算需求[2-3]。基于异构计算平台设计高效节能的任务资源管理调度方案，能够最大限度地利用异构计算资源，降低系统功耗，从而满足不断增长的计算需求[4-5]。

任务调度策略在资源利用上的微小优化即可有效地减少任务执行时间，大幅地降低服务成本[6]。因此，为了提高异构计算平台的任务调度效率并减少能耗，文献[7]提出了基于蚁群算法的实时传感器节点任务调度算法。文献[8]提出了基于粒子群算法和遗传算法的混合元启发式算法，以最小化最大完工时间，提高资源利用率。异构计算平台的资源类型和组成结构各异，导致基于启发式思想的调度算法解集空间大、执行时间长。强化学习[9]是当下流行的机器学习方法，通过与环境不断交互最大化累计奖励，从而在解集空间中快速求解最优策略[10]。目前已有许多利用强化学习算法思想来解决计算平台上任务调度问题的实例。文献[11]利用深度Q学习算法实现了单任务的在线调度。文献[12]设计了一种基于强化学习和排队理论的任务调度算法，通过对虚拟机状态进行聚类减少状态空间的维度。

上述的研究中，异构计算平台的调度策略大多依赖启发式算法，而利用强化学习求解时，任务特征缺少多个任务的全局信息，导致模型训练不准确。为此，笔者以最小化任务的平均完成时间为目标设计了一种任务调度算法——JEDERL。JEDERL利用图神经网络[13]对异构计算资源和任务状态信息进行编码，提取资源特征及任务的局部和全局特征，并基于深度确定性策略梯度算法(Deep Deterministic Policy Gradient，DDPG)[14]进行算法的设计与求解。

1 问题建模

以任务的复杂性、计算资源的异构性、系统中不同计算资源的网络传输开销等特性为基础，以最小化任务平均完成时间为目标设计优化模型。具体如下。

1.1 系统模型

(1)

(2)

1.2 优化目标

(3)

(4)

对于单个任务Gv，其完成时间即为其子任务实际完成时间的最大值为

(5)

各个任务完成时间之和记为TSys：

(6)

以最小化任务的平均完成时间为目标，优化目标模型如下所示：

(7)

式(7)所示的约束条件为，任意子任务实际开始时间大于其前继子任务实际完成时间；任意子任务所用的计算资源不是同一个，即一个计算资源在某一时刻只能处理一个子任务。

2 面向异构计算平台的任务调度算法设计

2.1 任务调度框架设计

结合图神经网络与DDPG设计的基于异构计算资源的任务调度框架如图1所示。任务编码模块的图神经网络负责处理就绪子任务，聚合任务特征，经过3个不同层次的嵌入编码后，智能体根据任务的局部特征和全局特征计算当前系统中所有就绪子任务的执行优先级，产生待调度子任务；设备编码模块的图神经网络聚合异构计算平台上的异构计算资源特征；调度决策模块将任务特征与计算资源特征作为输入，输出任务调度动作作用于环境中，生成奖励更新神经网络参数，更新异构计算资源可用性状态，不断迭代，直至模型收敛。

图1 基于异构计算资源的任务调度框架

2.2 可伸缩的任务状态信息编码

神经网络通常需要固定大小的向量作为输入[15]。因此，使用图神经网络对任务状态进行编码[16]，将任务信息嵌入到一组向量中。具体的嵌入过程按层次执行，如图2所示。图嵌入将任务的有向无环图(Directed Acycic Graph，DAG)结构(其节点带有一组属性)作为输入，将3种不同类型且处于不同层次的嵌入作为输出结果：

(1)子任务单元的嵌入收集当前子任务节点及其祖先节点的信息，如图2(a)所示；

(2)任务单元的嵌入聚合整个有向无环图中所有子任务节点的信息，如图2(b)所示；

(3)全局嵌入将所有任务的有向无环图信息嵌入到一起，如图2(b)所示。

(a)子任务单元嵌入编码过程

(8)

2.3 基于DDPG的任务调度算法

基于异构计算资源的任务调度框架如图1所示，智能体接收到状态信息的输入，以获得最大奖励为目标采取动作，与环境交互不断更新状态。具体的状态、奖励、动作定义如下。

奖励(Reward)：基于DDPG算法单步更新的特点，奖励函数为每一步更新提供一个即时的奖励值。奖励函数如式(9)所示，目标是尽可能缩短任务平均完成时间：

(9)

动作(Action)：在关于就绪子任务选择的动作探索中，假设在当前时刻t，平台系统中处于就绪状态的子任务个数为nt，通过图神经网络对每一个就绪子任务进行嵌入信息编码后，就能得到关于这些就绪子任务的向量Vt，将就绪子任务的向量Vt转换成可以表征选择就绪子任务的概率向量Pt，之后智能体利用概率采样的方式选择每一步的动作，并通过环境给予的反馈来更新下次动作选择的概率。

算法1基于DDPG的任务调度算法JEDERL。

输入：待训练的策略网络，训练任务信息，异构计算平台信息。

输出：收敛的策略网络。

① 随机初始化在线critic网络Q(s，a|θQ)和actor网络μ(s，a|θμ)的参数θQ和θμ

② 初始化目标网络中的critic网络Q′和actor网络μ′：θQ′←θQ，θμ′←θμ

③ 初始化经验回放池M、随机性噪声pnoise等超参数

④ for episode=1，2，…，mdo

⑤s1=env.reset()

⑥ fort=1，2，…，tdo

3 实 验

3.1 实验环境及参数设置

使用5台异构服务器来构建异构计算平台硬件环境，其中每种异构计算资源包含多种计算类型，表示为DCPU={DCPU，1，DCPU，2，DCPU，3}，DGPU={DGPU，1，DGPU，2，DGPU，3}，DFPGA={DFPGA，1，DFPGA，2}，DDSP={DDSP，1，DDSP，2}，不同类型计算资源的计算能力存在差异。表1给出了每台服务器上承载的异构计算资源类型和数量。

表1 实验使用的计算资源类型及数目

随机生成25个不同拓扑结构的有向无环图任务作为数据集，这些任务包含不同大小和计算类型的子任务个数共计501个。设置DDPG中actor网络和critic网络的学习率分别为0.001和0.005，目标网络的更新率β为0.01，训练的批数量大小为16；在计算critic网络的未来奖励时，设置折扣因子为0.9。

3.2 实验结果与分析

将笔者提出的任务调度算法JEDERL与随机调度、先进先出调度、轮盘法调度、短任务优先调度以及基于设备嵌入的强化学习(Device Embedding Reinforcement Learning，DERL)算法进行对比。其中，随机调度算法(Random)在每一时刻随机选择平台上的某个就绪子任务进行调度；先进先出调度算法(FIFO)执行先到达的子任务；轮盘法调度算法(Roulette)按机器使用顺序为子任务分配执行节点；短任务优先调度算法(SJF)按任务大小排序，优先调度小任务；DERL算法的实现参照文献[17]，为未使用图嵌入技术对就绪子任务进行编码的基于DDPG的任务调度算法，将其与文中提出的算法进行对比，作为消融实验[18]。

对使用不同算法时任务的平均完成时间和最大完成时间进行对比分析，实验结果如图3所示。其中，横坐标为任务的编号，纵坐标为任务的完成时间，图中虚线表示任务的平均完成时间，实线表示任务的最大完成时间。由图3可以得到，JEDERL的任务平均完成时间相较于Random算法减少约27.8%，相较于先进先出调度算法减少约12.6%，相较于Roulette算法减少约28.6%，相较于短任务优先调度算法减少约 21.9%，相较于DERL算法减少约 5.3%；JEDERL的任务最大完成时间相较于Random算法减少约 26.9%，相较于FIFO算法减少约35.8%，相较于Roulette算法减少约49.3%，相较于SJF算法减少约 15.9%，相较于DERL算法减少约30.2%。实验结果表明，笔者提出的JEDERL算法通过对任务与计算资源的优化表征，可伸缩状态信息编码有效地提取了任务与资源的全局信息，使得任务以更好的顺序匹配到合适的计算资源，充分利用异构计算资源算力，从而有效减少了任务的平均完成时间和最大完成时间。

(a)随机调度

为了验证JEDERL算法的稳定性，进一步对比不同算法在任务数量、服务器数量变化时任务平均完成时间的大小。图4中的实验结果表明，当服务器数量确定时，任务平均完成时间随任务数量的增加而增加，这是由于有限的资源可以同时处理的任务量受限，造成任务堆积；在同一任务数量下，任务平均完成时间随服务器数量的增加有所减少，原因在于服务器数量的增加使得同一时间有更多的资源被用于任务执行，从而减少任务平均完成时间。将图4中不同服务器个数下的任务平均完成时间做均值处理，JEDERL算法优于Random算法约25.9%，优于DERL算法约6.4%，即JEDERL算法能够在变化的环境中保持其性能。

(a)平台中服务器个数为5

4 结束语

根据异构计算平台的特性，以最小化任务平均完成时间为优化目标设计模型，笔者提出了一种基于深度确定性策略梯度算法的任务调度算法，并使用图神经网络对有向无环图任务和计算资源进行嵌入编码，解决了异构计算平台上任务资源特征伸缩性差、缺少全局信息的问题。实验结果表明，笔者提出的算法优于随机调度、先进先出调度、短任务优先调度、轮盘法调度以及现有的强化学习调度算法。