Cache一致性验证的结构化激励生成算法

程开丰 罗汉青 梁利平

摘 要：为解决Cache一致性验证中传统随机激励方法的冗余覆盖及覆盖死角等问题，提出了一种高层次结构化激励生成算法和相应的高层次功能覆盖率模型.首先根据实际多核应用场景将冲突访存操作分类成基本同步和复杂同步，并进一步抽象成有向二分图模型，由此提出一种通用的层次化输入空间等价类划分算法和对应的高层次HSPC（Host Slave Pair Coverage）功能覆盖率模型，最后基于树的搜索提出了结构化激励生成算法.上述方案成功应用于IMEDiamond SoC的Cache一致性的功能验证中，实际结果表明，相比传统基于代码的覆盖率，高层次HSPC功能覆盖率模型的揭示功能Bug能力更强，而且相对于传统的随机生成，结构化的激励能够将覆盖率收敛所需的激励数减少96.3%.

关键词：Cache一致性；有向二分图模型；等价类划分；高层次功能覆盖率模型；结构化激励生成

中图分类号：TP302 文献标志码：A

Abstract： In order to deal with the problems of redundant and failed coverage in the traditional random stimuli for cache coherence verification， a high level structural stimuli generation algorithm and the corresponding functional coverage model were presented. Firstly， conflict memory accesses were categorized into basic/complex synchronizations， and thus abstracted into general bipartite graph model. Consequently， a general layered equivalence partition algorithm of ISS and the corresponding high level HSPC （Host Slave Pair Coverage） functional coverage model were proposed. Finally， two structural stimuli generation algorithms based on the search of ISS tree were presented. Experiments were performed in the functional verification of the cache system of IMEDiamond SoC， and the result indicates the HSPC coverage model can help uncover functional bugs more easily when compared with code coverage， and structural stimuli generation can reduce 96.3% stimuli for coverage convergence when compared with random stimuli generation.

Key words：Cache coherence； directed bipartite graph model； equivalence partition； high level functional coverage model； structural stimuli generation

所有基于仿真的功能驗证都需要做好两个环节：输入激励的生成与最后结果正确性的判断.Cache一致性的验证是多处理器系统功能验证中非常重要的一个部分.其输入激励是多核并行访存程序，结果正确性的判断是基于特定的内存一致性模型（MCC，Memory Consistency Model）.

在已有的相关研究中，1979年Lamport[1]提出了顺序一致性模型（Sequential Consistency， SC），由于SC模型最符合程序员的直观思维，所以在多处理器系统设计和验证中一直占主导地位.1994年Gibbons和Korach[2]在理论上分析了存储一致性验证的复杂性，其中把在SC模型下的验证定义为VSC（Verifying Sequential Consistency）问题，并证明了VSC是NP难问题.1997年胡伟武等[3]给出了另一种SC模型下判断多核访存操作正确性的方法.与Gibbons等只根据访存结果来寻找判断是否存在多核顺序交织序列不同，该方法关注记录了多核程序PRG的静态程序PRO（PRG）和动态执行序E（PRG），并指出最后执行结果符合SC的充要条件是E（PRG）SymbolHC@ PRO（PRG）对应的有向图无环.上述研究本质都是关于Cache一致性结果正确性判断，缺少对输入多核程序生成方法的研究.

1990年Wood等[4]采用了仿真的手段对多核一致性协议进行了验证，其中多核访存程序采用的是随机生成.2010年王朋宇等[5]在文献[3]的工作基础上实现了一种线性时间复杂度的片上多核处理器存储一致性验证工具LCHECK，其中多核访存程序生成部分仍采用随机的策略.可见现有对Cache一致性验证时的激励基本都基于随机生成，随机化方法虽然有时能够发现一些corner bug，但有两个明显的不足：

1）现实中输入激励空间（ISS，Input Stimuli Space）的元素并不是均匀分布的，而随机产生输入激励时并不考虑此等情况，故最后对ISS的覆盖是不均匀的，即简单的激励点会被反复覆盖，而困难的激励点则很难甚至无法覆盖；

2）多核相对单核最大的特点是允许无冲突程序间的并行执行，以提高整体性能，故绝大多数实际的多核应用程序不会随意进行Cache一致性操作，而是在特定情形下有规律的进行.随机产生的多核程序也没有考虑此实际情况，本文在考虑了实际的多核应用特点下，针对Cache一致性的功能验证提出了一套通用的ISS高层次抽象和等价类划分方法，并提出了高层次的HSPC（Host Slave Pair Coverage）功能覆盖率模型以及基于树遍历的结构化激励生成算法，最后通过实际的工程检验证明：相比传统的基于RTL代码的覆盖率模型，HSPC功能覆盖率模型能更好地帮助发现功能bug；相比传统随机生成验证激励，同等覆盖率下，结构化激励能够大幅减少测试激励数目，缩短验证周期.

1 具体方案

1.1 有向二分图模型

在Cache一致性系统的仿真验证中，其输入激励为多核冲突访存程序.由于多核相对单核最大的特点是允许无冲突程序间的并行执行，以提高整体性能.故对实际的多核Cache一致性操作的应用场景有如下基本假设：

A1）多核冲突访存程序一般应用于多核间特定节点的同步；

A2）多核同步可分为基本同步（Basic Synchronization，BS）与复杂同步（Complex Synchronization，CS），其中CS可以分解为多个BS操作；

A3）BS本质上为单写多读（Single Write Multiple Read，SWMR）的多核冲突访存程序，且要求BS中所有读操作最后要能读到BS中写操作的值；

A4）同一CS中包含的各BS之间访存地址不同；但对具体的访存地址的值和数据不敏感.

A5）不同核之间可以区分，即不具有对称性.

A6）有意义的程序中任何核的任何有意义的写操作都会有至少一个读操作与其对应.

上述假设是合理的，因为以下两点：

1）基于snoopy的MESI等Cache一致性协议在设计时就并不关心绝对的访存地址的值，而只关心多核访存地址间是否冲突等相对关系.

2）多核系统中一般都会有主核与从核之分，而且不同核与snoopy等一致性模块间的物理延时一般也是不同的，所以不同核之间是可以区分的.

由此可将多核CS操作抽象成有向二分图模型（DBGM，Directed Bipartite Graph Model）G=〈Vw，Vr，E〉，其中图的各元素含义如下.

1）主点集Vw：发起写操作的内核抽象成顶点后构成的集合；

2）从点集Vr：发起读操作的内核抽象成顶点后构成的集合；

3）点集V：所有参与访存操作的内核抽象成顶点后构成的集合，即V=Vw∪Vr；

4）有向边集E：Vw中顶点vwi到Vr中顶点vrj之间存在有向边eij=〈vwi，vrj〉的充要条件是vri对应内核发起的读操作的结果来自vwi对应内核发起的写操作.

一个示例CS的有向二分图模型如图1所示.

1.4 结构化激励生成

结构化激励生成算法分成如下两步：

步骤1：对ISST的叶子节点进行搜索遍历以确定SysSti中各活动主从核及相应的主从对应关系；

步驟2：根据基本假设A4，SysSti中BS对具体访存地址是不敏感的，故当遍历得到每个叶子节点后，既得到了Cache一致性验证激励所需要的三大核心信息：活跃主核、活跃从核划分以及主从之间的对应关系，然后随机产生访存地址及访存数据等细节信息以生成最终的激励.

上述激励生成算法产生的激励不仅保留了底层逻辑信号级随机性，而且能在高层次上充分保证对ISS的高覆盖率.

下面重点介绍第一步，即对ISS树的搜索遍历.在介绍具体的搜索算法之前，首先介绍一个重要的转换关系.根据1.3节中的划分算法，每个叶节点Si，j，k，l可以由其下标四元组〈i，j，k，l〉来唯一索引确定，故叶子节点的搜索遍历就转换成了对〈i，j，k，l〉四元组的搜索遍历.

由于经典计算机算法中对树的搜索有深度优先搜索（DFS，Depth First Search）和宽度优先搜索（BFS，Breadth First Search）两大类，此处可以加以借鉴，但与经典树搜索需要遍历所有节点不同的是，此ISS树只需要搜索叶子节点，所以相应的搜索算法在细节上也有些许不同，具体分别介绍如下.

1.4.1 DFS

其基本思想从激励角度看是个严格的顺序关系，每种特定的主接口组合要驱动完所有可能的从接口，然后再切换到下一种主接口组合；而且对于主接口组合，先考虑单一主接口，然后是2个主接口同时发请求，再是3个主接口同时，一直到最后所有主接口同时发请求.从ISS树角度看，第3层所有叶子节点按照从左到右的顺序被遍历，具体算法实现的流程如图3所示.

其中NumChild（S）函数返回节点S的儿子节点数目.

1.4.2 BFS

其基本思想从激励角度看是个循环关系，每个循环内部每种特定的主接口组合驱动完一种可能的从接口后就切换到另一主接口组合，直到所有的主接口组合都被遍历到.从ISS树角度看，S1，S2，…，SNHI的叶子节点交替地被遍历，具体算法实现的流程如图4所示.

其中CycInc（x）函数是对变量x进行循环递增（当x超过最大值时，回归到最小值）；Searched（S）函数返回1时，表示以S为根节点的子树已经被搜索，否则返回0；Dead（S）返回1时表示以S为根节点的子树中所有叶子节点都已经被遍历，否则返回0.

2 验证实例

为具体展示上述激励方案的效果，本文选择了IMEDiamond系统作为功能验证实例.

为比较不同覆盖率模型，帮助揭示Bug的能力，实验对比了Line、Condition和Toggle等基于代码的覆盖率和本文所提出的高层次HSPC功能覆盖率，各覆盖率值与揭示的功能bug数间关系.考虑到多核Cache访问时，最主要的功能缺陷来自多核竞争和异核交互（即多个核有写操作以及一个核读取另一核写的值），所以实验时的bug模型也模拟了这种错误，分别在多核竞争和异核交互时引入缺陷（比如多个核有写操作时仲裁错误以及一个核读取另一核写的值时错误）.最终的实验结果统计如图5所示.

由图 5可以有以下结论：

1）相对所有的代码覆盖率，HSPC都能够在很小的覆盖率下发现同样数目的功能bug；

2）代码覆盖率很难达到100%，而HSPC却能够达到100%；

3）最终覆盖率收敛时，HSPC指导下发现的功能bug数要多于代码覆盖率.综上可见，HSPC揭示功能bug的能力比传统的代码覆盖率要更强大.

为比较不同的激励生成算法所产生激励与功能覆盖率之间的关系，实验比较了不同核数NC下为达到相同100% 的HSPC覆盖率，本文结构化方法所需激励数StructStiNum相对传统随机方法所需激励数RanStiNum减少的比例ReduceRatio=1-StructStiNumRanStiNum，如图6所示.

由图 6可见，随着核数的增加，ReduceRatio一直呈上升趋势，即随机化方法产生的激励中冗余激励的比例越来越高.NC=8时，ReduceRatio已经达到了96.3%.

此外在16核Intel Xeon E5520、主频2.27 GHz、内存25 GB、Linux系统环境下，LeafNum及激励生成时间（StrucTsti为结构化激励时间，RanTsti为随机激励时间）与NC之间的关系统计如表1所示.

由表1可有以下结论：

1）激励生成时间与LeafNum一样，与NC之间都是指数增长关系，符合公式（2）.

2）在NC≤8时结构化激励生成时间最大也就44 s，而随机激励已经到了3 883 s，是结构化方法的87倍.

3）本文的方法适合核数NC不是很大的多核系统，当NC超过8时，为了控制激励生成时间，需要采取进一步的输入空间化简方法.

3 结 语

为解决传统多核处理器Cache一致性验证中随机激励方法的冗余覆盖及传统代码覆盖率模型揭错率低等问题，本文根据多核应用程序本身的特点，提出了一种多核冲突访存抽象建模的方法，并由此进一步给出了相应的高层次HSPC功能覆盖率模型和结构化激励生成算法.实际系统的验证效果表明相比传统的代码覆盖率，HSPC覆盖率模型的揭示功能Bug的能力更强；而且相对于传统的纯随机激励，结构化的激励消除了冗余，能够更快地加快覆盖率收敛.

此外对于单核发起多个写操作的情形，由于物理上不同的写也是顺序发起的，根据前述基本假设A6，每个写都有各自对应的读操作，所以可以根据不同写发起的时间先后，将不同的写划归入不同的时间片，每个时间片内每个核只有一个写操作，此时本文的方法仍然适用.

参考文献

[1] LAMPORT L. How to make a multiprocessor computer that correctly executes multiprocessor programs [J]. IEEE Transaction on Computers， 1979， C-28（9）： 690-691.

[2] GIBBONS P B，KORACH E. On testing cachecoherent shared memories [C]// ACM Symposium on Parallel Algorithms and Architectures. 1994： 177-188.

[3] 胡伟武，夏培肃. 顺序一致共享存储系统中的乱序执行技术基本理论[J]. 计算机学报， 1997，20（6）： 481-490.

HU W W， XIA P S. Outoforder execution in sequentially consistent shared memory systems： principles[J]. Chinese Journal of Computers， 1997，20（6）： 481-490. （In Chinese）

[4] WOOD D A， GIBSON G A， AND KATZ R H. Verifying a multiprocessor cache controller using random test generation [J]. IEEE Design and Test， 1989， 7（4）：13-25.

[5] 王朋宇， 陳云霁，沈海华， 等. 片上多核处理器存储一致性验证[J]. 软件学报， 2010， 21（4）： 863-874.

WANG P Y， CHEN Y J， SHEN H H， et al. Memory consistency verification of chip multiprocessor[J]. Journal of Software， 2010， 21（4）： 863-874. （In Chinese）

[6] GRAHAM R L， KNUTH D E， PATASHNIK O.Concrete mathematics[M]. USA： AddisonWesley， 1994： 257-267.

[7] 王志君，梁利平，吴凯 ，等.一种面向多媒体和通信应用的处理器指令集及架构实现[J].湖南大学学报（自然科学版）， 2014，41（10）：108-114.

WANG Z J， LIANG L P， WU K， et al. Architecture and implementation of an application specific instruction set for multimedia and communication[J]. Journal of Hunan University（Natural Sciences）， 2014，41（10）：108-114. （In Chinese）

[8] 王志君，梁利平， 洪钦智 ，等.一种DSP和通用CPU一体化的处理器架构及其4核实现[J].微电子学与计算机，2014，31（10）：32-38.

WANG Z J， LIANG L P， HONG Q Z， et al.The architecture of an unified DSP plus generalpurpose CPU and the implementation of a 4core homogenous processor[J]. Microelectronics & Computer， 2014，31（10）：32-38.（In Chinese）