安立奎，韩丽艳

(1. 渤海大学 数理学院，辽宁 锦州 121013; 2.渤海大学 信息科学与技术学院，辽宁 锦州 121013 )



支持指令预取和缓存划分的多核实时系统缓存WCRT最小化

安立奎*，1，韩丽艳2

(1. 渤海大学 数理学院，辽宁 锦州 121013; 2.渤海大学 信息科学与技术学院，辽宁 锦州 121013 )

对嵌入式多核实时系统，为了保证任务的可调度性和可靠性，最坏情况下的性能是一个优先考虑的问题．顺序指令预取可以提高实时任务的最坏情况下的性能，但对于实时系统中不同的子任务，在不同预取度下，指令预取获得的最坏情况下性能效率也不同，因此会影响整个实时系统的最坏情况下响应时间WCRT (Worst-Case Response Time)．本文利用缓存划分技术消除多核实时系统中多个子任务在共享缓存上的干扰，然后提出了多核实时系统的WCRT优化方法．该方法建立ILP(Integer-Linear Programming)方程，通过调整共享缓存划分因子和系统中子任务的指令预取度来最小化系统的WCRT．实验对多核上的DEBIE系统进行实例分析，结果表明优化算法在保证DEBIE系统满足时间截止期的情况下，使得优化后的WCRT比不同预取度下的WCRT平均减少12.2 %．

最坏情况下响应时间；指令预取度；缓存划分

0 引言

在多核实时系统中，任务执行时间必须满足时间截止期(Deadline)，否则将会引起灾难性后果．最坏情况执行时间WCET(Worst-Case Execution Time)分析能够获得实时任务最坏情况下的执行时间，多核实时系统的WCRT(Worst-Case Response Time)是运行在所有核上任务的结束时间的最大值，它与实时系统中每个子任务的WCET有密切关系．减少WCRT对于实时系统中任务的可靠性和可调度性来说非常重要．

许多嵌入式多核系统支持顺序指令预取技术，由于Next-N-Line指令预取代价小且容易实现，它已被许多商业处理器所采用．当访问L1指令缓存行pi时，指令预取器会预取缓存行pi+1,pi+2，…，pi+N这里N是指令预取度．顺序指令预取可以覆盖取指令过程中短的非连续流，但是它并不能消除由于长距离的转移而引起的指令缺失，因此顺序指令预取的性能获益和缺失时预取的缓存块N有很大关系．因此对具有并发多任务的实时系统，所有子任务采用相同预取度，不益于提高整个系统的WCRT．

在多核下实时系统缓存WCRT分析方面：文献〔1〕对并发程序建立MSC(Message Sequence Chart)图，通过分析并发多个任务在共享缓存上的干扰，提出了WCRT分析方法．文献〔2〕优化任务到核的映射，减少任务在共享缓存上的干扰和实时应用系统的WCRT．在文献〔1〕和〔2〕中考虑的仅是共享指令缓存，并没有分析数据在共享缓存上的干扰，也没有关注指令预取对实时系统的WCET的影响．单核下最坏情况下指令预取效率方面：文献〔3〕研究了基于Next-N-Line 的指令硬件预取技术对WCET的影响；为改进文献〔3〕中Next-N-Nine指令预取器的有效性，文献〔4〕提出一种基于循环的预取优化机制和一种针对WCET的指令预取方法．文献〔5〕提出支持指令预取和锁缓存的模型来优化实时单任务的WCET 和WCEC(Worst-Case Energy Consumption)．在文献〔3〕、〔4〕和〔5〕中，它们也仅考虑的是单核下的单层指令缓存的指令预取效率，并没有考虑多核下实时系统的指令预取效率．通过查阅文献后得知，目前没有研究人员针对嵌入式多核下结合指令预取和缓存划分的最坏情况下性能优化工作展开深入研究．

本文的研究目的是利用顺序指令预取提高多核实时系统的WCRT ，为此采用基于组(Set)缓存划分技术〔6〕，消除实时系统中并发多任务在共享缓存上干扰，保证系统WCRT可分析性，提出了多核实时系统的支持指令预取和缓存划分的WCRT优化算法．所做的贡献主要有：

1)实验验证了指令预取度对于实时任务的WCRT的重要影响．

2)设计了结合指令预取和缓存划分的ILP(Integer-Linear Programming)方程，在保证多核实时系统满足时间截止期的情况下，最小化其WCRT．

3)对实时系统DEBIE进行实例分析，验证了优化算法的有效性．

1 嵌入式多核模型和研究动机

1.1 嵌入式多核结构和任务模型

图1是一种支持指令预取的嵌入式多核模型．有NC个同构的处理器核．每个核有私有的L1指令/数据缓存，所有的核共享L2联合缓存．缓存的替换策略是LRU (Least Recently Used)．L1和L2缓存通过实时总线连接．顺序指令预取器采用支持Prefetch-on-miss预取策略的Next-N-Line指令预取．

执行环境是一个基于静态优先级的非抢占系统，每一个任务被分配给唯一的一个静态优先级，如果多个任务被映射到同一核上执行，优先级高的任务先执行．如果任务开始执行，在它完成前，不允许被别的任务抢占．任务之间的通信和同步是通过邮箱(Mailbox)，并且邮箱足够大，消息不会溢出．消息在系统内部的通信状况通过MSC描述．

1.2 支持指令预取的WCET分析

如果L2缓存划分因子已经分配给L2缓存，对于一个实时任务Ti，Tpipeline是流水线执行时间，TM是总的访存时间，支持指令预取的缓存WCETi可以通过公式(1)计算：

WCETi=Tpipeline+TM=LhitL1*nhitL1+LmissL1*nmissL1+LmissL2*nmissL2

(1)

这里LhitL1是在L1缓存命中一次延迟，nhitL1是在L1缓存命中次数，LmissL1是在L1缓存缺失一次延迟，nmissL1是在L1缓存缺失次数，LmissL2是在L2缓存缺失一次延迟，nmissL2是在L2缓存缺失次数.nhitL1,nmissL1,nmissL2通过指令预取扩展的缓存WCET分析工具——chronos〔7〕测得．

1.3 研究动机

对文献〔8〕中的实时Mälardalen wcet benchmarks，图3是不同预取度下正规化的支持指令预取的缓存WCET，当预取度N是0表示没有指令预取，关闭预取器．这里L1 指令/数据缓存是256B，直接映射，分配给每个任务的L2缓存是512B，2路组关联．支持指令预取的缓存WCET通过扩展缓存分析工具〔7〕的支持指令预取语义获得，L1缓存命中是1 circle，L1缓存缺失是6 circles，L2缓存缺失是30 circles．

通过上面的分析可以看出指令的预取度与它在最坏情况下性能获益没有线性关系，这是由于程序跳转目标的不确定性，大的预取度一方面会减少缓存的缺失，降低WCET，另一方面也可能会增加缓存的干扰，增加任务执行时候的缓存缺失和降低性能，所以较大预取度并不一定会提高任务的最坏情况下的性能，还会增加更多的系统负载和能量消耗．运行在多核系统上的实时系统具有多个相互依赖的实时任务，这样对于所有任务采用相同的预取度，不利于减少WCRT，提高实时系统的最坏情况下性能效率，因此就非常有必要对实时系统中不同的任务的指令预取度进行调整，优化系统的WCRT．

2 WCRT优化框架

如果实时系统中的所有子任务被映射到相应的处理器核，我们优化实时系统的WCRT．由于太大的预取度会给多核系统的负载带来沉重负担，影响系统性能，这里我们设定预取度的取值范围是从0到4，0表示关闭指令预取器，最大预取度阈值为4．

2.1 优化目标

实时系统RS={T,D,M,L,P,WCRTs}组成，T是其所有子任务的集合T={T1,T2,…,TNT}，D是顺序指令预取度集合D={d1,d2,…,dND}，M是任务T到预取度D的映射：M:T→D．L2缓存划分因子集合P={p1,…,pNP}，pi=i,(i=1,2,…,NP)．L是任务T到L2缓存划分因子集合P的映射：L:T→P．WCRTs是实时系统的最坏情况又响应时间.

用Pred(Ti)来表示任务Ti的前驱的集合，只有Pred(Ti)中的任务都执行结束，任务Ti才可以执行．用Starti(L,M)表示任务Ti在映射L和M下的开始时间，用Finishi(L,M)表示任务Ti在映射L和M下的结束时间．那么任务Ti的开始时间是Ti所有前驱任务完成时间的最大值，如公式(2).任务Ti的结束时间是Ti开始时间与任务Ti本身在映射L和M下最坏执行时间WCETi(L,M)的和，如公式(3)．

Starti(L,M)=Max(Finishj(L,M)),Tj∈Pred(Ti)

(2)

Finishi(L,M)=Starti(L,M)+WCETi(L,M)

(3)

实时系统在映射L和M下的支持指令预取的WCRT是运行在所有核上任务的结束时间的最大值，如公式(4)所示：

WCRT(L,M)=Max(Finishi(L,M)),1≤i≤NT

(4)

我们的优化目标是寻找映射L和M，使得多核实时系统的WCRT最小，即：

Min(Max(Finishi(L,M))),1≤i≤NT

(5)

2.2 优化方程

C1. 任务到核的映射约束

首先定义0-1变量Cij，表示任务Ti是否被映射到核Cj上，

0≤Cij≤1,where 1≤i≤NTand 1≤j≤NC

每一个任务只允许被映射到一个处理器核上，因此对于∀i

C2.核到L2缓存划分的约束

如果L2缓存共有W个组，可以被划分的组的集合P={p1,…,pNP}，定义0-1变量Lij，表示核Ci是否被分配了pj组，

0≤Lij≤1,where 1≤i≤NCand 1≤j≤NP

每一个核只允许分配一个组，因此对于∀i

同时所有核分配的总组数不能大于W，因此有

C3.任务选择WCET的约束

如果任务可以选择的预取度的集合D={d1,d2,…,dND}，定义0-1变量Tijk，表示任务Ti是采用预取度dj，此时的L2缓存划分因子是pk，因此有

用数组W[i][j][k]存储任务Ti采用预取度dj， L2缓存划分因子是pk下的WCET，用整型变量Wi表示任务Ti应该选择的WCET，因此有

定义0-1变量Aijkm，表示每一任务Ti被分配了唯一的处理器核Cj，预取度dk, L2缓存划分是pm,对1≤i≤NT,1≤j≤NC,1≤k≤ND,1≤m≤NP有

Aijkm-Cij<=0

Aijkm-Ljm<=0

Aijkm-Tikm<=0

Aijkm-Cij-Ljm-Tikm≥-2

C4. WCRT计算约束

为了计算所有任务的WCRT，我们需要计算所有核上任务的最晚结束时间．定义0-1变量Mijk表示任务Ti与任务Tj是否映射到核Ck上，有

把上面的方程线性化，有

Cik+Cjk-Mijk≤1

Cik+Cjk-2Mijk≥0

定义另外一个0-1变量Mij表示任务Ti与任务Tj是否映射到同一个处理器核上，有

把上面的方程线性化

Mij≥Mijk,∀k,1≤k≤NC

如果两个任务Ti与Tj映射到同一个处理器核上，定义0-1变量Bij，表示任务Ti在任务Tj之前执行，定义0-1变量Bji表示任务Tj在任务Ti之前执行，对于1≤i≤NT-1,i≤j≤NT有

Bij≤1

Bji≤1

Bij+Bji+Mij=2

对于任务Ti，用整型变量Si表示任务Ti的开始时间，用整型变量Fi表示任务Ti的结束时间，那么被映射到同一核上的任务，先执行的任务的结束时间要小于后执行任务的开始时间，如果没有映射到同一核上，则没有此限制，则对于1≤i≤NT-1,i≤j≤NT,有

Si-Fj+MW*Bij≥0

Sj-Fi+MW*Bji≥0

这里MW是比所有任务的WCET的和都大的一个常量．

对于所有的任务根据公式(3)，

Fi-Si-Wi=0,1≤i≤NT

对所有任务的WCRTs，有

WCRTs-Fi≥0,1≤i≤NT

C5.优化目标

我们优化的目标是满足时间截止期(Deadline)的情况下最小化WCRTs，即

WCRTs≤DEADLINE

Min WCRTs

3 实验评估

这部分我们评估实时系统的基于指令预取的WCRT优化算法．N是指令预取的预取度，当N为0时，表示没有指令预取，关闭预取器．

3.1 评估环境

我们嵌入式多核假设有4个同构的处理器核，对于每一个核，有5阶段流水，顺序执行，分支预测是完美的(Perfect)．L1指令/数据缓存是512B，直接映射，缓存行大小是16B．L2缓存的总大小是8KB，被4个处理器核共享，4路组关联，缓存行是32B，有64组．L1缓存的命中延迟是1 circle，缺失延迟是6 circles．L2缓存的缺失延迟是30 circles．利用IBM CPLEX12.2 ILP solver〔9〕来求解 WCRT优化方程.

实验使用的benchmark是DEBIE是由Patria Finavitec 和UniSpace Kent联合开发的空间碎片探测器系统〔10〕，所有的实验运行在Intel(R) Core(TM) i5-3230 机器上，有4GB内存，运行Ubuntu Linux 8.04操作系统．

3.2 实验结果

3.2.1 指令预取对实时任务最坏情况性能的影响

图4比较了DEBIE系统不支持指令预取和支持指令预取在不同预取距度下的最坏情况的WCRT．预取度N从1，2，3到4．实验结果被没有预取的WCRT(N是 0)结果归一化了．

从图4中可以看出，在不同的预取度下，系统的最坏情况下的性能得到了提升．DEBIE系统的WCRT平均被提高了53.9%．当预取度是4时候，最坏情况下的性能提高的最明显，达到了56.5%．指令预取效率比较高主要有两个方面的原因：一方面是缓存WCET分析工具〔7〕本身分析的保守性，扩大了指令预取在最坏情况下的效率；另外一方面这是由于DEBIE系统中一些WCET较大的任务都是事务密集型的，数据计算量非常小，指令预取大大减少了这些任务指令访存次数，从而节省了访存延迟，提高了实习系统在最坏情况下的性能．同时指令预取度是2的情况下的最坏情况下的性能比指令预取度是3的最坏情况下的性能要好．这也表明并不是指令预取度越大，预取的效率就越高．

3.2.2 优化算法对最坏情况性能的影响

图5是DEBIE系统优化后的WCRT和不同预取度下的WCRT比值．预取度从0，1，2，3到4，这里当N是0表示没有预取，关闭预取器．

从图5可以看出优化后的支持指令预取的最坏情况下的性能比没有预取的最坏情况下的性能提高了59.7%，这是由于整个系统的指令较多，需要进行的数据计算很少，指令预取提高最坏情况下的性能明显．同时经过优化后的WCRT比不同预取度下的WCRT平均减少了12.2%，这说明本文的实时系统缓存WCRT优化方法是有效的．

4 结论

对于性能有很高要求的并发多任务多核实时系统，我们利用缓存划分技术消除多个任务在共享缓存上的干扰，提出支持指令预取的WCRT优化方法．该方法建立ILP方程，在保证实时系统满足时间截止期的情况下，通过调整子任务的预取度和L2缓存划分因子来最小化多核实时系统的WCRT．通过对粒子探测系统DEBIE的分析，实验表明本文优化的算法是有效的，在一定范围内指令预取能够提高DEBIE的最坏情况下的性能．如果任务的并行度越高，优化的效果就会更明显．

今后我们希望能够把指令预取和缓存划分结合起来对实时系统的最坏情况下的能耗进行优化．

〔1〕LIANGY,DINGH,MITRAT,etal.Timinganalysisofconcurrentprogramsrunningonsharedcachemulti-cores.Real-TimeSystem〔J〕. 2012, 48(6): 638-680.

〔2〕DIHG H， LINGY Y, MITRA T.Shared Cache Aware Task Mapping for WCRT Minimization 〔C〕. Design Automation Conference, 2013.

〔3〕YAN J, ZHANG W. WCET analysis of instruction caches with prefetching〔J〕. ACM SIGPLAN Notices, 2007, 42(7): 175-184.

〔4〕DING Y, YAN J, ZHANG W. Optimizing Instruction Prefetching to Improve Worst-Case Performance for Real-Time Applications〔J〕. JCSE, 2009, 3(1): 59-71.

〔5〕GRAN R, SEGARRA J, RODRIGUEZ C, et al. Optimizing a combined WCET-WCEC problem in instruction fetching for real-time systems〔J〕. Journal of Systems Architecture, 2013, 59(9): 667-678.

〔6〕YU C, PETROV P.Off-chip memory bandwidth minimization through cache partitioning for multi-core platforms〔C〕.47th ACM/EDAC/IEEE Design Automation Conference, 2000.

〔7〕CHATTOPADHYAY S, ROYCHOUDHURY A. Unified cache modeling for WCET analysis and layout optimizations〔C〕.Proc of 2009 30th IEEE Real-Time Systems Symposium, 2009.

〔8〕Mälardalen Real-Time Research Center. WCET Benchmarks [EB/OL]. [2013-10]. http://www.mrtc.mdh.se/projects/wcet/benchmarks.html.

〔9〕IBM. ILOG CPLEX[EB/OL]. [2013-05]. http://www.ibm.com/software/.

〔10〕KUITUNEN J, DROLSHAGEN G, MCDONNELL J A M, et al. DEBIE - first standard in-situ debris monitoring instrument〔C〕.Proc of the Third European Conference on Space Debris, 2001.

Cache WCRT minimization for multi-cores real-time system with instruction prefetching and cache partitioning

AN Li-kui1, HAN Li-yan2

(1. School of Mathematics and Physics, Bohai University,Jinzhou 121013, China; 2. School of Information Science and Technology, Bohai University,Jinzhou 121013, China)

For the real-time system on the embedded multi-cores, the worst-case performance is a prior to be considered to guarantee the schedulability and the reliability of the tasks. Sequent instruction prefetching can improve the worst-case performance of real-time tasks. But for different subtasks in real-time system, under the different prefetching degrees, the worst-case performance efficiency gained by instruction prefetching are different, which will influence the WCRT (Worst-Case Response Time) of the whole real-time system. This paper first uses cache partitioning technology to eliminate interferences of multiple real-time subtasks on the shared cache, and then puts forward the WCRT optimization method for the multi-cores real-time system. This method establishes IIP(Integer-linear programming) to minimize the WCRT of real-time system through adjusting instruction prefetching degrees and cache partitioning factors. DEBIE system on the multi-cores is analyzed in experiment, the experiment results show that the optimization method can reduce the WCRT of the DEBIE system 12.2% on an average than those under the different instruction prefetching degrees when guarantees the DEBIE system meet the time deadline.

worst-case response time; instruction prefetching degree; cache partitioning

2016-08-08.

辽宁省自然科学基金项目(No：LN2014160)；辽宁省教育厅项目(No： L2013424).

安立奎(1978-)，男，讲师，主要从事计算机体系结构、实时计算方面的研究.

anlikui2012@126.com．

TP314

A

1673-0569(2016)04-0365-08