基于抽象解释技术的多层Cache分析的设计与实现

摘 要：在WCET分析中，最重要的一类工作就是Cache分析。目前，大多数的基于抽象解释技术的Cache分析中，分析算法是作用于整个程序的，如果能够根据程序的层次结构，挖掘程序执行在Cache中的局部特性，那么就可以有效的提高WCET的分析精度。基于这一需求，本文主要研究基于抽象解释技术的多层Cache分析，研究的主要内容包括：程序层次结构的分析，基于抽象解释技术的多层Cache分析和整数线性规划问题的建模与WCET求解，采用多层Cache分析能有效的提高WCET的分析精度。

关键词：WCET；抽象解释；多层Cache分析

中图分类号：TP311.1

本文设计并实现了“基于抽象解释技术的多层Cache分析”。该分析方法按照程序中循环的嵌套关系，首先将程序划分成若干个层次。之后，按照传统基于抽象解释技术的分析手段，针对每个层次对应的循环体，分别进行分析，探索程序的局部Cache访问特性。最终，根据各个层次的分析得到的结果，进行整数线性规划的编码，并计算出更加精确的WCET估计值。

1 系统总体设计

图1为WCET分析工具总体分析框架，展示了WCET分析工具完整的工作流程。其中绿色的模块表示的是本文研究的主体工作在整个工具中所处的位置。

在本工具中，待分析的程序为C代码编写，通过面向SimpleScalar平台的gcc交叉编译器，可以将源程序编译为PISA指令集的可执行程序，这个可执行程序就是WCET分析工具的直接输入。程序读入工具之后，分析工具将可执行程序进行反编译，提取详细的指令信息，并生成程序的CFG。程序的CFG表示了程序的流程结构，这一信息将成为处理器行为分析的输入。处理器行为分析目前主要包括Cache分析。Cache分析的结果主要是判断程序的指令或数据在Cache中的命中情况。循环变量、不可行路径等信息可以由用户手工输入，这些输入为“功能性约束条件”，根据下一步计算的需要，这些约束条件将被映射为不同模型中所需要的形式。

在程序流程、处理器行为分析、以及功能性约束等信息都齐备以后，需要采用某种手段计算求解程序的WCET。蓝色线条部分表示的是基于隐式路径枚举的计算方法。根据计算需要，程序流程信息、处理器行为信息、功能性约束等分别被转化为线性约束描述的“控制流程约束”、“处理器行为约束”以及“映射后的功能约束”等，这些约束与目标函数结合起来，就形成了一个整数线性规划的问题，这一问题可以交付商业的求解软件（如CPLEX）或开源的数学规划求解软件（如lp_solve）进行求解，最终得到程序的WCET值。在另外一条分支上，可执行程序可以交给SimpleScalar模拟器进行模拟执行，用以获得程序的WCET观测值，它通常用来和WCET估计值进行比较，以粗略的分析后者的精确程度。

本文主体工作主要体现为以下三个方面：第一，在原来的分析流程完成了“路径分析”并得到了程序的控制流程圖（CFG）之后，本文的工作增加了一个功能，就是对程序的整体CFG进行分析，获得依照嵌套循环来划分的程序的层次结构。第二，在已经存在的基于抽象解释的Cache分析模块的基础上，对其进行了改进，使之能够有效的分析局部程序对应的局部CFG。第三，扩充原有的“处理器行为约束”功能，使得分层次Cache分析得到的结果能够被建模到ILP描述中，并参与WCET计算，最终获得更加精确的分析结果。

2 基于抽象解释的Cache分析功能的设计与实现

2.1 基于抽象解释的Cache分析基本思想

通过对程序执行过程的静态模拟，分析出由于程序的执行而造成的Cache中内容的变化情况，并从中提取出在此程序执行过程中的每一个访存操作在Cache中的命中情况。在抽象解释技术中，用一个抽象的Cache状态（Abstract Cache State）来表示一系列具体的Cache状态（Concrete Cache State）。同时，他们还为抽象的Cache状态定义了一些抽象的Cache动作函数，这些动作函数是Update函数和Join函数，其中Update函数是用来对抽象Cache状态中的内容进行更新的，而Join函数则是用来合并两个抽象Cache状态中的内容的。这些抽象的Cache动作函数在一定程度上能够反映出由于程序的执行而对Cache中的内容所造成的影响。因此，抽象的Cache状态以及这些抽象的Cache动作函数能够在抽象空间内对Cache的具体行为进行完整的描述。在对程序执行过程的静态模拟过程中，抽象Cache状态中的内容将会按照所规定的动作函数而发生变化。

基于抽象解释技术的Cache分析方法针对抽象的指令Cache状态主要采用三种分析，它们分别是Must分析、May分析和Persistence分析。Must分析是用来确定哪些指令在指令Cache中一定是命中的；而May分析则能够确定出哪些指令在指令Cache中是可能命中的，根据这一结果可以判断出那些在指令Cache中一定不命中的指令。Persistence分析能够识别出那些一旦被载入到指令Cache中就不会再被替换出去的指令。

Must、May和Persistence分析都是根据程序的控制流程信息来对抽象的指令Cache状态进行分析的，并且这三种分析所对应的分析过程都是一个不断迭代的过程。当这三种分析都各自收敛到一个固定点（Fixpoint）的时候，这三种分析便可以结束对抽象的指令Cache状态的分析。此时，根据此抽象的指令Cache状态中的内容可以确定出此程序中每条指令在指令Cache中的命中情况，从而可以得到关于这些指令的分类情况。

2.2 多层Cache分析的主要过程

根据Must，May，Persistence分析的目标，在本文的多层Cache分析中，拟采用如下的分析方法：（1）对于最顶层的循环，也就是程序本身，分别进行Must，May和Persistence分析；（2）对于非最顶层的循环，只进行Persistence分析。

在本文的实现中，采用了文献[2]中的Must、May和Persistence分析方法。由于三个分析的流程是类似的，因此仅以本文所用到的最主要的Persistence分析，介绍抽象解释对一个循环体进行分析的主要算法。Must和May分析是类似的。

Persistence分析算法

功能：给定一个循环体，对其进行Persistence分析

函数名称：Persistence_Analysis （ loop ）

输入：mloop_t类型的循环体——loop

输出：每条指令的Persitence分析结果，记录在相应的指令信息中

3 整数线性规划问题建模

通过对多层Cache分析，得到了程序每条指令在各个层次上的Persistence分析结果（在最外层，还有Must和May分析的结果）。例如一条指令A位于第三层次的某个循环体内，那么指令A一定也属于某个第二层次的循环体以及某个第一层次的循环体。指令A在这三个层次对应的循环体中，都有相应的Persistence分析结果。

利用这一结果将程序的WCET计算问题，用一个整数线性规划问题进行描述。

3.1 目标函数

计算程序的WCET，就是用整数线性规划的方式将程序的执行时间加以表示，然后让整数线性规划的求解器来求这个表达式的最大值。因此需要设计目标函数，可以表示为公式（1）的形式。

其中，Ci表示每个基本块执行一次的执行时间，Xi表示每个基本块执行的次数。将各个基本块的总的执行时间求和，并求其最大值，便可得到程序的WCET。其中，Ci又可以表示为三个部分，CAM、CAH、CFM分别对应于当前基本块中，所有AM、AH、FM指令对应的执行时间。由于本文对程序进行多层分析，因此CFM可以进一步被表达为公式（2）的形式。

对于所有被判定为FM的指令，必须区分它是在哪一个层次上被判定为FM的。假定在第j层次上，有mj条指令被判定为FM，那么用 表示这mj条指令失效的次数，用 表示这mj条指令命中的次数。因此，所有的FM指令最终的执行时间表达式可以用公式（2）来表达。

3.2 路径信息约束

为了求解这个整数线性规划的问题，还需要一些约束。在研究WCET分析问题中，第一类约束是路径信息约束，如公式（3）所示。

公式（3）表明，一个基本块的执行次数，等于它对应的所有入边被执行的次数之和，也等于它对应的所有出边被执行的次数之和。

3.3 循環次数约束

还需要一些约束来表明程序的循环最多会执行多少次。假定对于某个循环体，Xi是循环体的尾节点（Tail），Xj是循环体的入节点（Entry），循环最多执行p次，那么可以知道，循环体的入节点每执行一次，循环体的尾节点最多可以执行p次。为了表达这一信息，引入了循环次数约束，其形式如公式（4）所示。

3.4 基本块失效总次数约束

在公式（2）中，描述一个基本块中，所有被判定为FM指令的执行时间。对于其中的失效和命中次数变量，还需要根据其所在的层次，施加必要的约束。以一个位于某个第二层循环体的基本块Xi为例，假定它所属的第一、二层的循环体的入节点分别为X1，X2。那么，可以有公式（5～8）的一些约束。这些约束描述了在某个特定循环层次上，被判定为FM的指令，其失效次数的上限，以及失效次数和命中次数之和为多少。

将上述的目标函数和所有的约束组合成为一个整数线性规划的问题，通过求解目标函数所表达的极值问题，可以求解出程序的WCET。

4 结束语

通过对6个测试程序进行实验，可以看出，通过多层Cache分析，可以有效的提高WCET的分析精度。实际效果，根据程序自身的特性不同而不同。对于那些循环体很小的程序，多层Cache分析的精度收益不大；但是对于外层循环体很大（难以完全装入Cache）而内层循环体很小的程序，采用多层Cache分析能够有效提高分析精度。

参考文献：

[1]Jane， W.S. Liu. Real-Time Systems. Pearson Education，2002.

[2]Ferdinand C， Wilhelm R. Fast and Efficient Cache Behavior Prediction for Real-Time Systems [J].Real-Time System， 1999，17（2-3）：131-181.

[3]Yau-Tsun Steven Li and Sharad Malik. Performance Analysis of Embedded Software Using Implicit Path Enumeration [A].in Workshop on Languages， Compilers and Tools for Real-Time Systems [C].1995，456-461.

作者简介：毛金玲（1974-），女，辽宁海城人，设备工程系，讲师，硕士，研究方向：软件开发。

作者单位：辽宁建筑职业学院，辽宁辽阳 111000