本发明涉及任务资源调度领域，具体涉及一种基于强化学习的深度学习任务调度方法。
背景技术：
随着以深度学习技术为核心的产品和服务逐渐融入我们的日常生活，工业界和学术界纷纷开始投入更大规模的人力、物力和财力支持该领域的研发。各个企业开始基于主流的cpu gpu异构集群来构建自身的深度学习研发平台，同时处理多种不同的深度学习任务，从而满足多用户的研发需求。如何能够最大程度发挥异构集群平台的计算能力，提高整个集群资源利用率和任务完成效率，同时降低运维成本，是一个极具挑战的任务。
当前数据中心的任务调度策略大多是基于启发式算法，不需要挖掘任务内在的性能特征，通常将任务当作一个黑盒子。这种调度算法虽然泛化能力较强，但是缺乏细粒度任务性能的挖掘。近年来也逐渐有一些基于预测的深度学习任务调度算法，但该类调度算法存在两个方面的不足：一方面预测精度很有限，该类算法往往基于任务自身迭代性或收敛性来进行预测，对于更加复杂的网络模型预测偏差较大；另一方面离线评估的开销过大，预测的基础在于离线评估，而离线评估需要大量的时间开销和资源占用，这都是很难满足的条件。
技术实现要素：
鉴于基于预测的调度算法的不足，本发明提出一种基于强化学习的深度学习任务调度方法，需要解决以下几个问题：
一是能够基于强化学习的典型算法完成对深度学习任务调度的场景建模，将任务调度问题转化为一个强化学习问题，完成状态空间、动作空间、反馈函数等模块设计与实现；
二是能够基于强化学习算法来设计自适应的深度学习任务调度算法，能够在线自适应调整不同深度学习任务的任务划分和放置策略，并依据任务性能的实时反馈，在线更新并调整策略；
三是基于tensorflow等主流框架完成插件整合，在不改变用户编程方式和任务提交方式的基础上，完成任务的放置策略的选择，同时也不影响集群管理者的现有运维方式。
技术问题：
假设当前cpu gpu异构对称集群有n个节点，每个节点有m个gpu，在深度学习多任务调度场景下，需要为每个任务找到一个最佳的任务划分和放置策略选择。而该策略的选择需要尽可能提高任务的完成效率和整个集群的资源利用率。本发明旨在提出一种基于任务在线执行性能反馈并自适应调整的强化学习策略，来完成上述调度目标，如何完成场景建模和自适应调度算法设计是本发明要解决的核心技术问题。
技术方案：
本发明提出一种基于强化学习的深度学习任务调度策略，来提高任务完成效率和集群资源利用率，其实现机制如下：
a.状态空间设计。在多任务调度场景下，需要记录并学习不同调度策略对每个任务性能的影响，而每个任务在不同策略下的性能通过一个q值表进行记录。理论上应该为每个深度学习任务构建一个独立的状态，而状态空间就是所有深度学习任务集合。但是实际场景下由于用户提交的任务差异性较大，类型较复杂，如果每个任务作为一个独立状态会导致状态空间爆炸，并影响学习效率。因此本发明加入一种分组策略，来降低状态空间的维度，提高整个强化学习q值表的效率。
b.动作空间设计。动作空间包含了为每个任务可能选择的分布式对称放置策略，主要包括任务平均划分到多个节点和多个gpu设备上。同时考虑到在任务在线调度的情况下，集群的资源空闲度具有不确定性，因此额外增加一种等待的动作选项，即当前任务可以选择等待到下一个调度点进行调度策略选择，从而可能会获得更多资源分配。动作空间的选择主要依赖于一种贪心策略和q值表，其中q值表代表动作选择需要基于对已知信息的利用，而贪心策略为动作选择增加一些探索性。
c.反馈函数设计。为每个任务选择调度策略之后，通过在线任务执行性能能够获取一个反馈，而该反馈值用于自身调度策略q值表的更新。反馈越高的调度决策后续被选择的可能性也会增大，反之则会降低。而反馈函数的设计一方面需要反映任务执行性能，另一方面也需要反映该调度策略下对资源的利用情况。
d.更新策略设计。基于任务性能反馈对q值表进行更新，更新的方式主要依据bellman最优方程，直到整个q值表收敛并稳定。
e．自适应调度算法设计。整个调度算法基于事件驱动机制，在新任务提交或旧任务完成时会自动触发调度点机制。在每个调度点上会自动遍历当前任务等待队列，并依次根据贪心算法为每个任务选择调度决策，并实时监控其性能并计算反馈，反过来对调度器进行在线优化和更新。
本发明取得的技术效果：
本发明提出一种基于强化学习的深度学习任务调度方法，采用本方法可以取得以下技术效果：
第一：本发明提出的基于强化学习的调度策略可以基于深度学习任务在不同调度策略下的性能在线反馈进行自适应学习，并自适应更新调度决策，从而最大化任务执行效率和集群资源利用率。
第二：本发明的设计与实现均属于轻量级，底层实现对上层用户透明，不需要修改用户的编程方式和任务提交方式，同时对于运维人员友好，部署方便简洁。
附图说明
图1为本发明提出的基于强化学习的深度学习任务调度方法完整示意图，
图2为本发明提出的基于强化学习的深度学习任务调度算法系统架构图。
具体实施方式
本发明的目的在于面向深度学习多任务调度场景，基于任务在线性能反馈，自适应学习并调整调度策略，尽可能提高任务完成效率和集群资源的利用效率。而该发明的核心在于如何面向该场景完成强化学习建模以及自适应调度算法的设计。
本发明提出的基于强化学习的深度学习任务调度方法如图1所示。该方法主要包括场景建模和调度算法设计两个部分。场景建模主要是在强化学习一般结构的基础上，结合深度学习任务调度场景完成各个模块的设计与实现。调度算法设计主要通过为每个任务调度策略的在线选择及任务性能反馈更新来实现提高整个集群任务完成效率和资源利用率的目标。具体的实施方式包括以下几点内容：
（1）状态空间设计与建模。理想状态下每个深度学习任务需要作为一个独立的状态进行学习并在q值表中进行记录和更新，但是考虑到实际应用场景中，深度网络模型的结构和超参数差异性较大，会导致状态空间爆炸而无法进行学习。考虑到深度网络模型在计算和通信上具有一定相似性特征，因此本发明提出一种基于k-means的分组策略来有效降低状态空间的维度。通过分析每个深度学习任务的计算量和通信量来构建一个计算通信比的指标，并基于该指标进行k-means聚类分组，同一个分组内的深度学习任务采用同一种调度策略选择，这样可以大大提高q值表学习效率和收敛速度。
（2）动作空间设计。动作空间包含每个深度学习任务可能的各种放置策略，而这个放置策略往往是一个有限集合，尤其是在一个对称的异构集群上。我们通过一个二元组来描述放置策略，即任务占用的节点数和每个节点内占用的gpu数。而任务在不同放置策略下进行平均划分，即每个gpu设备上划分的计算量均等。考虑到系统资源占用情况处于一个持续动态变化的过程，有些具有较高q值的动作选项可能当前系统无法满足。因此本发明增加一个等待选项，即该任务可以在任务队列中保留到下一个调度点进行调度决策。同时为了避免该任务被饿死，每个任务最多选择一次等待动作。
（3）反馈函数设计。反馈函数用来评价不同放置策略对任务性能的影响，也通过该函数完成对任务调度策略的更新和调整。考虑到本发明的目标在于任务性能和集群资源利用率，因此反馈函数也涉及到上述两点。反馈函数r可以表示为
其中t和s分别表示深度学习任务和放置策略。process函数为任务的标准化执行性能，cost函数为任务对资源的占用情况。通过该反馈函数的设计原理，可以综合反映出该任务在不同放置策略下的性能和资源占用情况。
（4）更新策略。在反馈函数设计的基础上，需要对q值表进行更新和优化，从而实现对调度策略的自适应调整。本发明采用bellman最优方程进行更新，通过不断优化更新使得q值表逐渐趋于稳定，并为每个任务实现最优的放置策略选择，从而提高资源利用率和任务完成效率。
（5）自适应调度算法设计。整个基于强化学习的调度实现框架如图2所示。整个调度基于事件驱动机制，每当有新任务到达或原有任务完成会触发调度点机制，并完成一次在线任务调度。
当用户提交任务到集群平台，该任务会自动进入一个任务等待队列。在事件触发的调度点上，之前提交的任务执行信息会被收集并计算反馈函数值，并依据反馈值来更新q值表。随后调度器会对任务等待队列进行遍历，直至整个遍历完成或当前集群系统已无空闲资源。
在遍历的过程中，对每个深度学习任务首先需要根据距离计算其状态空间分组，并通过ε贪心算法进行动作选择。如果随机概率小于ε则随机选择动作决策，如果随机概率大于ε，则选择q值表中概率最高的动作。完成动作选择后，调度器会将该任务调度到集群上进行执行，并监控其执行性能。如果该任务选择了等待选项，则会被继续保留在任务等待队列中，直到下一个调度点的到来。调度器默认采用先来先服务（fcfs）的调度顺序，整个调度过程中，ε也会随着处理的任务数目而自适应下降，降低动作选择的随机性，而逐渐提高现有知识的利用性。此外，任务提交的记录会被保存，并每间隔超过20个任务会根据k-means算法重新计算状态空间分组，并相应调整q值表。
本发明在上述调度策略设计的基础上，完成基于tensorflow的插件融合。由于整个系统实现轻量级，并不会对tensorflow框架本身有过多的修改，底层的系统调度与实现对用户和研发人员透明，并不需要修改其编程和任务提交的方式。
显然，本领域的技术人员可以根据本发明的技术构思对本发明进行各种改动和变形，而这些修改和变形属于本发明权利要求及等同技术范围之内，则都应属于本发明权利要求的保护范围。
1.一种基于强化学习的深度学习任务调度方法，包括场景建模和调度算法设计，其特征在于，具体包括：
a.状态空间设计，在多任务调度场景下，每个任务在不同策略下的性能通过一个q值表进行记录，为每个深度学习任务构建一个独立的状态，状态空间就是所有深度学习任务集合，加入一种分组策略，降低状态空间的维度，提高整个强化学习q值表的效率；
b.动作空间设计，动作空间包括任务平均划分到多个节点和多个gpu设备上，增加等待动作，即当前任务可以选择等待到下一个调度点进行调度策略选择，动作空间的选择依赖于贪心策略和q值表，其中q值表代表动作选择需要基于对已知信息的利用；
c.反馈函数设计，为每个任务选择调度策略之后，通过在线任务执行性能获取一个反馈，而该反馈用于自身调度策略q值表的更新，反馈越高的调度决策后续被选择的可能性也会增大，反之则会降低，反馈函数r表示为
其中t和s分别表示深度学习任务和放置策略，process函数为任务的标准化执行性能，cost函数为任务对资源的占用情况；
d.更新策略设计，基于任务性能反馈对q值表进行更新，更新的方式依据bellman最优方程，直到整个q值表收敛并稳定；
e．自适应调度算法设计，整个调度算法基于事件驱动机制，在新任务提交或旧任务完成时会自动触发调度点机制，在每个调度点上自动遍历当前任务等待队列，并依次根据贪心算法为每个任务选择调度决策，并实时监控其性能并计算反馈，反过来对调度器进行在线优化和更新。
2.根据权利要求1所述的一种基于强化学习的深度学习任务调度方法，其特征在于，所述自适应调度算法，具体为：
当用户提交任务到集群平台，该任务会自动进入一个任务等待队列，在事件触发的调度点上，之前提交的任务执行信息会被收集并计算反馈函数值，并依据反馈值来更新q值表，随后调度器会对任务等待队列进行遍历，直至整个遍历完成或当前集群系统已无空闲资源；
在遍历的过程中，对每个深度学习任务首先需要根据距离计算其状态空间分组，并通过ε贪心算法进行动作选择，如果随机概率小于ε则随机选择动作决策，如果随机概率大于ε，则选择q值表中概率最高的动作，完成动作选择后，调度器会将该任务调度到集群上进行执行，并监控其执行性能，如果该任务选择了等待选项，则会被继续保留在任务等待队列中，直到下一个调度点的到来，调度器默认采用先来先服务的调度顺序，整个调度过程中，ε也随着处理的任务数目而自适应下降，降低动作选择的随机性，而逐渐提高现有知识的利用性，此外，任务提交的记录会被保存，并每间隔超过20个任务根据k-means算法重新计算状态空间分组，并相应调整q值表。
技术总结