基于多项式符号代数的数字电路形式验证方法研究

论文摘要

随着数字集成电路设计规模的增大和功能复杂性的提高,功能验证已经成为设计流程中的瓶颈。传统的模拟验证方法无法满足现时复杂集成电路设计带来的巨大的验证需求。形式验证技术,例如模型检验和等价验证,因此发展成为模拟验证方法的一种重要补充,正日益受到学术界的关注。现有的形式验证技术大多基于传统的位级方法,例如BDD或布尔SAT,它们主要针对低层次门级电路和以控制流为主的电路的验证,难以胜任以数据流为主的高层次复杂电路设计的验证。作为一种新近提出的电路表示和计算方法,多项式符号代数能够克服BDD和布尔SAT方法的某些不足。本文深入研究了多项式符号代数方法在数字电路形式验证中的应用,取得了如下创新性成果：(1)提出了基于多项式符号代数的模型检验方法。首先,扩展了传统的Kripke结构的概念,得到了所谓状态转换系统的新概念。用该状态转换系统代替传统的Kripke结构来抽象高层次设计中的控制逻辑,并统一用多项式方法描述高层次设计中的数据通路和控制逻辑,从而有效地避免了数据域和控制域之间频繁的约束传播和回溯操作。进而,给出了一个高层次设计模型检验的方法框架。在该方法框架之下,原有的模型检验问题被转化为一个假设和结论均具有多项式形式的一阶逻辑定理证明问题,一个基于多项式符号计算的判定过程被用来有效地解决该定理证明问题。针对典型高层次设计的实验结果表明,与现有的基于非线性求解器的高层次模型检验方法相比,该方法在保证验证准确性的情况下,平均要快1到5倍。(2)提出了基于多项式符号代数的等价验证方法。该方法直接在高层次建模数据通路设计,给出了高层次数据通路的多项式集合表示的一般形式及构造方法。由于避免了将高层次数据通路设计展开为门级网表,对于同样的验证问题,该方法涉及的信号变量的数目和约束表达式的数目要比基于BDD和布尔SAT的等价验证方法少得多。进而,从多项式集合公共零点的角度定义了高层次数据通路的功能等价性,并给出了一个基于多项式符号计算的有效的代数求解算法。针对高层次基准数据通路的实验结果表明,与现有的基于*BMD和整数线性规划的高层次等价验证方法相比,该方法在保证错误诊断能力的情况下,平均要快1倍到1个数量级。(3)提出了基于多项式符号代数的层次化验证方法。首先,引入了一种基于广义表数据结构的层次化电路表示模型。基于此种层次化表示,并应用多项式代数中的消元定理和扩张定理,得到了一种层次化的电路功能计算方法。该方法将原本规模较大的计算问题划分为一些小的计算问题,并以一种逐层递归的方式完成原有计算,从而有效地提高了计算效率。进而,将这种新的电路功能计算方法用于设计验证,实现了层次化的模型检验和等价验证算法。实验结果表明,采用层次化策略能够有效地提高原有模型检验和等价验证算法的验证效率。就本文的实验电路而言,模型检验算法的效率平均提高了23%,等价验证算法的效率平均提高了17%。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景意义
• 1.2 本文主要工作
• 1.3 论文的结构
• 第2章 数字电路形式验证综述
• 2.1 形式验证应用的数学方法
• 2.1.1 正则判决图方法
• 2.1.2 代数方法
• 2.2 形式验证技术
• 2.2.1 模型检验
• 2.2.2 等价验证
• 2.3 本章小结
• 第3章 基于多项式符号代数的模型检验方法
• 3.1 引言
• 3.2 思想来源
• 3.3 高层次设计的多项式建模
• 3.3.1 数据通路建模
• 3.3.2 控制逻辑建模
• 3.4 性质描述
• 3.5 高层次设计模型检验的多项式符号代数方法
• 3.5.1 时序设计的展开
• 3.5.2 从待验证性质的前件产生多项式等式集合
• 3.5.3 从待验证性质的后件产生多项式等式集合
• 3.5.4 应用多项式符号代数方法求解定理证明问题
• 3.5.5 验证示例
• 3.6 实验结果及其分析
• 3.7 本章小结
• 第4章 基于多项式符号代数的等价验证方法
• 4.1 引言
• 4.2 问题的提出
• 4.3 高层次数据通路的多项式集合表示
• 4.3.1 高层次数据通路的相关定义
• 4.3.2 多项式集合表示的一般形式
• 4.4 高层次数据通路等价验证的多项式符号代数方法
• 4.4.1 思想来源
• 4.4.2 从代数几何的角度定义数据通路的功能等价
• 4.4.3 等价问题的求解
• 4.4.4 验证示例
• 4.5 实验结果及其分析
• 4.6 本章小结
• 第5章 基于多项式符号代数的层次化验证方法
• 5.1 引言
• 5.2 数字电路的层次化表示
• 5.2.1 电路广义表
• 5.2.2 信号数值编码
• 5.2.3 电路模块功能计算
• 5.2.4 计算示例
• 5.3 层次化的形式验证方法
• 5.3.1 层次化的模型检验算法
• 5.3.2 层次化的等价验证算法
• 5.4 实验结果及其分析
• 5.5 本章小结
• 结论
• 参考文献
• 攻读博士学位期间发表的论文和取得的科研成果
• 致谢