随机测试程序生成方法和系统以及设计验证方法

摘要

本发明提供一种随机测试程序生成方法，包括下列步骤：1)编写并解析指令模板，并构建约束网络；2)利用小桶间的相容度计算小桶的计数函数；3)基于所述计数函数根据所述约束网络来计算随机变量的随机解；4)利用所述随机解设置指令的操作数，生成由所述指令构成的随机测试程序。利用该方法生成的测试程序更广，减少了实际RTL仿真时的时间消耗，同时也降低了出错时的调试难度。

说明书

技术领域

本发明涉及微处理器的指令级功能验证，特别涉及一种随机测试程序生成方法和系统以及相应的设计验证方法。

背景技术

随着设计规模的扩大，尤其是多核技术的发展，控制逻辑越来越复杂，涉及的状态空间也日益扩大，验证在处理器设计过程中成为非常关键的一步。指令级验证是当前微处理器验证中广泛采用的方法。

当前生成测试程序的方法主要有人工手写测试程序、约束随机测试生成以及覆盖率驱动的测试生成。在超大规模集成电路(VLSI)的设计验证中，约束随机测试生成是最主要的方法，对于那些采用随机难以覆盖到的功能点，可以采用人工手写测试程序的方法作为辅助。

虽然随机生成的测试程序覆盖面广，可能覆盖到设计和验证人员完全没有想到的功能角落，但是大量随机生成的测试向量也会造成验证功能点的重复覆盖，延长验证的收敛时间，降低验证效率，因此需要在产生随机程序的同时人为加入一些约束，使之尽量不重复，从而更有效、更有针对性的完成验证任务。

随机测试程序生成的方法和架构从90年代开始逐渐成熟，一般包括两部分：测试模板文件和随机求解引擎。前者用来描述指令序列，如指令的种类、变量的约束条件等；后者接受模板文件中提取出来的随机变量和约束信息，建立一个约束网络，将问题转成一个约束满足问题(CSP：constraint satisfaction problem)，求该约束满足问题的均匀分布的随机解。针对约束求解问题，R.Dechter首先提出了桶消元方法用以计算推理网络的解空间，该方法不会引入过多的术语，可以用以计算约束满足问题的解空间。但是尽管桶消元法已经具有较低的内存开销，它也是指数级的，不能处理规模较大的约束满足问题。因此，降低计数函数的维数成了当务之急。

Dechter和Emek等人又提出划分小桶的做法来减小时空问题，用多个维数较小的计数函数来近似表示单个维数较大的计数函数。很明显，小桶消元法的精确度很大程度上依赖于小桶个数t的取值。实践证明，t越大，虽然空间复杂度降低，但所需的时间也相应增加，这就意味着需要在时间和空间中折中。

综上所述，采用现有的约束求解技术生成随机测试程序具有很高的时空复杂度，迫切需要一种简易、高效地随机测试程序生成方法，其随机变量所在的约束网络的解空间的均匀度高，程序的冗余度和重复程度低，具有更高的验证广度和深度。

发明内容

本发明提供一种随机测试程序生成方法和系统，其目的在于提高当前随机测试程序生成中约束求解的均匀度，提高随机验证的效率。

根据本发明的一个方面，提供了一种随机测试程序生成方法，包括下列步骤：

1)编写并解析指令模板，并构建约束网络；

2)利用小桶间的相容度计算小桶的计数函数；

3)基于所述计数函数根据所述约束网络来计算随机变量的随机解；

4)利用所述随机解设置指令的操作数，生成由所述指令构成的随机测试程序。

在该方法中，所述步骤2)包括下列步骤：

根据公式$>N_i^{p^{*}}={\Sigma }_{X_p}{\Pi }_{N_l\in {\mathrm{bucket}}_{\mathrm{pi}}}{N}_l$>生成桶bucket_p中的小桶bucket_pi的初始计数函数其中1≤p≤桶个数，1≤i≤桶bucket_p中小桶个数t，X_p是所述桶bucket_p中的随机变量，N_l是分到所述小桶bucket_pi的计数函数或约束条件，1≤l≤小桶bucket_pi中的计数函数和约束条件个数；

根据$>{\rho }_i=\underset{j\ne i}{\overset{i}{\Pi }}\frac{{\Sigma }_{s\in S_{\mathrm{pj}}}\min (N_j^{p^{*}}\left(s\right),1)}{\left|S_{\mathrm{pj}}\right|}$>估算在所述小桶bucket_pi中对变量X_p取不同值时所述小桶bucket_pi与所述桶bucket_p中其它小桶bucket_pj的相容度ρ_i，其中1≤j≤小桶个数t，S_pj为所述小桶bucket_pj中除X_p外的随机变量集合，表示小桶bucket_pj的计数函数；

根据$>N_i^p={\Sigma }_{X_p}{\rho }_i{\Pi }_{N_l\in {\mathrm{bucket}}_{\mathrm{pi}}}{N}_l$>计算所述小桶bucket_pi的计数函数N_i^p，并把所述计数函数N_i^p分到S_pi中序号数最大的随机变量对应的小桶中。

根据本发明的另一方面，提供了一种随机测试程序生成系统，包括：

约束网络构建部件，用于编写并解析指令模板，并构建约束网络；

约束求解器，用于基于利用小桶间的相容度计算的小桶的计数函数根据所述约束网络来计算随机变量的随机解；

指令生成部件，用于根据所述随机解设置指令的操作数，生成由所述指令构成的随机测试程序。

在该系统中，所述约束网络构建部件进一步包括：

指令模板编写模块，用于编写指令模板；

解析器，用于解析所述指令模板并构建约束网络。

在该系统中，所述指令生成部件进一步包括：

指令信息设置模块，用于设置指令信息；

指令生成模块，用于根据所述约束求解器计算的所述随机解设置指令的操作数，并根据所述指令信息生成由所述指令构成的随机测试程序。

根据本发明的又一方面，提供了一种设计验证方法，包括下列步骤：

利用如上所述的方法生成的随机测试程序进行设计验证。

与现有技术相比，本发明的有益效果在于测试程序的验证面更广，大大减少了实际RTL仿真时的时间消耗，同时也降低了出错时的调试难度。

附图说明

图1为现有技术的桶消元方法的流程图；

图2为根据本发明一个具体实施例的随机测试程序生成的框图；

图3为根据本发明一个具体实施例的生成计数函数的流程图；

图4为计算随机变量的随机解的流程图；

图5为测试程序中指令序列的生成过程。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图，对根据本发明一个实施例的基于小桶消元的随机测试程序生成方法进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

图1的流程图示出了R.Dechter提出的桶消元方法，其执行过程如下：

步骤S101，初始化：根据变量序列X₁，X₂，...，X_n建立桶序列bucket₁，bucket₂，...bucket_n，将每个约束条件C_i分到各个桶中，每个桶bucket_p的变量集合为S_p，其中1≤p≤桶个数n。若某个约束条件中变量的下标最高为q，则将该约束放入bucket_q；

步骤S102，定义变量p指向桶序列的最后一个桶bucket_n；

步骤S103，利用$>N^p={\Sigma }_{X_p}{\Pi }_{N_i\in {\mathrm{bucket}}_p}{N}_i$>求桶bucket_p的计数函数，其中N_i为bucket_p中约束条件和新生成的计数函数的集合{N₁，N₂，...，N_j}中的元素。将N^p放入集合$>{\cup }_{i=1}^j{S}_i-\left\{X_p\right\}$>在变量序列中序号数最大的变量所对应的桶中。

步骤S104，p指向下一个桶；

步骤S105，判断p是否指向桶序列的第一个桶bucket₁，如果是，执行步骤S106；否则执行步骤S103；

步骤S106，返回每个桶中的计数函数。

由于每次循环处理一个桶，而剩下的桶中的计数函数和约束条件都不会再含有这个桶变量，因此称之为桶消元。从图1的流程图中可以看出，求解空间时是从下往上计算的；生成解时顺序刚好相反，是从上往下。按照约束网络的解空间给随机变量分配权重，从而确定变量的取值。因为该方法可以预知权重值，所以生成的解比较接近均匀分布。但是尽管桶消元法内存开销已经较低，它也是指数级的，不能处理规模较大的约束满足问题，其时空复杂度为O(n·exp(ω^*(d)))，其中n＝|X|，表示序列X中元素个数，ω^*(d)为约束网络在排序d下的导出宽度(induced-width)。这是因为计数函数N^p的自变量为序列X₁，X₂，...，X_n中X_p前面的某些变量的集合，有可能维数比较大，如果每个变量的值域都很大，那么计算该函数要消耗很多时间，存储它的结果也会占用很多空间。

为解决上述问题，Dechter和Emek等人提出的小桶消元方法用多个维数较小的计数函数来近似表示单个维数较大的计数函数。例如，对一个维数为16、值域为{1，0}的计数函数，它所需的空间为2¹⁶；若拆分成四个维数为4的计数函数，所需的空间就减少到4*2⁴。小桶消元方法在桶消元法的基础上对上述计算计数函数的步骤S103进行了改进：

把bucket_p中的约束条件和计数函数N₁，N₂，...，N_j分到t个小桶中Q’＝{Q₁，Q₂，...，Q_t}，对Q₁的计数函数$>N_1^p={\Sigma }_{X_p}{\Pi }_{i=1}^k{N}_{1_i};$>对Q_l∈Q′，l＞1，计数函数为则$>N_l^p={\max }_{U_l}{\Pi }_{i=1}^k{N}_{l_i},$>其中$>U_l={\cup }_{i=1}^k{S}_{l_i}-\left\{X_p\right\},$>为小桶Q_l中约束条件和计数函数的变量集合。将N_l^p放入U_l中序号数最大的变量所对应的桶中。该小桶消元方法的精确度很大程度上依赖于小桶个数t的取值。实践证明，t越大，虽然空间复杂度降低，但所需的时间也相应增加，这就意味着需要在时间和空间二者中折中。此外，这种拆分降低了求解的准确性，因为约束网络被分解成多个分支后，各分支之间存在一定的互斥性，满足某个分支的取值可能在另一分支中不能满足；而且由于bucket_p中除N₁^p以外的计数函数可以采用多种计算方法，如取最小值、平均值等，因此必须对计数函数的求解方法进行修正。

考虑时间和空间复杂度，根据本发明的一个具体实施例对上述小桶消元方法的计算计数函数的步骤进行了进一步改进：

把bucket_p中的约束条件和计数函数N₁，N₂，...，N_j分到t个小桶中Q’＝{bucket_p1，...，bucket_pi，...，bucket_pt}，其中1≤i≤t。根据本发明的一个实施例，采用如下计算过程根据小桶序号从大到小的次序依次计算每个小桶的计数函数：

根据如下公式(1)生成小桶bucket_pi的初始计数函数为本领域普通技术人员可以理解，每个小桶可能没有计数函数，也可能具有一个或多个计数函数，在此处用符号表示小桶bucket_pi中的所有计数函数：

$>N_i^{p^{*}}={\Sigma }_{X_p}{\Pi }_{N_l\in {\mathrm{bucket}}_{\mathrm{pi}}}{N}_l---\left(1\right)$>

其中，N_l表示小桶bucket_pi中被分到的约束条件或计数函数，1≤l≤小桶bucket_pi中的计数函数和约束条件个数。

根据如下公式(2)估算在bucket_pi中对变量X_p取不同值时该小桶bucket_pi与其它小桶的相容度，即综合考虑对变量X_p所对应的大桶bucket_p中t个小桶除bucket_pi以外的其他所有小桶bucket_pj的计数函数：

$>{\rho }_i=\underset{j\ne i}{\overset{i}{\Pi }}\frac{{\Sigma }_{s\in S_{\mathrm{pj}}}\min (N_j^{p^{*}}\left(s\right),1)}{\left|S_{\mathrm{pj}}\right|}---\left(2\right)$>

其中S_pj为小桶bucket_pj中除X_p外的所有变量集合，s表示S_pj中的变量，与类似，表示小桶bucket_pj的计数函数；

利用如下公式(3)计算小桶bucket_pi的计数函数：

$>N_i^p={\Sigma }_{X_p}{\rho }_i{\Pi }_{N_l\in {\mathrm{bucket}}_{\mathrm{pi}}}{N}_l---\left(3\right)$>

将该计数函数放入除桶变量X_p以外的其它变量中序号数最大的变量对应的小桶中，即将N_i^p分到S_pi中序号数最大的随机变量对应的小桶中。

因为ρ_i表示当X_p取某值时，在其它小桶中能够被接受的概率的连积，近似反映了各个子变量间的相等关系，因此这种新算法较为平衡地处理了各小桶间的关系，求得的解空间有更好的均匀度。本领域普通技术人员可以理解，上面仅给出用于计算相容度的一种实施方法，也可以采用其它方式计算相容度。

图2示出了根据本发明的一个具体实施例基于上述改进的小桶消元方法的随机测试程序生成的框图。如图所示，随机测试程序生成方法包括以下步骤：

步骤S201：编写指令模板，其包含了体系结构相关的信息，例如寄存器分组、指令分组和指令序列的定义，同时还包含了一些随机变量的声明以及它们之间的约束关系。

一个指令模板的示例如下：

指令分组：

.defgroup group_name

     Instruction1  ratio1

     Instruction2  ratio2

     Instruction3  ratio3

     ……

.end

寄存器分组：

.defgpr             .defgpfr

     r0  ratio0          f0  ratio0

     r1  ratio1          f1  ratio1

     r3  ratio3          f2  ratio2

     ……                ……

.end                .end

*未被指定权值ratio的寄存器在完全随机的模式下不会产生，以保护其存储的内容

定义单个随机变量：

.defvar  variable_name

     Scope1  weight1

     Scope2  weight2

     ……

.end

定义随机变量数组：

.defgvar variablearray_name

     1   Scope1   weight1

     2   Scope2   weight2

     ……

.end

定义约束条件：

.defcons

     Constraint1  arg1  arg2

     Constraint2  arg1  arg2

     Constraint3  arg1  arg2

     ……

.end

表1支持的约束关系的示例

  约束符号  参数  说明  ＝  arg1：var  arg2：var|constant  arg1＝＝arg2

  ne  arg1：var  arg2：var|constant  arg1≠arg2  gt或＞  arg1：var  arg2：var|constant  arg1＞arg2  lt或＜  arg1：var  arg2：var|constant  arg1＜arg2  ge或＞＝  arg1：var  arg2：var|constant  arg1＞＝arg2  le或＜＝  arg1：var  arg2：var|constant  arg1＜＝arg2  align  arg1：var  arg2：constant  arg1％arg2＝＝0

定义宏：

.defmacro

     Macro_name1   value1

     Macro_name2   value2

     Macro_name3   value3

……

.end

定义指令序列：

.defseq  sequence_name

     Ins_name       [operandcons1][operandcons2]......[*times]

     InsGroup_name  [operandcons1][operandcons2]......[*times]

     InsSeq_name                                      [*times]

     ……

.end

*操作数约束operandcons的形式为操作数字段名＝<常数|随机变量名>

顶层序列配置：

.deftop

      Instruction1           ratio1

      Instruction_group1     ratio2

      Instruction_sequence1  ratio3

      ……

.end

步骤S202，对指令模板进行文法分析，将信息分成两部分：一部分是随机变量和约束定义，一部分是指令序列的定义信息，该指令序列的定义信息用于后面具体数据结构的定义，指导指令序列的生成。根据随机变量和约束定义构建随机变量约束网络，作为约束求解器的输入。一个约束网络的示例如下：

约束网络R＝(X，D，C)，其中：

变量集合X＝{A，B，E}；变量域集合D＝{{1，2}，{2，5，6}，{0，3，5}}，D_i为变量X_i的取值区间；约束集合C＝{A≠B，E≥B}。

步骤S203，基于改进的小桶消元方法根据步骤S202中构建的约束网络，产生均匀分布的随机解。该步骤主要包括两步：从下往上生成计数函数；从上往下计算变量的值。下面结合图3和图4详细说明该过程：

图3示出了根据本发明一个具体实施例的生成计数函数的流程：

步骤S301，初始化：创建桶，其数量等于随机变量数，并全部清空；

步骤S302，根据每个随机变量的取值区间生成临时值域。因为从步骤S201中指令模板的定义可知，除寄存器号的约束外，其它约束都是针对连续变量，而它们的计数函数的时间和空间占用都是幂级膨胀，因此对连续变量应先根据变量取值区间的权重采集st个抽样值，经过预处理后作为其临时值域，然后才进行桶消元。此外，如果解空间无解或产生的解数目达到一定数目cnt时则需要重新抽样，优选的，cnt为st的1～2倍，cnt太小会导致桶消元核心结构重建过于频繁，从而降低了系统的效率。阈值st的选择会影响抽样的均匀程度：当st取值太大，同样会造成计数函数的计算和存储开销膨胀；当st取值太小，很有可能会使得符合要求的值太少。所以应该根据实际应用中具体情况来确定st的值，而且不同的变量可以选用不同的抽样数。

步骤S303，建立随机变量与桶的对应关系，即变量X_i对应的桶为bucket_i；

步骤S304，对所有随机变量进行排序。首先，初始化：对约束网络变量集合X中的每个变量X_i，设其相关变量的集合为R_i，且R_i＝φ；然后，对X_i所在的每个约束条件，假设该约束条件涉及的变量集合为S，那么令R_i←R_i∪S-{X_i}；最后，根据|R_i|从大到小的顺序排列X_i，得到的序列即为所求。

因为相关变量少的变量排在后面，消元时其对应的桶先处理，每处理完一个桶消一次元，因此处理相关变量多的桶时，大部分变量早已消去，因此维数也就比原来减少很多。经过这样的预处理，求解的时间和内存开销降低了很多。

步骤S305，基于上述改进的小桶消元方法计算小桶的计数函数。

图4示出计算随机变量的随机解的流程。其中变量index用来控制变量的求解方向，即从上往下：

步骤S401，初始化所有随机变量，设置其为未赋值状态且index＝1；

步骤S402，对选取的随机变量，根据指令模板中的信息，获取其临时值域；

步骤S403，对值域中的每个值，判断其是否违反约束，如果违反，执行步骤S402，重新获取值域；反之，则执行步骤S404；

步骤S404，计算该变量所在的桶中的所有计数函数在当前赋值情况下的值，将其值作为该变量的权重；

步骤S405，根据步骤S404中的权重挑选一个值，并且将index指向下一个桶，即index＝index+1，如果index指向最后一个小桶，则执行步骤S406，否则执行步骤S402；

步骤S406，检查每个变量是否都赋值完，是则执行步骤S407；否则，执行步骤S402，完成剩余变量的赋值；

步骤S407，检查所有约束关系在当前赋值下是否都满足，是则完成约束网络的求解过程；否则，执行步骤S402，重新获取值域，使不满足的约束关系在新的赋值下得到满足。

步骤S204，根据指令序列采用的描述语言，建立该语言下步骤S202中所述指令序列信息的数据结构，同时设置指令序列所需的其他信息，具体包括定点寄存器定义、浮点寄存器定义、指令分组、序列定义和顶层序列定义，并设立测试程序的长度和随机种子。下面是一条指令数据结构的具体实例：

Ins_struct_name{

      Field_name1   Op；

      Field_name2   Rs；

      Field_name3   Rt；

      Field_name4   Rd；

      Field_name5   Imm；

      Field_name6   Target；

}

步骤S205，根据步骤S203中计算的随机解来设置指令的操作数，并根据步骤S204中建立的指令数据结构生成指令序列，该指令序列构成测试程序。下面结合图5说明指令序列的生成过程：

步骤S501，作为入口，第一次生成指令时，指令缓冲必然为空，此后逐步往该缓冲中加入指令。如果指令缓冲为空，则执行步骤S503；否则执行步骤S502；

步骤S502，从缓冲中取出一条临时指令，但它还不是最终生成的指令，需要送到步骤S508中进行进一步修正；

步骤S503，从顶层配置中选出一个顶层序列项；

步骤S504，判断步骤S503中选出的序列项的类型，先看其是否是指令序列，若是，则执行步骤S505；否则，执行步骤S506；

步骤S505，根据指令信息中给出的索引值在指令序列所在的数据结构中找到相应的序列定义，生成临时指令串，放入指令缓冲中，这样下次循环开始时才会生成序列的内容；

步骤S506，如果序列项不是指令序列时，就要判断其是否是指令分组，若是，则执行步骤S507；否则，执行步骤S508；

步骤S507，根据指令信息中给出的索引值在指令分组所在的数据结构中找到相应的单条指令的操作码；

步骤S508，根据指令的操作码按照步骤S204中的指令数据结构随机生成一条实际的指令；

步骤S509，检查生成的指令的操作数有没有约束。对分组和单指令类型的操作数是没有约束的，指令直接存入指令缓冲，而从指令缓冲中取出的临时指令带有约束，执行步骤S510；

步骤S510，对有约束的指令，需要根据步骤S203中求得的随机变量的随机解修正指令的操作数，然后再将其放入指令缓冲中。

上述生成的随机测试程序可以用于分别由模拟器和待测模块(DUT)运行，并根据二者的运行结果相同与否来确定待测模块设计是否成功。该操作具体如下：

模拟器运行步骤S205中生成的测试程序，给出测试程序中每条指令运行结果，包括寄存器堆的状态以及整个测试程序完成后内存存储的内容。同时，还修正某些不符合要求的操作数，以使指令能在RTL正常工作。

待测模块(DUT)运行步骤S205中生成的测试程序，进行RTL仿真，得到实际设计模块的寄存器堆的状态和内存中的值。

比较上述RTL得到的实际结果与模拟器运行产生的参考结果。如果二者一致，则待测模块设计没有错误；如果结果不一致，说明DUT和模拟器的行为有差异，此时需要查看程序的上下文，分析是参照结果的错误还是设计错误。比较结果时，为了既能快速定位错误点又能确保较快的仿真速度，对寄存器堆，该测试程序在每条指令提交时就会将参照结果与系统仿真结果进行实时比较检测，及时发现系统设计中的问题。当有指令提交时就把提交指令的参考值从结果文件中取出，并与RTL的仿真结果比较，如果发现不一致就说明有错误，终止仿真。对于内存，整个测试程序都执行完时，系统从用户态切换到核心态，将cache中的数据刷新到内存，然后再统一比较。

根据本发明的一个实施例，提供了一种基于小桶消元的随机测试程序生成系统，包括下列部件：

约束网络构建部件，用于编写并解析指令模板，并构建约束网络。进一步地，该约束网络构建部件包括：指令模板编写模块，用于编写指令模板；解析器，用于解析所述指令模板并构建约束网络。

约束求解器，用于基于利用小桶间的相容度计算的小桶的计数函数根据所述约束网络来计算随机变量的随机解。

指令生成部件，用于根据所述随机解设置指令的操作数，生成由所述指令构成的随机测试程序。进一步地，该指令生成部件包括：指令信息设置模块，用于设置指令信息；指令生成模块，用于根据所述约束求解器计算的所述随机解设置指令的操作数，并根据所述指令信息生成由所述指令构成的随机测试程序。

通过在求解约束网络的小桶消元方法中引入相容度因子生成计数函数，可以得到更均匀的随机解，增加了操作数取值的多样性，能更充分地把一种模式的各种情况展现出来。因为用较短的测试程序就能达到很广的覆盖面，大大减少了实际RTL仿真时的时间消耗，同时也降低了出错时的调试难度。

应该注意到并理解，在不脱离后附的权利要求所要求的本发明的精神和范围的情况下，能够对上述详细描述的本发明做出各种修改和改进。因此，要求保护的技术方案的范围不受所给出的任何特定示范教导的限制。