一种基于异构多核架构的类型化任务联合调度系统及方法与流程

1.本发明涉及多处理器的多任务联合调度技术领域，尤其涉及一种基于异构多核架构的类型化任务联合调度系统及方法。


背景技术：

2.近年来，异构多核处理器因其出色的计算性能和并行任务处理能力，被广泛地应用于智能手机、自动化机器人、可穿戴设备等移动嵌入式电子产品中。然而，受限于电池技术的缓慢发展，移动设备在性能提升的同时，还要满足一定的能耗限制。传统的性能提升技术主要依靠提高内核频率来提升性能，但也带来了能耗的增加。因此，在一定的能量消耗的条件下，我们需要探索如何尽可能提高异构多核处理器的性能。
3.异构多核系统的性能可以通过负载均衡进行优化。目前大量研究将系统建模为不同的排队模型，采用基于排队理论的负载均衡方法。该类研究的主要目标是最小化任务的平均响应时间，且均考虑任务排队系统为无限容量。然而，当任务数量过多时，会导致处理器系统出现过载现象，后到达的任务将处于无限等待状态，最终造成额外的等待时延。
4.另一方面，任务类型逐渐成为多处理器系统中性能优化的主要关注点。一些研究侧重于一种类型的任务，而另外一些研究则侧重于多种类型的任务。侧重多类型任务的相关研究均考虑了类型化任务的性能优化或功率优化，但大部分研究都是将某一类任务视为可预加载的，再基于此研究另外一类任务的负载调度策略，很少有文献提到类型化任务的联合调度问题。然而，类型化任务之间的约束关系对任务调度至关重要。
5.因此，综合上述问题，现有技术需要一种在系统能量和任务优先级约束下，考虑有限容量的类型化任务联合调度系统及方法。


技术实现要素：

6.本发明提供一种基于异构多核架构的类型化任务联合调度系统及方法，解决的技术问题在于：如何在系统能量和任务优先级约束下，有效降低任务的平均响应时间，实现系统的最佳负载分配。
7.为解决以上技术问题，本发明提供一种基于异构多核架构的类型化任务联合调度系统，包括任务请求端、任务管理器、全局调度器、队列缓存器和任务调度器；
8.所述任务请求端用于向所述任务管理器提交来自不同终端用户的实时任务请求和非实时任务请求，并设置实时任务的优先级高具有强抢占特性，非实时任务优先级低；
9.所述任务管理器用于接收所述实时任务请求和所述非实时任务请求，并分别按照这两类任务的到达时间形成包括实时任务流和非实时任务流的混合类型化任务流，然后将所述混合类型化任务流发送至所述全局调度器；
10.所述全局调度器用于接收所述混合类型化任务流，并根据联合调度机制将其划分多个实时任务子流和非实时任务子流，同时确定各个任务子流的任务参数和各个任务子流之间的执行顺序；
11.所述队列缓存器用于有限缓存两类所述任务子流，并结合任务执行顺序进行队列排序，得到多个等待队列；
12.所述任务调度器用于并行接收多个所述等待队列，并将多个所述等待队列中的任务子流分配至多个本地调度器，以及根据系统能量动态调整每个本地调度器中各个处理器的速度。
13.优选的，所述联合调度机制的联合调度过程为：
14.给定n个多核本地调度器s1,s2,...,sn，任务平均大小实时任务总到达率λ
′
，非实时任务总到达率λ
″
，实时任务的截止期限t
dead
，以及电源可用功率求本地调度器上实时任务到达率λ
′1,λ
′2,...,λ
′n，非实时任务到达率λ
″1,λ
″2,...,λ
″n，以及处理器速度s1,s2,...,sn，使得在系统能量约束下，非实时任务的平均响应时间最小化，同时满足实时任务的最大响应时间不超过其截止期限，其中本地调度器si具有ci个速度为si、容量为mi、静态功耗为p
i*
的同构多核处理器，i＝1,2,...,n。
15.具体的，所述联合调度机制的联合调度过程数学化表达为类型化任务联合调度问题：
[0016][0017]
其中，表示非实时任务在系统中的平均响应时间，t
″i表示非实时任务在所述本地调度器si中的平均响应时间；ρ
″i表示所述本地调度器si中实时任务和非实时任务的总核心利用率；约束条件c1表示系统处于平衡状态的约束条件，即其中1≤i≤n；c2表示实时任务的总到达率约束；c3表示非实时任务的总到达率约束；c4表示实时任务的最大响应时间t
′
max
不超过截止期限t
dead
，即实时任务的时限约束，其中是实时任务分布λ
′1,λ
′2,...,λ
′n和处理器速度s1,s2,...,sn的函数，t
′i表示实时任务在所述本地调度器si中的平均响应时间，其中i∈n＝{1,2,...,n}；c5表示系统的平均功率消耗p不超过系统可用功率即系统的能量约束；min表示取最小，max表示取最大。
[0018]
具体的，根据任务之间的优先级约束，将所述类型化任务联合调度问题分解为实时任务调度问题和非实时任务调度问题，分别对所述实时任务调度问题和所述非实时任务调度问题进行求解得到实时任务和非实时任务在所述本地调度器中的负载分布；
[0019]
其中所述实时任务调度问题为：在考虑实时任务截止期限和负载均衡需求的同时，优化实时任务的最大响应时间，求解实时任务在所述本地调度器中的负载分布；
[0020]
所述实时任务调度问题表示为：
[0021]
p2:min t
′
max
(λ
′1,λ
′2,...,λ
′n)＝max{t
′1(λ
′1),t
′2(λ
′2),...,t
′n(λ
′n)}
[0022]
s.t.c6:f
′
(λ
′1,λ
′2,...,λ
′n)＝λ
′
[0023]
c7:t
′
max
(λ
′1,λ
′2,...,λ
′n)≤t
dead
[0024]
c8:σ≤ε
[0025]
其中，约束条件c6是c2的变型，且f
′
表示各个实时任务子流的到达率之和，即f
′
(λ
′1,λ
′2,...,λ
′n)＝λ
′1+λ
′2+...+λ
′n；约束条件c7是c4的变型；约束条件c8是实时任务负载均衡约束，ε为负载均衡因子，取值范围为0≤ε≤10-2
；σ为负载均衡有效度，表示为其中表示系统中实时任务的平均任务完成时间；
[0026]
采用惯性权重系数粒子群优化方法迭代更新负载均衡策略，在满足任务时限约束下，求解所述实时任务调度问题。
[0027]
具体的，所述非实时任务调度问题为：在系统功率约束下，以最小化非实时任务的平均响应时间为目标进行负载分配；
[0028]
所述非实时任务调度问题表示为：
[0029][0030]
其中，约束条件c9,c10,c11,c12分别为c1,c3,c4,c5的变型，且在约束条件c10中f表示各个非实时任务子流的到达率之和，即f(λ
″1,λ
″2,...,λ
″n)＝λ
″1+λ
″2+...+λ
″n；约束条件c11中的g表示实时任务的最大响应时间，即且0≤β＜t
dead
，i∈n＝{1,2,...,n}；为考虑问题的极限情况，假设约束条件c12中的能量消耗p等于系统可用功率
[0031]
本发明还提供一种基于异构多核架构的类型化任务联合调度方法，包括步骤：
[0032]
s1、获取来自不同终端用户的实时任务请求和非实时任务请求，并设置实时任务的优先级高具有强抢占特性，非实时任务优先级低；
[0033]
s2、分别按照实时任务和非实时任务的到达时间形成包括实时任务流和非实时任务流的混合类型化任务流；
[0034]
s3、根据联合调度机制将其划分多个实时任务子流和非实时任务子流，同时确定各个任务子流的任务参数和各个任务子流之间的执行顺序；
[0035]
s4、有限缓存两类所述任务子流，并结合任务执行顺序进行队列排序，得到多个等待队列；
[0036]
s5、并行接收多个所述等待队列，并将多个所述等待队列中的任务子流分配至多个本地调度器，以及根据系统能量动态调整每个本地调度器中各个处理器的速度。
[0037]
进一步地，在所述步骤s3中，所述联合调度机制的联合调度过程为：
[0038]
给定n个多核本地调度器s1,s2,...,sn，任务平均大小实时任务总到达率λ
′
，非实时任务总到达率λ
″
，实时任务的截止期限t
dead
，以及电源可用功率求本地调度器上实
时任务到达率λ
′1,λ
′2,...,λ
′n，非实时任务到达率λ
″1,λ
″2,...,λ
″n，以及处理器速度s1,s2,...,sn，使得在系统能量约束下，非实时任务的平均响应时间最小化，同时满足实时任务的最大响应时间不超过其截止期限，其中本地调度器si具有ci个速度为si、容量为mi、静态功耗为p
i*
的同构多核处理器，i＝1,2,...,n。
[0039]
进一步地，所述联合调度机制的联合调度过程数学化表达为类型化任务联合调度问题：
[0040][0041]
其中，表示非实时任务在系统中的平均响应时间，t
″i表示非实时任务在所述本地调度器si中的平均响应时间；ρ
″i表示所述本地调度器si中实时任务和非实时任务的总核心利用率；约束条件c1表示系统处于平衡状态的约束条件，即其中1≤i≤n；c2表示实时任务的总到达率约束；c3表示非实时任务的总到达率约束；c4表示实时任务的最大响应时间t
′
max
不超过截止期限t
dead
，即实时任务的时限约束，其中是实时任务分布λ
′1,λ
′2,...,λ
′n和处理器速度s1,s2,...,sn的函数，t
′i表示实时任务在所述本地调度器si中的平均响应时间，其中i∈n＝{1,2,...,n}；c5表示系统的平均功率消耗p不超过系统可用功率即系统的能量约束；min表示取最小，max表示取最大。
[0042]
进一步地，所述步骤s3具体包括步骤：
[0043]
s31、根据任务之间的优先级约束，将所述类型化任务联合调度问题分解为实时任务调度问题和非实时任务调度问题；
[0044]
其中所述实时任务调度问题为：在考虑实时任务截止期限和负载均衡需求的同时，优化实时任务的最大响应时间，求解实时任务在所述本地调度器中的负载分布；
[0045]
所述实时任务调度问题表示为：
[0046]
p2:min t
′
max
(λ
′1,λ
′2,...,λ
′n)＝max{t
′1(λ
′1),t
′2(λ
′2),...,t
′n(λ
′n)}
[0047]
s.t.c6:f
′
(λ
′1,λ
′2,...,λ
′n)＝λ
′
[0048]
c7:t
′
max
(λ
′1,λ
′2,...,λ
′n)≤t
dead
[0049]
c8:σ≤ε
[0050]
其中，约束条件c6是c2的变型，且f
′
表示各个实时任务子流的到达率之和，即f
′
(λ
′1,λ
′2,...,λ
′n)＝λ
′1+λ
′2+...+λ
′n；约束条件c7是c4的变型；约束条件c8是实时任务负载均衡约束，ε为负载均衡因子，取值范围为0≤ε≤10-2
；σ为负载均衡有效度，表示为其中表示系统中实时任务的平均任务完
成时间；
[0051]
所述非实时任务调度问题表示为：
[0052][0053]
其中，约束条件c9,c10,c11,c12分别为c1,c3,c4,c5的变型，且在约束条件c10中f表示各个非实时任务子流的到达率之和，即f(λ
″1,λ
″2,...,λ
″n)＝λ
″1+λ
″2+...+λ
″n；约束条件c11中的g表示实时任务的最大响应时间，即且0≤β＜t
dead
，i∈n＝{1,2,...,n}；为考虑问题的极限情况，假设约束条件c12中的能量消耗p等于系统可用功率
[0054]
s32、采用惯性权重系数粒子群优化方法迭代更新负载均衡策略，在满足任务时限约束下，对所述实时任务调度问题进行求解，得到实时任务在所述本地调度器中的负载分布；
[0055]
s33、采用基于拉格朗日的凸优化方法简化所述非实时任务调度问题，并采用满足能量约束的二分搜索方法求解简化后的所述非实时任务调度问题，得到实时任务在所述本地调度器中的负载分布。
[0056]
进一步地，所述步骤s32具体包括步骤：
[0057]
s321、根据调度规则，初始化粒子种群和参数设置；
[0058]
s322、根据适应度函数，计算每个粒子的适应度值f；
[0059]
s323、求解个体最佳适应值和群体最佳适应值
[0060]
s324、根据惯性权重系数更新公式更新惯性权重系数ω，即
[0061][0062]
其中，ω
ini
和ω
end
分别表示ω的初始值和迭代至最大次数时的值，f
avg
和f
min
表示当前粒子的平均目标和最小目标值；
[0063]
s325、根据公式更新每个粒子的速度和位置，其中速度更新公式为
[0064][0065]
位置更新公式为
[0066]
x
i+1
＝xi+v
i+1
，
[0067]
其中，v
i+1
和x
i+1
分别表示更新后粒子的速度和位置，vi和xi分别表示更新前粒子的速度和位置，r1和r2表示介于(0,1)的随机值，c1和c2为学习因子；
[0068]
s326、判断是否到达最大迭代次数ls，若未达到则转至步骤s322，若达到则结束迭代转至步骤s327；
[0069]
s327、得到全局最佳位置，即实时任务在所述本地调度器中的最佳负载分布；
[0070]
所述步骤s33具体包括步骤：
[0071]
s331、使用拉格朗日乘子法最小化t
″
，得等式其中φ,ψ,τ为三个拉格朗日乘子，为求导符号；
[0072]
s332：根据步骤s331中的等式右侧对非实时任务的负载分布变量λ
″i和处理器速度si求偏导，其中1≤i≤n；
[0073]
s333：对步骤s331等式左侧t
″
中的负载分布变量λ
″i和处理器速度si求偏导，其中1≤i≤n；
[0074]
s334：联立步骤s332和步骤s333中的求导结果，得到定理：对于能量约束下的所述非实时任务调度问题，当所有多核处理器具有相同速度时，n个多核处理器上的非实时任务平均响应时间t
″
最小，即s1＝s2＝...＝sn＝s，且
[0075][0076]
由上述公式可知：当系统能量(可用功率)改变时，多核处理器速度si也相应改变，并能找到最佳执行速率s高效完成任务，使得满足实时任务可调度性需求的同时，最小化非实时任务的平均响应时间，其中αi表示本地调度器si的功率因子，且1≤i≤n；
[0077]
s335：初始化电源可用功率以及非实时任务的负载分布上界λ
″
max
和负载分布下界λ
″
min
；
[0078]
s336：判断λ
″
max-λ
″
min
≥ν是否成立，若成立转至步骤s337，否则转至步骤s3312，其中ν是极小数，取值范围为10-8
≤ν≤10-6
；
[0079]
s337：取当前负载分布上界和负载分布下界的平均值λ
″
mid
作为当前迭代的负载分布，即
[0080]
s338：判断已分配的到达率是否大于非实时任务的总到达率，若大于则执行步骤s339，若小于则执行步骤s3310；
[0081]
s339：更新负载分布上界λ
″
max
＝λ
″
mid
；
[0082]
s3310：更新负载分布下界λ
″
min
＝λ
″
mid
；
[0083]
s3311：迭代次数加1，转至步骤s336，开始新的一轮迭代；
[0084]
s3312：得到非实时任务在所述本地调度器中的最佳负载分布和平均响应时间。
[0085]
本发明提供的一种基于异构多核架构的类型化任务联合调度系统及方法，具有如下优点和有益效果：
[0086]
(1)引入联合调度机制，根据任务大小和任务优先级对任务进行划分和排序；基于此，针对实时任务的时限特性，采用惯性权重系数粒子群优化方法迭代更新负载均衡策略，在满足实时任务可调度性需求的同时最小化实时任务的最大响应时间；同时，针对非实时任务的低优先权特性，利用基于拉格朗日的凸优化思想简化问题的求解，并采用一种满足能量约束的二分搜索算法，有效降低了非实时任务的平均响应时间，实现了系统的最佳负载分配；
[0087]
(2)通过根据系统能量动态调整处理器速率，并以最佳执行速率并行完成任务，有效解决了多任务调度系统中任务处理量大、处理响应实时性高的需求，保证了多类任务执
行的灵活性和实时性；
[0088]
(3)通过对队列系统容量的有限设计，较现有的任务调度系统处理器资源占用少、响应时间延迟低，能更好地满足嵌入式平台工程化应用环境的需求。
附图说明
[0089]
图1是本发明实施例提供的一种基于异构多核架构的类型化任务联合调度系统的架构图；
[0090]
图2是本发明实施例提供的一种基于异构多核架构的类型化任务联合调度方法的流程图；
[0091]
图3是本发明实施例提供的求解实时任务调度问题的步骤示意图；
[0092]
图4是本发明实施例提供的求解非实时任务调度问题的步骤示意图；
[0093]
图5是本发明实施例提供的不同方案下实时任务到达率与实时任务最大响应时间的关系曲线图；
[0094]
图6是本发明实施例提供的不同方案下非实时任务到达率与非实时任务平均响应时间的关系曲线图。
具体实施方式
[0095]
下面结合附图具体阐明本发明的实施方式，实施例的给出仅仅是为了说明目的，并不能理解为对本发明的限定，包括附图仅供参考和说明使用，不构成对本发明专利保护范围的限制，因为在不脱离本发明精神和范围基础上，可以对本发明进行许多改变。
[0096]
请参阅图1，本发明实施例提供一种基于异构多核架构的类型化任务联合调度系统，包括任务请求端、任务管理器、全局调度器、队列缓存器和任务调度器。
[0097]
任务请求端用于向任务管理器提交来自不同终端用户的实时任务请求和非实时任务请求，并设置实时任务的优先级高具有强抢占特性，非实时任务优先级低。
[0098]
任务管理器用于接收实时任务请求和非实时任务请求，并分别按照这两类任务的到达时间形成包括实时任务流和非实时任务流的混合类型化任务流，然后将混合类型化任务流发送至全局调度器。
[0099]
全局调度器用于接收混合类型化任务流，并根据联合调度机制将其划分多个实时任务子流和非实时任务子流，同时确定各个任务子流的任务参数和各个任务子流之间的执行顺序。
[0100]
队列缓存器用于有限缓存两类任务子流，并结合任务执行顺序进行队列排序，得到多个等待队列。队列缓存器为一组容量有限的m/m/c/m排队系统。
[0101]
任务调度器用于并行接收多个等待队列，并将多个等待队列中的任务子流分配至多个本地调度器，以及根据系统能量动态调整每个本地调度器中各个处理器的速度，以最佳执行速率并行完成任务，可有效解决多任务调度系统中任务处理量大、处理响应实时性高的需求，保证多类任务执行的灵活性和实时性。
[0102]
本地调度器的数目为n，且具有ci个速度为si，容量为mi的同构处理器，基于排队理论，基于排队理论，可以得到具有强抢占优先权的实时任务在本地调度器si中的平均响应时间为：
[0103][0104]
其中，ls
′i为本地调度器si中执行实时任务的平均处理器数目，lq
′i为等待队列li中实时的排队长度，λ
′i为实时任务在本地调度器si中的负载分布，且1≤i≤n。
[0105]
另外，实时任务具有强抢占优先权，实时任务核心利用率仅与实时任务到达率λ
′i有关，为：
[0106][0107]
记ti为实时、非实时任务在本地调度器si中时每个任务的平均响应时间，采用负指数分布的性质，由于具有高优先级的实时任务到达时，低优先级的非实时任务即使正在被执行也只有中断并重新加入排队等待，但其执行时间的分布不被前面已执行以及执行时间长短所影响，即其仍然为负指数分布。由此，ti可以按照到达率为λ
′i+λ
″i的m/m/c/m排队模型公式计算得出：
[0108][0109]
其中，li表示系统中正在执行或者等待执行的类型化任务的平均数，λ
″i表示非实时任务在本地调度器si中的负载分布，且1≤i≤n。
[0110]
根据公式(λ
′i+λ
″i)ti＝λ
′it
′i+λ
″it
″i，可得具有低优先权的非实时任务在本地调度器si中的平均响应时间为：
[0111][0112]
另外，本地调度器si中实时任务和非实时任务的总核心利用率表示为：
[0113][0114]
其中，1≤i≤n。
[0115]
假设p＝κcv2f表示处理器动态功耗，其中κ是活动因子，c是负载电容，v是电源电压，f是时钟频率。由于s
∝
f(
∝
表示正比于)，其中s为处理器速度，并且其中由此可以得到处理器功耗p
∝sα
，其中为了便于讨论，本发明将本地调度器si中一个处理器核心的动态功耗建模为静态功耗为p
i*
，因此，速度为si的处理器的功率模型可以表述为本发明考虑一种变频能量模型，在该模型中，处理器在空闲时仅消耗静态功率p
i*
。在本地调度器si中，ρ
″i代表单位时间内一个处理器正在执行任务的平均时间百分比，则1-ρ
″i代表一个处理器空闲的平均时间百分比。因此，本地调度器si中ci个处理器内核在单位时间内的平均功耗可以建模为：
[0116][0117]
其中，1≤i≤n。
[0118]
基于上述分析，全局调度器的联合调度机制建立为：
[0119]
给定n个多核本地调度器s1,s2,...,sn，任务平均大小实时任务总到达率λ
′
，非实时任务总到达率λ
″
，实时任务的截止期限t
dead
，以及电源可用功率求本地调度器上实时任务到达率λ
′1,λ
′2,...,λ
′n，非实时任务到达率λ
″1,λ
″2,...,λ
″n，以及处理器速度s1,s2,...,sn，使得在系统能量约束下，非实时任务的平均响应时间最小化，同时满足实时任务的最大响应时间不超过其截止期限，i＝1,2,...,n。即数学公式表示为：
[0120][0121]
其中，其中，表示非实时任务在系统中的平均响应时间，t
″i表示非实时任务在本地调度器si中的平均响应时间；ρ
″i表示本地调度器si中实时任务和非实时任务的总核心利用率；约束条件c1表示系统处于平衡状态的约束条件，即其中1≤i≤n；c2表示实时任务的总到达率约束；c3表示非实时任务的总到达率约束；c4表示实时任务的最大响应时间t
′
max
不超过截止期限t
dead
，即实时任务的时限约束，其中是实时任务分布λ
′1,λ
′2,...,λ
′n和处理器速度s1,s2,...,sn的函数，t
′i表示实时任务在本地调度器si中的平均响应时间，其中i∈n＝{1,2,...,n}；c5表示系统的平均功率消耗p不超过系统可用功率即系统的能量约束；min表示取最小，max表示取最大。
[0122]
根据任务之间的优先级约束，将类型化任务联合调度问题分解为实时任务调度问题和非实时任务调度问题，分别对实时任务调度问题和非实时任务调度问题进行求解得到实时任务和非实时任务在本地调度器中的负载分布。
[0123]
其中实时任务调度问题为：在考虑实时任务截止期限和负载均衡需求的同时，优化实时任务的最大响应时间，求解实时任务在本地调度器中的负载分布。实时任务调度问题具体表示为：
[0124]
p2:min t
′
max
(λ
′1,λ
′2,...,λ
′n)＝max{t
′1(λ
′1),t
′2(λ
′2),...,t
′n(λ
′n)}
[0125]
s.t.c6:f
′
(λ
′1,λ
′2,...,λ
′n)＝λ
′
[0126]
c7:t
′
max
(λ
′1,λ
′2,...,λ
′n)≤t
dead
[0127]
c8:σ≤ε
[0128]
其中，约束条件c6是c2的变型，且f
′
表示各个实时任务子流的到达率之和，即f
′
(λ
′1,λ
′2,...,λ
′n)＝λ
′1+λ
′2+...+λ
′n；约束条件c7是c4的变型；约束条件c8是实时任务负载均衡约束，ε为负载均衡因子，取值范围为0≤ε≤10-2
；σ为自定义的负载均衡有效度(来衡量各异构系统之间的实时任务处理时间差异，σ数值越小，说明系统中处理器处理时间越均衡，处理器的整体性能越好)，表示为其中
表示系统中实时任务的平均任务完成时间。
[0129]
该问题是一个多变量多约束的非线性极小极大问题，直接进行求解容易造成负载分配不均衡。采用惯性权重系数粒子群优化方法迭代更新负载均衡策略，在满足任务时限约束下，求解实时任务调度问题，具体的求解过程在下文的方法中进行详细介绍。
[0130]
非实时任务调度问题为：在系统功率约束下，以最小化非实时任务的平均响应时间为目标进行负载分配。非实时任务调度问题表示为：
[0131][0132]
其中，约束条件c9,c10,c11,c12分别为c1,c3,c4,c5的变型，且在约束条件c10中f表示各个非实时任务子流的到达率之和，即f(λ
″1,λ
″2,...,λ
″n)＝λ
″1+λ
″2+...+λ
″n；约束条件c11中的g表示实时任务的最大响应时间，即且0≤β＜t
dead
，i∈n＝{1,2,...,n}；为考虑问题的极限情况，假设约束条件c12中的能量消耗p等于系统可用功率
[0133]
非实时任务调度问题是一个多变量多约束的优化问题，可以采用经典的拉格朗日乘子法进行求解，但是会引入具有2n+3个变量的非线性方程组，即λ
″1,λ
″2,...,λ
″n，s1,s2,...,sn，和三个拉格朗日乘子，导致难以获得联合闭式解。为此，本发明以负载均衡为指导思想，以问题简化为主线，充分挖掘处理器速度和负载分布之间的数学关系，进而推导了异构多处理器系统在能量约束下的最优处理器速度配置。具体的，本发明采用基于拉格朗日的凸优化方法简化非实时任务调度问题，并采用满足能量约束的二分搜索方法求解简化后的非实时任务调度问题，具体的求解过程在下文的方法中进行详细介绍。
[0134]
基于上述系统，本发明实施例还提供一种基于异构多核架构的类型化任务联合调度方法，如图2所示，包括步骤：
[0135]
s1、获取来自不同终端用户的实时任务请求和非实时任务请求，并设置实时任务的优先级高具有强抢占特性，非实时任务优先级低；
[0136]
s2、分别按照实时任务和非实时任务的到达时间形成包括实时任务流和非实时任务流的混合类型化任务流；
[0137]
s3、根据联合调度机制将其划分多个实时任务子流和非实时任务子流，同时确定各个任务子流的任务参数和各个任务子流之间的执行顺序；
[0138]
s4、有限缓存两类任务子流，并结合任务执行顺序进行队列排序，得到多个等待队列；
[0139]
s5、并行接收多个等待队列，并将多个等待队列中的任务子流分配至多个本地调度器，以及根据系统能量动态调整每个本地调度器中各个处理器的速度。
[0140]
与系统对应的，在步骤s3中，联合调度机制的联合调度过程为：
[0141]
给定n个多核本地调度器s1,s2,...,sn，任务平均大小实时任务总到达率λ
′
，非实时任务总到达率λ
″
，实时任务的截止期限t
dead
，以及电源可用功率求本地调度器上实
时任务到达率λ
′1,λ
′2,...,λ
′n，非实时任务到达率λ
″1,λ
″2,...,λ
″n，以及处理器速度s1,s2,...,sn，使得在系统能量约束下，非实时任务的平均响应时间最小化，同时满足实时任务的最大响应时间不超过其截止期限，其中本地调度器si具有ci个速度为si、容量为mi、静态功耗为p
i*
的同构多核处理器，i＝1,2,...,n。
[0142]
联合调度机制数学化表达为一个类型化任务联合调度问题，表示为：
[0143][0144]
其中，表示非实时任务在系统中的平均响应时间，t
″i表示非实时任务在本地调度器si中的平均响应时间；ρ
″i表示本地调度器si中实时任务和非实时任务的总核心利用率；约束条件c1表示系统处于平衡状态的约束条件，即其中1≤i≤n；c2表示实时任务的总到达率约束；c3表示非实时任务的总到达率约束；c4表示实时任务的最大响应时间t
′
max
不超过截止期限t
dead
，即实时任务的时限约束，其中是实时任务分布λ
′1,λ
′2,...,λ
′n和处理器速度s1,s2,...,sn的函数，t
′i表示实时任务在本地调度器si中的平均响应时间，其中i∈n＝{1,2,...,n}；c5表示系统的平均功率消耗p不超过系统可用功率即系统的能量约束。
[0145]
具体的，步骤s3具体包括步骤：
[0146]
s31、根据任务之间的优先级约束，将类型化任务联合调度问题分解为实时任务调度问题和非实时任务调度问题；
[0147]
s32、采用惯性权重系数粒子群优化方法迭代更新负载均衡策略，在满足任务时限约束下，对实时任务调度问题进行求解，得到实时任务在本地调度器中的负载分布；
[0148]
s33、采用基于拉格朗日的凸优化方法简化非实时任务调度问题，并采用满足能量约束的二分搜索方法求解简化后的非实时任务调度问题，得到实时任务在本地调度器中的负载分布。
[0149]
在步骤s31中，实时任务调度问题为：在考虑实时任务截止期限和负载均衡需求的同时，优化实时任务的最大响应时间，求解实时任务在本地调度器中的负载分布。
[0150]
实时任务调度问题表示为：
[0151]
p2:min t
′
max
(λ
′1,λ
′2,...,λ
′n)＝max{t
′1(λ
′1),t
′2(λ
′2),...,t
′n(λ
′n)}
[0152]
s.t.c6:f
′
(λ
′1,λ
′2,...,λ
′n)＝λ
′
[0153]
c7:t
′
max
(λ
′1,λ
′2,...,λ
′n)≤t
dead
[0154]
c8:σ≤ε
[0155]
其中，约束条件c6是c2的变型，且f
′
表示各个实时任务子流的到达率之和，即f
′
(λ
′1,λ
′2,...,λ
′n)＝λ
′1+λ
′2+...+λ
′n；约束条件c7是c4的变型；约束条件c8是实时任务负载均衡约束，ε为负载均衡因子，取值范围为0≤ε≤10-2
；σ为负载均衡有效度，表示为
其中表示系统中实时任务的平均任务完成时间；
[0156]
非实时任务调度问题表示为：
[0157][0158]
其中，约束条件c9,c10,c11,c12分别为c1,c3,c4,c5的变型，且在约束条件c10中f表示各个非实时任务子流的到达率之和，即f(λ
″1,λ
″2,...,λ
″n)＝λ
″1+λ
″2+...+λ
″n；约束条件c11中的g表示实时任务的最大响应时间，即且0≤β＜t
dead
，i∈n＝{1,2,...,n}；为考虑问题的极限情况，假设约束条件c12中的能量消耗p等于系统可用功率
[0159]
如图3所示，步骤s32具体包括步骤：
[0160]
s321、根据调度规则，初始化粒子种群和参数设置(种群规模s，迭代次数ls，学习因子c1和c2，惯性权重ω
ini
和ω
end
)；
[0161]
s322、根据适应度函数，计算每个粒子的适应度值f；
[0162]
s323、求解个体最佳适应值p
besti
和群体最佳适应值g
besti
，p
besti
是局部最佳解，g
besti
是求解空间中所有局部解中的最优解；
[0163]
s324、根据惯性权重系数更新公式更新惯性权重系数ω，即
[0164][0165]
其中，ω
ini
和ω
end
分别表示ω的初始值和迭代至最大次数时的值，f
avg
和f
min
表示当前粒子的平均目标和最小目标值；
[0166]
s325、根据公式更新每个粒子的速度和位置，其中速度更新公式为
[0167]vi+1
＝ωvi+c1r1(p
besti-xi)+c2r2(g
besti-xi)，
[0168]
位置更新公式为
[0169]
x
i+1
＝xi+v
i+1
，
[0170]
其中，v
i+1
和x
i+1
分别表示更新后粒子的速度和位置，vi和xi分别表示更新前粒子的速度和位置，r1和r2表示介于(0,1)的随机值，c1和c2为学习因子；
[0171]
s326、判断是否到达最大迭代次数ls，若未达到则转至步骤s322，若达到则结束迭代转至步骤s327；
[0172]
s327、得到全局最佳位置，即实时任务在本地调度器中的最佳负载分布。
[0173]
如图4所示，步骤s33具体包括步骤：
[0174]
s331、使用拉格朗日乘子法最小化t
″
，得等式其中φ,
ψ,τ为三个拉格朗日乘子，为求导符号；
[0175]
s332：根据步骤s331中的等式右侧对非实时任务的负载分布变量λ
″i和处理器速度si求偏导，其中1≤i≤n；
[0176]
s333：对步骤s331等式左侧t
″
中的负载分布变量λ
″i和处理器速度si求偏导，其中1≤i≤n；
[0177]
s334：联立步骤s332和步骤s333中的求导结果，得到定理：对于能量约束下的非实时任务调度问题，当所有多核处理器具有相同速度时，n个多核处理器上的非实时任务平均响应时间t
″
最小，即s1＝s2＝...＝sn＝s，且
[0178][0179]
由上述公式可知：当系统能量(可用功率)改变时，多核处理器速度si也相应改变，并能找到最佳执行速率s高效完成任务，使得满足实时任务可调度性需求的同时，最小化非实时任务的平均响应时间，其中1≤i≤n；
[0180]
s335：初始化电源可用功率以及非实时任务的负载分布上界λ
″
max
和负载分布下界λ
″
min
；
[0181]
s336：判断λ
″
max-λ
″
min
≥ν是否成立，若成立转至步骤s337，否则转至步骤s3312，其中ν是极小数，取值范围为10-8
≤ν≤10-6
；
[0182]
s337：取当前负载分布上界和负载分布下界的平均值λ
″
mid
作为当前迭代的负载分布，即
[0183]
s338：判断已分配的到达率是否大于非实时任务的总到达率，若大于则执行步骤s339，若小于则执行步骤s3310；
[0184]
s339：更新负载分布上界λ
″
max
＝λ
″
mid
；
[0185]
s3310：更新负载分布下界λ
″
min
＝λ
″
mid
；
[0186]
s3311：迭代次数加1，转至步骤s336，开始新的一轮迭代；
[0187]
s3312：得到非实时任务在本地调度器中的最佳负载分布和平均响应时间。
[0188]
在其他实施方式中，亦可采用其他有效的求解方法求解实时任务调度问题和非实时任务调度问题。
[0189]
综上，本发明实施例提供的一种基于异构多核架构的类型化任务联合调度系统及方法，具有如下优点和有益效果：
[0190]
(1)引入联合调度机制，根据任务大小和任务优先级对任务进行划分和排序；基于此，针对实时任务的时限特性，采用惯性权重系数粒子群优化方法迭代更新负载均衡策略，在满足实时任务可调度性需求的同时最小化实时任务的最大响应时间；同时，针对非实时任务的低优先权特性，利用基于拉格朗日的凸优化思想简化问题的求解，并采用一种满足能量约束的二分搜索算法，有效降低了非实时任务的平均响应时间，实现了系统的最佳负载分配；
[0191]
(2)通过根据系统能量动态调整处理器速率，并以最佳执行速率并行完成任务，有效解决了多任务调度系统中任务处理量大、处理响应实时性高的需求，保证了多类任务执
r,et al.optimal power allocation and load balancing for non-dedicated heterogeneous distributed embedded computing systems[j].journal of parallel and distributed computing,2019,130(aug.):24-36.
[0200]
②
bdtpo，未考虑异构多核架构下专有任务的负载分配，专有任务是预加载的且具有截止时间，并利用双向时序功耗优化策略实现通用任务的负载分配；可参考文献：huang j,li r,wei y,et al.bi-directional timing-power optimisation on heterogeneous multi-core architectures[j].ieee transactions on sustainable computing,2021,6(4):572-585.
[0201]
③
本发明所提方案proposed，系统中的实时任务具有实时特性和优先执行权力，且利用类型化任务的联合调度优化策略实现实时任务和非实时任务的联合调度和负载均衡。
[0202]
由于olb和bdtpo均将异构多核系统建模为m/m/1的排队系统，为公平起见，考虑本发明中的系统为m/m/1/m排队系统。同时，为保证实验结果的普适性，本实施例利用随机分布来预加载专有任务。
[0203]
在图5中，比较了能量约束下不同调度方案下实时任务到达率对实时任务最大响应时间的影响。随着实时任务到达率的增加，三种方案下的最大响应时间均呈上升趋势。选择olb方案时，最大响应时间最大，且当到达率超过20时，最大响应时间超过系统设定的实时任务截止期限1s。这是由于olb方案没有考虑实时任务的时限约束。此外，通过比较bdtpo方案和所提方案可以看出，系统有限容量的引入和实时任务的有效分配有利于系统性能的提升。所提方案根据系统能量消耗情况对实时任务进行有效负载调度，满足时限约束和负载均衡需求，有效降低了任务响应时延。
[0204]
在图6中，比较了能量约束下不同方案下非实时任务到达率对非实时任务平均响应时间的影响。随着任务到达率的增加，所有方案的任务平均响应时间都保持上升趋势。可以看出，当到达率超过21时，olb和bdtpo的非实时任务平均响应时间均远大于所提方案。由于olb和bdtpo方案对实时任务进行预加载操作，处理器无法根据系统能量状态进行有效的负载分配，从而导致部分处理器处于过载状态，最终使得低优先权的非实时任务阻塞在等待队列中。这会产生额外的等待时延，导致其平均响应时间增加。同时可以看出，olb方案的系统性能略优于bdtpo方案，并随着到达率的增加，性能差距越明显。该趋势已在bdtpo文献中展示。此外，所提方案中有限系统容量的引入，可以有效避免排队等待导致的额外延迟，因此本发明所提方案比其他方案表现出更好的性能。
[0205]
上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。

技术特征：
1.一种基于异构多核架构的类型化任务联合调度系统，其特征在于，包括任务请求端、任务管理器、全局调度器、队列缓存器和任务调度器；所述任务请求端用于向所述任务管理器提交来自不同终端用户的实时任务请求和非实时任务请求，并设置实时任务的优先级高具有强抢占特性，非实时任务优先级低；所述任务管理器用于接收所述实时任务请求和所述非实时任务请求，并分别按照这两类任务的到达时间形成包括实时任务流和非实时任务流的混合类型化任务流，然后将所述混合类型化任务流发送至所述全局调度器；所述全局调度器用于接收所述混合类型化任务流，并根据联合调度机制将其划分多个实时任务子流和非实时任务子流，同时确定各个任务子流的任务参数和各个任务子流之间的执行顺序；所述队列缓存器用于有限缓存两类所述任务子流，并结合任务执行顺序进行队列排序，得到多个等待队列；所述任务调度器用于并行接收多个所述等待队列，并将多个所述等待队列中的任务子流分配至多个本地调度器，以及根据系统能量动态调整每个本地调度器中各个处理器的速度。2.根据权利要求1所述的一种基于异构多核架构的类型化任务联合调度系统，其特征在于，所述联合调度机制的联合调度过程为：给定n个多核本地调度器s1,s2,...,s
n
，任务平均大小实时任务总到达率λ
′
，非实时任务总到达率λ
″
，实时任务的截止期限t
dead
，以及电源可用功率求本地调度器上实时任务到达率λ
′1,λ
′2,...,λ
′
n
，非实时任务到达率λ1″
,λ2″
,...,λ
n
″
，以及处理器速度s1,s2,...,s
n
，使得在系统能量约束下，非实时任务的平均响应时间最小化，同时满足实时任务的最大响应时间不超过其截止期限，其中本地调度器s
i
具有c
i
个速度为s
i
、容量为m
i
、静态功耗为p
i*
的同构多核处理器，i＝1,2,...,n。3.根据权利要求2所述的一种基于异构多核架构的类型化任务联合调度系统，其特征在于，所述联合调度机制的联合调度过程数学化表达为类型化任务联合调度问题：p1:mint
″
(λ
′1,λ
′2,...,λ
′
n
,λ1″
,λ2″
,...,λ
n
″
,s1,s2,...,s
n
)s.t.c1:ρ
i
″
＜1c2:λ
′1+λ
′2+...+λ
′
n
＝λ
′
c3:λ1″
+λ2″
+...+λ
n
″
＝λ
″
c4:t
′
max
(λ
′1,λ
′2,...,λ
′
n
,s1,s2,...,s
n
)≤t
dead
其中，表示非实时任务在系统中的平均响应时间，t
i
″
表示非实时任务在所述本地调度器s
i
中的平均响应时间；ρ
i
″
表示所述本地调度器s
i
中实时任务和非实时任务的总核心利用率；约束条件c1表示系统处于平衡状态的约束条件，即其中1≤i≤n；c2表示实时任务的总到达率约束；c3表示非实时任务的总到达率约束；c4表示实时任务的最大响应时间t
′
max
不超过截止期限t
dead
，即实时任务的时限
约束，其中是实时任务分布λ
′1,λ
′2,...,λ
′
n
和处理器速度s1,s2,...,s
n
的函数，t
i
′
表示实时任务在所述本地调度器s
i
中的平均响应时间，其中i∈n＝{1,2,...,n}；c5表示系统的平均功率消耗p不超过系统可用功率p，即系统的能量约束；min表示取最小，max表示取最大。4.根据权利要求3所述的一种基于异构多核架构的类型化任务联合调度系统，其特征在于：根据任务之间的优先级约束，将所述类型化任务联合调度问题分解为实时任务调度问题和非实时任务调度问题，分别对所述实时任务调度问题和所述非实时任务调度问题进行求解得到实时任务和非实时任务在所述本地调度器中的负载分布；其中所述实时任务调度问题为：在考虑实时任务截止期限和负载均衡需求的同时，优化实时任务的最大响应时间，求解实时任务在所述本地调度器中的负载分布；所述实时任务调度问题表示为：p2:min t
′
max
(λ
′1,λ
′2,...,λ
′
n
)＝max{t1′
(λ
′1),t
′2(λ
′2),...,t
′
n
(λ
′
n
)}s.t.c6:f
′
(λ
′1,λ
′2,...,λ
′
n
)＝λ
′
c7:t
′
max
(λ
′1,λ
′2,...,λ
′
n
)≤t
dead
c8:σ≤ε其中，约束条件c6是c2的变型，且f
′
表示各个实时任务子流的到达率之和，即f
′
(λ
′1,λ
′2,...,λ
′
n
)＝λ
′1+λ
′2+...+λ
′
n
；约束条件c7是c4的变型；约束条件c8是实时任务负载均衡约束，ε为负载均衡因子，取值范围为0≤ε≤10-2
；σ为负载均衡有效度，表示为其中表示实时任务在系统中的平均任务完成时间；采用惯性权重系数粒子群优化方法迭代更新负载均衡策略，在满足任务时限约束下，求解所述实时任务调度问题。5.根据权利要求4所述的一种基于异构多核架构的类型化任务联合调度系统，其特征在于，所述非实时任务调度问题为：在系统功率约束下，以最小化非实时任务的平均响应时间为目标进行负载分配；所述非实时任务调度问题表示为：p3:mint
″
(λ1″
,λ2″
,...,λ
n
″
,s1,s2,...,s
n
)c10:f(λ1″
,λ2″
,...,λ
n
″
)-λ
″
＝0c11:g(s1,s2,...,s
n
)+β-t
dead
＝0其中，约束条件c9,c10,c11,c12分别为c1,c3,c4,c5的变型，且在约束条件c10中f表示各个非实时任务子流的到达率之和，即f(λ1″
,λ2″
,...,λ
n
″
)＝λ1″
+λ2″
+...+λ
n
″
；约束条件c11中的g表示实时任务的最大响应时间，即且0≤β＜t
dead
，i∈n＝{1,2,...,n}；为考虑问题的极限情况，假设约束条件c12中的能量消耗p等于系统可用功率
6.一种基于异构多核架构的类型化任务联合调度方法，其特征在于，包括步骤：s1、获取来自不同终端用户的实时任务请求和非实时任务请求，并设置实时任务的优先级高具有强抢占特性，非实时任务优先级低；s2、分别按照实时任务和非实时任务的到达时间形成包括实时任务流和非实时任务流的混合类型化任务流；s3、根据联合调度机制将其划分多个实时任务子流和非实时任务子流，同时确定各个任务子流的任务参数和各个任务子流之间的执行顺序；s4、有限缓存两类所述任务子流，并结合任务执行顺序进行队列排序，得到多个等待队列；s5、并行接收多个所述等待队列，并将多个所述等待队列中的任务子流分配至多个本地调度器，以及根据系统能量动态调整每个本地调度器中各个处理器的速度。7.根据权利要求6所述的一种基于异构多核架构的类型化任务联合调度方法，其特征在于，在所述步骤s3中，所述联合调度机制的联合调度过程为：给定n个多核本地调度器s1,s2,...,s
n
，任务平均大小实时任务总到达率λ
′
，非实时任务总到达率λ
″
，实时任务的截止期限t
dead
，以及电源可用功率求本地调度器上实时任务到达率λ
′1,λ
′2,...,λ
′
n
，非实时任务到达率λ1″
,λ2″
,...,λ
n
″
，以及处理器速度s1,s2,...,s
n
，使得在系统能量约束下，非实时任务的平均响应时间最小化，同时满足实时任务的最大响应时间不超过其截止期限，其中本地调度器s
i
具有c
i
个速度为s
i
、容量为m
i
、静态功耗为p
i*
的同构多核处理器，i＝1,2,...,n。8.根据权利要求7所述的一种基于异构多核架构的类型化任务联合调度方法，其特征在于，所述联合调度机制的联合调度过程数学化表达为类型化任务联合调度问题：p1:mint
″
(λ
′1,λ
′2,...,λ
′
n
,λ1″
,λ2″
,...,λ
n
″
,s1,s2,...,s
n
)s.t.c1:ρ
i
″
＜1c2:λ
′1+λ
′2+...+λ
′
n
＝λ
′
c3:λ1″
+λ2″
+...+λ
n
″
＝λ
″
c4:t
′
max
(λ
′1,λ
′2,...,λ
′
n
,s1,s2,...,s
n
)≤t
dead
其中，表示非实时任务在系统中的平均响应时间，t
i
″
表示非实时任务在所述本地调度器s
i
中的平均响应时间；ρ
i
″
表示所述本地调度器s
i
中实时任务和非实时任务的总核心利用率；约束条件c1表示系统处于平衡状态的约束条件，即其中1≤i≤n；c2表示实时任务的总到达率约束；c3表示非实时任务的总到达率约束；c4表示实时任务的最大响应时间t
′
max
不超过截止期限t
dead
，即实时任务的时限约束，其中是实时任务分布λ
′1,λ
′2,...,λ
′
n
和处理器速度s1,s2,...,s
n
的函数，t
i
′
表示实时任务在所述本地调度器s
i
中的平均响应时间，其中i∈n＝{1,2,...,n}；c5表示系统的平均功率消耗p不超过系统可用功率即系统的能量约束；min表示取最小，max表示取最大。
9.根据权利要求8所述的一种基于异构多核架构的类型化任务联合调度方法，其特征在于，所述步骤s3具体包括步骤：s31、根据任务之间的优先级约束，将所述类型化任务联合调度问题分解为实时任务调度问题和非实时任务调度问题；其中所述实时任务调度问题为：在考虑实时任务截止期限和负载均衡需求的同时，优化实时任务的最大响应时间，求解实时任务在所述本地调度器中的负载分布；所述实时任务调度问题表示为：p2:min t
′
max
(λ
′1,λ
′2,...,λ
′
n
)＝max{t1′
(λ
′1),t
′2(λ
′2),...,t
′
n
(λ
′
n
)}s.t.c6:f
′
(λ
′1,λ
′2,...,λ
′
n
)＝λ
′
c7:t
′
max
(λ
′1,λ
′2,...,λ
′
n
)≤t
dead
c8:σ≤ε其中，约束条件c6是c2的变型，且f
′
表示各个实时任务子流的到达率之和，即f
′
(λ
′1,λ
′2,...,λ
′
n
)＝λ
′1+λ
′2+...+λ
′
n
；约束条件c7是c4的变型；约束条件c8是实时任务负载均衡约束，ε为负载均衡因子，取值范围为0≤ε≤10-2
；σ为负载均衡有效度，表示为其中表示系统中实时任务的平均任务完成时间；所述非实时任务调度问题表示为：p3:mint
″
(λ1″
,λ2″
,...,λ
n
″
,s1,s2,...,s
n
)c10:f(λ1″
,λ2″
,...,λ
n
″
)-λ
″
＝0c11:g(s1,s2,...,s
n
)+β-t
dead
＝0其中，约束条件c9,c10,c11,c12分别为c1,c3,c4,c5的变型，且在约束条件c10中f表示各个非实时任务子流的到达率之和，即f(λ1″
,λ2″
,...,λ
n
″
)＝λ1″
+λ2″
+...+λ
n
″
；约束条件c11中的g表示实时任务的最大响应时间，即且0≤β＜t
dead
，i∈n＝{1,2,...,n}；为考虑问题的极限情况，假设约束条件c12中的能量消耗p等于系统可用功率s32、采用惯性权重系数粒子群优化方法迭代更新负载均衡策略，在满足任务时限约束下，对所述实时任务调度问题进行求解，得到实时任务在所述本地调度器中的负载分布；s33、采用基于拉格朗日的凸优化方法简化所述非实时任务调度问题，并采用满足能量约束的二分搜索方法求解简化后的所述非实时任务调度问题，得到实时任务在所述本地调度器中的负载分布。10.根据权利要求9所述的一种基于异构多核架构的类型化任务联合调度方法，其特征在于：所述步骤s32具体包括步骤：s321、根据调度规则，初始化粒子种群和参数设置；s322、根据适应度函数，计算每个粒子的适应度值f；
s323、求解个体最佳适应值和群体最佳适应值s324、根据惯性权重系数更新公式更新惯性权重系数ω，即其中，ω
ini
和ω
end
分别表示ω的初始值和迭代至最大次数时的值，f
avg
和f
min
表示当前粒子的平均目标和最小目标值；s325、根据公式更新每个粒子的速度和位置，其中速度更新公式为位置更新公式为x
i+1
＝x
i
+v
i+1
，其中，v
i+1
和x
i+1
分别表示更新后粒子的速度和位置，v
i
和x
i
分别表示更新前粒子的速度和位置，r1和r2表示介于(0,1)的随机值，c1和c2为学习因子；s326、判断是否到达最大迭代次数l
s
，若未达到则转至步骤s322，若达到则结束迭代转至步骤s327；s327、得到全局最佳位置，即实时任务在所述本地调度器中的最佳负载分布；所述步骤s33具体包括步骤：s331、使用拉格朗日乘子法最小化t
″
，得等式
▽
t
″
＝φ
▽
f+ψ
▽
g+τ
▽
p，其中φ,ψ,τ为三个拉格朗日乘子，
▽
为求导符号；s332：根据步骤s331中的等式右侧对非实时任务的负载分布变量λ
i
″
和处理器速度s
i
求偏导，其中1≤i≤n；s333：对步骤s331等式左侧t
″
中的负载分布变量λ
i
″
和处理器速度s
i
求偏导，其中1≤i≤n；s334：联立步骤s332和步骤s333中的求导结果，得到定理：对于能量约束下的所述非实时任务调度问题，当所有多核处理器具有相同速度时，n个多核处理器上的非实时任务平均响应时间t
″
最小，即s1＝s2＝...＝s
n
＝s，且其中α
i
表示本地调度器s
i
的功率因子，且1≤i≤n；s335：初始化电源可用功率p以及非实时任务的负载分布上界λ
″
max
和负载分布下界λ
″
min
；s336：判断λ
″
max-λ
″
min
≥ν是否成立，若成立转至步骤s337，否则转至步骤s3312，其中ν是极小数，取值范围为10-8
≤ν≤10-6
；s337：取当前负载分布上界和负载分布下界的平均值λ
″
m
″
id
作为当前迭代的负载分布，即s338：判断已分配的到达率是否大于非实时任务的总到达率，若大于则执行步骤s339，若小于则执行步骤s3310；
s339：更新负载分布上界λ
″
m
″
ax
＝λ
″
m
″
id
；s3310：更新负载分布下界λ
″
m
″
in
＝λ
″
m
″
id
；s3311：迭代次数加1，转至步骤s336，开始新的一轮迭代；s3312：得到非实时任务在所述本地调度器中的最佳负载分布和平均响应时间。

技术总结
本发明涉及多处理器的多任务联合调度技术领域，具体公开了一种基于异构多核架构的类型化任务联合调度系统及方法，其通过引入联合调度机制，根据任务大小和任务优先级对任务进行划分和排序；基于此，针对实时任务的时限特性，采用惯性权重系数粒子群优化方法迭代更新负载均衡策略，在满足实时任务可调度性需求的同时最小化实时任务的最大响应时间；同时，针对非实时任务的低优先权特性，利用基于拉格朗日的凸优化思想简化问题的求解，并采用一种满足能量约束的二分搜索算法，有效降低了非实时任务的平均响应时间，实现了系统的最佳负载分配。配。配。


技术研发人员：于彦涛 文小洪 潘伟 刘国金 牛彬 黄心雨 欧阳水清 黄天聪 吴玉成
受保护的技术使用者：国网山西省电力公司晋中供电公司 北京智芯微电子科技有限公司
技术研发日：2023.02.21
技术公布日：2023/7/11