一种基于图神经网络的资源调度方法

摘要

本发明公开了一种基于图神经网络的资源调度方法，根据实际的处理器数量及各个处理器的算力，将输入的图神经网络进行分割；根据当前处理器的计算能力及历史任务执行效果，将各个子任务分配到各处理器上执行；跟踪分配到各处理器任务执行情况，根据任务执行情况对任务调度进行优化。本发明结合现有计算资源将总的计算任务分割成子任务集合，以便适应不同的计算资源组合，估计计算资源处理完目前正在处理的任务以及当前待计算任务所需的时间进行任务调度，以提高计算资源的利用率；根据当前任务的执行情况判断该任务与分配得到的计算资源是否亲和，决定是否对正在执行的任务进行再拆分以及计算资源再分配，进一步提高计算效率。

权利要求

1.一种基于图神经网络的资源调度方法，其特征在于，包括以下步骤：根据实际的处理器数量及各个处理器的算力，将输入的图神经网络进行分割，得到子任务集合，其过程包括：

输入一个图神经网络；将处理器按其浮点计算能力降序排序，并对处理器依次编号为

1，2，..，numProcessor；根据实际的处理器数量及各个处理器的算力确定子任务的数量及规模；将图神经网络按照确定的数量和规模分割子任务，得到子任务集合并输出；

图神经网络每一层分割的子任务数等于处理器数量numProcessor；Hashrate(i)表示处理器i的算力，subTaskScale(j，i)表示图神经网络第j层网络所分割出的第i个子任务的规模，并通过以下公式计算：

根据当前处理器的算力及历史任务执行效果，将子任务集合中的各个子任务分配到各处理器上执行，将子任务集合中的各个子任务分配到各处理器上执行的过程，包括：步骤S21：输入子任务集合；

步骤S22：判断当前子任务集合是否为空，是则结束，否则转步骤S23；

步骤S23：判断当前子任务集合中是否存在依赖准备完毕的任务，是则转步骤S24，否则转步骤S22；

步骤S24：选择依赖准备完毕的最低层任务中规模最大的任务nextTsak；

步骤S25：对每个处理器，根据历史处理器计算任务的速率velocity估计该处理器执行完当前任务curTask及当前待执行任务nextTask所需的时间，根据评估的时间给处理器评分，预估时间越短分值越高；

步骤S26：选取当前分值最高的处理器P，将当前待执行任务nextTask分配给处理器P执行，转步骤S22；

其中，跟踪分配到各处理器的任务执行时间及任务规模完成情况，确定任务执行情况，根据任务执行情况对任务调度进行优化，包括：设跟踪任务为y，其所分配的处理器为x，跟踪y在x上的执行情况，若执行情况良好，则结束；否则为任务y未被执行的部分进行计算资源再分配；其中跟踪y在x上的执行情况的过程，包括：步骤S31：设任务y已经执行的时间为t，初始值为0，T为一个基准变量，初始值为a*time[x]，0＜a＜1；

步骤S32：统计任务y执行的时间；

步骤S33：判断任务y执行时间是否等于b*time[x]，0＜b＜a，是则确定任务y执行情况良好；否则转步骤S34；

步骤S34：判断任务y执行时间是否等于T，是则转步骤S35，否则转步骤S32；

步骤S35：判断已经计算完成的任务规模是否大于或等于c*t*velocity[P]，velocity[P]表示当前分值最高的处理器计算任务的速率，0＜c＜1，转步骤S34；否则确定任务执行情况差；

为任务y未被执行的部分进行计算资源再分配的过程，包括：步骤S41：获取任务y未执行部分再分配后可执行的最长时间为maxTime＝time[x]‑t；

步骤S42：给当前所有处理器评分，按分数降序排序并依次编号为1～numProcessor；

步骤S43：设选取的处理器中编号最大为k，初始k＝1；

步骤S44：选取处理器1～k执行任务，将任务平均分割成k份，预计分配给处理器1～k；

步骤S45：统计各处理器执行完分配的任务所需的时间，并将结果求和，得到本任务执行完成所需的预估时间estimateTime；

步骤S46：判断预估时间estimateTime是否小于maxTime或k等于处理器数量numProcessor，是则转步骤S48；否则转步骤S47；

步骤S47：k在原基础上加1，转步骤S44；

步骤S48：将任务分配给处理器1～k执行。

2.根据权利要求1所述的基于图神经网络的资源调度方法，其特征在于，所述步骤S25中实现的过程，包括：

步骤S251：计算当前的每个处理器i执行上一个任务的速率velocity[i]，设lastTime[i]表示处理器i上一次执行一个任务所需的时间，该任务规模表示为scale[i]，则处理器i执行上一任务的速率为：velocity[i]＝scale[i]/lastTime[i]；

步骤S252：预估处理器i执行完当前任务及当前待执行任务所需的时间time[i]，设处理器i当前正在执行的任务剩余规模为curScale[i]，待处理任务的规模为nextScale，则预估处理器i执行完当前任务及当前待执行任务所需的时间为：time[i]＝velocity[i]*(curScale[i]+nextScale)；

步骤S253：将time[i]归一化得到timenormalize[i]；

步骤S254：计算处理器得分为scores[i]＝(1‑timenormalize[i])*100。

3.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质存储有计算机指令，所述计算机指令用于使所述计算机执行如权利要求1‑2任一项所述的基于图神经网络的资源调度方法。

4.一种计算机设备，其特征在于，包括：存储器和处理器，所述存储器和所述处理器之间互相通信连接，所述存储器存储有计算机指令，所述处理器通过执行所述计算机指令，从而执行如权利要求1‑2任一项所述的基于图神经网络的资源调度方法。

说明书

一种基于图神经网络的资源调度方法

技术领域

[0001] 本发明涉及数据处理技术领域，具体涉及一种基于图神经网络的资源调度方法。

背景技术

[0002] 图神经网络(Graph Neural Network，GNN)是一类基于深度学习的处理非欧氏空间信息的方法，近年来，对于GNN的研究成为深度学习领域的研究热点。GNN是一种连接模
型，它通过图的节点之间的消息传递来捕捉图的依赖关系。与标准神经网络不同的是，图神
经网络保留了一种状态，可以表示来自其邻域的具有任意深度的信息。图卷积网络(Graph 
Convolution Networks,GCN)是一类非常强大的用于图数据的神经网络架构，其强大的体
现在即使是随机初始化的两层GCN也可以生成图网络中节点的有用特征表征。因此GCN被广
泛应用于各研究领域，基于GCN的推理是其重要应用之一。

[0003] GCN的推理任务属于计算密集型任务，因此如何协调现有计算资源对GCN推理进行加速是一个重要的研究方向。现有对于GCN推理加速优化方法较为单一，常见的方法是截止
时间优先(Earliest Deadline First，EDF)。在该方法中对于每一个新的就绪状态，调度器
都是从那些已就绪但还没有完全处理完毕的任务中选择最早截止时间的任务，并将执行该
任务所需的资源分配给它。在有新任务到来时，调度器必须立即计算截止时间，排出新的定
序，即正在运行的任务被剥夺，并且按照新任务的截止时间决定是否调度该新任务。但这种
方法不能根据处理器的计算能力和实时处理情况动态地进行任务调度，没有考虑异构系统
处理器和任务之间的亲和性，不能根据任务实际执行情况对调度方案进行调整，这使得任
务执行效率和计算资源利用率相对较低。

发明内容

[0004] 因此，本发明要解决的技术问题在于克服现有技术中的任务执行效率和计算资源利用率低的缺陷，因此提供一种基于图神经网络的资源调度方法，综合考虑处理器的计算
能力及实时处理情况对计算任务进行调度，减少计算资源浪费，根据处理器的对任务的实
际执行情况进行调度策略上的调整，提高执行效率。

[0005] 为达到上述目的，本发明提供以下技术方案：

[0006] 第一方面，本发明实施例提供一种基于图神经网络的资源调度方法，包括以下步骤：

[0007] 根据实际的处理器数量及各个处理器的算力，将输入的图神经网络进行分割，得到子任务集合；

[0008] 根据当前处理器的计算能力及历史任务执行效果，将子任务集合中的各个子任务分配到各处理器上执行；

[0009] 跟踪分配到各处理器的任务执行时间及任务规模完成情况，确定任务执行情况，根据任务执行情况对任务调度进行优化。

[0010] 在一实施例中，根据实际的处理器数量及各个处理器的算力，将图神经网络进行分割的过程，包括：

[0011] 输入一个图神经网络；

[0012] 将处理器按其浮点计算能力降序排序，并对处理器依次进行编号；

[0013] 根据实际的处理器数量及各个处理器的算力确定子任务的数量及规模；

[0014] 将图神经网络按照确定的数量和规模分割子任务，得到子任务集合并输出。

[0015] 在一实施例中，通过以下公式计算确定子任务的数量及规模：

[0016]

[0017] 其中，subTaskScale(j,i)表示图神经网络的第j层网络的第i个子任务，处理器数量为numProcessor，其中1≤i≤numProcessor；Hashrate(i)表示处理器i的算力，floor表
示向下取整。

[0018] 在一实施例中，根据当前处理器的计算能力及历史任务执行效果，将子任务集合中的各个子任务分配到各处理器上执行的过程，包括：

[0019] 步骤S21:输入子任务集合；

[0020] 步骤S22:判断当前子任务集合是否为空，是则结束，否则转步骤S23；

[0021] 步骤S23:判断当前子任务集合中是否存在依赖准备完毕的任务，是则转步骤S24，否则转步骤S22；

[0022] 步骤S24：选择依赖完毕最低层任务中规模最大的任务nextTsak；

[0023] 步骤S25：对每个处理器，根据历史处理器计算任务的速率估计该处理器执行完当前任务curTask及当前待执行任务nextTask所需的时间，根据评估的时间给处理器评分，预
估时间越短分值越高；

[0024] 步骤S26：选取当前分值最高的处理器P，将当前待执行任务nextTask分配给处理器P执行，转步骤S22。

[0025] 在一实施例中，所述步骤S25中实现的过程，包括：

[0026] 步骤S251：计算当前的每个处理器i执行上一个任务的速率velocity[i]，设lastTime[i]表示处理器i上一次执行一个任务所需的时间，该任务规模表示为scale[i]，
则处理器i执行上一任务的速率为：velocity[i]＝scale[i]/lastTime[i]；

[0027] 步骤S252：预估处理器i执行完当前任务及当前待执行任务所需的时间time[i]，设处理器i当前正在执行的任务剩余规模为curScale[i]，待处理任务的规模为nextScale，
则预估处理器i执行完当前任务及当前待执行任务所需的时间为：time[i]＝velocity[i]*
(curScale[i]+nextScale)；

[0028] 步骤S253：将time[i]归一化得到timenormalize[i]；

[0029] 步骤S254：计算处理器得分为scores[i]＝(1‑timenormalize[i])*100。

[0030] 在一实施例中，所述跟踪分配到各处理器的任务执行时间及任务规模完成情况，确定任务执行情况，根据任务执行情况对任务调度进行优化的过程，包括：

[0031] 设跟踪任务为y，其所分配的处理器为x，跟踪y在x上的执行情况，若执行情况良好，则结束；否则为任务y为被执行的部分进行计算资源再分配；其中跟踪y在x上的执行情
况的过程，包括：

[0032] 步骤S31：设任务y已经执行的时间为t，初始值为0，T为一个基准变量，初始值为a*time[x]，0

[0033] 步骤S32：统计任务y执行的时间；

[0034] 步骤S33：判断任务y执行时间是否等于b*time[x]，0

[0035] 步骤S34：判断任务y执行时间是否等于T，是则转步骤S35，否则转步骤S32；

[0036] 步骤S35：判断已经计算完成的任务规模是否大于或等于c*t*velocity[P]，0

[0037] 在一实施例中，为任务y为被执行的部分进行计算资源再分配的过程，包括：

[0038] 步骤S41：获取任务y未执行部分再分配后可执行的最长时间为maxTime＝time[x]‑t；

[0039] 步骤S42：给当前所有处理器评分，按分数降序排序并依次编号为1～numProcessor；

[0040] 步骤S43：设选取的处理器中编号最大为k，初始k＝1；

[0041] 步骤S44：选取处理器1～k执行任务，将任务平均分割成k份，预计分配给处理器1～k；

[0042] 步骤S45：统计各处理器执行完分配的任务所需的时间，并将结果求和，得到本任务执行完成所需的预估时间estimateTime；

[0043] 步骤S46：判断预估时间estimateTime是否小于maxTime或k等于处理器数量numProcessor，是则转步骤S48；否则转步骤S47；

[0044] 步骤S47：k在原基础上加1，转步骤S44；

[0045] 步骤S48：将任务分配给处理器1～k执行。

[0046] 第二方面，本发明实施例提供一种计算机可读存储介质，所述计算机可读存储介质存储有计算机指令，所述计算机指令用于使所述计算机执行本发明实施例第一方面的基
于图神经网络的资源调度方法。

[0047] 第三方面，本发明实施例提供一种计算机设备，包括：存储器和处理器，所述存储器和所述处理器之间互相通信连接，所述存储器存储有计算机指令，所述处理器通过执行
所述计算机指令，从而执行本发明实施例第一方面的基于图神经网络的资源调度方法。

[0048] 本发明技术方案，具有以下优点：

[0049] 本发明提供了一种基于图神经网络的资源调度方法，首先结合现有计算资源将总的计算任务分割成子任务集合，以便适应不同的计算资源组合，然后结合任务之间的依赖
关系选取当前待计算的任务，并根据计算资源的历史表现情况，估计计算资源处理完目前
正在处理的任务以及当前待计算任务所需的时间，依据该预估时间进行任务调度，以提高
计算资源的利用率，降低执行任务的时间；最后根据当前任务的执行情况判断该任务与分
配得到的计算资源是否亲和，来决定是否对正在执行的任务进行再拆分以及计算资源再分
配，保证系统的高吞吐率及低延迟，进一步提高计算效率，适用于大部分基于图神经网络搭
建的智能计算系统。

附图说明

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

[0051] 图1本发明实施例中提供的基于图神经网络的资源调度方法的一个具体示例的工作流程图；

[0052] 图2为本发明实施例中提供的任务分割的流程图；

[0053] 图3本发明实施例中提供的子任务调度的流程图；

[0054] 图4本发明实施例中提供的给处理器评分的流程图；

[0055] 图5为本发明实施例对任务调度进行优化的总流程图；

[0056] 图6为本发明实施例提供的进行计算资源再分配的流程图；

[0057] 图7为本发明实施例提供的计算机设备一个具体示例的组成图。

具体实施方式

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

[0059] 此外，下面所描述的本发明不同实施方式中所涉及的技术特征只要彼此之间未构成冲突就可以相互结合。

[0060] 实施例1

[0061] 本发明实施例提供一种基于图神经网络的资源调度方法，主要应用在混合异构系统和多核设备上，适用于大部分基于图神经网络搭建的智能计算系统，例如推荐系统，自然
语言处理系统，知识图谱等，如图1所示，该方法包括以下步骤：

[0062] 步骤S1：根据实际的处理器数量及各个处理器的算力，将输入的图神经网络进行分割，得到子任务集合。

[0063] 在本发明实施例中的图神经网络采用图卷积网络GCN，任务分割的流程如图2所示，包括：

[0064] 步骤S11：输入一个GCN；

[0065] 步骤S12：将处理器按其浮点计算能力降序排序，并对处理器依次进行编号为1,2,...,numProcessor；

[0066] 步骤S13：根据实际的处理器数量及各个处理器的算力确定子任务的数量及规模，通过以下公式计算：

[0067]

[0068] 其中，subTaskScale(j,i)表示GCN的第j层网络的第i个子任务，其中1≤i≤numProcessor；Hashrate(i)表示处理器i的算力，floor表示向下取整；

[0069] 步骤S14：将图神经网络每层网路按照确定的数量和规模分割子任务，得到子任务集合，得到子任务集合并输出。

[0070] 步骤S2：根据当前处理器的计算能力及历史任务执行效果，将子任务集合中的各个子任务分配到各处理器上执行。

[0071] 该步骤主要为子任务调度的过程，具体执行的过程如图3所示，包括：

[0072] 步骤S21:输入子任务集合；

[0073] 步骤S22:判断当前子任务集合是否为空，是则结束，否则转步骤S23；

[0074] 步骤S23:判断当前子任务集合中是否存在依赖准备完毕的任务，是则转步骤S24，否则转步骤S22；

[0075] 步骤S24：选择依赖完毕最低层任务中规模最大的任务nextTsak；

[0076] 本发明实施例中，每个任务表示为subTask(j,i)＝(Dn,Flag)，其中j和i表示该任务为GCN网络的第j层的第i个子任务；Dn表示该任务依赖于GCN网络的第j‑1层的第n个任务
的结果，Flag＝1表示该任务的依赖已经准备好，该任务可被处理器执行，初始第一层的任
务的Flag＝1，在此基础上选取j最小的任务，并在选取j最小的任务的基础上选取规模最大
的任务作为当前待执行的任务nextTsak。

[0077] 步骤S25：对每个处理器，根据历史处理器计算任务的速率估计该处理器执行完当前任务curTask及当前待执行任务nextTask所需的时间，根据评估的时间给处理器评分，预
估时间越短分值越高；

[0078] 步骤S26：选取当前分值最高的处理器P(1≤P≤numProcessor)，将当前待执行任务nextTask分配给处理器P执行，转步骤S22。

[0079] 上述步骤S25中实现的过程，如图4所示，包括：

[0080] 步骤S251：计算当前的每个处理器i(1≤i≤numProcessor)执行上一个任务的速率velocity[i]，对于当前的每个处理器i(1≤i≤numProcessor)，设lastTime[i]表示处理
器i上一次执行一个任务所需的时间，该任务规模表示为scale[i]，则处理器i执行上一任
务的速率为：

[0081] velocity[i]＝scale[i]/lastTime[i]；

[0082] 步骤S252：预估处理器i执行完当前任务及当前待执行任务所需的时间time[i]，设处理器i当前正在执行的任务剩余规模为curScale[i]，待处理任务的规模为nextScale，
则预估处理器i执行完当前任务及当前待执行任务所需的时间为：time[i]＝velocity[i]*
(curScale[i]+nextScale)；

[0083] 步骤S253：将time[i]归一化得到timenormalize[i]；

[0084] 步骤S254：计算处理器得分为scores[i]＝(1‑timenormalize[i])*100。

[0085] 步骤S3：跟踪分配到各处理器的任务执行时间及任务规模完成情况，确定任务执行情况，根据任务执行情况对任务调度进行优化。

[0086] 对任务调度进行优化的总流程如图5所示，设跟踪任务为y，其所分配的处理器为x，跟踪y在x上的执行情况，若执行情况良好，则结束；否则为任务y为被执行的部分进行计
算资源再分配；其中跟踪y在x上的执行情况的过程，如图6所示，包括：

[0087] 步骤S31：设任务y已经执行的时间为t，初始值为0，T为一个基准变量，初始值为a*time[x]，0

[0088] 步骤S32：统计任务y执行的时间；

[0089] 步骤S33：判断任务y执行时间是否等于b*time[x]，0

[0090] 步骤S34：判断任务y执行时间是否等于T，是则转步骤S35，否则转步骤S32；

[0091] 步骤S35：判断已经计算完成的任务规模是否大于或等于c*t*velocity[P]，0

[0092] 在一具体实施例中 仅作为举例不以此为限，其根据实际经验值确定。

[0093] 如图7所示，为任务y为被执行的部分进行计算资源再分配的过程，包括：

[0094] 步骤S41：获取任务y未执行部分再分配后可执行的最长时间为maxTime＝time[x]‑t；

[0095] 步骤S42：给当前所有处理器评分，按分数降序排序并依次编号为1～numProcessor；

[0096] 步骤S43：设选取的处理器中编号最大为k，初始k＝1；

[0097] 步骤S44：选取处理器1～k执行任务，将任务平均分割成k份，预计分配给处理器1～k；

[0098] 步骤S45：统计各处理器执行完分配的任务所需的时间，并将结果求和，得到本任务执行完成所需的预估时间estimateTime；

[0099] 步骤S46：判断预估时间estimateTime是否小于maxTime或k等于处理器数量numProcessor，是则转步骤S48；否则转步骤S47；

[0100] 步骤S47：k在原基础上加1，转步骤S44；

[0101] 步骤S48：将任务分配给处理器1～k执行。

[0102] 在本发明实施例提供的基于图神经网络的资源调度方法，首先结合现有计算资源将总的计算任务分割成子任务集合，以便适应不同的计算资源组合，然后结合任务之间的
依赖关系选取当前待计算的任务，并根据计算资源的历史表现情况，估计计算资源处理完
目前正在处理的任务以及当前待计算任务所需的时间，依据该预估时间进行任务调度，以
提高计算资源的利用率，降低执行任务的时间；最后根据当前任务的执行情况判断该任务
与分配得到的计算资源是否亲和，来决定是否对正在执行的任务进行再拆分以及计算资源
再分配，保证系统的高吞吐率及低延迟，进一步提高计算效率。

[0103] 实施例2

[0104] 本发明实施例提供一种计算机设备，如图7所示，该设备可以包括处理器51和存储器52，其中处理器51和存储器52可以通过总线或者其他方式连接，图7以通过总线连接为
例。

[0105] 存储器52作为一种非暂态计算机可读存储介质，可用于存储非暂态软件程序、非暂态计算机可执行程序以及模块，如本发明实施例中的对应的程序指令/模块。处理器51通
过运行存储在存储器52中的非暂态软件程序、指令以及模块，从而执行处理器的各种功能
应用以及数据处理，即实现上述方法实施例1中的基于图神经网络的资源调度方法。

[0106] 存储器52可以包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需要的应用程序；存储数据区可存储处理器51所创建的数据等。此外，存储
器52可以包括高速随机存取存储器，还可以包括非暂态存储器，例如至少一个磁盘存储器
件、闪存器件、或其他非暂态固态存储器件。在一些实施例中，存储器52可选包括相对于处
理器51远程设置的存储器，这些远程存储器可以通过网络连接至处理器51。上述网络的实
例包括但不限于互联网、企业内部网、企业内网、移动通信网及其组合。

[0107] 一个或者多个模块存储在存储器52中，当被处理器51执行时，执行实施例1中的基于图神经网络的资源调度方法。

[0108] 上述计算机设备具体细节可以对应参阅实施例1中对应的相关描述和效果进行理解，此处不再赘述。

[0109] 本领域技术人员可以理解，实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成的程序可存储于一计算机可读取存储介质中，该程
序在执行时，可包括如上述各方法的实施例的流程。其中，存储介质可为磁碟、光盘、只读存
储记忆体(Read‑Only Memory，ROM)、随机存储记忆体(Random Access Memory，RAM)、快闪
存储器(Flash Memory)、硬盘(Hard Disk Drive，缩写：HDD)或固态硬盘(Solid‑State 
Drive，SSD)等；存储介质还可以包括上述种类的存储器的组合。

[0110] 显然，上述实施例仅仅是为清楚地说明所作的举例，而并非对实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或
变动。这里无需也无法对所有的实施方式予以穷举。而由此所引申出的显而易见的变化或
变动仍处于本发明创造的保护范围之中。