基于隐藏路径枚举技术的最差情况执行时间分析原理浅析

孟凡奇

摘 要：最差情況执行时间分析是系统实时性评估、任务可调度性分析以及软硬件协同设计的基础，本文以Chronos工具为例，对最常用的隐藏路径枚举技术的基本原理进行简要分析。

关键词：隐藏路径枚举技术；最差情况执行时间；实时性

最差情况执行时间（Worst-case Execution Time，WCET）分析通常被分为动态、静态和混合3种方法。其中，静态方法通常要经过：控制流分析；处理器建模；WCET计算3个处理环节。隐藏路径枚举技术（Implicit Path Enumeration Technique，IPET）是静态WCET分析方法在计算环节最常用的技术。

1 基本原理

该方法的基本思想是在分析程序控制流图的基础上，使用整数线性规划求解最长执行路径。为了进一步说明隐藏路径枚举法的基本原理，首先介绍基本块的定义。

定义1 基本块[1]是目标程序中这样的连续语句序列：（1）只有第一条语句可以有多个入口；（2）只有最后一条语句可以有多个出口；（3）内部不含分支、跳转语句。

2 举例分析

下面以程序“insertsort.c”为例介绍IPET方法。首先对源程序（图1（a）所示）进行编译生成可执行程序，然后对可执行程序反汇编，并生成控制流图如图2（a）所示。

该控制流图的字符表达形式如图1（b）所示，其中“3： 400358：[4，3]”的含义是基本块3的起始地址是400358，可以到达基本块4和基本块3。在获得控制流图的基础上，针对基本块的执行次数（即，循环上界、不可行路径）添加约束，其字符表达形式如图1（c）所示。例如，“c0.0=1”的含义是过程P0中的基本块B0的执行次数是1次。接下来需要根据控制流图和约束生成整数线性规划所需的计算表达式。这里需要用到以下定理[2]：

定理1 基本块的执行次数等于流入该基本块的所有边的执行次数，也等于从该基本块流出的所有边的执行次数。即：

其中，NB表示基本块B的执行次数。 表示从基本块B流出的所有边的执行次数。 表示流入到基本块B的所有边的执行次数[2]。

为了计算图1（a）中程序的最差执行时间，需要使用整数线性规划求解基本块B2的执行次数NB2，以使WCET最大化，即：

其中，NBi是基本块Bi的执行次数。Ci为基本块Bi的执行时间，利用指令模型、Cache模型、流水线模型及分支预测模型计算得到。

除了图2中已知和推理出来的表达式以外，还可以利用定理1从图2（c）得到以下表达式：

显然，由于基本块NB2的执行时间有C2>0，在其他基本块的执行次数已经确定的情况下，NB2越大，整个程序的执行时间越长。因此，整数线性规划求解的结果必然是NB2=9。至此，所有基本块的执行次数都已确定，利用公式2即可获得程序的WCET估计值。

综上所述，隐藏路径枚举技术在实际应用中表现出了比较好的求解效率。尽管如此，由于其基于整数线性规划，而整数线性规划的描述能力并非是最强的，依然无法描述复杂的程序控制流程信息。同时，整数线性规划问题的求解效率会随着程序复杂度的提高而大幅增加。

[参考文献]

[1]孙昌爱，金茂忠，刘超，等.程序执行时间的静态预估与可视化分析方法[J].软件学报，2003，14（1）：68-75.

[2]Li X，Liang Y，Mitra T，et al.Chronos：A timing analyzer for embedded software[J].Science of Computer Programming，2007， 69（1）：56-67.