一种DAG任务调度方法、装置、设备及存储介质

摘要

本申请公开了一种DAG任务调度方法、装置、设备及存储介质。该方法包括：按照有向图神经网络、顺序解码器的顺序构建网络模型，并以最小任务调度长度为目标定义网络模型的目标函数；获取DAG任务数据集，并对DAG任务数据集内每个DAG任务生成对应的信息矩阵；利用信息矩阵对网络模型进行训练，并根据目标函数利用强化学习更新网络模型的模型参数，以得到训练后的DAG任务调度模型；利用DAG任务调度模型确定待执行DAG任务内子任务的调度顺序，并根据调度顺序利用并行计算系统执行待执行DAG任务。能够缩短DAG任务调度长度，提高DAG任务并行执行效率，解决难以为DAG任务的最佳优先级分配收集足够多监督标签的问题。

权利要求

1.一种DAG任务调度方法，其特征在于，包括：

按照有向图神经网络、顺序解码器的顺序构建网络模型，并以最小任务调度长度为目标定义所述网络模型的目标函数；

获取DAG任务数据集，并对所述DAG任务数据集内每个所述DAG任务生成对应的信息矩阵；

利用所述信息矩阵对所述网络模型进行训练，并根据所述目标函数利用强化学习更新所述网络模型的模型参数，以得到训练后的DAG任务调度模型；

利用所述DAG任务调度模型确定待执行DAG任务内子任务的调度顺序，并根据所述调度顺序利用并行计算系统执行所述待执行DAG任务；

其中，所述利用所述信息矩阵对所述网络模型进行训练，并根据所述目标函数利用强化学习更新所述网络模型的模型参数，包括：将所述信息矩阵输入至所述网络模型，利用所述有向图神经网络根据所述子任务的特征和子任务间依赖关系输出得到每个子任务的向量表示；

利用所述顺序解码器，根据所述子任务的向量表示基于注意力机制和所述DAG任务的上下文环境对所述DAG任务内的子任务进行优先级排序；

根据所述优先级排序利用DAG任务调度模拟器计算所述DAG任务的任务调度长度；

根据所述任务调度长度和所述目标函数，利用强化学习更新所述网络模型的模型参数，直至所述网络模型收敛。

2.根据权利要求1所述的DAG任务调度方法，其特征在于，所述按照有向图神经网络、顺序解码器的顺序构建网络模型之前，还包括：基于聚合函数和非线性激活函数构建用于DAG任务特征学习的图卷积层；

按照输入层、K层图卷积层、输出层的顺序构建得到所述有向图神经网络。

3.根据权利要求1所述的DAG任务调度方法，其特征在于，所述按照有向图神经网络、顺序解码器的顺序构建网络模型之前，还包括：以DAG任务内子任务的优先级分配状态为变量，为所述DAG任务定义上下文环境的向量表达式；

基于注意力机制和所述上下文环境的向量表达式构建用于优先级排序的顺序解码器。

4.根据权利要求1所述的DAG任务调度方法，其特征在于，所述以最小任务调度长度为目标定义所述网络模型的目标函数，包括：以DAG任务在不同时间步下优先级排序对应的任务调度长度和任务调度长度下限为自变量，生成DAG任务的减速评价指标；所述任务调度长度下限根据DAG任务的关键路径的路径长度确定；

基于策略梯度算法和所述减速评价指标构建奖励函数；

基于所述奖励函数构建所述网络模型的目标函数。

5.根据权利要求1所述的DAG任务调度方法，其特征在于，所述获取DAG任务数据集，包括：配置DAG任务参数；所述DAG任务参数包括任务层数、目标结点的子结点个数、目标结点的子结点生成概率、相邻两个任务层之间连接边添加概率以及各个子任务的计算负载；

根据所述DAG任务参数生成DAG任务以得到所述DAG任务数据集。

6.根据权利要求1所述的DAG任务调度方法，其特征在于，所述对所述DAG任务数据集内每个所述DAG任务生成对应的信息矩阵，包括：根据所述DAG任务数据集内所述DAG任务中每个子任务的特征生成结点特征矩阵；

根据所述DAG任务数据集内不同子任务之间的连接关系生成邻接矩阵；

基于所述结点特征矩阵和所述邻接矩阵得到所述DAG任务对应的信息矩阵。

7.一种DAG任务调度装置，其特征在于，包括：

网络构建模块，用于按照有向图神经网络、顺序解码器的顺序构建网络模型，并以最小任务调度长度为目标定义所述网络模型的目标函数；

数据集获取模块，用于获取DAG任务数据集，并对所述DAG任务数据集内每个所述DAG任务生成对应的信息矩阵；

训练模块，用于利用所述信息矩阵对所述网络模型进行训练，并根据所述目标函数利用强化学习更新所述网络模型的模型参数，以得到训练后的DAG任务调度模型；

调度顺序确定模块，用于利用所述DAG任务调度模型确定待执行DAG任务内子任务的调度顺序，并根据所述调度顺序利用并行计算系统执行所述待执行DAG任务；

所述训练模块，还用于将所述信息矩阵输入至所述网络模型，利用所述有向图神经网络根据所述子任务的特征和子任务间依赖关系输出得到每个子任务的向量表示；利用所述顺序解码器，根据所述子任务的向量表示基于注意力机制和所述DAG任务的上下文环境对所述DAG任务内的子任务进行优先级排序；根据所述优先级排序利用DAG任务调度模拟器计算所述DAG任务的任务调度长度；根据所述任务调度长度和所述目标函数，利用强化学习更新所述网络模型的模型参数，直至所述网络模型收敛。

8.根据权利要求7所述的DAG任务调度装置，其特征在于，还包括：图卷积层构建单元，用于基于聚合函数和非线性激活函数构建用于DAG任务特征学习的图卷积层；

有向图神经网络构建单元，用于按照输入层、K层图卷积层、输出层的顺序构建得到所述有向图神经网络。

9.根据权利要求7所述的DAG任务调度装置，其特征在于，还包括：向量表达式定义单元，用于以DAG任务内子任务的优先级分配状态为变量，为所述DAG任务定义上下文环境的向量表达式；

顺序解码器构建单元，用于基于注意力机制和所述上下文环境的向量表达式构建用于优先级排序的顺序解码器，以得到所述解码器。

10.根据权利要求7所述的DAG任务调度装置，其特征在于，所述网络构建模块，包括：减速评价指标构建单元，用于以DAG任务在不同时间步下优先级排序对应的任务调度长度和任务调度长度下限为自变量，生成DAG任务的减速评价指标；所述任务调度长度下限根据DAG任务的关键路径的路径长度确定；

奖励函数构建单元，用于基于策略梯度算法和所述减速评价指标构建奖励函数；

目标函数构建单元，用于基于所述奖励函数构建所述网络模型的目标函数。

11.根据权利要求7所述的DAG任务调度装置，其特征在于，所述数据集获取模块，包括：任务参数配置单元，用于配置DAG任务参数；所述DAG任务参数包括任务层数、目标结点的子结点个数、目标结点的子结点生成概率、相邻两个任务层之间连接边添加概率以及各个子任务的计算负载；

任务生成单元，用于根据所述DAG任务参数生成DAG任务以得到所述DAG任务数据集。

12.根据权利要求7所述的DAG任务调度装置，其特征在于，所述数据集获取模块，包括：结点特征矩阵生成单元，用于根据所述DAG任务数据集内所述DAG任务中每个子任务的特征生成结点特征矩阵；

邻接矩阵生成单元，用于根据所述DAG任务数据集内不同子任务之间的连接关系生成邻接矩阵；

信息矩阵确定单元，用于基于所述结点特征矩阵和所述邻接矩阵得到所述DAG任务对应的信息矩阵。

13.一种电子设备，其特征在于，包括：

存储器，用于保存计算机程序；

处理器，用于执行所述计算机程序，以实现如权利要求1至6任一项所述的DAG任务调度方法。

14.一种计算机可读存储介质，其特征在于，用于存储计算机程序；其中计算机程序被处理器执行时实现如权利要求1至6任一项所述的DAG任务调度方法。

说明书

一种DAG任务调度方法、装置、设备及存储介质

技术领域

[0001] 本发明涉及任务调度技术领域，特别涉及一种DAG任务调度方法、装置、设备及存储介质。

背景技术

[0002] 目前，在高性能和复杂功能需求的推动下，并行计算系统越来越多地用于执行实时应用程序，如具有感知、规划和控制等复杂功能组件的对高性能和实时性要求极高的自动驾驶任务。DAG（Directed Acyclic Graph，有向无环图）任务常常用来表示类似实时应用程序的多个任务组件（子任务）之间复杂依赖关系和形式化描述细粒度的并行任务调度问题，即DAG任务调度问题。考虑到非抢占式任务模型可以避免任务迁移和切换开销，针对DAG任务的基于优先级的非抢占式调度受到广泛关注，该问题研究如何将给定的DAG任务非抢占式地调度到并行计算系统上执行，使得处理时间最短，是一个典型的NP（Non‑deterministic Polynomial Complete）完全问题。现有技术中，长期的并行计算实践积累了大量优秀的启发式调度算法，如表调度算法和聚类调度算法。但由于启发式策略的性质，这些算法无法为 DAG任务调度程序建立基本的设计原则，例如在不同DAG任务规模和配置下如何利用DAG任务执行时间和DAG任务图拓扑结构特征为各个子任务分配优先级，并且调度性能不理想。

发明内容

[0003] 有鉴于此，本发明的目的在于提供一种DAG任务调度方法、装置、设备及介质，能够缩短DAG任务调度长度，提高DAG任务并行执行效率。其具体方案如下：

[0004] 第一方面，本申请公开了一种DAG任务调度方法，包括：

[0005] 按照有向图神经网络、顺序解码器的顺序构建网络模型，并以最小任务调度长度为目标定义所述网络模型的目标函数；

[0006] 获取DAG任务数据集，并对所述DAG任务数据集内每个所述DAG任务生成对应的信息矩阵；

[0007] 利用所述信息矩阵对所述网络模型进行训练，并根据所述目标函数利用强化学习更新所述网络模型的模型参数，以得到训练后的DAG任务调度模型；

[0008] 利用所述DAG任务调度模型确定待执行DAG任务内子任务的调度顺序，并根据所述调度顺序利用并行计算系统执行所述待执行DAG任务。

[0009] 可选的，所述按照有向图神经网络、顺序解码器的顺序构建网络模型之前，还包括：

[0010] 基于聚合函数和非线性激活函数构建用于DAG任务特征学习的图卷积层；

[0011] 按照输入层、K层图卷积层、输出层的顺序构建得到所述有向图神经网络。

[0012] 可选的，所述按照有向图神经网络、顺序解码器的顺序构建网络模型之前，还包括：

[0013] 以DAG任务内子任务的优先级分配状态为变量，为所述DAG任务定义上下文环境的向量表达式；

[0014] 基于注意力机制和所述上下文环境的向量表达式构建用于优先级排序的顺序解码器。

[0015] 可选的，所述以最小任务调度长度为目标定义所述网络模型的目标函数，包括：

[0016] 以DAG任务在不同时间步下优先级排序对应的任务调度长度和任务调度长度下限为自变量，生成DAG任务的减速评价指标；所述任务调度长度下限根据DAG任务的关键路径的路径长度确定；

[0017] 基于策略梯度算法和所述减速评价指标构建奖励函数；

[0018] 基于所述奖励函数构建所述网络模型的目标函数。

[0019] 可选的，所述获取DAG任务数据集，包括：

[0020] 配置DAG任务参数；所述DAG任务参数包括任务层数、目标结点的子结点个数、目标结点的子结点生成概率、相邻两个任务层之间连接边添加概率以及各个子任务的计算负载；

[0021] 根据所述DAG任务参数生成DAG任务以得到所述DAG任务数据集。

[0022] 可选的，所述对所述DAG任务数据集内每个所述DAG任务生成对应的信息矩阵，包括：

[0023] 根据所述DAG任务数据集内所述DAG任务中每个子任务的特征生成结点特征矩阵；

[0024] 根据所述DAG任务数据集内不同子任务之间的连接关系生成邻接矩阵；

[0025] 基于所述结点特征矩阵和所述邻接矩阵得到所述DAG任务对应的信息矩阵。

[0026] 可选的，所述利用所述信息矩阵对所述网络模型进行训练，并根据所述目标函数利用强化学习更新所述网络模型的模型参数，包括：

[0027] 将所述信息矩阵输入至所述网络模型，利用所述有向图神经网络根据所述子任务的特征和子任务间依赖关系输出得到每个子任务的向量表示；

[0028] 利用所述顺序解码器，根据所述子任务的向量表示基于注意力机制和所述DAG任务的上下文环境对所述DAG任务内的子任务进行优先级排序；

[0029] 根据所述优先级排序利用DAG任务调度模拟器计算所述DAG任务的任务调度长度；

[0030] 根据所述任务调度长度和所述目标函数，利用强化学习更新所述网络模型的模型参数，直至所述网络模型收敛。

[0031] 第二方面，本申请公开了一种DAG任务调度装置，包括：

[0032] 网络构建模块，用于按照有向图神经网络、顺序解码器的顺序构建网络模型，并以最小任务调度长度为目标定义所述网络模型的目标函数；

[0033] 数据集获取模块，用于获取DAG任务数据集，并对所述DAG任务数据集内每个所述DAG任务生成对应的信息矩阵；

[0034] 训练模块，用于利用所述信息矩阵对所述网络模型进行训练，并根据所述目标函数利用强化学习更新所述网络模型的模型参数，以得到训练后的DAG任务调度模型；

[0035] 调度顺序确定模块，用于利用所述DAG任务调度模型确定待执行DAG任务内子任务的调度顺序，并根据所述调度顺序利用并行计算系统执行所述待执行DAG任务。

[0036] 可选的，所述DAG任务调度装置，还包括：

[0037] 图卷积层构建单元，用于基于聚合函数和非线性激活函数构建用于DAG任务特征学习的图卷积层；

[0038] 有向图神经网络构建单元，用于按照输入层、K层图卷积层、输出层的顺序构建得到所述有向图神经网络。

[0039] 可选的，所述DAG任务调度装置，还包括：

[0040] 向量表达式定义单元，用于以DAG任务内子任务的优先级分配状态为变量，为所述DAG任务定义上下文环境的向量表达式；

[0041] 顺序解码器构建单元，用于基于注意力机制和所述上下文环境的向量表达式构建用于优先级排序的顺序解码器，以得到所述解码器。

[0042] 可选的，所述网络构建模块，包括：

[0043] 减速评价指标构建单元，用于以DAG任务在不同时间步下优先级排序对应的任务调度长度和任务调度长度下限为自变量，生成DAG任务的减速评价指标；所述任务调度长度下限根据DAG任务的关键路径的路径长度确定；

[0044] 奖励函数构建单元，用于基于策略梯度算法和所述减速评价指标构建奖励函数；

[0045] 目标函数构建单元，用于基于所述奖励函数构建所述网络模型的目标函数。

[0046] 可选的，所述数据集获取模块，包括：

[0047] 任务参数配置单元，用于配置DAG任务参数；所述DAG任务参数包括任务层数、目标结点的子结点个数、目标结点的子结点生成概率、相邻两个任务层之间连接边添加概率以及各个子任务的计算负载；

[0048] 任务生成单元，用于根据所述DAG任务参数生成DAG任务以得到所述DAG任务数据集。

[0049] 可选的，所述数据集获取模块，包括：

[0050] 结点特征矩阵生成单元，用于根据所述DAG任务数据集内所述DAG任务中每个子任务的特征生成结点特征矩阵；

[0051] 邻接矩阵生成单元，用于根据所述DAG任务数据集内不同子任务之间的连接关系生成邻接矩阵；

[0052] 信息矩阵确定单元，用于基于所述结点特征矩阵和所述邻接矩阵得到所述DAG任务对应的信息矩阵。

[0053] 第三方面，本申请公开了一种电子设备，包括：

[0054] 存储器，用于保存计算机程序；

[0055] 处理器，用于执行所述计算机程序，以实现前述的DAG任务调度方法。

[0056] 第四方面，本申请公开了一种计算机可读存储介质，用于存储计算机程序；其中计算机程序被处理器执行时实现前述的DAG任务调度方法。

[0057] 本申请中，按照有向图神经网络、顺序解码器的顺序构建网络模型，并以最小任务调度长度为目标定义所述网络模型的目标函数；获取DAG任务数据集，并对所述DAG任务数据集内每个所述DAG任务生成对应的信息矩阵；利用所述信息矩阵对所述网络模型进行训练，并根据所述目标函数利用强化学习更新所述网络模型的模型参数，以得到训练后的DAG任务调度模型；利用所述DAG任务调度模型确定待执行DAG任务内子任务的调度顺序，并根据所述调度顺序利用并行计算系统执行所述待执行DAG任务。本申请中基于有向图神经网络和强化学习得到DAG任务调度模型，有向图神经网络能自动识别DAG任务内子任务相关的丰富特征，顺序解码器能够利用这些特征对子任务进行任务优先级排序，同时，利用强化学习优化模型实现最小化DAG任务调度长度的调度目标，能够缩短DAG任务调度长度，提高DAG任务并行执行效率，并且利用强化学习能够解决难以为DAG任务的最佳优先级分配收集足够多监督标签的问题。

附图说明

[0058] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。

[0059] 图1为本申请提供的一种DAG任务调度方法流程图；

[0060] 图2为本申请提供的一种具体的DAG任务调度系统结构图；

[0061] 图3为本申请提供的一种具体的有向图神经网络结构图；

[0062] 图4为本申请提供的一种具体的DAG任务调度模型训练方法流程图；

[0063] 图5为本申请提供的一种DAG任务调度装置结构示意图；

[0064] 图6为本申请提供的一种电子设备结构图。

具体实施方式

[0065] 为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

[0066] 现有技术中，长期的并行计算实践积累了大量优秀的启发式调度算法，如表调度算法和聚类调度算法，但由于启发式策略的性质，这些算法无法为 DAG 任务调度程序建立基本的设计原则，例如在不同DAG任务规模和配置下如何利用DAG任务执行时间和DAG任务图拓扑结构特征为各个子任务分配优先级，并且调度性能不理想。为克服上述技术问题，本申请提出一种DAG任务调度方法，能够缩短DAG任务调度长度，提高DAG任务并行执行效率。

[0067] 本申请实施例公开了一种DAG任务调度方法，参见图1所示，该方法可以包括以下步骤：

[0068] 步骤S11：按照有向图神经网络、顺序解码器的顺序构建网络模型，并以最小任务调度长度为目标定义所述网络模型的目标函数。

[0069] 本实施例中，首先按照有向图神经网络（DGNN，Directed  Graph Neural Network）、顺序解码器的顺序构建网络模型，并以最小任务调度长度为目标定义该网络模型的目标函数；其中，上述有向图神经网络用于识别DAG任务内子任务的任务特征并输出每个子任务对应的嵌入式表示，即向量表示，任务特征包括执行时间和依赖关系；上述顺序解码器用于根据有向图神经网络输出的嵌入式表示对所有子任务的优先级进行排序，输出子任务的优先级排序。目标函数用于指导网络模型的学习，以便网络模型最后能够实现根据输入的DAG任务输出该DAG任务的最小任务调度长度。其中，上述网络模型中还包括DAG任务调度模拟器，用于计算DAG任务在给定并行计算系统上的调度长度。

[0070] 在进行本实施例的详细描述之前，首先对本实施例中涉及的基础概念进行解释。并行计 算系统 ，一般可 描述为 一个四 元组 。其中 ：
是处理节点集合； 是处理节点
之间通信链路集合； 是处理节点的计算速度集合， 表
示  的计算速度，且满足 ；  是通信链路
带宽的集合， 表示通信链路 的带宽。

[0071] DAG任务，是指具有复杂依赖关系的、可在并行计算系统上并行执行的多个子任务 ，常 用 带 权的 有 向 无环 图 表 示 ，并 记 为 。其 中 ，是结点集合，每个结点表示一个子任务， 为子任务总
数。

[0072] 是有向边集合，有向边 表示从该边所连接的子任务 到其另一子任务 之间的通信和数据依赖关系， 必须在收到 的计算结果之后才能启动执行。 是计算负载的集合， 表示子任务 的计算负
载，并记所有子任务计算负载之和为 ，则有 。

[0073] 设Pred(ti)和Succ(ti) 分别为 的直接前驱子任务集和直接后继子任务集。称与Pred(ti)和Succ(ti)中所有子任务间的连接边的集合分别为 的入射边集 和出射边集 ；记 的入度和出度分别为 和 ，则有
和 。若 ，则称 是入口子任务
并记为tentry；若 ，则称 是出口子任务并记为texit。路径
是子任务结点的有限序列，且满足 ，有
 。如果一条路径同时包含入口子任务和出口子任务，则称该路径为完整路径。
λ的路径长度Λ(λ)是该路径上所有子任务的计算负载之和，即

[0074] 。

[0075] 路径长度最长的完整路径称为关键路径。每个子任务结点vi的原始特征xi除了包含任务负载、入度、出度结点级特征外，还包括关键路径长度和非关键路径长度，非关键路径长度可通过DAG任务总计算负载减去关键路径长度得到。例如图2所示，为一种具体的DAG任务调度系统，展示了一个含9个结点、具有唯一入口和出口的DAG任务，结点内的字符串表示子任务ID和计算负载。事实上，DAG任务可能有多个入口和出口，可以通过添加一个虚拟的入口子任务或出口子任务以及相应连接边，将其变成具有唯一入口和出口的DAG任务。除非特别说明，本实施例中均指后一类DAG任务，且满足子任务个数满足n远远大于并行计算系统节点数m。

[0076] 本实施例中，所述按照有向图神经网络、顺序解码器的顺序构建网络模型之前，还可以包括：基于聚合函数和非线性激活函数构建用于DAG任务特征学习的图卷积层；按照输入层、K层图卷积层、输出层的顺序构建得到所述有向图神经网络。利用上述有向图神经网络学习上述DAG任务内每个子任务的向量表示；

[0077] 上述向量表示，记做 ；

[0078] 如图3所示，设计有向图神经网络，它由输入层（input layer）、K层图卷积层（graph conv layer）和输出层（output layer）组成，输入层读取DAG任务的结点特征矩阵X和邻接矩阵A；第k层图卷积层的图卷积操作由聚合函数（aggregate函数）和非线性激活函数实现，如下：

[0079]             (1)

[0080]                               (2)

[0081] 其中，aggregate函数聚合来自子任务 的直接前驱发来的消息，update函数对聚合后的消息执行非线性变换；Pred(ti)为 的直接前驱子任务集。对于aggregate函数，它可以采用多种方式如取最大值、取平均值等，本专利采用注意力机制实现：

[0082]   (3)

[0083] 其中，αij表示子任务tj对ti的注意力系数，它通过训练学习得到。对于update函数，它可以是任意的非线性激活函数。不是一般性，本实施例中采用ReLu函数实现：

[0084] 即 ；

[0085] 输出层直接输出第K层图卷积层学习到的顶点嵌入式表示。可以理解的是，通过利用聚合函数和非线性激活函数构建的图卷积层，能更好的适应DAG任务图的有向特性，提取子任务间的依赖关系，能够识别子任务自身特征以及在DAG任务中与其余子任务的依赖关系，从而更加有效的学习子任务结点的嵌入式表示，以便为后续的子任务优先级排序提供更丰富的特征，进而提高优先级排序的准确性。

[0086] 本实施例中，所述按照有向图神经网络、顺序解码器的顺序构建网络模型之前，还可以包括：以DAG任务内子任务的优先级分配状态为变量，为所述DAG任务定义上下文环境的向量表达式；基于注意力机制和所述上下文环境的向量表达式构建用于优先级排序的顺序解码器。可以理解的是，上述解码器为顺序解码器用于为DAG任务的所有子任务排序，具体的根据有向图神经网络学习到的DAG任务所有n个子任务结点的嵌入式表示。

[0087] 顺序解码器基于注意力机制顺序选择子任务结点以生成大小为n的优先级排序，它对应一个优先级有序的子任务排列 且满足：优先级 。

[0088] 本实施例中顺序解码器可以将DAG任务优先级分配形式化描述为如下公式定义的概率分布：

[0089]                 (4)

[0090] 其中， 为待优化的网络参数。顺序解码器首先从概率分布 中采样具有最高优先级的子任务结点，然后再从 中采样次高优先级子任务结点，以此类
推，直至采样选出所有子任务结点。

[0091] 在每个时间步 ，顺序解码器按照如下规则选择子任务结点 并赋予其优先级 ：

[0092]                     (5)

[0093] 其中 ，argmax函数用于确定最大值自变量点集；条件概率分布按照如下公式计算得到：

[0094]  (6)

[0095] 其中，softmax为归一化指数函数； 为待训练的特征变换矩阵；tanh为激活函数；att为注意力函数； 是时间步 尚未分配优先级的子任务集合，已分配优先级的子任务集合记为 ，且满足 ，针对一个DAG任务的优先级排序过程中，集合及 会根据优先级分配状态实时更新；cont为顺序解码器实时子任务选择的上下文环境，可以理解的是，公式（6）中，将子任务的向量表示与上下文环境的向量表示进行比较，然后利用注意力机制分配子任务的权重；上下文环境的向量表示计算公式如下：

[0096] cont=W[contO; contU]+b,                         (7)

[0097] 其中，W 表示线性变换，“[;]”表示张量连接符；contO和contU分别为 和 对应的嵌入式表示，它们通过以下公式计算得到：

[0098]                           (8)

[0099]                           (9)

[0100] 其中，σ为非线性激活函数。由此基于注意力机制构建顺序解码器，将子任务结点的选择问题归结为从条件概率分布中随机选择子结点编号的问题，以根据子任务结点的向量表示，更加准确地确定子任务的优先级排序。

[0101] 本实施例中，所述以最小任务调度长度为目标定义所述网络模型的目标函数，可以包括：以DAG任务在不同时间步下优先级排序对应的任务调度长度和任务调度长度下限为自变量，生成DAG任务的减速评价指标；所述任务调度长度下限根据DAG任务的关键路径的路径长度确定；基于策略梯度算法和所述减速评价指标构建奖励函数；基于所述奖励函数构建所述网络模型的目标函数。可以理解的是，DAG任务调度问题可以建模表示为马尔科夫决策过程(MDP，Markov Decision Process)；一个基本的MDP通常可以用一个五元组来描述：

[0102] 。

[0103] 其中， 是所述顺序解码器n个时间步动作的集合，在时间步 的动作表示顺序解码器从DAG任务中选择子任务结点 并赋予其优先级 ； 是n个时
间步的状态集合；时间步 的状态 包括DAG任务所有子任务结点的嵌入式表示
以及已分配优先级的子任务 ；

[0104] 即 。

[0105] 表示环境即时返回值，用以评估顺序解码器上一个选择动作效果。由于DAG任务调度的目标是最小化任务调度长度，本实施例中基于减速评价指标设计一个奖励函数:

[0106]                     (10)

[0107] 其中， 表示在时间步 ，DAG任务优先级排序 对应的子任务 的调度长度， 表示在时间步
，DAG任务优先级排序 对应的子任务 的任务调度长度的下界。在一
个由m个计算节点组成的并行计算系统上， 可基于关键路径长度
计算，具体计算公式如下：

[0108]  (11)

[0109] 其中， 为根据优先级排序 确定的到子任务 关键路径长度，  为根据优先级排序 确定的到子任务 的所有子任务计算负载之和。

[0110] 在MDP中，假设状态转换矩阵Π是确定性的，因为对于给定的状态和动作，下一个状态的确定没有随机性，这是因为调度动作不执行任务，它只影响调度策略并改变任务的排列。最后，设折扣因子Δ为常量1，根据公式(4)和(10)，利用基于策略梯度算法，以最大化DAG任务优先级排序π对应的累计奖励的期望为目标，定义网络模型的目标函数J为：

[0111]       (12)

[0112] 其中， 表征指定DAG任务优先级顺序为从学习策略中采样得到的。

[0113] 步骤S12：获取DAG任务数据集，并对所述DAG任务数据集内每个所述DAG任务生成对应的信息矩阵。

[0114] 本实施例中，获取用于模型训练的DAG任务数据集，然后提取DAG任务数据集内每个DAG任务的信息矩阵，包括结点特征矩阵和邻接矩阵。具体的，本实施例中，所述对所述DAG任务数据集内每个所述DAG任务生成对应的信息矩阵，可以包括：根据所述DAG任务数据集内所述DAG任务中每个子任务的特征生成结点特征矩阵；所述结点特征矩阵为表征子任务的计算负载、归一化计算负载以及子任务的入度和出度的特征矩阵；根据所述DAG任务数据集内不同子任务之间的连接关系生成邻接矩阵；基于所述结点特征矩阵和所述邻接矩阵得到所述DAG任务对应的信息矩阵。

[0115] 本实施例中，所述获取DAG任务数据集，可以包括：配置DAG任务参数；所述DAG任务参数包括任务层数、目标结点的子结点个数、目标结点的子结点生成概率、相邻两个任务层之间连接边添加概率以及各个子任务的计算负载；根据所述DAG任务参数生成DAG任务以得到所述DAG任务数据集。因缺乏公开可用的大规模DAG任务数据集，本实施例中首先生成DAG任务，具体可以基于DAG任务参数利用并行任务生成模型获取。如嵌套fork‑join任务模型合成DAG任务；该模型由四个参数控制，分别是ndepth、nchild、pfork和ppert。其中，ndepth表示DAG任务层数或者深度；nchild表示某个结点的子结点个数；pfork表示为某结点生成子结点的概率；ppert在相邻两层结点之间随机添加连接边的概率。对于第k层中的每个子任务结点ti，其子结点tj和边eij是基于概率pfork生成的；第k+1层中的子结点数量由均匀分布nchild确定，即通过均匀分布确定目标结点下的子结点个数。此过程从入口子任务结点开始并重复ndepth次，从而创建具有ndepth层的DAG任务。此外，以概率ppert在DAG任务的第k层和第 k+1层结点之间随机添加连接边，ppert值越大生成的DAG任务的并行度就越高。最后，添加从最后一层结点到出口结点的边，并为每个子任务分配计算负载。其中，子任务的计算负载服从参数为μ(μ>0)和δ的正态分布，其中，μ表示子任务的平均计算负载，δ表示各个子任务的计算负载的标准差，当然，也可以假设为其它分布，只要保证各个子任务的计算负载为正值即可，此处不做限定。对构造好的DAG任务，提取每个子任务结点的特征并构造结点特征矩阵X；根据结点间互连关系，构造邻接矩阵A。

[0116] 步骤S13：利用所述信息矩阵对所述网络模型进行训练，并根据所述目标函数利用强化学习更新所述网络模型的模型参数，以得到训练后的DAG任务调度模型。

[0117] 本实施例中，构建得到网络模型后，首先进行模型参数初始化。按照特定策略如正态分布随机初始化、Xavier初始化或He Initialization初始化，对有向图神经网络各层参数W进行初始化，并对顺序解码器模型参数 进行初始化。

[0118] 然后，利用上述DAG任务数据集对应的信息矩阵对网络模型进行训练，其中，得到上述DAG任务数据集后，将上述DAG任务数据集划分为训练集和测试集，具体可以采用交叉验证法、留出法或留一法等划分方法，其中，测试集用于对上述网络模型进行训练，测试集用于对训练后的网络模型进行测试。

[0119] 本实施例中，所述利用所述信息矩阵对所述网络模型进行训练，并根据所述目标函数利用强化学习更新所述网络模型的模型参数，可以包括：

[0120] S130：将所述信息矩阵输入至所述网络模型，利用所述有向图神经网络根据所述子任务的特征和子任务间依赖关系输出得到每个子任务的向量表示；

[0121] S131：利用所述顺序解码器，根据所述子任务的向量表示基于注意力机制和所述DAG任务的上下文环境对所述DAG任务内的子任务进行优先级排序；

[0122] S132：根据所述优先级排序利用DAG任务调度模拟器计算所述DAG任务的任务调度长度；

[0123] S133：根据所述任务调度长度和所述目标函数，利用强化学习更新所述网络模型的模型参数，直至所述网络模型收敛。

[0124] 即以信息矩阵中包含的结点特征矩阵和邻接矩阵作为网络模型的输入，进行前向传播，经由有向图神经网络获取所有子任务的向量表示，顺序解码器输出子任务优先级排序，可以通过DAG任务模拟调度器按序调度子任务执行，并计算相应调度长度，然后按照公式(12)计算模型目标函数值；并按照一定策略如随机梯度下降或者Adam等算法，反向传播修正各层网络参数值。由此，利用强化学习算法，以最小化DAG任务调度长度为目标，通过奖励调度长度更短的DAG任务优先级排序，持续优化网络模型；因而得到的调度长度更短，并行计算效率更高。可有效避免难以为DAG任务的最佳优先级分配收集足够多监督标签的困难。

[0125] 具体的，网络模型训练，通过对公式(11)定义的目标函数J求关于 的梯度：

[0126]

[0127] (13)[0128] 其中， 为梯度算子。公式(12)中的模型梯度可以用蒙特卡洛随机梯度下降法来估计：

[0129]    (14)

[0130] 其中， 表示由数据集中随机采样得到的DAG任务的子任务的集合。利用随机梯度下降法或Adam算法优化目标函数，待目标函数值不再减少或者达到最大迭代次数，模型训练终止，此时得到的调度方案即为最佳调度方案。即基于蒙特卡洛随机梯度下降法估计目标函数梯度。由此，本实施例中基于有向图神经网络和目标函数实现对DAG任务的深度强化学习。其中，DAG任务调度长度可以通过DAG任务调度模拟器按照排列依次调度所有子任务到并行计算系统ARC上并行执行，并记录出口任务的完成时间，得到DAG任务调度长度。

[0131] 步骤S14：利用所述DAG任务调度模型确定待执行DAG任务内子任务的调度顺序，并根据所述调度顺序利用并行计算系统执行所述待执行DAG任务。

[0132] 本实施例中，训练得到DAG任务调度模型后，将待执行DAG任务的结点特征矩阵和邻接矩阵输入至该模型，将模型求得的最佳DAG任务调度顺序作为结果进行输出，并根据调度顺序利用并行计算系统执行待执行DAG任务。由此，针对DAG任务的非抢占式调度问题，本实施例基于深度强化学习和有向图神经网络进行任务优先级排序，进而确定任务的调度顺序，减少任务的执行时间，提高任务的执行效率。

[0133] 本实施例中还提出一种基于深度强化学习和有向图神经网络的DAG任务调度系统。如图2所示，该系统由输入模块、有向图神经网络、顺序解码器、调度长度计算模块以及模型参数更新模块组成。输入模块负责读取DAG任务的结点特征矩阵X和邻接矩阵A；有向图神经网络以X和A为输入，识别DAG任务的执行时间和依赖关系，学习子任务的嵌入式表示；这些嵌入式表示经由顺序解码器解码，输出得到所有子任务的优先级排序；调度长度计算模块根据该排序，调度它们在并行计算系统上执行，并将调度长度作为反馈信号，利用强化学习算法来更新模型参数。由此，上述基于深度强化学习和有向图神经网络的DAG任务调度系统以DAG任务为输入，通过有向图神经网络为DAG任务的每个子任务生成嵌入式表示，利用顺序解码器产生所有子任务的优先级排序，并计算该排序对应的任务调度长度或完工时间。系统以最小化DAG任务的调度长度为目标，计算出的调度长度被用作奖励信号以通过强化学习算法来更新模型。

[0134] 由上可见，本实施例中按照有向图神经网络、顺序解码器的顺序构建网络模型，并以最小任务调度长度为目标定义所述网络模型的目标函数；获取DAG任务数据集，并对所述DAG任务数据集内每个所述DAG任务生成对应的信息矩阵；利用所述信息矩阵对所述网络模型进行训练，并根据所述目标函数利用强化学习更新所述网络模型的模型参数，以得到训练后的DAG任务调度模型；利用所述DAG任务调度模型确定待执行DAG任务内子任务的调度顺序，并根据所述调度顺序利用并行计算系统执行所述待执行DAG任务。本申请中基于有向图神经网络和强化学习得到DAG任务调度模型，有向图神经网络能自动识别DAG任务内子任务相关的丰富特征，顺序解码器能够利用这些特征对子任务进行任务优先级排序，同时，利用强化学习优化模型实现最小化DAG任务调度长度的调度目标，能够缩短DAG任务调度长度，提高DAG任务并行执行效率，并且利用强化学习能够解决难以为DAG任务的最佳优先级分配收集足够多监督标签的问题。

[0135] 相应的，本申请实施例还公开了一种DAG任务调度装置，参见图5所示，该装置包括：

[0136] 网络构建模块11，用于按照有向图神经网络、顺序解码器的顺序构建网络模型，并以最小任务调度长度为目标定义所述网络模型的目标函数；

[0137] 数据集获取模块12，用于获取DAG任务数据集，并对所述DAG任务数据集内每个所述DAG任务生成对应的信息矩阵；

[0138] 训练模块13，用于利用所述信息矩阵对所述网络模型进行训练，并根据所述目标函数利用强化学习更新所述网络模型的模型参数，以得到训练后的DAG任务调度模型；

[0139] 调度顺序确定模块14，用于利用所述DAG任务调度模型确定待执行DAG任务内子任务的调度顺序，并根据所述调度顺序利用并行计算系统执行所述待执行DAG任务。

[0140] 由上可见，本实施例中按照有向图神经网络、顺序解码器的顺序构建网络模型，并以最小任务调度长度为目标定义所述网络模型的目标函数；获取DAG任务数据集，并对所述DAG任务数据集内每个所述DAG任务生成对应的信息矩阵；利用所述信息矩阵对所述网络模型进行训练，并根据所述目标函数利用强化学习更新所述网络模型的模型参数，以得到训练后的DAG任务调度模型；利用所述DAG任务调度模型确定待执行DAG任务内子任务的调度顺序，并根据所述调度顺序利用并行计算系统执行所述待执行DAG任务。本申请中基于有向图神经网络和强化学习得到DAG任务调度模型，有向图神经网络能自动识别DAG任务内子任务相关的丰富特征，顺序解码器能够利用这些特征对子任务进行任务优先级排序，同时，利用强化学习优化模型实现最小化DAG任务调度长度的调度目标，能够缩短DAG任务调度长度，提高DAG任务并行执行效率，并且利用强化学习能够解决难以为DAG任务的最佳优先级分配收集足够多监督标签的问题。

[0141] 在一些具体实施例中，所述DAG任务调度装置具体可以包括：

[0142] 图卷积层构建单元，用于基于聚合函数和非线性激活函数构建用于DAG任务特征学习的图卷积层；

[0143] 有向图神经网络构建单元，用于按照输入层、K层图卷积层、输出层的顺序构建得到所述有向图神经网络。

[0144] 在一些具体实施例中，所述DAG任务调度装置具体可以包括：

[0145] 向量表达式定义单元，用于以DAG任务内子任务的优先级分配状态为变量，为所述DAG任务定义上下文环境的向量表达式；

[0146] 顺序解码器构建单元，用于基于注意力机制和所述上下文环境的向量表达式构建用于优先级排序的顺序解码器，以得到所述解码器。

[0147] 在一些具体实施例中，所述网络构建模块11具体可以包括：

[0148] 减速评价指标构建单元，用于以DAG任务在不同时间步下优先级排序对应的任务调度长度和任务调度长度下限为自变量，生成DAG任务的减速评价指标；所述任务调度长度下限根据DAG任务的关键路径的路径长度确定；

[0149] 奖励函数构建单元，用于基于策略梯度算法和所述减速评价指标构建奖励函数；

[0150] 目标函数构建单元，用于基于所述奖励函数构建所述网络模型的目标函数。

[0151] 在一些具体实施例中，所述数据集获取模块12具体可以包括：

[0152] 任务参数配置单元，用于配置DAG任务参数；所述DAG任务参数包括任务层数、目标结点的子结点个数、目标结点的子结点生成概率、相邻两个任务层之间连接边添加概率以及各个子任务的计算负载；

[0153] 任务生成单元，用于根据所述DAG任务参数生成DAG任务以得到所述DAG任务数据集。

[0154] 在一些具体实施例中，所述数据集获取模块12具体可以包括：

[0155] 结点特征矩阵生成单元，用于根据所述DAG任务数据集内所述DAG任务中每个子任务的特征生成结点特征矩阵；

[0156] 邻接矩阵生成单元，用于根据所述DAG任务数据集内不同子任务之间的连接关系生成邻接矩阵；

[0157] 信息矩阵确定单元，用于基于所述结点特征矩阵和所述邻接矩阵得到所述DAG任务对应的信息矩阵。

[0158] 在一些具体实施例中，所述训练模块13具体可以包括：

[0159] 向量表示确定单元，用于将所述信息矩阵输入至所述网络模型，利用所述有向图神经网络根据所述子任务的特征和子任务间依赖关系输出得到每个子任务的向量表示；

[0160] 优先级排序确定单元，用于利用所述顺序解码器，根据所述子任务的向量表示基于注意力机制和所述DAG任务的上下文环境对所述DAG任务内的子任务进行优先级排序；

[0161] 任务调度长度确定单元，用于根据所述优先级排序利用DAG任务调度模拟器计算所述DAG任务的任务调度长度；

[0162] 模型优化单元，用于根据所述任务调度长度和所述目标函数，利用强化学习更新所述网络模型的模型参数，直至所述网络模型收敛。

[0163] 进一步的，本申请实施例还公开了一种电子设备，参见图6所示，图中的内容不能被认为是对本申请的使用范围的任何限制。

[0164] 图6为本申请实施例提供的一种电子设备20的结构示意图。该电子设备20，具体可以包括：至少一个处理器21、至少一个存储器22、电源23、通信接口24、输入输出接口25和通信总线26。其中，所述存储器22用于存储计算机程序，所述计算机程序由所述处理器21加载并执行，以实现前述任一实施例公开的DAG任务调度方法中的相关步骤。

[0165] 本实施例中，电源23用于为电子设备20上的各硬件设备提供工作电压；通信接口24能够为电子设备20创建与外界设备之间的数据传输通道，其所遵循的通信协议是能够适用于本申请技术方案的任意通信协议，在此不对其进行具体限定；输入输出接口25，用于获取外界输入数据或向外界输出数据，其具体的接口类型可以根据具体应用需要进行选取，在此不进行具体限定。

[0166] 另外，存储器22作为资源存储的载体，可以是只读存储器、随机存储器、磁盘或者光盘等，其上所存储的资源包括操作系统221、计算机程序222及包括DAG任务在内的数据223等，存储方式可以是短暂存储或者永久存储。

[0167] 其中，操作系统221用于管理与控制电子设备20上的各硬件设备以及计算机程序222，以实现处理器21对存储器22中海量数据223的运算与处理，其可以是Windows Server、Netware、Unix、Linux等。计算机程序222除了包括能够用于完成前述任一实施例公开的由电子设备20执行的DAG任务调度方法的计算机程序之外，还可以进一步包括能够用于完成其他特定工作的计算机程序。

[0168] 进一步的，本申请实施例还公开了一种计算机存储介质，所述计算机存储介质中存储有计算机可执行指令，所述计算机可执行指令被处理器加载并执行时，实现前述任一实施例公开的DAG任务调度方法步骤。

[0169] 本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其它实施例的不同之处，各个实施例之间相同或相似部分互相参见即可。对于实施例公开的装置而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。

[0170] 结合本文中所公开的实施例描述的方法或算法的步骤可以直接用硬件、处理器执行的软件模块，或者二者的结合来实施。软件模块可以置于随机存储器（RAM）、内存、只读存储器（ROM）、电可编程ROM、电可擦除可编程ROM、寄存器、硬盘、可移动磁盘、CD‑ROM、或技术领域内所公知的任意其它形式的存储介质中。

[0171] 最后，还需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

[0172] 以上对本发明所提供的一种DAG任务调度方法、装置、设备及介质进行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。