论文部分内容阅读
形式化方法是计算机系统设计验证的一条有效途径。形式验证(formal verification)作为传统基于模拟的验证方法的补充，成为VLSI(Very Large Scale Integration)设计验证的一种非常有希望的方法，从而引起人们的日益关注。用传统的方法验证系统功能有三个缺点：一是很难对一些隐蔽错误进行定位；二是要耗费大量的仿真时间；三是测试覆盖率低。随着VLSI(Very Large Scale Integration)系统规模的增大，这些缺陷越来越令人无法容忍。
一般来说，形式验证方法可以分为等价性检验（equivalence checking）、模型检验(model checking)和定理证明(theorem proving)方法。
一、模型检验
将原始设计表示成有限状态机，将要验证的性质用时态逻辑描述。然后，遍历有限状态机以检验性质是否存在。有限状态机模型通常采用Kripke结构，在该结构上路径是无限延伸的。模型检验的优点是：全自动进行而无须人机交互。当断定某性质不满足时，模型检验能提供反例，以便于定位设计错误。凭借时态逻辑强大的描述能力，模型检验能够对各种复杂的时序性质进行验证。
状态空间爆炸问题是模型检验的主要缺点。
对模型检验问题的研究虽然取得了重大的进步，但现今仍然是具有挑战性的研究课题。迄今已提出很多新算法和改进算法，如偏序化简、组合推理、抽象、利用对称性、基于自动机(automata)的验证等。
二、定理证明
定理证明的原理是:首先定义一种数学逻辑,该逻辑系统实际上是一个形式化的系统,由一系列公理和推理规则组成。然后用这种数学逻辑分别表示被验证系统和其被期望的特性定理证明器的类型很多,既有高度自动化的通用系统,也有为专用目的设计的,具有交互功能的系统。自动化的定理证明系统可用作通用的搜索程序并且在许多领域取得了显著的成就;交互式的定理证明系统则更多地用于数学的系统和形式化处理以及形式方法的机械化。
与模型检验不同,定理证明可直接处理无限的状态空间。它使用类似于结构化的推导过程来证明具有无限状态的系统。另外值得指出的一点是,由于大多数定理证明器是交互的,在找到证明的过程中,用户的直觉往往起着决定性的作用,因此定理证明的速度相当慢而且容易出错。定理证明是形式验证技术中最先进的方法，但仍需进一步研究。
三、等价性检验
目前，模型检查与定理证明的方法还不成熟，而等价性检查已成IC设计流程的一部分。在三种形式验证方法中等价性检验用得最为广泛。
等价性检验的基本原理是依据数学的定理和公理，，用数学方法来验证参考设计与修正设计之间的等价性。利用等价性检验工具可对这两种设计方案进行彻底的检验以保证它们在所有可能的条件下都有一致的性能。还可以利用等价性检验来验证不同RTL或门级实施方案的等价性以及设计实现所利用的标准单元库的精确的描述来建立被比较的两个模型之间的关系。
上图给出了等价性验证的基本概念。等价性验证用于验证A与B是否等价。这里B是由A转换而成的。这里A与B可以是RTL代码，也可以是门级网表。在进行等价性验证时，A称为参考（reference）,B称为实现（implementation）。可以用形式验证来检查综合结果是否正确（RTL设计与门级网表比较）、插扫描链前后网表是否一致、布局前后网表是否一致、插时钟树前后网表是否一致、布线前后网表是否一致。
等价性检验程序自动确定被比较的两个设计的关系,而不需要用户的输入。因此它的优点是使用简单,且很容易集成到设计流程中。目前Cadence公司已经推出了等价性验证工具Affirma。它把建立被比较的两个设计之间的关系和等价性证明合并为一个步骤进行。
当等价性检验工具检测出两个设计之间在功能上的一个差别,它就显示一个反例,即一组原始输入或若干锁存器以及它们的引起这个差别的原始的信息。如果把模拟程序同等价性检验工具集成在一起,就可以利用这些信息进行模拟以便找出造成这种差别的原因。
需要说明的是，等价性验证仅能保证两个设计的一致性，不能保证设计本身的正确性。因此，在VLSI设计中，仿真仍是必不可少的步骤。
四、形式验证在工业界的应用状况
形式验证的验证过程是数学化的，而不是如模拟那样，是试验性质的。数学化的验证克服了模拟的不足，因为它的覆盖是完全的，并且可以减少验证时间，加快产品上市。形式化验证是可以对电路描述进行自动化的验证，减少了验证的复杂度。它用数学方法表达系统的规范或系统的性质,并且根据数学理论来证明所设计的系统满足系统的规范或具有所期望的性质,在不能证明所期望的性质时,则可能发现设计错误。克服了传统验证方法如模拟和测试的不足,实践证明形式验证确实通过形式规范和证明而增强了对系统的理解而发现了设计错误,或者通过形式化的自动验证发现了用其他方法不能发现的设计错误。
工业界对形式验证技术的应用大致通过两种形式：一是将形式验证技术集成到现有的模拟验证技术中；二是开发单独的形式验证工具。总的来看，近几年商业的形式验证软件增长迅速。与此同时，我们还看到，来自学术界的各种工具的出现更是令人目不暇接。我们相信，由于需求的带动，这种增长有持续发展的趋势。
参考文献：
[1]薛宏熙, 边计年,苏明.数字系统设计自动化.北京：清华大学出版社.1996.p260-302.
[2]韩俊刚,杜慧敏.数字硬件的形式化验证. 北京：北京大学出版社.2001. p1-25.
[3]邵明，李光辉，李晓维.模型检验中迁移关系的分组策略.计算机辅助设计与图形学学报. 2003. 15(9): p1101-1105.
一般来说，形式验证方法可以分为等价性检验（equivalence checking）、模型检验(model checking)和定理证明(theorem proving)方法。
一、模型检验
将原始设计表示成有限状态机，将要验证的性质用时态逻辑描述。然后，遍历有限状态机以检验性质是否存在。有限状态机模型通常采用Kripke结构，在该结构上路径是无限延伸的。模型检验的优点是：全自动进行而无须人机交互。当断定某性质不满足时，模型检验能提供反例，以便于定位设计错误。凭借时态逻辑强大的描述能力，模型检验能够对各种复杂的时序性质进行验证。
状态空间爆炸问题是模型检验的主要缺点。
对模型检验问题的研究虽然取得了重大的进步，但现今仍然是具有挑战性的研究课题。迄今已提出很多新算法和改进算法，如偏序化简、组合推理、抽象、利用对称性、基于自动机(automata)的验证等。
二、定理证明
定理证明的原理是:首先定义一种数学逻辑,该逻辑系统实际上是一个形式化的系统,由一系列公理和推理规则组成。然后用这种数学逻辑分别表示被验证系统和其被期望的特性定理证明器的类型很多,既有高度自动化的通用系统,也有为专用目的设计的,具有交互功能的系统。自动化的定理证明系统可用作通用的搜索程序并且在许多领域取得了显著的成就;交互式的定理证明系统则更多地用于数学的系统和形式化处理以及形式方法的机械化。
与模型检验不同,定理证明可直接处理无限的状态空间。它使用类似于结构化的推导过程来证明具有无限状态的系统。另外值得指出的一点是,由于大多数定理证明器是交互的,在找到证明的过程中,用户的直觉往往起着决定性的作用,因此定理证明的速度相当慢而且容易出错。定理证明是形式验证技术中最先进的方法，但仍需进一步研究。
三、等价性检验
目前，模型检查与定理证明的方法还不成熟，而等价性检查已成IC设计流程的一部分。在三种形式验证方法中等价性检验用得最为广泛。
等价性检验的基本原理是依据数学的定理和公理，，用数学方法来验证参考设计与修正设计之间的等价性。利用等价性检验工具可对这两种设计方案进行彻底的检验以保证它们在所有可能的条件下都有一致的性能。还可以利用等价性检验来验证不同RTL或门级实施方案的等价性以及设计实现所利用的标准单元库的精确的描述来建立被比较的两个模型之间的关系。
上图给出了等价性验证的基本概念。等价性验证用于验证A与B是否等价。这里B是由A转换而成的。这里A与B可以是RTL代码，也可以是门级网表。在进行等价性验证时，A称为参考（reference）,B称为实现（implementation）。可以用形式验证来检查综合结果是否正确（RTL设计与门级网表比较）、插扫描链前后网表是否一致、布局前后网表是否一致、插时钟树前后网表是否一致、布线前后网表是否一致。
等价性检验程序自动确定被比较的两个设计的关系,而不需要用户的输入。因此它的优点是使用简单,且很容易集成到设计流程中。目前Cadence公司已经推出了等价性验证工具Affirma。它把建立被比较的两个设计之间的关系和等价性证明合并为一个步骤进行。
当等价性检验工具检测出两个设计之间在功能上的一个差别,它就显示一个反例,即一组原始输入或若干锁存器以及它们的引起这个差别的原始的信息。如果把模拟程序同等价性检验工具集成在一起,就可以利用这些信息进行模拟以便找出造成这种差别的原因。
需要说明的是，等价性验证仅能保证两个设计的一致性，不能保证设计本身的正确性。因此，在VLSI设计中，仿真仍是必不可少的步骤。
四、形式验证在工业界的应用状况
形式验证的验证过程是数学化的，而不是如模拟那样，是试验性质的。数学化的验证克服了模拟的不足，因为它的覆盖是完全的，并且可以减少验证时间，加快产品上市。形式化验证是可以对电路描述进行自动化的验证，减少了验证的复杂度。它用数学方法表达系统的规范或系统的性质,并且根据数学理论来证明所设计的系统满足系统的规范或具有所期望的性质,在不能证明所期望的性质时,则可能发现设计错误。克服了传统验证方法如模拟和测试的不足,实践证明形式验证确实通过形式规范和证明而增强了对系统的理解而发现了设计错误,或者通过形式化的自动验证发现了用其他方法不能发现的设计错误。
工业界对形式验证技术的应用大致通过两种形式：一是将形式验证技术集成到现有的模拟验证技术中；二是开发单独的形式验证工具。总的来看，近几年商业的形式验证软件增长迅速。与此同时，我们还看到，来自学术界的各种工具的出现更是令人目不暇接。我们相信，由于需求的带动，这种增长有持续发展的趋势。
参考文献：
[1]薛宏熙, 边计年,苏明.数字系统设计自动化.北京：清华大学出版社.1996.p260-302.
[2]韩俊刚,杜慧敏.数字硬件的形式化验证. 北京：北京大学出版社.2001. p1-25.
[3]邵明，李光辉，李晓维.模型检验中迁移关系的分组策略.计算机辅助设计与图形学学报. 2003. 15(9): p1101-1105.