多层Cache的需求分析与总体设计

毛金玲

摘要：从对基于抽象解释技术的多层Cache需求分析中可以得出，系统的功能性需求相对来说比较易于实现，而非功能性需求由于涉及的范围很广，加上诸多外在因素的影响则比较严格。对于非功能性需求影响最大的就是系统的架构，所以在设计和实现系统时，要在对系统的架构给予充分重视的前提下，实现功能性需求，最后介绍了系统的总体设计框架。

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

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

1 基于抽象解释技术的多层Cache需求分析

进行层次化分析的主要目的，是发掘程序局部的Cache访问特性，从而提高Cache分析的精度。层次化Cache分析的意义，可以通过一个例子进行简单的说明。

图1表示了一个带有两层循环的程序的控制流程图，其中Loop1是外层循环，Loop2是内层循环。其中，图中的每个节点是一个包含若干条指令的基本块。为了讨论问题方便，不失一般性，我们假定每个基本块只包含一条指令。我们假定，外层循环中的A指令和内层循环中的B、C指令都映射到了一个两路组相联（2-Way Associative）的Cache组中。我们以PERSISTENCE分析为例，说明进行层次化分析，可以提高分析的精确性。

如果对图1所示的程序进行PERSISTENCE分析，我们会发现，由于A、B、C三个指令都映射到了同一个Cache组中，且该Cache的相联度为2，所以如果对整个程序进行PERSISTENCE分析，A、B、C三条指令都无法被判断为First Miss（FM）。如果不能得到这一结果，在进行WCET估计的时候，A、B、C三条指令都将被当做Always Miss（AM）指令来处理。也就是说，在进行WCET估计的时候，这三条指令每次执行，都被看作是失效（Miss）。

但是，如果我们对内层循环Loop2的行为进一步分析，会发现，在绝大多数情况下，B和C指令在Cache中还是命中的。因为对于内层循环而言，一旦进入内层循环执行，B和C第一次在Cache中都可能是不命中，因为可能在先前的执行中，指令A已经占据了Cache组中的一个位置，导致B和C失效。但是在内层循环的其它次执行过程中，B和C都将是命中，因为第一轮的执行已经将这两条指令都载入了Cache组中。换言之，B和C的行为特性是：程序每次进入内层循环，B和C最多各发生1次失效，在其它各次执行中，B和C在Cache中都将为命中。

显然，如果我们能够按照循环层次，对程序的局部进行分析，是有可能发现那些在面向整个程序进行分析无法分析出来的Cache命中，因此可以提高分析的精确性。虽然图1仅仅是一个简单的示例程序，考虑在大规模的程序中，尤其是那些外层循环体较大而内层循环体较小的程序中，上面的这种情况可能广泛存在，因此，采用多层分析优化分析精度，具有很大的提升空间。这就是开展本文研究工作的真实意义所在。

2 系统的具体实现目标

基于抽象解释技术的多层Cache分析，其使用到的核心技术仍旧是原始的基于抽象解释技术的分析方法。本文工作与传统工作的不同，就是将程序根据循环嵌套关系划分为若干个层次，为每个层次的局部程序进行抽象解释分析，得到局部的分析结果，最后再根据不同层次得到的结果，给出一种基于整数线性规划（Interger Linear Programming， ILP）的求解表示，并计算程序的WCET估计值。为此，本文所设计的软件部分，应该包含如下几个具体功能：

①程序层次结构的分析：实现多层Cache分析，最初始也是最关键的功能之一，就是对程序的层次结构进行正确的分析和划分。以一个简单的二层嵌套循环为例，在我们的分析中，我们首先将整个程序看成是一个最外层的循环，我们称它位于第1层；那么，第一层实际的循环，就位于程序的第2层，内层嵌套循环位于程序的第3层。需要有一个正确的算法，能够把一个复杂程序的循环嵌套层次正确分析出来。

②抽象解释Cache分析技术的实现：需要实现一个基于抽象解释的Cache分析模块，该模块能够将上一步分析得到的不同层次的局部程序作为输入，利用传统的抽象解释分析方法，分析局部程序中的指令的局部行为特征。

③基于多层抽象解释分析结果的ILP描述的生成：在进行完抽象解释的分析之后，我们得到的结果是程序指令在各个层次上的Cache命中与否的结果。利用这个结果，我们可以计算出程序（或者局部程序）中每个基本块的WCET估计值。为了得到整个程序的WCET估计值，我们还需要利用“隐式路径枚举”技术，将各个层次得到的分析结果进行建模，通过求解对应的ILP问题，最终计算出程序的WCET估计值。

3 系统总体设计

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

根据本文所设计的“基于抽象解释的多层Cache分析”的功能需求，本文工作对该WCET分析工具的扩充主要体现为三个方面：

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

4 结语

从对基于抽象解释技术的多层Cache需求分析中可以得出，系统的功能性需求相对来说比较易于实现，而非功能性需求由于涉及的范围很广，加上诸多外在因素的影响则比较严格。对于非功能性需求影响最大的就是系统的架构，所以在设计和实现系统时，要在对系统的架构给予充分重视的前提下，实现功能性需求。

参考文献：

[1]Hennessy J，Patterson D.Computer Architecture：A Quantitative Approachz[M].Morgan Kuafmann，1996.

[2]Damien G.Study of Different Cache Line Replacement Algorithms in Embedded Systems[D].ARM France SAS Les Cardoulines B2-Route des.

[3]付雄.利用程序分析和优化提高Cache性能[D].中国科学技术大学，2007.