指令预取感知的多核系统WCRT和WCEC优化

韩丽艳，安立奎

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

0 引 言

对于嵌入式多核下的实时系统，最坏情况下响应时间(worst-case response time，WCRT)是一个优先考虑的问题，来保证实时任务的可靠性和可调度性[1]。同时对于一些能量供应受限的实时系统，例如卫星的传感监视系统，普适系统，最坏情况下的能量消耗(worst-case energy consumption，WCEC)也是一个非常重要的因素[2]。

许多嵌入式多核系统支持顺序指令预取技术来提高系统的性能，文献[3]研究表明硬件预取也能够降低系统的能耗。实时系统通常具有多个并发个子任务，由于系统中的子任务有事务密集型的，也有数据密集型的，顺序指令预取的性能和能量效率就与指令预取度有着密切关系,如果这些子任务采用相同预取度，不利于提高实时系统的性能和降低系统的能耗。

目前文献[4]提出一种多核实时系统的WCRT分析方法，通过分析并发多个任务在共享缓存上的干扰来实现。文献[5]通过优化任务到核的映射，减少实时系统的WCRT。文献[4-5]并没有关注指令预取对与实时系统的最坏情况下的能耗的影响。文献[6-7]研究了Next-N硬件指令预取技术对WCET(worst-case execution time)的影响，考虑的仅是单核下的单级指令缓存，并没有考虑多核实时系统的多级缓存，也没有考虑实时系统最坏情况下的能量效率。文献[8]用循环译码的指令缓存减少能量消耗，提出了一个支持指令预取的能量有效的单核嵌入式模型。文献[9]用单层指令预取缓冲区和锁缓存来优化任务的WCET和WCEC。文献[10]提出一种基于基本块的指令预取方法来优化系统WCET的评估值。

针对具有多级缓存的嵌入式多核系统，目前还没有利用指令预取来优化其最坏情况下性能和能量消耗方面的研究工作。为此，文中提出了支持指令预取的WCRT和WCEC优化模型，设计了相应的优化算法，通过实例分析验证了优化算法的有效性。

1 支持指令预取的嵌入式多核模型

1.1 嵌入式多核结构

图1 支持指令预取器的嵌入式多核架构

并发多任务的执行环境是一个基于静态优先级的非抢占系统，假设实时系统有NT个相互依赖的实时任务。这些任务根据它们之间可并行化的关系被映射到了NC(NC<6)处理器核，与实时系统无关的非实时任务都被映射到了剩下的核中。这里，缓存划分的目的是为了消除并发的多个实时任务在共享缓存上的干扰，确保实时任务的时间可分析性。L2优先分给实时任务使得每个核上的实时任务WCET满足其截止期，剩余的L2缓存分给非实时任务。

1.2 能量模型

文中采用文献[12]中的能量消耗计算模型，对于不同的预取度n(n≥0)，当n为0时，表示没有采用预取操作，这时候关闭预取器，式(1)计算单个实时任务T支持指令预取的最坏情况下的能耗：

E(T,n)=Estatic(n)+Edynamic(n)

(1)

其中,

Ec_dynamic(n)=Ec*cn,Ep_dynamic(n)=Ep*pn

任务T最坏情况下总的能耗是由最坏情况下的静态能耗Estatic(n)和动态能耗Edynamic(n)组成。其中Cstatic，pstatic分别是处理器和预取器的静态能耗，tn是当预取度是n时的任务最坏情况执行时间，当n=0时，意味着关闭预取器。动态能耗Edynamic(n)由处理器和预取器的动态能耗组成，Ec表示每次访问存储器所耗费在存储系统上的能耗，cn是当预取度为n时的最坏情况下访存次数。Ep表示每次预取操作预取器的动态能耗，pn是最坏情况下的预取操作次数。

2 支持指令预取的WCRT和WCEC优化

2.1 实时系统WCRT和WCEC优化模型

实时系统RS={TS,D,M,WCRT,WCEC}，TS是其所有子任务的集合TS={T1,T2,…,TNT}，D是顺序指令预取度集合D={0,1,…,Np}，0表示关闭指令预取器，M是任务TS到预取度D的映射：M:TS→D。

通过实时系统的MSG(message sequence graph)图，得到了实时系统任务之间的依赖关系，用Pred(Ti)来表示任务Ti的所有前驱任务的集合，Start(M,Ti)表示任务Ti的在映射M下的开始时间，Finish(M,Ti)表示任务Ti在映射M下的结束时间， WCET(M,Ti)表示任务Ti在映射M下的最坏情况执行时间，任务Ti的开始时间是Ti所有前驱任务完成时间的最大值，如式(2)，任务Ti的结束时间是Ti开始时间与WCET(M,Ti)的和，如式(3)：

Start(M,Ti)=Max(Finish(M,Ti)),Tj∈Pred(Ti)

(2)

Finish(M,Ti)=Start(M,Ti)+WCET(M,Ti)

(3)

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

WCRT=Max(Finish(M,Ti)),1≤i≤NT

(4)

为了通过上面的公式计算实时系统的WCRT，文中根据MSG建立与实时系统相对应的有向无环任务图TG=(V,E)，每个节点vi∈V表示一个实时任务Ti，每条有向边ei∈E表示任务间的依赖关系。每条边上有一个权值，它代表这条边的始点代表的任务Ti在映射M下支持指令预取的WCET。为了计算整个系统的WCRT，文中需要给这个无环图的终节点再增加一个汇集节点T_end作为任务图的终点，那么整个实时系统的WCRT是运行在所有核上的任务的结束时间的最大值，也就是TG的源点(开始任务)到汇集节点(终止任务)的关键路径长度。

实时系统在最坏情况下的能量消耗WCEC是所有子任务在映射M下最坏能量消耗的和，如式(5)，其中WCEC(M,Ti)是任务Ti在映射M下的WCEC。

(5)

文中的优化目标是寻找映射M，使得在实时系统的WCRT最小化的情况下，WCEC最小，即：

(6)

当，

Minize(Maxmize(Finish(M,Ti))),1≤i≤NT

(7)

2.2 WCRT和WCEC优化算法

2.2.1 WCRT和WCEC优化原理

对于实时系统，WCET(dj,Ti)表示任务Ti在预取距离dj下的WCET，首先通过式(8)确定映射Mp，对于每一个子任务Ti，在给定的预取度范围D内，Mp确定它取得最小WCET的预取距离dj:

(8)

在映射Mp下，计算TG的关键路径P={Tp1,Tp2,…,Tpn},关键路径P的长度是整个实时系统的最小化的WCRT。此时令M(Ti)=Mp(Ti),如果Ti∈P。

对于非关键路径上的实时任务Tj∉P，在不改变关键路径的情况下，最小化Tj的WCET并不能够减小整个系统的WCRT，这时候取它们的能量获益最高的预取度，会降低整个系统的能量消耗。M(Tj)=dk，这里dk使得任务Tj在不改变TG的关键路径情况下WCEC最小。

下面通过一个例子对WCRT和WCEC优化方法进行说明。假设有两个核，实时系统具有6个子任务，图2是其MSG描述，图3是其相应的TG，其边上的权值是所有子任务支持指令预取的不同预取度下最小的WCET。

图2 实时系统MSG

图3 实时系统TG

由TG可以计算从任务T1到任务Tend的关键路径P:T1→T3→T5→Tend，路径长度是800，这里整个实时系统的最优的WCRT就是800。对于非关键路径P:T1→T2→T4→T6→Tend上的实时任务T2，T4，T6，为了不影响与它们对应的关键路径P，它们总共可以延长100，在这个范围内，再次调整T2，T4，T6的指令预取度，使得能量获益最大。

2.2.2 WCRT和WCEC优化算法实现

优化算法的难点主要有两处：一是如何识别出非关键子路径，计算非关键子路径的可以被延长的时间片；二是如何把时间片分给非关键子路径上的每个任务，取得能量收益的最大化。

对于顺序指令预取，不同的预取度N对于系统的性能和能耗都有不同的影响。矩阵元素P[i][j]和E[i][j]分别存储任务Ti(1≤i≤NT)在预取度j(0≤j≤NP)下的最坏情况下的性能和能量消耗。P_D[i](1≤i≤NT)表示任务Ti在结合性能和能耗优化后，在执行时候的应该采用的预取度。非关键子路径构建算法如下：

算法1：非关键子路径构建。

输入：任务TG，P[i][j]，P_D[i](初始化为0)。

输出：优化后的WCRT，非关键子路径集合NPS，P_D[i](性能优化后的预取度)。

(1)通过P[i][j]把任务Ti取得最好的WCET的预取度k赋值给P_D[i]，∀j∈[0,NP],p[i][k]≤p[i][j]，同时给TG中与Ti相对应的边赋最优的WCET值。

(2)根据实时系统的TG，P_D[i]和P[i][j]计算最优情况下支持指令预取的关键路径P和WCRT。

(3)对所有非关键路径上的任务，按拓扑序列构建任务队列TQ。

(4)从TQ队头选择一个任务Tj，以Tj直接前驱Tk(关键任务)为头构建非关键子路径队列NP。从Tj开始，依次在TQ中寻找每个非关键任务的直接后继Tm，并把Tm从TQ中删除，加入到NP队尾，直到任务Tm的直接后继为一关键任务Tc，把Tc也加入到NP中，把NP加入到NPS中。

(5)重复过程4，构建非关键子路径集合NPS={NP1,NP2,…,NPn},直到TQ为空。

图3中的T2，T4，T6是非关键路径上的任务，按拓扑序列TQ={T2,T4,T6}。第1个非关键任务是T2，它的直接前驱T1作为非关键子路径队列NP1的队头，T2的直接后继是T4,把T4从TQ中删除，插入到NP1队尾，T4的直接后继是T6，它也被插入到NP1队尾。T6的后继是关键任务Tend,把Tend也加入NP1队尾，此时NP1是一条非关键子路径。这时非关键任务队列TQ为空，算法结束。至此图3所示的TG中存在一条非关键子路径NP1={T1,T2,T4,T6,Tend}，非关键路径长度是700。

对于一条非关键子路径队列NP，它可以被延长的时间片是从队头到队尾之间关键路径长度与非关键路径长度的差。

在非关键子路径上的任务，文中用穷举法在允许被延长的时间内，调整实时任务的预取度，优化能耗，P_E[i](1≤i≤NT)表示任务Ti在结合性能和能耗优化后，在执行时应该采用的预取度。优化算法如下：

算法2：优化WCEC。

输入：实时系统任务图TG，非关键子路径集合NPS={NP1,NP2,…,NPn}，P[i][j]，E[i][j]，P_D[i]。

输出：优化后的WCEC，P_E[i](结合性能和能耗优化后的预取度)。

(1)对每一个非关键子路径NPi={Ti1,Ti2,…,Tin}，计算NPj队列中两个关键任务Ti1和Tin之间的关键路径的长度ti，它是两个关键任务最早开始时间的差值。

(2)计算最优性能下非关键子任务的能量消耗：

Ei=Ε[i2][P_D[i2]]+E[i3][P_D[i3]]+…+E[in-1][P_D[in-1]]

(3)用穷举法求出在时间不超出ti情况下的取得最优能耗的指令预取度。

FOR(ki2from 0 toNP) DO

FOR(ki3from 0 toNP) DO

……

FOR(kin-1from 0 toNP) DO

IF(P[i1][P_D[i1]]+P[i2][ki2]+…+P[in-1][kin-1]≤ti)THEN

IF(E[i2][ki2]+E[i3][ki3]+…+E[in-1][kin-1]≤Ei)THEN

Ei=E[i2][kι2]+…+E[in-1][kin-1]

P_E[i2]=ki2;…P_E[in-1]=kin-1;

END IF

END IF

END FOR

……

END FOR

END FOR

(4)重复过程1到3，直到NPS为空。

(5)用式(9)计算实时系统优化后的最坏情况下的能量消耗。

(9)

3 实验评估

这部分评估文中支持指令预取的实时系统WCRT 和WCEC优化算法。

3.1 评估环境

嵌入式多核假设有6个同构的处理器核，对于每一个核，有5阶段流水，顺序执行。L2缓存是8 KB，缓存行是32 B，4路组关联，有64组。L1指令和数据缓存是512 B，缓存行大小是16 B，直接映射。L1缓存的命中延迟是1 circle，缺失延迟是6 circles。L2缓存的缺失延迟是30 circles，预取度N的取值范围是从0到5。

实验运行在Intel i5-3230 机器上,4 GB内存，运行Ubuntu Linux 8.04操作系统。

文中子任务的WCET通过支持指令预取的缓存WCET分析工具[13]测得。采用文献[12]中的能量消耗计算模型。芯片的工艺是32 nm,频率是1.0GH,总的缓存访问和缓存缺失可以通过静态分析获得。不同工艺下每次访问的动态能耗和静态能耗是CACTI5[14]的测试结果。硬件预取器通过一些硬件表来实现[3],它的能耗可以被精确模拟。这里假设有一个1 024-bit的指令预取缓冲队列，在32 nm工艺下，预取器消耗0.063 mW的静态能耗，每次读的能耗是0.002 nJ，每次写的能耗是0.003 nJ。

文中使用的benchmark是DEBIE空间碎片探测器系统[15]，根据DEBIE的系统状态和功能，文献[16]对系统进行了并行化处理，图4是系统的MSG图。当DEBIE的所有实时任务被映射到了核1，2，3到4，分配给每个核的L2缓存组是由它上面运行的最大的任务所决定的，最大任务的WCET最小的L2组被分配给了该处理器核，表1是分配给核1，2,3和4的L2组。余下的组被核5和核6共享。

图4 DEBIE 系统的MSG

表1 L2缓存划分结果

3.2 实验结果

3.2.1 优化算法对最坏情况下的性能的优化

为了分析文中的优化算法对于最坏情况下系统性能的影响，图5给出的是DEBIE系统在文中算法优化后的WCRT和不同预取度下的WCRT的比值，比值越小则表明性能提高越明显。

从图5可以看出，优化后的支持指令预取的最坏情况下的性能比没有预取的最坏情况下(N为0)的性能提高了57.7%，与预取度是5的比值接近于1。这是由于整个系统的指令较多，需要进行的数据计算很少，指令预取度越大，指令预取提高最坏情况下的性能越明显，此时优化的效果反而不明显。

图5 不同预取度下WCRT的比值

3.2.2 指令预取对最坏情况能耗的影响

为了分析指令预取度对于最坏情况下系统性能的影响，图6比较了系统在不同预取度下的支持指令预取和不支持指令预取的WCEC，结果被WCEC(N是0)归一化了。

图6 归一化的WCEC

从图6可以看出，不同预取度下DEBIE系统在最坏情况下的能量消耗都被减少了。预取节省的平均能耗为28.3%，预取度越大，节能效果反而不好，原因是预取度越大，消耗的动态能耗比重越大，预取减少的总的能量消耗也就越少。

3.2.3 最坏情况下能量的优化

为了分析文中的优化算法对于最坏情况下能量消耗的影响，图7比较了DEBIE系统在保证系统性能最优的情况下，文中算法优化后的WCEC和不同预取度下的WCEC比值，比值越小则表明能耗降低越明显。

图7 不同预取度下WCEC的比值

从图7可以看出，优化后的WCEC比不支持指令预取(N是0)的最坏情况下的WCEC提高30.5%，但此时不是性能最优。当预取度N是5时，性能最优，这时优化后的最坏情况下的能量消耗减少了10.8%。能量优化的效率与程序的访存次数和动态能耗在总能耗中的比重有关系。预取度越大，访存次数也就越多，动态能耗消耗得也就越多，因而能量优化的效果越明显。

4 结束语

对于性能和能耗要求很高的多核实时系统，提出支持指令预取的WCRT和WCEC优化算法，通过调整子任务的预取度在保证性能最优的情况下来优化最坏情况下的能耗。实验通过对DEBIE系统的分析，表明优化算法是有效的，系统中子任务的并行程度高，指令访存次越多数多，优化的效果越明显。

今后希望能够研究数据预取对于实时系统WCEC的影响，并提出支持指令预取和数据预取的实时系统最坏情况下的性能和能耗优化方法。