专利名称:基于边界条件和自检查随机测试的cpu约束生成验证法的制作方法
技术领域:
本发明属于计算机自动验证技术领域,特别涉及计算机微处理器随机验证方法。
背景技术:
随着微处理器的功能越来越强大、结构也越来越复杂,从而导致了微处理器系统结构的研制与开发成为一个十分复杂过程,要求在系统结构设计的早期阶段,能够对其功能和结果作严格的测试与验证。
微处理器的验证方法通常分成两大类形式化方法和基于模拟的方法。形式化方法主要是通过数学抽象,利用数学方法上的状态机变迁进行功能模拟与验证,在理论上证明系统的正确性,以100%的精度保证系统的正确性。由于当代CPU广泛采用了高复杂性指令集、多级流水线、分支预测等技术,这使得形式化方法在实践上变得越来越不可行,因此通常情况下,形式化方法仅仅应用于那些具有简单结构的CPU验证。
基于模拟的CPU验证方法则是通过让系统执行大量的模拟验证程序来验证系统的正确性,为了保证验证的可靠性和覆盖率,要求验证系统具有较高的有效性。基于模拟的CPU验证方法有两种穷举法和随机法。穷举法CPU验证一般应用在8位和16位处理器等简单的处理器上。对32位及32位以上的处理器,由于处理器状态空间的增大,使得穷举法CPU验证无法实现。随机法CPU验证就是利用自动生成的随机测试程序进行测试,典型的应用就是随机测试程序生成器。随机法的应用很大程度上取决于随机测试程序的质量,具有良好分布的随机测试程序能取得比较好的测试效果。
在随机法CPU验证中有两种具体的实现方式“生成—验证”的方法和“约束—验证”的方法。“生成—验证”的方法就是先随机生成一条指令(随机选择指令,随机选择指令的操作数),然后,验证这条指令是不是合法的指令。“约束—验证”的方法是一种基于约束满足问题提出的随机测试程序生成算法。这两种方法都存在一些不足的地方,“生成—验证”的方法产生测试程序的速度快,但生成的测试程序质量不高。而“约束—验证”的方法产生的测试程序质量有一定提高,但测试程序的产生过程速度非常低,测试程序生成器的构建很复杂,不适合快速的处理器验证需求。为此我们提出了“约束生成验证”的方法,使得测试程序的生成速度与“生成—验证”方法接近,产生与“约束—验证”方法同等质量的测试程序。并且,测试程序生成器的构建非常容易,适合体系结构独立的测试平台的快速构建。
在CPU验证的过程中,会用到手写测试程序、应用程序和随机测试程序。手写测试程序是测试者根据设计规格以及测试过程中的一些测试要求,手工编写的一些测试程序。这些程序量不是很大。手写测试程序是处理器验证过程中非常重要的测试程序,是测试者测试经验的积累。应用程序是利用现有的应用程序作为测试程序,这些测试程序量大,但都是高级语言编写,在编译成目标代码的过程中,受编译器的影响,只能生成一个固定模式的指令序列,很难满足测试的需求。随机测试程序由于采用随机测试程序生成器自动生成,产生大量的测试程序,并且是直接生成汇编代码,不受编译器的限制,是CPU验证后期采用的非常重要的测试手段。随机测试程序的随机性,帮助测试者发现一些手写测试程序无法测试到的错误。但是随机测试程序的随机性,也使得测试的效率不高。实际上,在验证过程中,大量的错误是发生在边界部分,而在随机生成中,产生边界测试代码的机会非常少。基于这种考虑,我们发明了基于边界条件的随机测试程序生成。并且,构建了测试程序库,把手写测试程序作为测试程序片断加入到这个库中,使得测试经验得以保留。
在自动验证过程中,同一个测试程序输入到标准参考模型的C模拟器和寄存器转换级RTL(Register Transfer Level)模拟器中,C模拟器和RTL模拟器打印每一个周期的处理器状态,最后比较两个模拟器的处理器状态。这个自动验证过程是普遍采用的,在发现设计错误,进行了设计修改后,为了保证设计修改造成的错误不扩散,还需要对原有的测试程序重新测试。这是个耗时的过程,特别是在测试的后期,已经运行过很多测试程序,每一次的修改,都会造成很大的重新测试的时间消耗。针对这个问题,我们发明了自检查的测试程序生成方法,并利用自检查的测试程序构建了重新验证过程。
本项发明针对上述的问题,提出了一个基于边界条件和自检查随机测试的CPU约束生成验证方法。
发明内容
本发明的目的在于通过自动生成高质量的测试代码,利用随机测试程序的生成算法构建一个处理器的自动验证平台,使得处理器的验证过程能够自动进行,进而缩短处理器的验证时间。通过生成基于边界条件和自检查随机测试的CPU约束生成验证测试程序,使得该平台能够生成满足不同测试需求的测试程序,通过这些测试程序,进行自动验证以及设计修改后的重复验证,从而大大缩短验证的时间。
其主要创新点如下(1).提出了“约束生成验证”的随机测试程序生成算法,快速的生产高质量的随机测试程序。
(2).提出了基于边界条件的随机测试程序生成算法,更快速的发现设计错误。
(3).提出了自检查的随机测试程序生成算法和重新验证过程,加快了验证进度。
本发明所述算法的特征在于它是在微处理器中依次按以下步骤实现的第1步向微机中输入下述指令集所述指令集是由所有指令树组成的指令数组,而指令树是根据每条指令的语法拼成的,其中每一条指令含有
指令类型,表示该指令所属的部件类型;操作数数目,表示该指令的操作数数目;操作数表,它由该指令的操作数组成;每个操作数含有操作数类型域、操作数范围、操作数当前值、边界条件值列表及边界条件值的概率;其中,操作数类型有寄存器类型、立即数类型、存储器地址类型;指令格式,它是汇编指令的语法表示;指令编码,表示该指令的机器码编码方式;指令约束,表示该指令的约束条件;存储器地址方位表,表示该指令所操作的存储器范围;异常表,表示该指令有关的异常源的开启和关闭;指令计数,表示对所生成指令计数;第2步生成随机测试程序,它依次含有以下步骤第2.1步生成随机测试程序的初始化段第2.1.1步读取指令集中的约束条件,改变指令的约束,读取检查点的间隔,即自检粒度,它用指令条数来表示,检查点即程序中检查处理器状态的位置;第2.1.2步判断是否需要边界测试若需要边界测试,则改变指令约束为边界条件约束;否则,转入第2.1.3步;第2.1.3步初始化微处理器中的寄存器和存储器,形成随机测试程序的初始化段;第2.2步生成随机测试程序的程序段;第2.2.1步随机选择一条指令以及指令操作数;第2.2.2步对指令进行约束验证第2.2.2.1步在各指令的操作数的边界值表中加入相应的边界值以及生成该边界值的概率;第2.2.2.2步根据该边界值的概率,在该操作数的边界条件值表和操作数范围内随机选择一个操作数,生成一条指定概率的边界值指令;第2.2.2.3步在标准参考模型C模拟器中运行上述生成的边界值指令,根据运行结构判断若生成的指令是有效的,则转入第2.2.3步;否则转入第2.2.1步;第2.2.3步对第2.2.2步形成的基于边界条件的随机测试指令,自动生成自检查随机测试程序第2.2.3.1步在不同的测试阶段并根据不同的测试目的,设定下述自检查代码插入检查点位置;第2.2.3.2步记录各检查点的处理器的当前状态,即寄存器状态和存储器状态,对于下一个检查点来说,当前记录的这个状态称为历史状态;第2.2.3.3步记录各检查点在指令集中的当前位置,从中选取确定一个检查点,根据用户的要求,判断比较的方式若用户只要求比较发生变化的寄存器或存储器,则找出当前检查点与上一个检查点发生变化的寄存器或存储器,把变化的寄存器或存储器作为自检查的对象;否则,把当前的处理器状态,即寄存器和存储器状态,作为比较的对象,记录当前检查点的处理器状态;第2.2.3.4步生成自检代码取出当前处理器状态的值,即需要进行自检查的寄存器和存储器当前状态值,将这些值与在标准参考模型C模拟器运行到同一点得出的值进行比较,判断值是否相等;若相等,则转第2.2.4步;否则增加跳转指令,跳转的地址由用户指定,转到第2.2.4步;第2.2.4步判断是否达到最大指令数;若已经达到,则转第2.3步;否则,转第2.2.1步;第2.3步生成随机测试程序的结束段第2.3.1步生成随机测试程序的结束代码,包含顺序指令,它是当程序段中的一些转移指令,其跳转目标地址超过程序段的最后一条指令时,预先避免程序进入一个不确定的状态时而提出的;第2.3.2步若在生成过程中增加了自检查指令,则生成标志检查成功或者失败的代码;第3步将上述生成的测试程序写入文件中,该文件称为测试文件;第4步在RTL模拟器中验证微处理器的功能和实现第4.1步从测试文件取出一条指令;第4.2步把该条指令在RTL模拟器上运行,判断该指令是否是自检查指令若是自检查指令,将得到的处理器当前状态值和记录在测试程序中运行到该点的处理器状态值进行比较;第4.3步将测试验证结果记录;第4.4步判断测试程序是否结束若测试程序结束,则验证过程结束;否则,转第4.1步。
本发明提出了基于边界条件和自检查随机测试的CPU约束生成验证方法,还提出了适合于上述算法的指令集表示方法、循环测试程序的生成方法和测试程序库的构造方法。这个约束生成验证法具有体系结构独立的特点,能够很容易构建针对新的处理器体系结构的验证平台。新的算法和方法的应用,使得验证速度和验证质量都有很大提高。也使得利用上述方法建立的随机验证平台能够作为贯串处理器验证始终的一个工具,使测试经验得以保留。
图1“约束生成验证”法测试程序生成流程图;图2自检查程序的验证逻辑实现框图;图3一个具有自检功能的测试程序示例。
具体实施例方式
基于边界条件和自检查随机测试的CPU约束生成验证法的具体实施模式是这样的随机测试环境中包含两个模型体系结构模型和RTL模型。体系结构模型是期望的处理器模型,它采用C模拟器实现,是作为标准参考模型存在的。RTL模型是将要进行测试和验证的模型,随机测试及验证的目的是测试RTL模型是否与体系结构模型一致。
RTL模型和体系结构模型都能输出在每一个时钟周期的处理器状态,比较两个模型的处理器状态,就能判断两个模型是否一致。如果不一致,说明RTL模型出现了错误。随机测试的目标是达到RTL模型和体系结构模型的完全一致。
基于边界条件和自检查随机测试的CPU约束生成验证法的测试程序生成流程图如图1所示,基于边界条件和自检查随机测试的CPU约束生成验证法的验证逻辑框图如图2所示,具体的实施方式说明如下(1)在向微机中输入指令集时,指令集如下表示指令集的表示方法是本发明所述算法的基础,本表示方法的特点在于动态的改变指令的约束条件和加入操作数的边界值。
生成程序根据指令集的语法描述,生成合法的汇编指令语句。这种方法是根据指令的语法生成指令序列的,生成效率高,也很容易根据测试的要求,给生成算法加上不同的约束,从而产生需要的测试程序。
保证测试程序的合法性是测试程序的基础,由于随机测试程序是由汇编指令组成的指令序列,而微处理器的体系结构由指令集和相关的资源组成。指令集的每一条指令都具有特定的功能,并使用或者改变系统的资源。系统的资源包括寄存器堆、内存的分配、机器状态字、异常或中断等等。处理器的资源状况就成为了处理器状态。在处理器运行的每一周期都有不同的处理器状态。随机测试程序的生成过程就是随机选择指令,然后根据当前处理器状态,合法地随机地选择指令的操作数的过程。
(2)生成随机测试程序时,测试程序的结构如下本发明所产生的随机测试程序分为三段初始化段、程序段、结束段。初始化段主要是处理器资源的初始化代码,如寄存器的初始化代码、存储器的初始化代码。目的是在CPU软件模型和RTL模型中得到一个一致的处理器初始状态。
程序段是真正的测试程序代码,它是由汇编指令组成。从程序流的角度分析,汇编指令分为四种类型单入口单出口指令、单入口多出口指令、多入口单出口指令和多入口多出口指令。汇编指令又可分为顺序指令和转移指令。顺序指令只有一个出口,几个入口。转移指令又可分为条件转移指令和无条件转移指令,其中条件转移指令有两个出口,无条件转移指令有一个出口。为了简单起见,把无条件转移指令也看作条件永远成立的条件转移指令,也有两个出口,只是其中一个出口永远不会用到。经过以上分析,得出顺序指令是只有一个出口的指令(单入口单出口、多入口单出口),而转移指令是有多个出口的指令(单入口多出口、多入口多出口)。
结束段是测试程序的结束代码,主要起保护作用。在自检查随机测试程序中,结束段还具有测试结果指示作用。在程序段中,会存在一些转移指令,如果转移指令的跳转目标地址超过程序段的最后一条指令,就会使程序进入一个不确定的状态。在结束段中放入一些顺序指令(如空指令NOP),起到保护作用。在自检查的测试程序中,结束段中放置检查成功或者失败的标志代码,指示检查的结果。
(3)“约束生成验证”算法在体系结构模型中已经加入了每条指令的约束,这种约束是指令的默认约束。在生成随机测试程序时,用户的请求是通过用户界面(图形界面或命令行)输入的,输入的用户请求作为全局的约束加到所有的指令约束上,就形成了生成器的初始约束。在生成过程中,根据用户对不同种类指令的需求,随机选择合适的指令,然后根据指令的约束随机生成指令的操作数,产生的指令经过约束验证器检验其是否满足约束条件,如果不满足就放弃。随机生成算法的核心是指令的随机生成和指令有效性判断,处理器状态是随着指令的产生而随时更新的。
约束生成验证算法的逻辑步骤如下第一步,初始化处理器状态。
第二步,根据测试要求动态改变指令的约束条件。
第三步,随机选择一条指令以及指令的操作数。
第四步,对指令进行约束验证。包括判断该指令是否所要求的指令、指令是否符合语法要求、跳转地址是否有效地址、是否满足对异常处理的要求、地址操作是否在限定的地址范围等等。
第五步,若有效,按指令格式对该指令编码,写入文件。再根据处理器的程序指针的状态,决定是否模拟运行该指令,从而更新处理器状态。若程序指针大于当前的指令数,则不模拟该指令。若该指令无效,则重新生成操作数或放弃该指令。
第六步,若生成的指令数满足最大指令数的要求,则反汇编生成文件,完成生成过程。否则,返回第二步,继续上述过程。
在上述生成过程中,需要对生成的指令进行编码,以方便存储,也便于利用已存在的模拟器进行处理器状态的更新。在指令生成过程中,会存在循环的情况,对生成的指令进行编码存储也便于循环的执行。在随机生成过程中,需要模拟器的支持,模拟器的执行过程是根据程序指针的方向进行的,即只有程序指针所指的指令需要执行,从而更新处理器的状态。
(4)基于边界条件随机测试的CPU约束生成验证程序生成算法在测试程序的生成中,根据用户的要求,生成边界条件的测试程序。类似于手写的测试程序。这个过程是建立在边界条件库的基础上的,对于不同的指令集,以及指令集中不同的指令,它们的边界条件是不同的。
例如,对于一个立即数,边界条件是0,0x7FFFFFFF,0x80000000,0xFFFFFFFF,0x55555555,0xAAAAAAAA等。0x55555555和0xAAAAAAAA作为边界条件是为了测试在0x55555555和0xAAAAAAAA相加时,加法器的每一位都会有一个跳变,从而有更高的测试覆盖率。
在指令集表示中,在指令的操作数的边界值表中加入边界值以及生成边界条件的概率,在生成指令时,根据边界值的概率,会在这个操作数的边界值表和操作数值域内随机选择一个操作数,就能生成指定概率的边界值指令。
(5)基于自检查的随机测试程序生成算法和重新验证过程自检查的测试程序是指测试程序自身具有检测处理器行为正确性的能力。自检程序的应用主要用在1)单元测试(如算术逻辑运算单元、存储器读写);2)在已经验证通过的测试程序结束段的前面加入自检代码,形成自检程序,用于重新验证。基于边界条件和自检查随机测试的CPU约束生成验证法的具体实施模式是这样的随机测试环境中包含两个模型体系结构模型和RTL模型。体系结构模型是期望的处理器模型,采用C模拟器实现,是作为标准参考模型存在的。RTL模型是将要进行测试和验证的模型,随机测试及验证的目的是测试RTL模型是否与体系结构模型一致。RTL模型和体系结构模型都能输出在每一个时钟周期的处理器状态,比较两个模型的处理器状态,就能判断两个模型是否一致。如果不一致,说明RTL模型出现了错误。随机测试的目标是达到RTL模型和体系结构模型的完全一致。
对于具有自检功能的测试程序,在测试程序生成过程中,插入自检查代码,自检查代码是比较当前检查点和前一个检查点机器状态的寄存器和存储器的内容是否一致。这里的当前处理器的状态是根据标准参考模型得出的。因为体系结构模型的行为已经通过在C模拟器运行而反映在测试程序中,这种比较是在测试程序中实现的,并在RTL模拟器上运行完成的。在验证时,测试程序只需在RTL模拟器上运行即可,不需要在参考模型上运行并比较,使用自检程序进行测试由于减少了与体系结构模型执行结果的比较过程,大大缩短验证的时间,把已经通过验证的程序加上自检代码段保存下来,能用于处理器的重新验证。图2是自检查程序的验证逻辑实现框图。其中,RTL模拟器运行结果和C模拟器运行结果比较示例参见附图3。
自检查测试程序是在程序中插入比较代码,这些比较代码的比较对象是在测试程序生成中根据体系结构模型的模拟器状态得出的。如果检查失败,记录当前的位置,然后跳转到测试程序的结束段,退出。通过记录的失败位置查找检查失败的原因。
例如在RTL模型中,测试验证寄存器R3是否运行正确,设将寄存器R1和R2的值相加,两个寄存器的值分别为3和4,然后将结果赋值给寄存器R3,并且在第三条指令后设置检查点,则由于通过在标准参考模型的C模拟器中运行至该点的结果可以知道,此时R3的值应该为7,因此,当前运行在RTL模拟器的寄存器R3的值也应为7,由此可得到两条自检查代码如下比较R3寄存器的值是否等于7;如果不相等,则转向结束代码段。上述例子的程序片断如图3所示。其中,指令4和指令5是自检代码。
自检代码在测试程序的任何位置插入。自检代码插入位置的间隔称为自检粒度。自检粒度大,则测试程序的随机性好,但是错误的定位不准确,还需要进一步确定错误的位置。自检粒度小,则影响了测试程序的随机性,但错误的定位准确。粒度的大小根据测试目的的不同而调整。比如,在测试的初期,要测试算术逻辑运算(ALU)单元,就采用小粒度的自检程序。在测试的后期,采用粒度大的自检程序。
自检程序的生成过程是这样的,首先确定一个检查点,比较这个检查点的处理器状态与上一个检查点的处理器状态的差异(如寄存器的变化、存储器的变化等)。把变化的地方作为比较的对象,生成自检代码;或者把当前的整个处理器状态作为比较的对象(如所有寄存器);然后插入用于自检查的比较代码,并记录当前检查点的处理器状态。最后在结束段,安排测试成功和失败的退出代码。
在自动验证过程中,如果发现验证错误,需要对设计进行修改,修改后需要对设计进行重新验证。特别是在验证的后期,一次设计的修改,就要运行以前所有的测试程序,以验证本次的设计修改是否会引入新的错误。针对此,我们引入了基于自检查测试程序验证过程。验证过程通过使用自检查的测试程序,加快重新验证的时间。因为自检查的测试程序不需要在体系结构模拟器上运行,节省了体系结构模拟器的运行时间以及Trace文件的比较时间,大大加快了验证的进度。
权利要求
1.基于边界条件和自检查随机测试的CPU约束生成验证法,其特征在于,它是在微处理器中依次按以下步骤实现的第1步向微机中输入下述指令集所述指令集是由所有指令树组成的指令数组,而指令树是根据每条指令的语法拼成的,其中每一条指令含有指令类型,表示该指令所属的部件类型;操作数数目,表示该指令的操作数数目;操作数表,它由该指令的操作数组成;每个操作数含有操作数类型域、操作数范围、操作数当前值、边界条件值列表及边界条件值的概率;其中,操作数类型有寄存器类型、立即数类型、存储器地址类型;指令格式,它是汇编指令的语法表示;指令编码,表示该指令的机器码编码方式;指令约束,表示该指令的约束条件;存储器地址方位表,表示该指令所操作的存储器范围;异常表,表示该指令有关的异常源的开启和关闭;指令计数,表示对所生成指令计数;第2步生成随机测试程序,它依次含有以下步骤第2.1步生成随机测试程序的初始化段第2.1.1步读取指令集中的约束条件,改变指令的约束,读取检查点的间隔,即自检粒度,它用指令条数来表示,检查点即程序中检查处理器状态的位置;第2.1.2步判断是否需要边界测试若需要边界测试,则改变指令约束为边界条件约束;否则,转入第2.1.3步;第2.1.3步初始化微处理器中的寄存器和存储器,形成随机测试程序的初始化段;第2.2步生成随机测试程序的程序段;第2.2.1步随机选择一条指令以及指令操作数;第2.2.2步对指令进行约束验证第2.2.2.1步在各指令的操作数的边界值表中加入相应的边界值以及生成该边界值的概率;第2.2.2.2步根据该边界值的概率,在该操作数的边界条件值表和操作数范围内随机选择一个操作数,生成一条指定概率的边界值指令;第2.2.2.3步在标准参考模型C模拟器中运行上述生成的边界值指令,根据运行结构判断若生成的指令是有效的,则转入第2.2.3步;否则转入第2.2.1步;第2.2.3步对第2.2.2步形成的基于边界条件的随机测试指令,自动生成自检查随机测试程序第2.2.3.1步在不同的测试阶段并根据不同的测试目的,设定下述自检查代码插入检查点位置;第2.2.3.2步记录各检查点的处理器的当前状态,即寄存器状态和存储器状态,对于下一个检查点来说,当前记录的这个状态称为历史状态;第2.2.3.3步记录各检查点在指令集中的当前位置,从中选取确定一个检查点,根据用户的要求,判断比较的方式若用户只要求比较发生变化的寄存器或存储器,则找出当前检查点与上一个检查点发生变化的寄存器或存储器,把变化的寄存器或存储器作为自检查的对象;否则,把当前的处理器状态,即寄存器和存储器状态,作为比较的对象,记录当前检查点的处理器状态;第2.2.3.4步生成自检代码取出当前处理器状态的值,即需要进行自检查的寄存器和存储器当前状态值,将这些值与在标准参考模型C模拟器运行到同一点得出的值进行比较,判断值是否相等;若相等,则转第2.2.4步;否则增加跳转指令,跳转的地址由用户指定,转到第2.2.4步;第2.2.4步判断是否达到最大指令数;若已经达到,则转第2.3步;否则,转第2.2.1步;第2.3步生成随机测试程序的结束段第2.3.1步生成随机测试程序的结束代码,包含顺序指令,它是当程序段中的一些转移指令,其跳转目标地址超过程序段的最后一条指令时,预先避免程序进入一个不确定的状态时而提出的;第2.3.2步若在生成过程中增加了自检查指令,则生成标志检查成功或者失败的代码;第3步将上述生成的测试程序写入文件中,该文件称为测试文件;第4步在RTL模拟器中验证微处理器的功能和实现第4.1步从测试文件取出一条指令;第4.2步把该条指令在RTL模拟器上运行,判断该指令是否是自检查指令若是自检查指令,将得到的处理器当前状态值和记录在测试程序中运行到该点的处理器状态值进行比较;第4.3步将测试验证结果记录;第4.4步判断测试程序是否结束若测试程序结束,则验证过程结束;否则,转第4.1步。
全文摘要
本发明涉及属于计算机自动验证技术领域的基于边界条件和自检查随机测试的CPU约束生成验证法。其具体实施模式是随机测试环境中分别包含体系结构模型和RTL模型。体系结构模型是期望的处理器模型,它采用C模拟器实现,是作为标准参考模型存在的。RTL模型是将要进行测试和验证的模型,随机测试及验证的目的是测试RTL模型是否与体系结构模型一致。RTL模型和体系结构模型都能输出在每一个时钟周期的处理器状态,比较两个模型的处理器状态,就能判断两个模型是否一致。本发明具有体系结构独立的特点,能够很容易构建针对新的处理器体系结构的验证平台,使得验证速度和验证质量都有很大提高,也使建立的随机验证平台能作为贯串处理器验证始终的一个工具。
文档编号G06F11/36GK1684047SQ20041010182
公开日2005年10月19日 申请日期2004年12月24日 优先权日2004年12月24日
发明者姚文斌, 张悠慧, 王惊雷 申请人:清华大学