2019, Vol. 40
随着半导体技术的发展, CMOS晶体管尺寸不断变小, 在一个模组中可以集成更多的核.例如, 因特尔公司的Intel Xeon Phi协处理器可以多达60个核左右[1].芯片在硬件设计上朝着越来越多核体系结构发展, 然而目前的软件和调度策略并不能充分地利用多核的性能.例如:一个应用程序的执行时间是100个时间单位, 无论系统中的核个数是多少, 应用程序都必须在100个时间单位后完成执行.假如该应用程序可以同时在100个处理器上执行, 那么仅需1个时间单位便可完成.
多核实时调度领域中常用的并行模型主要有:Fork-Join模型[2]、同步并行模型[3-6]以及DAG(directed acyclic graph)模型[7-12].由于DAG并行模型对节点并行约束较少, 因此针对DAG并行模型的研究呈上升趋势.由于任务内的并行关系导致顺序执行任务模型的调度策略并不适用于并行任务模型.
本文针对DAG模型分析DAG任务集在多核处理器上的响应时间.响应时间分析是实时嵌入式系统中判定任务可调度性的重要手段.目前, 并行任务的可调度性分析已初步取得了一些成果, 但针对G-EDF(global earliest deadline first)的响应时间分析的工作却相对欠缺.文献[6]针对同步并行模型, 提出一种基于干涉量的响应时间分析方法.然而该方法和同步并行模型有很大的相关性, 并不适用于DAG并行模型.文献[10]提出基于DAG模型的响应时间分析方法, 然而该方法却忽略了DAG模型的特有结构.文献[12]针对DAG并行模型基于G-EDF的可调度性分析提出一种基于松弛时间的G-EDF调度策略, 该方法为了获得分析效率而盲目过量估计特定窗口的任务执行情况, 导致分析结果过于悲观.
本文针对以上问题, 首先提出一种更加准确的carry-in工作量的估算方法.其次, 根据被分析任务实际完成的时间计算问题窗口的最大工作量.最后, 结合两种新提出的工作量估算策略分析被分析任务的最差响应时间.本文通过仿真实验, 验证了本文提出的分析方法的性能优于文献[12]中提出的算法.下文中将文献[12]中提出的算法简称为DAG-G-EDF, 把新提出的基于改善carry-in工作量的G-EDF响应时间分析方法简称为IMP-G-EDF-RTA.
1 问题模型本文讨论的问题是在M个同构单位速率处理器组成的处理器平台上分析具有n个DAG任务组成的任务集，采用G-EDF调度策略进行调度时的可调度性.任务集表示为τ={τ1, …, τn}.1个DAG任务τi表示为(Gi, Di, Ti).其中, Gi表示有向无环图, Di表示任务τi的相对截止期, Ti表示任务τi的两个连续实例的最小释放时间间隔也称为周期.Gi=(Vi, Ei), Vi为Gi所有节点的集合, Ei为Gi所有边的集合.每个节点θi, u∈Vi的最差执行时间(WCET: worst case execution time)表示为ei, u.Ei中的1条有向边(θi, u, θi, v)表示节点θi, v必须在节点θi, u完成后才能开始执行.节点θi, u进入就绪状态当且仅当其所有直接前继完成了执行.
DAG任务τi的1条路径定义为Gi的1个节点序列θi, 1, …, θi, f, 该节点序列中连续的2个节点之间存在1条有向边, 即(θi, j, θi, j+1)∈Ei, 1≤j < f.路径的长度定义为路径上所有节点的WCET之和.Gi的关键路径定义为最长路径，表示为LCi.任务τi的WCET表示为Ci:
|
DAG任务τi会释放无限多的实例, 每个实例的响应时间定义为从其释放到其完成之间的时间间隔.任务τi的响应时间定义为所有实例的最差响应时间(WCRT: worst case response time):Ri=max(fi-ri).显然枚举所有实例是无法实现的, 因此常用方法是估算一个任务的WCRT.本文只考虑限制截止期任务的情况, 即:Di≤Ti.显而易见, LCi严格不大于Di时任务τi才能被调度, 但Ci≤Di不是必须的.任务τi的利用率表示为Ui, 且定义Ui=Ci/Ti.而任务集的利用率用U表示, 且定义
任务的优先级按照EDF进行分配, 即每个已经释放且未完成的任务实例的最小绝对截止期优先调度的策略进行调度.本文假设处理器时钟是单位时间的, 即所有的任务相关参数都是正整数.
2 最新研究方法及其悲观性分析本节首先介绍常用的多核处理器分析方法的基础理论[10], 然后对文献[12]提出的G-EDF分析方法进行介绍, 最后分析该方法的悲观性.本文以任务τk作为被分析任务进行阐述.
2.1 问题窗口和工作量定义1(问题窗口)设被分析任务τk在rk处释放在fk处完成执行, 则窗口[rk, fk]称为任务τk的问题窗口.
任务集中的任何一个除了τk以外的任务在问题窗口内产生的工作量可以由两种类型的实例组成:carry-in任务实例(该类实例在问题窗口前释放, 但截止期在问题窗口内)和body任务实例(释放和截止期都在问题窗口内的实例).每个任务τi只有一个carry-in任务实例称之为JiCI, 而body任务实例有多个.
引理1(最坏执行情况)当di=dk时, 任务τi在问题窗口[rk, fk]内的工作量最大.
如图 1所示, 该引理的正确性是显而易见的.任务τi的body实例在窗口[rk, fk]内的个数最多为
|
图 1 任务τi的最坏执行情况 Fig.1 Worst case execution of task τi |
|
图 1仅仅为了示意任务的释放和执行, 因此用1个矩形表示DAG任务的执行是合理的.任务τi在长度为Lk的问题窗口内的工作量组成为Nib个body实例和1个carry-in实例.因此, carry-in执行的窗口长度为最差, 即
|
文献[4]证明了当carry-in的实例执行模式为处理器个数是无限多的模式执行时carry-in的工作量最大, 下文按此结论进行分析.
2.2 基本分析方法及其悲观性为了忽略DAG任务的结构特性, 文献[10]把DAG任务按照所有WCET平均分配到所有处理器上执行的模式进行分析, 如图 2所示.
|
图 2 基本分析方法示例 Fig.2 Illustration of baseline method |
在该模式下任务的可调度性判定条件为
|
该方法忽略DAG执行结构会在问题窗口内代入更多的干涉量.为了改善这一悲观性, 文献[12]提出了目前最新的研究方法.
2.3 DAG-G-EDF调度方法及悲观性文献[12]的基本思路是:在计算carry-in的工作量时, 考虑每个任务的松弛时间, 从而减少carry-in实例执行窗口的长度.该方法下的carry-in长度最差为
|
式中Si表示任务τi的最差松弛时间.然而该方法依然存在悲观性:首先, 通过对窗口和任务的执行观察发现, 在可调度的前提下每个任务的完成不晚于其截止期, 则问题窗口长度不大于Dk, 因此按照Dk分析的松弛时间太过悲观; 其次, carry-in任务实例执行在最坏情况下, carry-in工作量的估算可以更加精确.针对这两点的悲观性, 下文提出IMP-G-EDF-RTA分析方法.
3 IMP-G-EDF-RTA分析为了解决上文中的悲观性, 首先提出carry-in实例工作量的估算方法.carry-in实例执行窗口定义为从问题窗口开始时刻到该实例完成执行的时间窗口.然后提出问题窗口内每个任务的最大工作量的计算.最终提出被分析任务的上界.
|
表 1 算法1 Table 1 Algorithm 1 |
假设τi的carry-in实例窗口长度为LiCI, 则从该实例释放到问题窗口开始的长度至少为Liout=max(0, Ti-LiCI-(Ti-Ri)), 如图 3所示.在该窗口内carry-in实例的执行受到高优先级任务实例的干涉, 每个任务的干涉量最多是
|
图 3 Carry-in实例窗口的组成 Fig.3 Constitution of carry-in window |
|
任务τi的carry-in任务实例在时间窗口Liout内执行的工作量至少为Wiout(Liout), Wiout(Liout)可由算法1计算.算法1的基本思路是:在窗口长度为Liout内的carry-in实例的工作量根据窗口提供的计算能力减去高优先级任务实例在最坏情况下执行的工作量, 则剩余的可用于carry-in实例执行, 再结合carry-in实例节点的结构特性进行估算.在算法1中s[u]和f[u]分别表示节点u的开始执行的时间和完成执行的时间.
引理2 任务τi的carry-in任务实例, 在时间窗口LiCI内执行的工作量最多为WiCI(LiCI), WiCI(LiCI)=Ci-Wiout(max(0, Ti-LiCI-(Ti-Ri))).
证明 一个任务实例的最大工作量是Ci, 已知在carry-in实例窗口开始前至少已经完成了Wiout(max(0, Ti-LiCI-(Ti-Ri))), 剩下的工作量需要在carry-in执行窗口内完成, 最多是Ci-Wiout(max(0, Ti-LiCI-(Ti-Ri))).
该方法的优越性主要体现在在LiCI长度的时间窗口里不一定都在执行carry-in实例.而该窗口内carry-in最晚可以执行到的时刻可以根据该实例承受的最大干涉去估计, 从而减少carry-in实例的干涉.
3.2 工作量的估算本节提出一种更加精确的carry-in实例执行窗口长度计算方法.首先, 假设任务τk从释放到完成执行的长度为Xk.显而易见, Xk≤Dk.在τk问题窗口内, 任务τi的body实例的计算发生了变化, 由于任务τk在Xk内完成了执行, 则只有在Xk内的工作量才能干涉任务τk的执行.任务τi的body任务实例最多为
|
Pi(Xk, Lk) < 0表示任务τi没有body实例, 则carry-in长度为LiCI(Xk, Lk), 如图 4所示.
|
图 4 Pi(Xk, Lk) < 0情况下, carry-in实例执行窗口的长度 Fig.4 Length of carry-in window when Pi(Xk, Lk) < 0 |
而当Pi(Xk, Lk)≥0需要在Pi(Xk, Lk)长度上减去body实例的周期长度再减去松弛时间, 剩余的是carry-in的长度LiCI(Xk, Lk), 如图 5所示.
|
图 5 Pi(Xk, Lk)≥0情况下, carry-in实例执行窗口的长度 Fig.5 Length of carry-in window when Pi(Xk, Lk)≥0 |
因此,
|
其中:
|
综上, 每个任务τi在被分析任务τk长度为Lk的问题窗口内的工作量为
|
被分析任务τk除了关键路径上的节点, 其他节点的执行会干涉关键路径上节点的执行, 总的干涉量之和为
|
该分析方法从任务τk可能的完成时刻进行分析, 避免由于窗口过大造成的干涉量的悲观估计, 因此本文的分析结果优于文献[12]的分析方法.
3.3 IMP-G-EDF-RTA方法本文分析了任何一个任务τi在已知被分析任务的问题窗口长度内的工作量.根据问题窗口的定义Lk≤Dk, 最悲观情况下Lk=Dk.显然Xk的取值满足Lk≤Xk≤Dk.
已知Xk和Lk的情况下, 所有可以干涉任务τk执行的工作量总和定义为Ωk(Xk, Dk):
|
定理1 Rk是式(1)从X=LCk开始迭代的最小不动解,
|
(1) |
则Rk是任务τk的WCRT上界.
证明 根据上文的分析, 该定理显然正确.
4 实验分析采用仿真实验, 验证当参数不同时本文所提算法的性能.基于Win 7系统下的python 3.6.5进行仿真实验.
4.1 任务集的随机生成本文采用文献[13]提出的DAG任务集生成方法随机生成任务集.每个任务τi各个参数按照以下方式生成:1)周期Ti采用均匀分布取值，范围为[100, 1 000], 截止期Di=Ti; 2)任务τi的节点个数也采用均匀分布从[30,40]内取值; 3)1个DAG最多有Ni(Ni-1)/2条边，为了表示随机性，每个DAG任务边的数量用参数Pr×(Ni×(Ni-1))/2表示，当Pr=1时表示DAG图是全连接的，当Pr=0时表示图中没有边；4)对于τi每个节点的WCET从[1, Ti/Ni]范围内随机生成.
基本分析方法表示为Base-line; 最新算法表示为DAG-G-EDF; 本文提出的算法称为IMP-G-EDF.通过接受率和提升率来对比三个算法.
接受率(Acc. Ratio):算法A的接受率定义为可以被算法A调度的任务集数量和全部被调度的任务集数量的比值.
提升率(Imp.Ratio):算法A和Base-line比较的提升率定义为该算法比Base-line算法增加的可调度性的平均比率.
4.2 仿真结果实验1对比三个算法的可调度性随利用率变化的趋势.基本参数设计:图 6中曲线的每一个点表示在该利用率下算法接受率, 而图 7中的曲线每个点表示该利用率下对应算法的提升率.利用率本文采用了规范化利用率, 即Um=U/M.每个任务的并行度也可用参数Pr表示, DAG任务中边越多, 表示节点需要满足的制约关系越多, 并行度越低.因此仿真实验时取Pr∈(0.1, 1].该实验包括两个结果, 对应不同的处理器个数的结果.
|
图 6 三个算法的接受率比较 Fig.6 Acceptance ratio for three algorithms |
|
图 7 算法的提升率 Fig.7 Improvement ratio of algorithms |
仿真实验取M=8, 实验步骤如下:
1) 对利用率进行分段, 从0到1取15个利用率段, 每一个利用率段表示为(Umin, Umax].
2) 针对每个利用率段, 首先生成一个具有两个任务的任务集; 该任务集中的利用率范围为(Umin, Umax]; 其他参数采用4.1节中任务各个参数的生成方法生成.
3) 如果任务集的利用率U>Umax, 抛弃该任务集回到2).
4) 先判定该任务集的可调度性，然后根据调度后的结果进行操作, 如果新算法不能调度该任务集则回到2), 否则增加一个任务回到3).
图 6的实验结果表明本文提出的算法在接受率层面较DAG-G-EDF算法有所提升，且在Um取值为0.5时接受率提高了25%.图 7的实验结果表明在WCRT上的改进最高可达30%.
为了观察相同并行度不同处理器个数下的任务可调度性变化的趋势, 固定Pr=0.5, 对处理器个数为[2,16]上任务集利用率为[3.9, 4.1]上任务集的可调度性的变化规律进行了实验.实验中每个采样点取样5 000个任务集, 任务的各项参数根据4.1节的介绍获取.实验结果如图 8所示, 在处理器个数比较多的情况下两个算法的可调度性趋于1, 因为任务集的利用率远小于处理器个数.在处理器个数相对较少时, 本文算法的接受率明显高于DAG-G-EDF算法和Base-line算法, 本文所提算法的接受率最多高于DAG-G-EDF 30%.
|
图 8 处理器参数M不同时的接受率实验 Fig.8 The test of acceptance ratio for the varying M |
1) 本文分析了DAG并行任务模型G-EDF可调度性分析的基本现状及悲观性.
2) 结合造成DAG并行任务模型G-EDF可调度性分析悲观的原因, 提出一种新的基于窗口长度的carry-in实例工作量估算方法.
3) 结合新的carry-in估算方法, 提出一种更加精确的问题窗口工作量估算方法.
4) 为了验证本文算法的性能, 进行了随机仿真实验, 实验结果表明本文提出的算法最高可提升目前最好算法的25%的性能.
| [1] |
Intel.Intel Xeon Phi product family[DB/OL]. (2013-07-03)[2017-06-20]. http://www.intel.com/content/www/us/en/processors/xeon/xeon-phi-detail.html, 2018.
|
| [2] |
Lakshmanan K, Kato S, Rajkumar R.Scheduling parallel real-time tasks on multi-core processors[C]//IEEE Real-Time Systems Symposium.San Diego: IEEE Computer Society, 2010: 259-268.
|
| [3] |
Saifullah A, Agrawal K, Lu C, et al.Multi-core real-time scheduling for generalized parallel task models[C]//Real-Time Systems Symposium.San Juan: IEEE, 2012: 217-226.
|
| [4] |
Chwa H S, Lee J, Phan K M, et al.Global EDF schedulability analysis for synchronous parallel tasks on multicore platforms[C]//Euromicro Conference on Real-Time Systems.Paris: IEEE Computer Society, 2013: 25-34.
|
| [5] |
Cláudio M, Bertogna M, Pinho L M.Response-time analysis of synchronous parallel tasks in multiprocessor systems[C]//International Conference on Real-Time Networks and Systems.Versailles: ACM, 2014: 3-12.
|
| [6] |
Nelissen G, Berten V, Milojevic D.Techniques optimizing the number of processors to schedule multi-threaded tasks[C]//Euromicro Conference on Real-Time Systems.Pisa: IEEE Computer Society, 2012: 321-330.
|
| [7] |
Axer P, Quinton S, Neukirchner M, et al.Response-time analysis of parallel fork-join workloads with real-time constraints[C]//Euromicro Conference on Real-Time Systems.Paris: IEEE Computer Society, 2013: 215-224.
|
| [8] |
Li J, Agrawal K, Lu C, et al.Analysis of global EDF for parallel tasks[C]//Euromicro Conference on Real-Time Systems.Paris: IEEE Computer Society, 2013: 3-13.
|
| [9] |
Bonifaci V, Marchetti-Spaccamela A, Stiller S, et al.Feasibility analysis in the sporadic DAG task model[C]//Real-Time Systems.Vancouver: IEEE, 2013: 225-233.
|
| [10] |
Baruah S, Bonifaci V, Marchettispaccamela A, et al.A for recurrent real-time processes[C]//Real-Time Systems Symposium.San Juan: IEEE Computer Society, 2012: 63-72.
|
| [11] |
Li J, Chen J J, Agrawal K, et al.Analysis of federated and global scheduling for parallel real-time tasks[C]//Euromicro Conference on Real-Time Systems.Madrid: IEEE Computer Society, 2014: 85-96.
|
| [12] |
Chwa H S, Lee J, Lee J, et al.
Global EDF schedulability analysis for parallel tasks on multi-core platforms[J]. IEEE Transactions on Parallel & Distributed Systems, 2017, 28(5): 1331–1345.
|
| [13] |
Cordeiro D, Mounié G, Perarnau S, et al.Random graph generation for scheduling simulations[C]//Proceedings of the 3rd International ICST Conference on Simulation Tools and Techniques.Torremolinos: ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), 2010: 60-71.
|