多层Cache分析模块的设计与测试

毛金玲

摘 要：该文主要介绍了实验是在什么样的系统配置和测试数据集上开展的。通过实验结果的对比可以看出，采用多层Cache分析，可以有效的发掘程序Cache访问的局部特性，得到更加精确的WCET估计值。

关键词：WCET 测试数据 多层Cache分析

中图分类号：UG64 文献标识码：A 文章编号：1672-3791（2015）02（b）-0012-02

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

1 系统设计原则

根据服务对象以及功能性需求，人们认为“基于抽象解释技术的多层Cache分析”模块的设计应符合以下原则。（1）功能稳定。Cache是处理机微体系结构中的重要组成部件，因此Cache分析模块也是一个WCET分析工具中的核心组件。其分析结果，直接影响到工具的其它分析功能。因此，该模块的分析必须保证功能完整稳定，把可能出现的错误降到最低。（2）规范性。从软件周期上来考虑，软件维护阶段在软件生命周期或生存期中占较大比重，有的可达软件生存周期的50%～70%。因此，在该软件的设计过程中，在各方面都应该遵从业界广为接受的软件开发规范，以尽可能提高后期软件的可维护性。（3）良好的可扩展性。可扩展性是软件工程追求的目标，能够大大提高软件的复用程度，降低开发成本。从该文所设计的软件自身特性来看，未来还有很大的功能扩展空间。为此，该软件的设计应尽可能模块化，并具有良好的层次结构。各模块与各层次之间定义明确的接口。这样在未来增加新功能的过程中，可以利用已有的功能实现更加复杂的功能，并大大增加代码的可重用性。

2 系统总体设计

图1表示了该文所属的WCET分析工具完整的工作流程。其中图中的数字1、2、3表示的是该文的工作在整个工具中所处的位置。下面，该文将对整个工具的工作流程作以简要介绍。首先介绍不增加该文工作的，WCET分析的原有工作流程。之后，再重点介绍该文所增加的主要功能。

在这一小节中，主要介绍给定一个程序的控制流程图，如何从中抽取程序的层次结构。在介绍这一功能的实现之前，首先用一个简单的例子，阐明对于一个一般的程序，它的层次结构应该是一种什么样的构造。

图2表示了一个复杂的程序控制流程图，该文将利用这个控制流程图来介绍程序层次结构的概念。首先，为了简化表达，把整个程序看作是一个最外层的循环体，这样，整个大图就占据一个程序的层次，称其为Level-0，如图中虚线所示。在这个程序的控制流程图中，可以看到，最上层的结构是一个分支结构，有一个循环，Loop1，位于程序左边的分支中；有两个循环，Loop2和Loop3，位于程序右边的分支中，且Loop3位于Loop2中，前者是后者的内层嵌套循环。根据这一关系，可知，Loop1和Loop2都是整个程序中的第一级循环，因此这两个循环都属于Level-0的下一个层次，称其为Level-1。类似的，Loop3位于Loop2的内部，因此，它存在于Loop2所在层次的下一层，称其为Level-2。

以上程序的层次结构，也可以通过图3所示的树形结构进行表示。其中，整个程序所在的Level-0是树的根节点，它有两个树枝节点，分别对应于位于Level-1的Loop1和Loop2；Loop2又有一个叶子节点，为Loop3，位于Level-2。

对于一个程序及其对应的控制流程图而言，需要得到的就是图3所示的层次结构。在下面一小节中，将介绍采用什么算法将一个给定的控制流程图对应的层次结构抽取出来。

3 参数配置与测试程序集

系统体系结构参数主要包括Cache的相连度、Cache的块大小、Cache中包含的Cache组的数量和指令到内存存取时间等。该实验将这几项特性的参数配置为如表1所示。所有的循环上限设置为10。

实验部分所采用的程序是从Mlardalen测试程序集中选取的6个测试程序。表2列出了关于这6个测试程序的一些基本信息，包括程序中包含的指令条数和循环个数等，这些信息能够在一定程度上反映出程序的复杂度。

4 实验结果

针对上一小节所给出的体系结构特性参数，也就是系统Cache配置参数，针对LRU替换算法，分别计算表2中的6个测试程序的WCET估计值。实验结果如表3所示。该文分别给出了两组实验结果。第一组实验结果对应于传统的单层Cache分析方法，第二组实验结果对应于本文设计实现的多层Cache分析方法。通过对比两种方法所得到的实验数据，可以分析该文所提出的分析方法的优点。

该文定义单层Cache分析的WCET估计值为W1，多层Cache分析的的WCET估计值为W2，那么该文定义分析精度的提高为：（W1、W2）/W1。

从上面的实验结果可以看出，通过采用多层Cache分析，平均可以将程序的WCET分析精度提高大约9%。其中，bs程序的分析结果没有任何提高，这是因为该程序中的循环体非常小，都能够被放入整个Cache中，因此不存在外层循环不足够放入Cache而内层循环可以放入Cache的情况，因此，对于这种特殊的程序，多层分析的效果无法展现出来。matmult程序的分析精度的提高幅度也不是很大，这是因为该程序的循环体也同样都比较小。虽然该程序的执行时间较长，但是由于循环体的大小问题，能够通过多层分析获得的精度提高有限。其他的测试程序比较有效的展现了采用多层分析能够得到的分析精度的提高。

5 结语

该文主要介绍了实验是在什么样的系统配置和测试数据集上开展的。通过实验结果的对比可以看出，采用多层Cache分析，可以有效的发掘程序Cache访问的局部特性，得到更加精确的WCET估计值。

参考文献

[1] Yau-Tsun Steven Li，Sharad Malik， Andrew Wolfe.Efficient Microarchitecture Modeling and Path Analysis for Real-Time Software [A]. Proceedings of the IEEE Real-Time Systems Symposium [C]，1995：298.

[2] Andreas Ermedahl.A Modular Tool Architecture for Worst-Case Execution Time Analysis [D].Sweden：Uppsala University，2003.

[3] 孙昌爱，金茂忠.基于程序插装的动态测试技术实现[J].小型微型计算机系统，2001（12）：1475-1479.