韩美灵, 邓庆绪, 张天宇, 林宇晗
东北大学?计算机科学与工程学院, 辽宁 沈阳 110169
收稿日期：2018-01-22
基金项目：国家自然科学基金资助项目(61472072, 61528202);辽宁重大装备制造协同创新中心资助项目。
作者简介：韩美灵(1988-), 女, 山东聊城人, 东北大学博士研究生;
邓庆绪(1970-), 男, 河南南阳人, 东北大学教授, 博士生导师。

摘要：由于未考虑DAG(directed acyclic graph)任务的自身结构, 基于G-EDF(global earliest deadline first)的DAG并行任务模型的可调度性分析存在很大的悲观性, 因此本文针对DAG任务集在多处理器系统中采用G-EDF调度策略下的响应时间分析进行了研究.首先针对carry-in任务实例执行的情况提出更加精确的carry-in工作量估算方法.基于该carry-in工作量估算方法提出一种基于完成时间的问题窗口工作量估算方法.最后, 结合上述两个改进策略提出了基于G-EDF的DAG任务响应时间分析方法.仿真实验表明, 所提出的方法较目前已知的调度策略方法可调度性至少提高15%, 最高可达25%.
关键词：嵌入式实时系统多核处理器并行任务模型全局调度响应时间分析
Response Time Analysis of Multiprocessor Systems for DAG Parallel Tasks Based on G-EDF
HAN Mei-ling, DENG Qing-xu, ZHANG Tian-yu, LIN Yu-han
School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China
Corresponding author: DENG Qing-xu, E-mail:hanmeiling@stumail.neu.edu.cn
Abstract: Since the self-structure of the DAG(directed acyclic graph)task is not considered, the schedulability analysis of the DAG parallel task model based on G-EDF(global earliest deadline first)is very pessimistic. The response time analysis of the DAG task set under the G-EDF scheduling strategy in multiprocessor systems was studied in this paper. First, a more accurate carry-in workload estimation method was proposed for the execution of the carry-in task instance. Then a method for estimating the problem window workload of completion time was put forward based on the carry-in workload estimation method. Based on the two proposed methods, this paper proposed a response time analyzing method to derive a response time upper bound of each task. The experiments show that the proposed method outperforms the state-of-the-art method by at least 15% and at most 25%.
Key words: embedded real-time systemsmultiprocessorsparallel tasks modelglobal schedulingresponse time analysis
随着半导体技术的发展, 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调度策略进行调度时的可调度性.任务集表示为τ={τ₁, …, τ_n}.1个DAG任务τ_i表示为(G_i, D_i, T_i).其中, G_i表示有向无环图, D_i表示任务τ_i的相对截止期, T_i表示任务τ_i的两个连续实例的最小释放时间间隔也称为周期.G_i=(V_i, E_i), V_i为G_i所有节点的集合, E_i为G_i所有边的集合.每个节点θ_{i, u}∈V_i的最差执行时间(WCET: worst case execution time)表示为e_{i, u}.E_i中的1条有向边(θ_{i, u}, θ_{i, v})表示节点θ_{i, v}必须在节点θ_{i, u}完成后才能开始执行.节点θ_{i, u}进入就绪状态当且仅当其所有直接前继完成了执行.
DAG任务τ_i的1条路径定义为G_i的1个节点序列θ_{i, 1}, …, θ_{i, f}, 该节点序列中连续的2个节点之间存在1条有向边, 即(θ_{i, j}, θ_{i, j+1})∈E_i, 1≤j < f.路径的长度定义为路径上所有节点的WCET之和.G_i的关键路径定义为最长路径，表示为LC_i.任务τ_i的WCET表示为C_i:
DAG任务τ_i会释放无限多的实例, 每个实例的响应时间定义为从其释放到其完成之间的时间间隔.任务τ_i的响应时间定义为所有实例的最差响应时间(WCRT: worst case response time):R_i=max(f_i-r_i).显然枚举所有实例是无法实现的, 因此常用方法是估算一个任务的WCRT.本文只考虑限制截止期任务的情况, 即:D_i≤T_i.显而易见, LC_i严格不大于D_i时任务τ_i才能被调度, 但C_i≤D_i不是必须的.任务τ_i的利用率表示为U_i, 且定义U_i=C_i/T_i.而任务集的利用率用U表示, 且定义
任务的优先级按照EDF进行分配, 即每个已经释放且未完成的任务实例的最小绝对截止期优先调度的策略进行调度.本文假设处理器时钟是单位时间的, 即所有的任务相关参数都是正整数.
2 最新研究方法及其悲观性分析本节首先介绍常用的多核处理器分析方法的基础理论^[10], 然后对文献[12]提出的G-EDF分析方法进行介绍, 最后分析该方法的悲观性.本文以任务τ_k作为被分析任务进行阐述.
2.1 问题窗口和工作量定义1(问题窗口)设被分析任务τ_k在r_k处释放在f_k处完成执行, 则窗口[r_k, f_k]称为任务τ_k的问题窗口.
任务集中的任何一个除了τ_k以外的任务在问题窗口内产生的工作量可以由两种类型的实例组成:carry-in任务实例(该类实例在问题窗口前释放, 但截止期在问题窗口内)和body任务实例(释放和截止期都在问题窗口内的实例).每个任务τ_i只有一个carry-in任务实例称之为J_i^CI, 而body任务实例有多个.
引理1(最坏执行情况)当d_i=d_k时, 任务τ_i在问题窗口[r_k, f_k]内的工作量最大.
如图 1所示, 该引理的正确性是显而易见的.任务τ_i的body实例在窗口[r_k, f_k]内的个数最多为
图 1(Fig. 1)

图 1 任务τi的最坏执行情况Fig.1 Worst case execution of task τi

图 1仅仅为了示意任务的释放和执行, 因此用1个矩形表示DAG任务的执行是合理的.任务τ_i在长度为L_k的问题窗口内的工作量组成为N_i^b个body实例和1个carry-in实例.因此, carry-in执行的窗口长度为最差, 即
文献[4]证明了当carry-in的实例执行模式为处理器个数是无限多的模式执行时carry-in的工作量最大, 下文按此结论进行分析.
2.2 基本分析方法及其悲观性为了忽略DAG任务的结构特性, 文献[10]把DAG任务按照所有WCET平均分配到所有处理器上执行的模式进行分析, 如图 2所示.
图 2(Fig. 2)

图 2 基本分析方法示例Fig.2 Illustration of baseline method

在该模式下任务的可调度性判定条件为
该方法忽略DAG执行结构会在问题窗口内代入更多的干涉量.为了改善这一悲观性, 文献[12]提出了目前最新的研究方法.
2.3 DAG-G-EDF调度方法及悲观性文献[12]的基本思路是:在计算carry-in的工作量时, 考虑每个任务的松弛时间, 从而减少carry-in实例执行窗口的长度.该方法下的carry-in长度最差为
式中S_i表示任务τ_i的最差松弛时间.然而该方法依然存在悲观性:首先, 通过对窗口和任务的执行观察发现, 在可调度的前提下每个任务的完成不晚于其截止期, 则问题窗口长度不大于D_k, 因此按照D_k分析的松弛时间太过悲观; 其次, carry-in任务实例执行在最坏情况下, carry-in工作量的估算可以更加精确.针对这两点的悲观性, 下文提出IMP-G-EDF-RTA分析方法.
3 IMP-G-EDF-RTA分析为了解决上文中的悲观性, 首先提出carry-in实例工作量的估算方法.carry-in实例执行窗口定义为从问题窗口开始时刻到该实例完成执行的时间窗口.然后提出问题窗口内每个任务的最大工作量的计算.最终提出被分析任务的上界.
表 1(Table 1)

表 1 算法1Table 1 Algorithm 1 Algorithm 1 Wiout(Liout) 1: 2: 3: 4: if Leftout>0 then 5: ??for each thread Θi, u∈Vi do 6: ????s[u]←0, f[u]←s[u]+e(u) 7: ??end for 8: ??GiT←(Vi, EiT) 9: ??topolohically sorted the thread in GiT 10: ??for each thread Θi, u∈Vi do 11: ????for each thread Θi, v∈ Children [U] do 12: ??????s[v]←f[u], f[v]←s[v]+e(u) 13: ????end for 14: ??end for 15: ??for each thread Θi, u∈Vi do 16: ????if f[u]≤Leftoutthen 17: ??????Wiout←Wiout+e(u) 18: ????else 19: ??????if s[u]≤Liout and f[u] >Leftoutthen 20: ??????Wiout←Wiout+max(0, Leftout-s[u]) 21: ??????end if 22: ????end if 23: ??end for 24: else 25: ??Wiout←0 26: end if 27: return Wiout

表 1 算法1 Table 1 Algorithm 1

3.1 Carry-in工作量估计技术假设τ_i的carry-in实例窗口长度为L_i^CI, 则从该实例释放到问题窗口开始的长度至少为L_i^out=max(0, T_i-L_i^CI-(T_i-R_i)), 如图 3所示.在该窗口内carry-in实例的执行受到高优先级任务实例的干涉, 每个任务的干涉量最多是
图 3(Fig. 3)

图 3 Carry-in实例窗口的组成Fig.3 Constitution of carry-in window

任务τ_i的carry-in任务实例在时间窗口L_i^out内执行的工作量至少为W_i^out(L_i^out), W_i^out(L_i^out)可由算法1计算.算法1的基本思路是:在窗口长度为L_i^out内的carry-in实例的工作量根据窗口提供的计算能力减去高优先级任务实例在最坏情况下执行的工作量, 则剩余的可用于carry-in实例执行, 再结合carry-in实例节点的结构特性进行估算.在算法1中s[u]和f[u]分别表示节点u的开始执行的时间和完成执行的时间.
引理2??任务τ_i的carry-in任务实例, 在时间窗口L_i^CI内执行的工作量最多为W_i^CI(L_i^CI), W_i^CI(L_i^CI)=C_i-W_i^out(max(0, T_i-L_i^CI-(T_i-R_i))).
证明??一个任务实例的最大工作量是C_i, 已知在carry-in实例窗口开始前至少已经完成了W_i^out(max(0, T_i-L_i^CI-(T_i-R_i))), 剩下的工作量需要在carry-in执行窗口内完成, 最多是C_i-W_i^out(max(0, T_i-L_i^CI-(T_i-R_i))).
该方法的优越性主要体现在在L_i^CI长度的时间窗口里不一定都在执行carry-in实例.而该窗口内carry-in最晚可以执行到的时刻可以根据该实例承受的最大干涉去估计, 从而减少carry-in实例的干涉.
3.2 工作量的估算本节提出一种更加精确的carry-in实例执行窗口长度计算方法.首先, 假设任务τ_k从释放到完成执行的长度为X_k.显而易见, X_k≤D_k.在τ_k问题窗口内, 任务τ_i的body实例的计算发生了变化, 由于任务τ_k在X_k内完成了执行, 则只有在X_k内的工作量才能干涉任务τ_k的执行.任务τ_i的body任务实例最多为
P_i(X_k, L_k) < 0表示任务τ_i没有body实例, 则carry-in长度为L_i^CI(X_k, L_k), 如图 4所示.
图 4(Fig. 4)

图 4 Pi(Xk, Lk) < 0情况下, carry-in实例执行窗口的长度Fig.4 Length of carry-in window when Pi(Xk, Lk) < 0

而当P_i(X_k, L_k)≥0需要在P_i(X_k, L_k)长度上减去body实例的周期长度再减去松弛时间, 剩余的是carry-in的长度L_i^CI(X_k, L_k), 如图 5所示.
图 5(Fig. 5)

图 5 Pi(Xk, Lk)≥0情况下, carry-in实例执行窗口的长度Fig.5 Length of carry-in window when Pi(Xk, Lk)≥0

因此,
其中:
综上, 每个任务τ_i在被分析任务τ_k长度为L_k的问题窗口内的工作量为
被分析任务τ_k除了关键路径上的节点, 其他节点的执行会干涉关键路径上节点的执行, 总的干涉量之和为
该分析方法从任务τ_k可能的完成时刻进行分析, 避免由于窗口过大造成的干涉量的悲观估计, 因此本文的分析结果优于文献[12]的分析方法.
3.3 IMP-G-EDF-RTA方法本文分析了任何一个任务τ_i在已知被分析任务的问题窗口长度内的工作量.根据问题窗口的定义L_k≤D_k, 最悲观情况下L_k=D_k.显然X_k的取值满足L_k≤X_k≤D_k.
已知X_k和L_k的情况下, 所有可以干涉任务τ_k执行的工作量总和定义为Ω_k(X_k, D_k):
定理1??R_k是式(1)从X=LC_k开始迭代的最小不动解,

(1)

则R_k是任务τ_k的WCRT上界.
证明??根据上文的分析, 该定理显然正确.
4 实验分析采用仿真实验, 验证当参数不同时本文所提算法的性能.基于Win 7系统下的python 3.6.5进行仿真实验.
4.1 任务集的随机生成本文采用文献[13]提出的DAG任务集生成方法随机生成任务集.每个任务τ_i各个参数按照以下方式生成:1)周期T_i采用均匀分布取值，范围为[100, 1 000], 截止期D_i=T_i; 2)任务τ_i的节点个数也采用均匀分布从[30,40]内取值; 3)1个DAG最多有N_i(N_i-1)/2条边，为了表示随机性，每个DAG任务边的数量用参数Pr×(N_i×(N_i-1))/2表示，当Pr=1时表示DAG图是全连接的，当Pr=0时表示图中没有边；4)对于τ_i每个节点的WCET从[1, T_i/N_i]范围内随机生成.
基本分析方法表示为Base-line; 最新算法表示为DAG-G-EDF; 本文提出的算法称为IMP-G-EDF.通过接受率和提升率来对比三个算法.
接受率(Acc. Ratio):算法A的接受率定义为可以被算法A调度的任务集数量和全部被调度的任务集数量的比值.
提升率(Imp.Ratio):算法A和Base-line比较的提升率定义为该算法比Base-line算法增加的可调度性的平均比率.
4.2 仿真结果实验1对比三个算法的可调度性随利用率变化的趋势.基本参数设计:图 6中曲线的每一个点表示在该利用率下算法接受率, 而图 7中的曲线每个点表示该利用率下对应算法的提升率.利用率本文采用了规范化利用率, 即U_m=U/M.每个任务的并行度也可用参数Pr表示, DAG任务中边越多, 表示节点需要满足的制约关系越多, 并行度越低.因此仿真实验时取Pr∈(0.1, 1].该实验包括两个结果, 对应不同的处理器个数的结果.
图 6(Fig. 6)

图 6 三个算法的接受率比较Fig.6 Acceptance ratio for three algorithms

图 7(Fig. 7)

图 7 算法的提升率Fig.7 Improvement ratio of algorithms

仿真实验取M=8, 实验步骤如下:
1) 对利用率进行分段, 从0到1取15个利用率段, 每一个利用率段表示为(U_min, U_max].
2) 针对每个利用率段, 首先生成一个具有两个任务的任务集; 该任务集中的利用率范围为(U_min, U_max]; 其他参数采用4.1节中任务各个参数的生成方法生成.
3) 如果任务集的利用率U>U_max, 抛弃该任务集回到2).
4) 先判定该任务集的可调度性，然后根据调度后的结果进行操作, 如果新算法不能调度该任务集则回到2), 否则增加一个任务回到3).
图 6的实验结果表明本文提出的算法在接受率层面较DAG-G-EDF算法有所提升，且在U_m取值为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(Fig. 8)

图 8 处理器参数M不同时的接受率实验Fig.8 The test of acceptance ratio for the varying M

5 结论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.