基于指令模板的通用处理器约束随机指令生成方法

刘 婧，王天成，王 健，3，李华伟

（1.湘潭大学信息工程学院，湖南 湘潭411105；2.中国科学院计算技术研究所计算机体系结构国家重点实验室，北京100190；3.中国科学院大学，北京100049）

基于指令模板的通用处理器约束随机指令生成方法

刘 婧1，王天成2，王 健2，3，李华伟2

（1.湘潭大学信息工程学院，湖南 湘潭411105；2.中国科学院计算技术研究所计算机体系结构国家重点实验室，北京100190；3.中国科学院大学，北京100049）

随着集成电路设计的复杂度越来越高，功能验证成为设计流程中的瓶颈。而通用处理器是集成电路中功能最为复杂的设计之一，对其功能验证提出更高要求。为此，给出一种约束随机指令生成方法，对ARM v8处理器进行模拟验证。从指令集中提取指令模板，用指令模板生成合法的ARM v8指令，通过调整约束支持各种功能场景的验证。基于结果自动比对的验证环境，对处理器进行充分验证，发现58处设计错误，可用在后续的FPGA硬件仿真中。验证结果表明，该方法可得到90%的结构覆盖率。

功能验证；通用处理器；指令模板；指令生成；约束随机指令

DO I：10.3969/j.issn.1000-3428.2015.10.058

1 概述

随着现代集成电路工艺的不断发展，芯片规模越来越大，复杂度越来越高。特别是在通用处理器领域，处理器的设计日趋复杂，功能验证已经成为设计流程中的瓶颈［1］。目前常用的功能验证方法有模拟验证和形式化验证。模拟验证通过生成验证激励分别施加于处理器设计和参考模型，通过将得到的模拟结果与参考结果进行对比，从而发现设计错误。形式化验证通过数学的方法证明被验证系统满足设计规范。形式化验证存在状态空间爆炸的问题只能处理较小的设计规模［2］，现在工业界主流的功能验证方法还是模拟验证。

对于模拟验证，得到高效的测试激励成为研究热

点。国内外很多研究机构也都在这个方面提出了众多的解决方法并开发相应的工具［3］。IBM HAIFA研究中心研发的Genesys-Pro［4］，为基于模型的随机程序生成器。加州大学欧文分校的学者提出一种体系结构描述语言驱动的验证激励生成方法［5］，该方法针对流水线处理器的验证。中国科学院计算技术研究所龙芯验证组提出了一种可配置随机测试程序生成器（Configurable Random test Program Generator，CRPG）［6］，它包含配置规范模型、参考指令集仿真器测试生成模型以及验证环境4个基本组件。国防科技大学提出了一种由体系结构描述驱动的基于约束求解的微处理器体系结构级测试程序自动生成的方法，并基于此开发了原型系统——MA2TG［7］。对于难达状态的覆盖，中国科学院计算技术研究所集成电路实验室研究了半形式化验证方法。先后提出了通过路径约束引导验证激励生成到达难达状态的方法［8］和通过抽象引导生成验证激励到达难达状态的方法［9］。

本文提出一种基于指令模板的通用处理器约束随机指令生成方法。该方法基于ARM v8指令集构建指令模板，编写合法性约束，指导生成合法的指令序列。在此基础上通过约束的调整可以生成针对特定场景的指令序列。

2 ARM v8处理器

本文验证的对象为一款基于ARM v8指令集的通用处理器核的设计，其结构如图1所示。

图1 ARM v8整体结构

该处理器特性如下：

（1）处理器采用12级流水结构。

（2）处理器支持四线程。

（3）处理器主要部件包括取指单元（IFU）、Instruction Buff（IB）、取指分发单元（IFU）、指令译码单元（DC）、运算逻辑单元（ALU）、浮点运算单元（FPU）、存储单元（LSU）。

（4）处理器包含4个通用寄存器堆和浮点寄存器堆，对应4个线程。

（5）处理器采用32位简单指令集结构，共支持指令220条。

（6）处理器集成了16 KB一级I-Cache和16 KB一级D-Cache，同时通过interface连接128 KB二级Cache。

如上所述，待验证处理器结构复杂，指令集庞大，即验证向量空间大，使得用手写激励覆盖所有的功能点实现困难。本文提取处理器功能点，采用约束随机的方法自动生成大量的合法指令覆盖这些功能点的方法对待验证处理器进行验证。

3 指令生成方法和实现

3.1 验证框架

本文提出一种基于指令模板的约束随机指令生成方法，并使用System Verilog语言实现了指令生成平台。采用模拟验证的方法，搭建验证平台对一款ARM v8处理器进行了验证。整个验证框架结构如图2所示。

图2 约束随机指令生成的验证框架

通过指令生成得到的验证激励分别施加于处理器核设计和参考模型，然后将得到的模拟结果和参考结果进行对比，以判断处理器核的行为是否正确。同时分析模拟过程中的覆盖率信息，根据覆盖率反馈的验证漏洞来创建新的验证场景，以生成新的验证激励提高验证覆盖率，加速验证的收敛。

3.2 指令模板

因为用于验证的指令必须符合ARM v8指令语法结构，所以本平台构建了能指导生成合法指令的指令模板，用于指导生成合法的指令。一条ARM v8汇编指令可能包含的各字段如图3所示。

图3 ARM v8指令各字段

在图3中，opcode为操作码，cond为条件码，dst0、dst1分别为第0号、第1号目的寄存器号，scr0、scr1分别为第0号、第1号源寄存器号，immd为立即数。

为了构建指令模板，本文对DUV已实现的所有ARM v8指令进行了分类。为了在验证过程中能控制验证的方向，在指令分类时有必要考虑到指令的功能。同时为了使指令模板的构建工作尽量简单，指令语法格式接近的指令，即图3中各字段内容及数量接近的指令也应归为一类。根据这2个标准本文最终对指令的分类情况如表1所示［10］。

表1 ARM v8指令分类

根据每类指令的特点约束其各字段在合法的范围内，拼接各字段成一条合法指令后输出［11］。对于每类指令都有的共性，定义了BaseInstruction类。其他各类指令对BaseInstruction类进行扩展，实现其特有的属性。图4为指令模板指导Load/Store Single Register类指令生成的过程［12］。

图4 指令模板指导Load/Store Single Register类指令生成

在BaseInstruction中确定可能用到的4个寄存器的编号，可选范围均为［0：31］。然后进入子类，Load/Single Register子类特有属性包括：

（1）目的寄存器数目，该子类只有一个目的寄存器。

（2）该类独有的操作码，可选范围为0～8，不同

的操作码隐含了传输字宽，由此可确定目的寄存器的位宽，32位及以下的数据的存储目的寄存器表示为W d，64位数据的存储目的寄存器表示为Xd。

（3）寻址方式，该类指令根据不同的寻址方式使用不同的源寄存器，当寻址方式是1时，基址寄存器（即源寄存器）为64位寄存器，偏移值为可扩充的12位无符号立即数或9位不可扩充的有符号立即数。当寻址方式是6时，基址寄存器为PC，偏移地址为19位有符号立即数，寻址范围为程序存储范围。

3.3 各功能场景下的指令生成

在生成指令前，在指令类层次上可对最终生成的指令序列中各指令类所占比例进行配置。在指令级层次上，可根据操作码的不同，对每条指令在本类指令中所占比例进行配置。也可根据验证重点的不同生成指令序列触发相应的功能场景，下文对本平台实现的几个重要的功能场景进行介绍。

3.3.1 数据相关指令生成

DUV采用12级流水结构，为了验证DUV在流水线存在资源读写冲突的情况下的行为是否符合设计规范的约定，本平台随机生成存在寄存器相关的指令序列以激活这一场景，以验证DUV的正确性。

数据相关指令生成方法需要完成下列任务：

（1）考虑到所有的相关模式。本指令的每个寄存器与其他指令的寄存器之间的相关性共有3种情况，本指令的寄存器与目标指令的源寄存器相关，本指令的寄存器与目标指令的目的寄存器相关，本指令与目标指令不存在寄存器相关。本指令的寄存器分为源寄存器和目的寄存器。当存在相关性时还分为与第0号和第1号寄存器相关2种情况。

（2）指定相关深度，2条存在相关性的指令之间的最大跨度，根据DUV流水线深度确定。

（3）能实现相关模式各类情况概率的可控性。

数据相关指令生成方法的关键在于编写合法性约束以及维护历史使用寄存器队列。在生成指令序列前，合法性约束能实现根据不同的验证要求对指令间相关性种类、各相关性种类的概率进行配置。

生成数据相关指令的寄存器编号通过如下所示的程序伪码得到：

foreach reg

//不存在相关性或相关深度所指记录无效则该寄存器编//号为随机值

if c-m-sel==‵N||hist-q.regs［c-d］.f==0；gen-reg-num=reg-num；//查询历史寄存器队列else

gen-reg-num=hist-q.regs［c-d］.c-m-sel；

hist-q.regs.push-front（regs-info）；

hist-q.regs.pop-back；

在生成指令时对于指令中的各寄存器，如果不存在相关性或者相关深度（c-d）所指的记录中有效性标志f为 0，则寄存器编号为 0～31的一个随机值reg-num，否则，寄存器编号为历史使用寄存器队列（hist-q）中相关深度、相关模式（c-m-sel）所指的寄存器的编号。最后把本条指令使用到的寄存器信息reg-info压入到hist-q队头。hist-q中的每条记录regs-info包括7个元素｛f，dest-cnt，scr-cnt，dest-0，dest-1，scr-0，scr-1｝，它们分别代表此条记录的有效性、目的寄存器数目、源寄存器数目、第0个目的寄存器的寄存器号、第1个目的寄存器的寄存器号、第0个源寄存器的寄存器号、第1个源寄存器的寄存器号。3.3.2 跳转指令生成

跳转指令关系到处理器转移预测、跳转预判、流水线等功能的实现是否符合要求。所以本文搭建的指令生成平台对跳转指令进行了重点验证。

生成跳转指令时很容易生成非法指令，为了生成合法指令，需要注意以下3点：

（1）每类跳转指令的跳转范围是一定的，所以在生成指令时要添加约束保证跳转范围的合法性。

（2）因为生成的指令序列是一定的，所以跳转所指向的目标地址应该存储了指令，需要添加约束使得跳转的范围在生成的指令序列范围内。

（3）跳转指令目标地址不能是绑定为一个指令包的中间指令，如要实现带寄存器的跳转指令（BR）要先向寄存器中写入跳转目标地址。本文用2条指令（mov、movk）完成写目标地址的写操作。因此BR指令的功能由这2条写地址指令后跟着实际的跳转指令（br）组成的指令包来完成。显然当其他跳转指令的目标地址指向该指令包的后2条指令时会发生错误。为了解决这个问题，本指令生成平台对生成的指令数进行计数，然后将跳转指令的目标地址和指令包起始地址都放置在指令序号模3为1的位置。

3.3.3 Load Forward指令生成

指令生成流程如图5所示。

图5 load forward指令生成流程

在访存指令中，如果 Load指令要取的数据在Store Buffer中，则直接从store buffer中forward到寄存器，而不访问内存。为了验证DUV在满足条件的情况下是否能成功实现forward功能，以及在条件不成立的情况下是否会出现forward紊乱，本文提出了一种控制激活load forward的方法：维护一个store指令（str-ins）历史访问地址队列（q-fwd）来存储str-ins历史访问的内存地址（mem-addr）。q-fwd共存储了指定条数（根据Store Buffer的长度而定）记录。

首先对load forward与q-fwd中各记录的相关概率进行配置，然后开始生成指令。若当前指令为str-ins则将mem-addr压入q-fwd队头，q-fwd队尾元素弹出，否则为load指令。若此load指令不激活load forward，此指令的mem-addr为随机值，否则mem-addr为q-fwd中相应记录，然后根据指令访存数据宽度对mem-addr进行对齐处理，此mem-addr拼接上指令其他字段，指令生成完成。

因为存储一致性的验证比较复杂，本平台对于四线程的验证采用生成4个指令序列，存储在互不重叠的内存单元以供给4个相应的线程的方式进行验证。

4 验证效果与分析

本文针对前述一款ARM v8处理器，搭建了指令生成平台和验证平台对其进行验证。在验证过程中，通过分析每个阶段的覆盖率报告，对该阶段未能覆盖到的功能，本平台采取添加约束，引导指令生成平台生成能激活这些功能的指令以达到提高覆盖，加速验证收敛的目的。在验证工作结束时，约束随机指令要求覆盖到的功能点全部覆盖到，即功能覆盖率达到100%。结构覆盖率达到了90%，对覆盖率进行分析后，发现关于中断与异常处理的模块未能覆盖到，而这些模块不通过随机约束指令来进行验证，所以采取定向激励来对其进行验证，使得结构覆盖率达到了100%。本平台在约束随机验证过程中帮助设计人员发现了58处设计错误，根据功能单元的不同，下面对错误出处进行了分类，如图6所示。

图6 各单元bug数

本文以每周发现错误为单位，对设计错误数进行了统计，如图7所示。从图中曲线趋势可以看出，随着验证过程的持续深入和时间的推移，错误数逐渐收敛。此后将有信心将验证的过程从模拟验证过度到后续的FPGA硬件仿真和原型验证，进行更大规模和更快速度的集成验证。

图7 每周发现的bug数

5 结束语

本文提出了一种基于指令模板的随机指令生成方法，搭建了指令生成平台并利用其对一款ARM v8处理器进行了验证。该指令生成平台具有较强的灵活性和易操作性。最终取得了结构覆盖率90%、发现设计错误58处的验证效果，为处理器进入后续的FPGA硬件仿真奠定了良好的基础。

［1］ ITRS.ITRS2008［EB/OL］.（2008-02-08）.http：//pub lic.itrs.net/.

［2］ 李晓维.集成电路设计验证［M］.北京：科学出版社，2010.

［3］ 沈海华.覆盖率驱动的随机测试生成技术综述［J］.计算机辅助设计与图形学学报，2009，21（4）：419-430.

［4］ Adir A.，Almog E，Fournler L，et al.Genesys-Pro：Innovations in Test Program Generation for Functional Processor Verification［J］.IEEE Design&Test of Computers，2004，21（2）：84-93.

［5］ Mishra P，Dutt N.Graph-based Functional Test Program Generation for Pipelined Processors［C］//Proceedings of Design Automation and Test in Europe Conference. Paris，France：［s.n.］，2004：182-187.

［6］ Shen H H，CRPG：A Configurable Random Test-program Generator for Microprocessors［C］//Proceedings of IEEE International Symposium on Circuits and Systems. Washington D.C.，USA：IEEE Press，2005：4171-4174.

［7］ 朱 丹.微处理器体系结构级测试程序自动生成技术［J］.软件学报，2005，16（12）：2172-2180.

［8］ Zhou Yanhong，Wang Tiancheng.Path Constraint Solving Based Test Generation for Hard-to-Reach States［C］//Proceedings of the 22nd Asian Test Symposium.New York，USA：ACM Press，2013：239-244.

［9］ Wang Jian.Functional Test Generation Guided by Steady-state Probabilities of Abstract Design［C］// Proceedings of Conference on Design Automation and Test in Europe.Berlin，Germ any：Springer，2014：5-13.

［10］ 顾震宇.基于仿真的32位RISC微处理器的功能验证方法［J］.小型微型计算机系统，2004，25（4）：752-756.

［11］ 段博海.银河飞腾 DSP模拟验证平台的设计与实现［D］.长沙：国防科学技术大学，2006.

［12］ 罗汉青，梁利平，叶甜春.DSP随机测试程序自动生成技术［J］.微电子学与计算机，2013，30（11）：154-159.

编辑 顾逸斐

Constraint Random Instruction Generation Method for General Processor Based on Instruction Template

LIU Jing1，WANG Tiancheng2，WANG Jian2，3，LI Huawei2
（1.College of Information Engineering，Xiangtan University，Xiangtan 411105，China；2.State Key Laboratory of Computer Architecture，Institute of Computing Technology，Chinese Academy of Sciences，Beijing 100190，China；3.University of Chinese Academy of Sciences，Beijing 100049，China）

Due to the increasing system complexity of hardware design，functional verification becomes the bottleneck of the design flow.General processor is one of the most complex designs of integrated circuits，and it brings a huge challenge on its functional verification.This paper proposes a constraint random instruction generation method，for the simulation-based verification of an ARM v8 processor.This instruction generation method is based on the templates that are extracted from the instruction set，which guide the valid ARM v8 instructions’generation，and can support a variety of functional scenarios’verification by adjusting the constraints.Based on automatically comparison of the results produced by the validation environment，it achieves fully verification of the processor，and 58 design mistakes are found.The achievement has a good foundation，for the subsequent FPGA hardware emulation.The verification results show that the method can obtain the structural coverage of 90%.

functional verification；general processor；instruction template；instruction generation；constraint random instruction

刘 婧，王天成，王 健，等.基于指令模板的通用处理器约束随机指令生成方法［J］.计算机工程，2015，41（10）：309-313.

英文引用格式：Liu Jing，Wang Tiancheng，Wang Jian，et al.Constraint Random Instruction Generation Method for General Processor Based on Instruction Template［J］.Computer Engineering，2015，41（10）：309-313.

1000-3428（2015）10-0309-05

A

TP031.6

国家自然科学基金资助项目（61176040）。

刘 婧（1989-），女，硕士研究生，主研方向：集成电路验证；王天成，工程师、硕士；王 健，博上研究生；李华伟，研究员。

2014-09-03

2014-11-05E-mail：liujing@ict.ac.cn