局部约束与全局约束对WCET分析的影响浅析-论文.pdf

《局部约束与全局约束对WCET分析的影响浅析-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验研究·局部约束与全局约束对WCET分析的影响浅析孟J螭(东北电力大学，吉林吉林132012)摘要：循环语句的执行次数对程序的执行时间是有影响的，通常循环次数越多，程序执行时间越长。因此，在最差情况执行时间分析中通常需要指明程序循环语句的执行次数上限。本文简要分析使用局部约束与全局约束标注循环上限对最差情况执行时间分析结果的影响。关键词：最差情况执行时间；循环上界；局部约束；全局约束众所周知，循环次数对执行时间是有影响的，通常循环部循环上界是“9”。这样一来，内层while的全局执行次数会次数越多，程序执行时间越长。因此，静态最差情况执行时间被记为小于等于9X9=81次。而其实际的最大

2、全局执行次数为(Worst—caseExecutionTime，WCET)分析通常都需要知道9+8+7+6+5+4+3+2+1：45次。于是，WCET4i~i计值被严重高估了。(自动分析或人工标注)循环上界，以便使WCET估计值更精确7{一一一，．一一一一一要获得更“。本文将探寻使用“局部”或“全局”约束法标注循环上界会8wh'ile(ilo)t精确的wcET估对程序的WCET分析有何影响，据此，我们可以决定何种情况下使用何种方法。兰1l0，lwhl'：ielmep(aCaj[】j3《．；a[j-z]¨){王值同，列’，右怀1局部约束与全局约束12aCj】a[j-Z]；注非正交多重嵌工3

3、a[j-1]1：emp；套循环的循环“局部”循环边界是指循环语句执行1次，其循环体可能的14j—-．：⋯⋯一执行次数范围。“全局”循环边界是指从程序开始运行到结束，lS)。边界。从表1中l61++；可以看出，使用循环语句的循环体可能的全部执行次数范围。以下面的代码为例，第1行for语句的“局部”和“全局”循～全局约束可以环边界都是[0，5]。第2行for语句的局部循环边界是[0，5]，全局获得比使用局部约束更精确的WCET估计值。程序fac．c来自于循环边界是[0，25]。Malardalen大学的WCET基准程序集。需要说明的表1局部约束与全局约束对WCET分析结果的影响lfor(i=

4、0；i<5；i++)是，由于WCET计程序(输入)局部约束(高估)全局约束(高估)观测值2fbr0=0；j<5；j++)算的是最差情fac(n=5)538(14．225％)475(0．849％)4713{c++；}况，因此，通常fac(n=15)3068(5．939％、2900(0．138％)2896仅需要提供循环上界。我们可以使用“局部”约束法或“全局”fac(n=25)7698(3．733％)7425(0．054％)7421约束法为计算WCET的整数线性规划提供所需的循环上界的表fac(n=35)14428(2．720％)14050(0．028％)14046达式。局部约束法使用局部循

5、环上界，分析工具会将局部循环上界转换成内外层语句执行次数的整数倍数关系。以上面的代可以采用“插桩一运行”的动态方法获取循环的全局执行码为例，如果第2个for循环的循环边界使用局部约束法进行标次数。首先，生成待处理程序的抽象语法树；然后，在抽象语法注，则会生成表达式“line2—51inel=O”，即第1行每执行1次，树中寻找循环语句节点；接着，在每一个循环语句节点的第一第2行执行5次。而全局约束使用全局循环边界，若第2个for使个子节点之前插装探针，用于输出该循环语句在原源程序中的用全局约束，则会生成表达式“line2=25”。行号；然后，将插桩后的抽象语法树还原为源程序；最后，这个多数

6、情况下，由于局部循环边界易于获取，所以局部约束已经插桩了的源程序获得各循环语句的执行次数。此方法的优法是较为常见的标注方式。然而，情况并非如此简单。对于上下点是易于实现、效率较高。但缺点是必须提供最差输入，否则获文敏感的循环，尤其是非正交多重嵌套循环，获取内循环的局得的循环执行次数未必是最差情况下的全局循环上界。部循环边界也并不容易。3结束语2全局约束与非正交循环局部约束适用于循环上界识别较为容易的正交循环。全若嵌套循环中内层循环的执行次数完全或部分地依赖于局约束适用于非正交循环的内循环语句，可以获得相较于局部外层循环能够直接修改的变量，则称此嵌套循环为“非正交”约束更为精确的WCET估

7、计值。因此，当程序中的嵌套循环是正嵌套循环。交的，建议使用局部约束标注循环上界，否则建议使用全局约以下面的程序片段为例，第1O行的while语句的局部循环束。执行次数既与外层循环的控制变量i有关，同时还与全局变量[参考文献]数组a有关。出于对安全的考虑，此类非正交多重嵌套循环在[1]吕鸣松，关楠，王义．面向WCET估计的Cache分析研究综述[33．软件学标注内循环的循环边界时，往往采用局部循环上界，即所有可报，2014，25(2)