基于贝叶斯网络的验证激励向量生成研究

王润 蒋剑飞 王琴

摘 要：为了解决传统数字芯片验证环节中基于仿真的验证（或动态验证）功能覆盖率收敛速度慢的缺点，提出一种新的以功能覆盖为导向的测试用例生成方法，该方法基于贝叶斯网络和机器学习技术，可实现从覆盖模型到测试用例生成器反馈回路的自动关闭，在DUT的验证过程中，使用该方法为所测试的设计生成新的激励。实验结果表明，基于贝叶斯网络的CDG技术测试用例使用较少，覆盖率收敛更快，与传统基于仿真的验证技术相比，测试用例数量减少了43%。基于贝叶斯网络的CDG技术提高了覆盖率的收敛速度，缩短了验证周期，相比于传统动态验证技术而言其芯片功能验证更完善。

关键词：功能验证;贝叶斯网络;机器学习;CDG;覆盖率

DOI：10. 11907/rjdk. 192567 开放科学（资源服务）标识码（OSID）：

中圖分类号：TP301文献标识码：A 文章编号：1672-7800（2020）007-0001-04

Research on Generation of Verification Incentive Vector Based on Bayesian Network

WANG Run，JIANG Jian-fei，WANG Qin

（Microelectronics Institute，Shanghai Jiao Tong University， Shanghai 200240，China）

Abstract：In order to solve the problem of slow convergence rate of functional coverage of simulation based verification （or dynamic verification） in the traditional verification of digital chips，this paper proposes a new method of test case generation based on function coverage. Based on Bayesian network and machine learning technology， this method provides an effective method to automatically close the feedback loop from coverage model to test case generator. In the verification process of DUT （design under test）， this method is used to generate new incentives for the tested design. The experimental results show that the CDG （coverage driven test case generation） technology based on Bayesian network uses fewer test cases， and the coverage convergence is faster. Compared with the traditional simulation based verification technology， the number of test cases is reduced by 43%. CDG technology based on Bayesian network improves the convergence rate of coverage and reduces the verification cycle. Compared with the traditional dynamic verification technology， the chip function verification is more complete.

Key Words：functional verification; Bayesian network; machine learning; CDG; coverage

0 引言

功能验证被广泛认为是硬件设计周期中的瓶颈[1]。目前，在完整的芯片开发周期中，70%的设计开发时间和资源被用于功能验证[2]。功能验证已经成为芯片和系统设计领域的一项主要挑战，当工程师需要在日益密集的芯片上设置越来越多的功能时，成功验证芯片和系统功能所需要的时间也越来越长，这就需要开发新的验证技术，在资源有限的情况下，为验证人员提供快速实现其目标的方法。目前，以覆盖率为导向的测试用例生成技术有两个主要缺点[3]：①覆盖率反馈中包含了人的参与、调整激励的生成和分析所需的大量人为劳动，因此增加了成本;②整个验证流程的反馈发生在仿真之后。首先需要进行仿真，然后才发现激励没有命中的感兴趣的覆盖点，这样才能调整激励。

常见的测试用例有几个来源[4]：①编写定向的直接测试用例[5]，存在的问题是仿真效率低下，对于复杂设计，固定场景的定向测试被认为是无效的[6];②小部分测试用例通过手工随机约束设计[7]，包括覆盖设计边界情况，存在的问题是，边界情况需要对设计有比较充分的理解才能覆盖到，如果对设计不甚了解，则覆盖边界情况需要耗费大量时间;③运行现有的测试用例集（遗留测试或商业测试套件）[8]，显然，当所验证的设计是比较成熟的模块，有比较完备的测试用例，这种方法才起作用。

以上方法都存在覆盖率收敛速度慢的缺点，鉴于此，本文提出一种面向覆盖的测试用例生成方法。本文方法是在一个统计推断的框架中映射CDG（Coverage Driven Testcase Generation）[9]，并应用机器学习技术实现CDG目标。具体而言，使用贝叶斯网络建模覆盖率信息和测试用例之间的关系，可以提高功能覆盖率收敛速度。

1 覆盖率驱动的测试用例生成

一般而言，CDG的目标是自动向测试用例生成器提供基于覆盖率分析的指令。这可以进一步分解为两个子目标：①向测试生成器提供有助于实现困难情况（即未覆盖或很少覆盖的任务）的指令，实现此子目标可以缩短完成测试计划所需时间，并减少手动编写指令的数量;②尽可能使用一组不同的指令，为任何覆盖率模型[10]提供更容易到达的指令，实现该子目标使验证过程更加健壮，因为它增加了验证过程中任务被覆盖的次数。此外，如果通过不同的方向到达覆盖率任务，则会大大增加发现与此激励相关的隐藏错误的机会。

以覆盖率为驱动的激励生成有几种不同风格，可以根据覆盖率反馈回路在调整过程中的位置对它们进行归类[11]，包括动态覆盖率控制激励生成、基于模型的覆盖率驱动测试生成、自动覆盖率控制生成等。图1为验证流程中对覆盖率分析的反馈回路，首先编码激励参数和偏置约束信息，通过PRNG（伪随机数发生器）生成满足特定约束条件的激励，通过模拟仿真将生成好的激励驱动到DUT（Design Under Test）的端口上，仿真工具會根据覆盖模型自动统计功能覆盖率，并将不同测试用例的覆盖率数据整合到一起，得到积累的覆盖率数据，然后通过人为的覆盖率分析，进一步调整约束偏置，生成修改后的新测试用例，继续仿真，直到达到覆盖率收敛为止，这样即可完成功能验证。有两种常用的CDG方法：基于反馈的CDG和基于构造的CDG。基于反馈的CDG依赖于来自覆盖率分析的反馈实现对测试生成器指令的自动修改。例如，在文献[12]中，使用遗传算法选择和修改测试用例以增加覆盖率;在文献[13]中，覆盖分析数据用于修改表示DUT的马尔科夫链的参数，然后使用马尔可夫链生成设计的测试用例;在文献[14]中，覆盖率分析结果触发一组修改测试指令的生成规则。相反，在基于构造的CDG中，DUT的外部模型用于生成测试指令，这些指令旨在准确地命中覆盖率任务。例如，在文献[15]中，一个流水线设计的FSM模型用于生成覆盖流水线中指令及相关性测试。

2 基于贝叶斯网络的面向覆盖的测试生成

贝叶斯网络是一组变量联合概率分布的图形表示，这种表达最初是为了编码变量间的不确定关系，最初由遗传学家苏厄尔·赖特[16]提出。贝叶斯网络将CDG映射到一个统计推断的框架中，可以概率方式表示CDG成分之间的复杂（可能是随机的）关系，是一种有效的建模方案。

2.1 贝叶斯网络

贝叶斯网络由两部分组成。第一个是有向无环图，其中每个顶点对应一个随机变量。该图反映所表示分布的一组条件独立属性：在给定其父级状态的图中，每个变量可能与其非子级无关。该图可表示概率分布的定性结构，并用于有效的推理和决策[17]。第二部分是局部交互模型的集合，描述每个变量[Xi]的条件概率[p（Xi|Pai）]。这两个分量共同代表一组变量[X][18]上唯一的联合概率分布。联合概率分布如式（1）所示。

可以看出，该式实际上隐含了上文图形结构的条件独立性。公式表明，贝叶斯网络指定的联合分布可以用单个局部交互模型的乘积表示。因此，虽然贝叶斯网络可以表示任意的概率分布，但它们为那些可以用简单结构表示的分布提供了计算优势。

贝叶斯网络可以有效解决通过贝叶斯规则产生一个节点（或一组节点）的值[X]的后验概率，如式（2）所示。

因此，可以通过选择最大后验概率[max p（X|E）]的形式进行统计推断[19]。

2.2 基于贝叶斯网络的CDG

CDG过程从构建贝叶斯网络模型开始，该模型描述测试指令与覆盖空间之间的关系。图2展示了一个简单但典型的贝叶斯网络，它对CDG的一小部分进行了建模。贝叶斯网络描述了影响生成的命令类型（cmd_type）的指令与CPU内活动内核（core_enable）之间的关系，以及生成的命令（cmd）、其响应（resp）和生成命令的内核（core）的覆盖属性。网络由输入节点（左边的白色圆圈）和定义覆盖空间的覆盖节点（右边的白色方块）组成，除上述可以物理观测到的节点之外，网络还可能包含隐藏的节点，即没有任何物理证据（观测）证明它相互作用的变量，这些变量在图中表示为阴影椭圆。在贝叶斯网络结构中加入隐藏节点主要是为了反映关于隐藏节点的专家领域的知识[20]。

2.3 基于贝叶斯网络的CGRA验证

可重构计算架构CGRA（Coarse-Grained Reconfigurable  Architecture）是指能根据变换的数据流或控制流，对硬件结构进行动态配置的一种体系结构[21]。CGRA最大的优势是能通过硬件结构组织不同粒度和不同功能的计算资源，通过运行过程中的硬件配置，调整硬件功能，根据数据流的特点，让功能配置好的硬件资源互连形成相对固定的计算通路，从而以接近“专用电路”的方式进行数据驱动下的计算[22]。当算法和应用变换时，再次通过配置，使硬件重构为不同的计算通路去执行，是一种高效而灵活的计算架构，因而能在算力和能耗上取得很好平衡，达到更高的能效比[23]。

对于CGRA的运算单元PE（Process Element），本文使用基于贝叶斯网络的CDG验证其功能覆盖率。使用的PE单元主要由3个子模块组成，如图3所示：输入Buffer单元，ALU和输出Buffer单元。输入端有时钟和复位信号、数据信息、配置信息和来自下层PE的反压信号。为了简化分析，对单个PE进行验证，每条指令由4个输入变量组成，第1个变量表示指令的第1个数据（1 bit valid + 2 bit tag + 32 bit data），第2个变量表示指令的第2个数据（1 bit valid + 2 bit tag + 32 bit data），第3个变量表示数据输出是否有效（1bit valid + 2bit tag + 1bit bool），valid位代表数据输入是否有效，每笔数据包含一个tag位，表示数据是否处于乱序执行模式。为了简化分析，对数据位和tag位分别进行处理，单条输入指令包括6笔数据信息。由于tag位是2bit位宽，PE有4个不同的tag以区分每笔数据，因此，将每4笔数据划分为一个transfer，使用tag表示每个transfer中的不同数据，如果上一个transfer的一笔数据在inbuffer里没有处理完，在下一个transfer输入形同tag的数据时会引起tag冲突。第4个变量表示PE的配置。

本實验对输入变量进行组合限制，使用100个直接测试用例，如图4所示。每组测试用例由6个输入变量，5个功能点组成，共11个变量，使用直接测试用例对网络模型进行训练。

使用一个覆盖模型检查PE状态及其指令属性，覆盖模型由7个属性组成：数据一的输入属性（dp1+tag）、数据二的输入属性（dp2+tag）、数据三的输入属性（dp3）、PE的配置状态（op）、PE的输出属性（state），目的是生成覆盖上述覆盖模型的指令流。在指定贝叶斯网络结构后，使用数据样本和相应的覆盖任务对其进行训练。为此，根据使用的指令和生成的覆盖任务构建一个训练集，然后使用许多已知学习算法中的一种估计贝叶斯网络参数（条件概率分布集）。训练完成的贝叶斯网络模型如图5所示，可以看出功能点State与4个输入变量相关联，分别为：Data1、H1、H2、Data2。

在评估阶段，训练好的贝叶斯网络可以通过后验概率确定期望覆盖任务的指令。例如，在该模型中，指令是测试生成器中内部绘制的可能结果的权重，可以为覆盖节点（例如state）的某个bin计算指令节点（例如data1、data2、H1、H2）的后验概率分布，后者直接转换为要写入测试生成器参数文件中的权重集，调整前后的激励变量权重分布对比如图6所示。

实验结果表明，使用CDG技术能够实现34个测试用例之后覆盖100%的功能点，而用户自定义的测试用例在60个测试用例之后才能实现功能点的全覆盖[14-15]。使用CDG技术的测试用例数量与使用随机测试用例技术的测试用例数量对比如图7所示。该建模技术能够有效实现覆盖率的目标，对难以覆盖的情况更容易达到，覆盖率可以实现更快收敛，节省了时间。

3 结语

本文提出了一种面向覆盖的测试用例生成方法，实验结果表明，该建模技术利用节点的先验概率与后验概率，可以在毫不了解设计的情况下有目的地修正覆盖率漏洞，达到覆盖率快速收敛的效果。该建模技术能够有效实现CDG的目标，即边界情况更容易覆盖到，覆盖率更容易收敛。本文研究为芯片的功能验证提供了切实可行的新思路，未来还可以继续深入研究动态贝叶斯网络，即将时间对贝叶斯网络结构的影响考虑进来，从而对随机过程中的时间依赖性进行建模。此外，可进一步集成专家领域知识，确定贝叶斯网络中的隐藏节点，精细化贝叶斯网络结构，从而实现覆盖模型的不同路径覆盖，提高芯片隐藏漏洞发现几率。

参考文献：

[1] BERGERON J. Writing testbenches： functional verification  of HDL models[M]. Dordrecht： Kluwer Academic Publishers，2000.

[2] ANDREW P. Functional verification[M].Functional Verification Coverage Measurement and Analysis. 2004.

[3] CIEPLUCHA M. Metric-driven verification methodology with regression management[J]. Journal of Electronic Testing，2019，35（1）：101-110.

[4] GLENN S，MEIL G，RODRIGUEZ E，et al. Functional design verification for the PowerPC 601 microprocessor[C].Proceedings of 12th IEEE on VLSI Test Symposium，1994.

[5] KANTROWITZ M，NOACK L M. I'm done simulating; now what？ verification coverage analysis and correctness checking of the DECchip 21164 Alpha microprocessor[C].Proceedings of 33rd IEEE，Design Automation Conference，1996：325-330.

[6] MEYER，ANDREAS.Principles of functional verification[M]. Oxford： Newnes，2003.

[7] CHEN W，WANG L C，BHADRA J，et al. Simulation knowledge extraction and reuse in constrained random processor verification[C]. 2013 50th ACM/ EDAC/IEEEDesign Automation Conference，2013：1-6.

[8] GANAPATHY G，NARAYAN R，JORDEN G，et al. Hardware emulation for functional verification of K5[C].33rd Design Automation Conference，1996：315-318.

[9] STAATS M，GAY G，WHALEN M，et al. On the danger of coverage directed test case generation[J]. Macromolecules，2012，31（15）：409-424.

[10] GRINWALD R，HAREL E，ORGAD M，et al. User defined coverage——a tool supported methodology for design verification[C].California：Proceedings of the 35th Design Automation Conference，1998：158-165.

[11] WILE B， GOSS J C， ROESNER W.全面的功能验证[M].北京：机械工业出版社，2017.

[12] BOSE，MRINAL. Automatic bias generation for biased random instruction generation[C].Seoul： CEC2001： Congress on Evolutionary Computing，2001.

[13] TASIRAN S，FALLAH F，CHINNERY D G，et al. A functional validation technique： biased-random simulation guided by observability-based coverage[C].19th International Conference on Computer Design， 2001：82-88.

[14] NATIV G，MITTENNAIER S，UR S，et al.Cost evaluation of coverage directed test generation for the IBM mainframe[C].Proceedings of International Test Conference，2001：793-802.

[15] UR S，YADIN Y.Micro-architecture coverage directed generation of test programs[C].Proceedings of the 36th Design Automation Conference，1999：175-180.

[16] MUSTAIN，BRIAN C.Correlation and Causation[J]. Science News，2013，121（24）：387.

[17] 周忠宝，董豆豆，周经伦. 贝叶斯网络在可靠性分析中的应用[J].系统工程理论与实践，2006，26（6）：95-100.

[18] PEARL J.Probabilistic reasoning in intelligent systems：network of plausible inference[M].San Francisco：Morgan Kaufmann Publishers，1988.

[19] RUPPERT，DAVID.Probabilistic networks and expert systems[J].Journal of the American Statistical Association，2001，96（456）：1524-1524.

[20] 譚国苹.含有隐藏变量的贝叶斯网络的学习与应用[D].北京：中央民族大学，2015.

[21] ZION K， STEVEN J E，WILTON S J E. Register file architecture optimization in a coarse-grained reconfigurable architecture[C].Proceedings of the 13th Annual IEEE Symposium on Field-Programmable Custom Computing Machines，2005：1-10.

[22] YANG C，LIU L B，WANG Y S，et al. Configuration approaches to enhance computing efficiency of coarse-grained reconfigurable array[J]. Journal of Circuits，Systems and Computers，2015，24（3）：1550043.

[23] GANGHEE L，SEOKHYUN L，KIYOUNG C，et al. Routing-aware application mapping considering steiner points for coarse-grained reconfigurable architecture[C].6th International Workshop on Applied Reconfigurable Computing，2010： 231-243.

（责任编辑：孙 娟）