A task intelligent scheduling method based on the number of cores
-
摘要:
新一代航天测控与通信地面系统由大规模异构云计算资源池构成。为了给不同的测控通信任务合理分配可用算力,提出了一种基于核数分配的智能调度方法,该算法根据每个任务占用核数大小来分配不同CPU/GPU进行任务处理。建立了任务核数分配问题的马尔科夫决策过程模型,根据执行任务数量和可供调度的处理器数量建立Q表,制定各处理器资源负载均衡的奖励值最大化原则,寻找使调度性能最优的任务分配路径,逐次计算奖励和更新Q值,完成多周期训练,根据奖励回路不断迭代优化输出调度结果。实验分析结果表明,本文算法可以在保证任务均衡部署的前提下最大化计算核的利用率,相比已有算法提升了多核分配的合理性,优化了系统整体性能。
Abstract:The new generation of ground systems for space tracking, telemetry, and command (TT&C) and communication is composed of a large-scale heterogeneous cloud computing resource pool. To allocate available computing power to different TT&C and communication tasks reasonably, an intelligent scheduling method based on core allocation is proposed. This algorithm allocates different CPUs/GPUs for task processing based on the number of cores required by each task. This paper establishes a Markov decision process (MDP) model for the task core allocation problem, constructs a Q-table based on the number of tasks to be executed and the number of available processors for scheduling, formulates a principle of maximizing reward values for load balancing across processor resources, searches for the task allocation path that optimizes scheduling performance, iteratively calculates rewards and updates Q-values, completes multi-cycle training, and continuously iterates and optimizes the output scheduling results based on the reward circuit. Experimental analysis results show that this algorithm can maximize the utilization rate of computing cores while ensuring balanced task deployment. Compared with existing algorithms, it enhances the rationality of multi-core allocation and optimizes the overall system performance.
-
Keywords:
- task /
- utilization /
- number of cores /
- scheduling
-
0 引 言
随着近年来我国在轨飞行器数量跃居世界前列,已规划低轨卫星数量过万,空间平台数量呈几何倍增长,天地测控与通信容量需求激增。现有测控基础设施“一站一制”,与测控对象绑定,通信制式封闭,烟囱式建设,测控资源孤立难以自适应转换和复用。由于陆、海、空、天各域之间电波传播环境差别巨大,导致测控体制、波形和链路协议各不相同,造成了多模态融合瓶颈,推动了新一代航天地面基础设施逐步向软件可定义、功能可重构的大规模航天测控云架构演进[1]。
聚合后的测控云化资源池需支持多制式多通道,超大规模处理资源调配困难。因此,如何合理分配可用的计算资源给不同的任务,成为了行业研究的热点问题[2-5]。
基于马尔可夫决策过程的任务分配算法[6]是一种基于状态转移概率的任务调度算法,它利用状态转移矩阵来表述任务间转换的可能性。每个任务都有一个当前状态及一个状态转移概率矩阵[7-8],用来描述任务之间的转移概率。每次进行调度行动时,都会依据当前的状态和状态转移可能性矩阵决定采取哪个行动,且会相应地更新状态转移概率矩阵。文献[9]通过强化学习算法训练调度器,动态地分配任务到可用的资源,从而最小化任务执行时间。文献[10]基于强化学习的任务调度方法,在边缘设备上有效地分配任务,以提高资源利用率和性能。文献[11]用实验数据对节点进行深度学习训练,再用强化学习方法进行资源分配,成功解决了动态资源的调度难题。文献[12]面向工业物联网中异构资源以及动态行为带来的挑战,提出了一个利用强化学习来同时优化能耗和成本的实时调度方法。文献[13]把计算机资源看成是一种组合优化问题,并提出了一种基于强化学习和模仿学习相结合的方法。
上述资源分配方案的模型及方法都较为复杂,需要大量的训练数据来提高学习效果,导致在处理分配调度问题时效率较低。实际应用中任务与资源存在大组合空间搜索难题,传统方法面临训练样本少、调度时效差等问题,迫切需要低复杂度的高效算法满足多任务-多资源动态分配的强实时性。本文提出了一种根据每个任务占的核数大小来分配不同算力的基于马尔可夫决策过程的任务分配算法。该算法可以保证任务均衡部署的前提下,使多核利用率最大化。通过对不同任务占的核数大小的分析,使任务之间的转移概率更加公平,从而提高系统的整体性能。
1 系统模型
1.1 状态转移矩阵和概率
在基于马尔可夫决策过程的任务分配算法中,状态转移矩阵是非常重要的。状态转移矩阵的计算需要考虑到任务之间的转移概率,其可用以下公式表示:
P(Xt+1|Xt)=P(Xt+1|Xt,Xt−1,⋯,X0) (1) 若该组变量{X0,X1,⋯,Xt}符合给定的条件概率P,它们所构成的集合就被称为马尔可夫链。样本轨迹指由这些随机变量之间连续的转换所构成的路径,即马尔科夫链。
转变的状态转换具有一定的概率,称为转移概率。能够以表格形式展现转移概率的状态转移图,称为马尔可夫表,即它是基于当前状态的概率转移描述。发生的可能性也能够通过公式里的条件概率来展现:
P′=P(st+1|st) (2) 从状态st到st+1的条件概率P′表示马尔可夫链的关键特性,认为未来的状态只依赖于当前的状态,不受过去历史的影响。
1.2 动作的选择
马尔可夫决策过程是由马尔可夫链增添了智能体的行为和奖励元素,因此转移函数发生了变化,有
P′=P(st+1|st,at) (3) at在状态st下将任务分配给适当的处理器。
转移概率是指当前状态下执行某个动作后转向另一种状态的可能性。马尔可夫决策过程的样本轨迹被比喻为马尔可夫链的一种扩展或升级形式:
MN={s0,a0,s1,a1,r1,s2,a2,r2,⋯,sN,aN,rN} (4) 它们分别对应着当前的状态sN、正在进行的动作aN以及当前状态rN。这是一种由初始状态s0按照特定策略π(a|s)驱动,生成与当前状态相关的行动,随之获得反馈奖励的状态-行为-奖励序列。π(a|s)指的是状态s转换成动作a的可能性,即:
π(a|s)=P(a|s) (5) 策略生成和状态迁移在马尔可夫决策过程中都带有随机元素,马尔可夫过程实际上能生成众多路径,且每条路径都配有相应的出现概率,例如某个路径MN的概率为
P(MN)=P(s0)N−1∏i=0P(ai|si)P(si+1|si,ai) (6) 1.3 奖惩值
智能体的目的是让整体路径的奖励和惩罚达到最大,在处理某个情境任务时,将有限且拥有终端状态的轨迹的奖惩值整体进行定义:
G=r1+r2+r3+⋯+rN (7) 在从不截止的任务里没有终止阶段,按照之前的公式来核算整个过程的奖励和惩罚就不合适了。当产生的结果是无穷大时,就无法让智能体的奖励和惩罚总和达到最大。在马尔科夫决策过程里,增添折扣因子γ∈[0,1],给全程的回馈奖励设定一个折减值。对于智能体,
G=r1+γr2+γ2r3+⋯+γNrN+1+⋯=∞∑i=0γiri+1 (8) 折扣因子影响对将来奖励和即时奖励的看重程度。当折扣因子为0时,重视即时奖励;而当其为1时,倾向于未来奖励。
1.4 状态-动作值函数
策略函数π(s):S→A用来映射状态到行为。策略函数本质上是描述每个状态下应采取的动作,即追求在所有情况下采取最佳行动策略,以便最大程度地收获奖励。
在某种策略下,状态值函数π用来评估某个状态优劣的指标,定义为
Vπ=Eπ[Gt|st=s] (9) 状态值函数能够计算在指定策略π中,从某个状态s出发预期能得到的收益,带入Gt可以得出:
Vπ=Eπ[∞∑i=0γirt+i+1|st=s] (10) 策略的差异会导致状态值函数的变化。
状态-动作值函数(Q函数)用来评估在既定策略π下执行某个动作在特定状态下产生效益优劣的工具,其具体定义是在策略π下的状态-动作价值:
Qπ(s,a)=Eπ[Gt|st=s,at=a] (11) 即按照策略π,从一个状态s出发执行行为a所能期望得到的收益,带入Gt得出:
Qπ(s,a)=Eπ[∞∑i=0γirt+i+1|st=s,at=a] (12) 状态值函数评价的是状态的价值,而Q函数评估的是特定状态的动作价值。
2 智能调度算法
针对动态测控与通信任务流的传统资源分配常采用基于规则的调度方法,存在着板卡资源碎片多、硬件利用率低、资源分配不合理等问题,本文提出根据测控任务流特征与硬件资源池状态,实时更新搜索的处理核分配策略,通过将优化问题建模成马尔科夫决策过程并迭代求解,实现测控任务流与硬件计算单元间的有效匹配。
贝尔曼方程常被应用于求解马尔科夫决策过程问题,其中最优值函数就是与所有策略下值函数相比能够产生最大值的值函数,即:
V∗(s)=maxπVπ(s) (13) 最优策略能够产生出最优值函数V∗(s),而Q函数的最大值也可以用来计算这个最优值函数:
V∗(s)=maxaQ∗(s,a) (14) 值函数的贝尔曼方程可表示为
Vπ(s)=∑aπ(s,a)∑s′,rP(s′,r|s,a)[r+γVπ(s′)] (15) Q函数的贝尔曼方程可以用另一种形式来表述:
Qπ(s,a)=∑s′,rP(s′,r|s,a)[r+γ∑a′π(a′|s′)Qπ(s′,a′)] (16) 动态规划方法用于求解得到贝尔曼方程。动态规划将复杂问题分解为更简单的子问题,随后求解每一个分支问题并存储答案,遇到重复的问题时不会再次计算,而是直接使用先前得到的结果。
2.1 值迭代和策略迭代
动态规划的实施方式存在两种:值迭代和策略迭代。
如图1所示,值迭代的步骤如下:
1)初始化随机值函数,即每个状态为随机值;
2)计算所有状态-动作的值,即Q函数的Q(s,a)值;
3)用最大的Q(s,a)值对值函数进行更新;
4)一直重复这个过程,直到值函数达到最优,即收敛。
如图2所示,策略迭代的步骤如下:
1)随机初始化一批策略;
2)评估通过随机策略得到的值函数是否最优,即策略评估;
3)对非最优策略进行优化提升;
4)不断重复上述步骤,直到更新后的策略和更新策略一样,即找到最优策略。
如图3所示,按照贝尔曼动态规划理念,智能体在当前状态下能够获得的时间累计折扣性奖励Rt可以这样表述:
Rt=rt+1+γrt+2+⋯=∞∑k=0γkrt+k+1 (17) 式中,rt+1为当前状态下的即时收益,对不同时间点的奖励给予重要性评估。智能体在给定策略π下,在特定时间点t处于某个状态st下执行某动作at后获得奖励的期望值被称为动作值函数Q(st,at):
Q(st,at)=Eπ(Rt|st,at)=Eπ(rt+1+γrt+2+γ2rt+2+⋯|st,at) (18) 依据给定的状态转移规律,可得动作值函数的贝尔曼方程形式,即:
Q(s,a)=rt+γ∑st+1P(st+1|st,at)∑at+1π(at+1|st+1)Qπ(st+1,at+1) (19) 进一步可得到动作值函数的最优贝尔曼方程:
Q(s,a)=r(st,at)+γmaxQ∗(st+1,at+1) (20) 根据时序差分学习原则,动作值函数的更新公式可以写为
Q(st,at)=Q(st,at)+α[rt+1+γmaxat+1∈A(st+1)Q(st+1,at+1)−Q(st,at)] (21) 其选择动作的策略依据为
π(s)=argmaxa∈A(s)Q(s,a) (22) 2.2 算法执行步骤
整个核数分配算法可以概括为:系统根据执行任务数量和可供调度的处理器数量建立Q表;制定各处理器资源均衡分配得到最大化奖励值的原则,寻找使调度性能最优的任务分配路径;逐次计算奖励和更新Q值,完成相应训练周期;根据奖励值不断迭代优化输出调度结果。图4为算法的流程图及核心步骤。
步骤1 模型初始化
1)确定处理器个数及处理能力(以核数为单位);输入任务流个数及每个任务占用的资源数即核数。
2)初始化Q值函数,创建Q值函数矩阵,该矩阵行的个数等于任务的个数,列的个数等于处理器的个数。
3)设置学习率、探索率和迭代次数,并根据式(8)设置折扣因子。
步骤2 调度策略
在每次迭代中,从任务流中第一个任务开始,对于每个任务,选择处理器处理的策略有两种:
1)根据式(14),以当前状态的Q值选择最优执行的处理器。
2)根据设置的探索率,随机选择处理器,全局探索可执行任务的处理器,不会使算法陷入局部最优解。
两种策略按照式(5)确定合适的比例可以保证算法在一定程度上进行探索和利用。
步骤3 执行强化学习
1)根据调度策略选择最优的动作后,将任务初次分配给相应的处理器,同时计算当次处理器资源利用率,实时更新初次分配后的处理器占用率。
2)在分配一个任务后,根据所有处理器的资源利用率和当前任务选择的处理器以及考虑未来任务的潜在奖励,利用学习率、折扣因子来综合计算奖励,并更新式(21)中的Q值函数。
步骤4 输出调度结果
在迭代次数完成后,使用学习到的Q值函数根据式(22)对每个任务进行调度分配,每个处理器上任务对应的Q值最大,即为需调度的处理器位置。
步骤5 分配性能评估
在完成调度结果后,输出各个处理器的资源占用情况和Q值矩阵在平均值和Frobenius范数上的变化量迭代趋势,研判算法调度性能。
3 仿真结果与分析
探索率设置为0.115,即学习过程中有11.5%的概率随机选择一个动作来探索环境,使算法在运行相同迭代次数后产生不同的结果,增加全局探索性。设置学习率为0.15,折扣因子为0.9,迭代次数为900。
输入15个核数占比不同的测控任务,每个任务占用的核数为8~14。供调度的处理器有5个,每个处理器能支持的最大核数为40~80。表1为3次算法运行后的输出结果,包含每个任务的调度结果。
根据表1,在探索因子的存在下,每次迭代到相同次数时,会产生不同的调度方案, 3次运行结果见表2。可以看出,虽然3种调度方案分配结果不同,但每个处理器的资源占用情况都达到了均衡配置,并不存在某个处理器过于空闲或忙碌。
选取Q值矩阵的平均值和Frobenius范数作为收敛变化表征指标,如图5所示。可以发现在900次迭代过程中,由于探索因子的存在,Q值矩阵的平均值和Frobenius范数变量在收敛过程中存在一定的抖动;随着迭代次数增大后,Q值矩阵的最终整体变化趋势都会近似收敛到0,达到各处理器资源均衡分配的目标。
表 1 15个输入任务对应的调度结果Tab. 1 15 tasks corresponding scheduling results个 输入任务 调度方案1 调度方案2 调度方案3 1 1 1 5 2 5 2 1 3 1 1 2 4 5 5 4 5 4 5 5 6 1 3 3 7 2 3 1 8 2 4 3 9 3 4 2 10 4 3 4 11 3 1 3 12 4 2 5 13 1 1 1 14 5 2 2 15 4 5 4 表 2 不同方案各处理器资源占用情况Tab. 2 Resource consumption of different schemes for each processor% 处理器 调度方案1 调度方案2 调度方案3 1 46.666 7 50.000 0 43.333 3 2 36.666 7 43.333 3 46.666 7 3 40.000 0 40.000 0 50.000 0 4 56.666 7 43.333 3 46.666 7 5 50.000 0 53.333 3 43.333 3 引入文献[14]的合作学习以及随机分配方法与本文算法进行对比,结果如图6所示。可以看到,本文算法在完成任务分配后,所得到的资源占用曲线较为平缓,资源占用率最大与最小变化在10%以内,而其他两种方法在不同处理器的资源占用率起伏较大,占用率最大与最小变化远超过10%,未达到较好的资源分配结果。
4 结 论
本文提出了一种基于每个测控任务所占核数大小来确定CPU/GPU等不同处理器的任务分配算法。在保证任务均衡部署的前提下,该算法可使多处理器利用率最大化。通过对不同任务占核数大小的分析发现,该算法在测控应用中具有很好的效果,具有很好的扩展性,且使任务分配更加合理,从而提高测控系统的整体性能。
-
表 1 15个输入任务对应的调度结果
Tab. 1 15 tasks corresponding scheduling results
个 输入任务 调度方案1 调度方案2 调度方案3 1 1 1 5 2 5 2 1 3 1 1 2 4 5 5 4 5 4 5 5 6 1 3 3 7 2 3 1 8 2 4 3 9 3 4 2 10 4 3 4 11 3 1 3 12 4 2 5 13 1 1 1 14 5 2 2 15 4 5 4 表 2 不同方案各处理器资源占用情况
Tab. 2 Resource consumption of different schemes for each processor
% 处理器 调度方案1 调度方案2 调度方案3 1 46.666 7 50.000 0 43.333 3 2 36.666 7 43.333 3 46.666 7 3 40.000 0 40.000 0 50.000 0 4 56.666 7 43.333 3 46.666 7 5 50.000 0 53.333 3 43.333 3 -
[1] 李超,焦义文,傅诗媛,等. 软件定义测控系统体系架构与关键技术[J]. 中国空间科学技术,2023,43(3):14-24. LI C,JIAO Y W,FU S Y,et al. Software defined TT&C system architecture and key technology[J]. Chinese space science and technology,2023,43(3):14-24. (in Chinese)
[2] ZHAO N,YE Z,PEI Y,et al. Multi-agent deep reinforcement learning for task offloading in UAV-assisted mobile edge computing[J]. IEEE transactions on wireless communications,2022,21(9):6949-6960. doi: 10.1109/TWC.2022.3153316
[3] ZHAO N,LIU Z,CHENG Y. Multi-agent deep reinforcement learning for trajectory design and power allocation in multi-UAV networks[J]. IEEE access,2020,8:139670-139679. doi: 10.1109/ACCESS.2020.3012756
[4] DING R,GAO F,SHEN X S. 3D UAV trajectory design and frequency band allocation for energy-efficient and fair communication:a deep reinforcement learning approach[J]. IEEE transactions on wireless communications,2020,19(12):7796-7809. doi: 10.1109/TWC.2020.3016024
[5] 李冠雄,李桂林. 基于强化学习的合作频谱分配算法[J]. 电波科学学报,2022,37(1):8-14. doi: 10.12265/j.cjors.2021016 LI G X,LI G L. Cooperative spectrum allocation algorithm based on reinforcement learning[J]. Chinese journal of radio science,2022,37(1):8-14. (in Chinese) doi: 10.12265/j.cjors.2021016
[6] WANG C,DENG D,XU L,et al. Resource scheduling based on deep reinforcement learning in UAV assisted emergency communication networks[J]. IEEE transactions on communications,2022,70(6):3834-3848. doi: 10.1109/TCOMM.2022.3170458
[7] JIANG F,WANG K,DONG L,et al. Stacked autoencoder-based deep reinforcement learning for online resource scheduling in large-scale MEC networks[J]. IEEE Internet of Things journal,2020,7(10):9278-9290. doi: 10.1109/JIOT.2020.2988457
[8] KUAI Z,WANG T,WANG S. Fair virtual network function mapping and scheduling using proximal policy optimization[J]. IEEE transactions on communications,2022,70(11):7434-7445. doi: 10.1109/TCOMM.2022.3211071
[9] ZHANG Q,SUN B,ZHANG J. A survey of reinforcement learning-based scheduling in cloud computing[J]. IEEE access,2021,9(1):587-602.
[10] MAO H,ALIZADEH M,MENACHE I,et al. Deep reinforcement learning for job scheduling in data centers[C]// Proceedings of the 13th USENIX Symposium on Networked Systems Design and Implementation (NSDI),2016.
[11] YU W,LIANG F,HE H,et al. Deep reinforcement learning-based task scheduling for edge computing[J]. IEEE Internet of Things journal,2018,18(8):1861-1874.
[12] MA X,XU H,GAO H,et al. Real-time virtual machine scheduling in industry IoT network:a reinforcement learning method[J]. IEEE transactions on industrial informatics,2022,19(2):2129-2139.
[13] GUO W,TIAN W,YE Y,et al. Cloud resource scheduling with deep reinforcement learning and imitation learning[J]. IEEE Internet of Things journal,2020,8(5):3576-3586.
[14] 梁智韬,贾高伟,王建峰. 无人机集群任务分配中群智能算法性能对比[J]. 火力与指挥控制,2022,47(6):28-37. doi: 10.3969/j.issn.1002-0640.2022.06.005 LIANG Z T,JIA G W,WANG J F. The comparison of swarm intelligence algorithm about the mission assignment of UAV swarm[J]. Fire control & command control,2022,47(6):28-37. (in Chinese) doi: 10.3969/j.issn.1002-0640.2022.06.005