等价性验证在Soc设计中的应用

本文介绍了仿真验证与形式验证的功能,重点讨论了等价性验证在soc设计中的应用及基本流程,分析了等价性验证过程中常遇到的一些问题并给出了解决方案,实验显示,该验证方法可准确快速的发现设计的错误,提高验证效率。     

基于布尔可满足性的逻辑电路等价性验证方法

提出了基于布尔可满足性(Boolean Satisfiability,SAT)的逻辑电路等价性验证方法。这一验证方法把每个电路抽象成一个有穷自动机(FSM),为两个待验证的电路构造积机,把等价性验证问题转换成了积机的断言判定问题。改进了Tseitin变换方法,并将其用于把电路约束问题变换成(Conjunctive Normal Form,CNF)公式。之后则用先进的CNF SAT求解器zChaff判定积机所生成的布尔公式的可满足性。事例电路验证说明了该方法的有效性。     

基于改进型SAT求解器算法的组合电路等价性检查研究

随着工艺节点的缩小,集成电路规模的增加,集成电路设计过程中逻辑等价性检查在确保设计功能正确性方面起着重要作用。文章研究了组合电路逻辑等价性检查技术,针对该领域常用的DPLL和CDCL算法存在的问题,提出了一种基于蒙特卡洛树搜索的改进算法。通过对ISCAS85测试集的一个子集的实验,证实该算法对CDCL算法有一定的改进,应用于组合电路等价性检查的平均运行时间减少了20%。     

结合二叉判决图和布尔可满足性的等价性验证算法

本文提出了一种结合二叉判决图BDD和布尔可满足性SAT的新颖组合电路等价性验证技术.算法是在与/非图AIG中进行推理,并交替使用BDD扩展和基于电路SAT解算器简化电路.如尚未解决,将用基于合取范式SAT解算器进行推理.与已有算法相比主要有如下改进:在AIG中结合多种引擎进行简化,不存在误判可能;充分利用了基于电路解算器和基于合取范式解算器各自优点,减小了SAT推理的搜索空间.实验结果表明了本算法的有效性.     

Design for Test of Asynchronous NULL Convention Logic (NCL) Circuits

Due to the absence of a global clock and the presence of more state holding elements that synchronize the control and data paths, conventional Automatic Test Pattern Generation (ATPG) algorithms fail when applied to asynchronous circuits, leading to poor fault coverage. This paper presents a design for test (DFT) technique for a popular asynchronous design paradigm called NULL Convention Logic (NCL) aimed at making NCL designs testable using existing DFT tools with reasonable gate overhead. The proposed technique performs test points (TPs) insertion using Sandia Controllability and Observability Program (SCOAP) analysis to enhance the controllability of feedback nets and observability for fault sites that are flagged unobservable. An Automatic DFT Insertion Flow (ADIF) algorithm and a custom ATPG NCL primitive gates library are developed. The developed DFT technique has been verified on several NCL benchmark circuits

时序电路的形式化证明

对硬件的形式化验证是硬件验证的一个发展方向,形式化验证一个时序电路就是证明电路的实现是否满足他的规格描述.本文提出了用等式逻辑ε的一个公式Ws来表示电路的实现,用Tempura的程序B表示对该电路的特性描述.公式B（∈）P引入来证明电路的正确性,这里P是电路的初始状态,是从Ws中抽取的,另外还要从Ws提取输出等式.这样,一旦证明了B（∈）P,就能证明实现满足规格描述.最后,给出了一个例子来说明此证明方法.     

Why is Combinational ATPG Efficiently Solvable for Practical VLSI Circuits?

Empirical observation shows that practically encountered instances of combinational ATPG are efficiently solvable. However, it has been known for more than two decades that ATPG is an NP-complete problem (Ibarra and Sahni, IEEE Transactions on Computers, Vol. C-24, No. 3, pp. 242–249, March 1975). This work is one of the first attempts to reconcile these seemingly disparate results. We introduce the concept of cut-width of a circuit and characterize the complexity of ATPG in terms of this property. We introduce the class of log-bounded width circuits and prove that combinational ATPG is efficiently solvable on members of this class. The class of of log-bounded width circuits is shown to strictly subsume the class of k-bounded circuits introduced by Fujiwara (International Symposium on Fault-Tolerant Computing, June 1988, pp. 64–69). We provide empirical evidence which indicates that an interestingly large class of practical circuits is expected to have log-bounded width, which ensures efficient solution of ATPG on them.     

Application of Deterministic Logic BIST on Industrial Circuits

We present the application of a deterministic logic BIST scheme based on bit-flipping on state-of-the-art industrial circuits. Experimental results show that complete fault coverage can be achieved for industrial circuits up to 100 K gates with 10,000 test patterns, at a total area cost for BIST hardware of typically 5–15%. It is demonstrated that a trade-off is possible between test quality, test time, and silicon area. In contrast to BIST schemes based on test point insertion no modifications of the circuit under test are required, complete fault efficiency is guaranteed, and the impact on the design process is minimized.     

Modeling Custom Digital Circuits for Test

Models meant for logic verification and simulation are often used for Automatic Test Pattern Generation (ATPG). For custom digital circuits, these models contain many tristate devices that tend to lower coverage for stuck-faults. Additionally, these tristate devices contribute to increased ATPG runtimes, fewer generated test sequences, and an overall lower test quality. The circuit under test is partitioned into channel connected sub-networks (CCSN) that consist of transistors that are connected at their source or drain terminals, except when these terminals are power, ground or primary inputs. Unlike other published work, algorithms presented in this paper analyze each CCSN in the context of its environment, thereby capturing the logical relationships among its input signals. Other algorithms presented include identification and modeling of embedded latches, clock generators and memory circuits. An abstract array model for memory that reduces the size of the model and increases simulation speed is also presented. When one specific feature of the algorithm was disabled, experimental results showed higher ATPG runtimes of about 35%, and an average decrease in fault coverage of around 15–20%. For the largest data cache, the memory modeling algorithm decreased the number of primitives from 1.23 million to 139 thousand.     

一种用于密码协议形式化验证的简单逻辑

给出了一个可用于密码协议形式化验证与设计的简单逻辑.该逻辑采用抽象的通道概念表示具有多种安全特性的通信链路,可在比现有认证逻辑的更抽象的层次上对协议进行处理.     

基于新型量子逻辑门库的最优NCV三量子电路快速综合算法

许多量子电路综合算法由于指数级时间与空间复杂度,只能用可逆逻辑门综合3量子逻辑电路,仅有少数算法实现用量子非门,控制非门,控制V门与控制V⁺门(NCV)综合3量子逻辑电路,主要方法是将电路综合问题简化为四值逻辑综合问题.本文提出用NCV门构造新型量子逻辑门库,该库与NCV门库在综合最优3量子逻辑电路上等价,因此又可将四值逻辑综合问题进一步简化为更易求解的二值逻辑综合问题,使用基于完备Hash函数的3量子电路快速综合算法,快速生成全部最优的3量子逻辑电路,以最小代价综合电路的平均速度是目前最好结果Maslov 2007的近127倍.     

面向SoC系统芯片中跨时钟域设计的模型检验方法

 传统方法无法在RTL验证阶段全面验证SoC系统芯片中的跨时钟域设计.为解决此问题,本文首先提出描述亚稳态现象的等价电路实现,用以在RTL验证中准确体现亚稳态现象的实际影响;然后使用线性时序逻辑对跨时钟域设计进行设计规范的描述;为缓解模型检验的空间爆炸问题,进一步针对跨时钟域设计的特点提出基于输入信号的迁移关系分组策略和基于数学归纳的优化策略.实验结果表明本文提出的方法不仅可以在RTL验证阶段有效地发现跨时钟域设计的功能错误,而且可以使验证时间随实验用例中寄存器数量的递增趋势从近似指数级增长减小到近似多项式级增长.     

不确定型模糊Kripke结构的计算树逻辑模型检测

本文研究了不确定型模糊Kripke结构的计算树逻辑的模型检测问题,并说明了该问题可以在对数多形式时间内解决.首先给出了不确定型模糊Kripke结构的定义,引入了模糊计算树逻辑的语法和语义.为了刻画存在量词∃和任意量词∀在不确定型模糊Kripke结构中的两种语义解释,在模糊计算树逻辑语法中引入了路径量词∃_sup,∃_inf和∀_sup,∀_inf,分别用于替换存在量词∃和任意量词∀.其次讨论了基于不确定型模糊Kripke结构的计算树逻辑模型检测算法,特别地对于模糊计算树逻辑公式∃_suppUq,∀_suppUq,∃_infpUq和∀_infpUq分别给出时间复杂度为对数多项式时间的改进算法.     

基于重定时的高性能控制电路间接测试生成方法

对性能驱动控制逻辑进行测试生成难度较大,通常要加入可测性结构,但会影响原电路优化性能并增加生产成本.本文以重定时理论为基础,提出了对高性能时序电路进行间接测试生成的方法,这种方法在不影响原电路任何优化特性的前提下,可显著降低测试生成时间,提高测试生成质量.在ISCAS’89部分基准电路进行实验,结果证明了其有效性.     

一种推广化符号轨迹赋值中伪报错的改进算法

介绍了推广化符号轨迹赋值中常用的模型检验强可满足性算法,分析了产生伪报错的原因,提出了一种降低伪报错的改进算法.该算法在前算法的基础之上减少了边的计算量,降低了由于抽象带来的伪报错问题,从而大大提高了计算过程中的准确率.实验结果表明,该改进算法在降低伪报错和减少计算量方面有明显提高.     

G-vector: A New Model for Glitch Analysis in Logic Circuits

One of the major factors which contribute to the power consumption in CMOS combinational logic circuits is the switching activities in the circuits. Many of such switching activities are due to spurious pulses, called glitches. In this paper, we propose a new model for describing signals that contain glitches, called G-vector. Unlike the previous works in which their primary concern is modeling the propagation of glitches to count the number of glitches in the circuits, our G-vector provides a general, but effective model for generation, propagation and elimination of glitches, enabling us to not only count the number of glitches but also locate the glitches so that such information can be utilized by system tools for the reduction of the number of glitches in the circuits. We provide a set of experimental results to demonstrate the effectiveness of our model.     

A Current-Mode Logic for Low-Voltage, High-Speed Mixed-Mode VLSI Circuits

A wired-AND current-mode logic (WCML) circuit is designed for high performance mixed analog and digital system designs on a common silicon substrate, using standard CMOS process. Current is used for digital information carrier in order to be able to reduce supply voltage, power consumption, digital switching noise and to increase operating frequency. The WCML circuit uses current-steering technique. It is composed of a simple current mirror with a current injector. Wired-AND connections cause the logic circuit to operate as a NAND logic gate which provides to implement any boolean function. High-speed is achieved by varying the injection current level even at low-voltage supply (<1.5 V) with low-power consumption.     

四量子可逆逻辑电路快速综合算法

量子可逆逻辑电路综合是以较小量子代价自动构造所求量子可逆逻辑电路.本文提出了一种新颖高效的4量子电路综合算法,巧妙构造置换的最短编码,通过对量子电路进行特定拓扑变换,无损压缩n量子最优电路占用内存空间近2×n!倍,通过对已生成最优电路的双向级联,可使用多种量子门,采用最小长度标准,以极高效率生成较长的4量子电路,如率先生成基于控制非门、非门、Toffoli门库的全部前8层共3120218828个电路,还可快速综合任意长度不超过16的最优电路,并对4量子标准测试电路进行快速且全面的优化.     

有界Petri网等价性的判定算法

Petri网语言是系统行为分析的一种重要工具,为了分析有界Petri网的行为等价,借助于有限自动机的等价性问题和算法,研究了有界Petri网的等价性问题和算法.定义了带标注Petri网语言等价性,证明了带标注的有界Petri网到有限自动机的等价转化,给出了判定有界Petri网的等价性算法,为模拟系统的性能比较提供了处理方法.     

SIVA: A System for Coverage-Directed State Space Search

We introduce SImulation Verification with Augmentation (SIVA), a tool for coverage-directed state space search on digital hardware designs. SIVA tightly integrates simulation with symbolic techniques for efficient state space search. Specifically, the core algorithm uses a combination of ATPG and BDDs to generate directed input vectors, i.e., inputs which cover behavior not excited by simulation. We also present approaches to automatically generate lighthouses that guide the search towards hard-to-reach coverage goals. Experiments demonstrate that our approach is capable of achieving significantly greater coverage than either simulation or symbolic techniques in isolation.