公开(公告)号：US20170083650A1

公开(公告)日：2017-03-23

申请号：US15266455

申请日：2016-09-15

Applicant: Pranav Ashar

Inventor： Pranav Ashar ,  Ian Andrew Guyler ,  Sanjeev Mahajan

IPC: G06F17/50

CPC classification number: G06F17/5027

Abstract: Methods and systems are described to augment gate-level simulation with the ability to efficiently detect and correct X-pessimism on-the-fly. Using static Boolean analysis, gates are identified in the simulated hardware where there is potential for the simulator to propagate an X while the actual hardware propagates a 1 or 0, i.e. gates where X-pessimism potentially occurs. Data regarding potentially pessimistic gates is utilized in real time during simulation to determine actual pessimism at the gate and to correct it when it happens.Whereas the understanding of X-pessimism and the method of augmenting simulation with attributes to correct X-pessimism in simulation on-the-fly is known in the public domain preceding known patents, various methods have been proposed recently to make on-the-fly X-pessimism correction more efficient for large ICs. The methods and systems described in the present invention, achieve new levels of performance and scalability of X-pessimism detection and correction.

公开(公告)号：US07711525B2

公开(公告)日：2010-05-04

申请号：US10157486

申请日：2002-05-30

Applicant: Malay Ganai ,  Lintao Zhang ,  Aarti Gupta ,  Zijiang Yang ,  Pranav Ashar

Inventor： Malay Ganai ,  Lintao Zhang ,  Aarti Gupta ,  Zijiang Yang ,  Pranav Ashar

IPC: G06F17/10

CPC classification number: G06F17/504

Abstract: A method for bounded model checking of arbitrary Linear Time Logic temporal properties. The method comprises translating properties associated with temporal operators F(p), G(p), U(p, q) and X(p) into property checking schemas comprising Boolean satisfiability checks, wherein F represents an eventuality operator, G represents a globally operator, U represents an until operator and X represents a next-time operator. The overall property is checked in a customized manner by repeated invocations of the property checking schemas for F(p), G(p), U(p, q), X(p) operators and standard handling of atomic propositions and Boolean operators.

Abstract translation: 一种用于任意线性时间逻辑时间属性的有界模型检查的方法。 该方法包括将与时间运算符F（p），G（p），U（p，q）和X（p）相关联的属性转换成包括布尔可满足性检查的属性检查模式，其中F表示可能性运算符，G表示全局 运算符，U表示直到运算符，X表示下一运算符。 通过重复调用F（p），G（p），U（p，q），X（p）运算符的属性检查模式以及原子命题和布尔运算符的标准处理来检查整体属性。

公开(公告)号：US20060190864A1

公开(公告)日：2006-08-24

申请号：US11037920

申请日：2005-01-18

Applicant: Malay Ganai ,  Aarti Gupta ,  Pranav Ashar

Inventor： Malay Ganai ,  Aarti Gupta ,  Pranav Ashar

IPC: G06F17/50

CPC classification number: G11C29/54 ,  G06F17/504 ,  G11C2029/0401

Abstract: A computer-implemented method for augmenting SAT-based BMC to handle embedded memory designs without explicitly modeling memory bits. As is known, verifying designs having large embedded memories is typically handled by abstracting out (over-approximating) the memories. Such abstraction is not useful for finding real bugs. SAT-based BMC, as of now, is incapable of handling designs with explicit memory modeling due to enormously increased search space complexity. Advantageously, our method does not require analyzing the designs and also guarantees not to generate false negatives.

Abstract translation: 一种用于增加基于SAT的BMC来处理嵌入式存储器设计而不明确建模存储器位的计算机实现的方法。 众所周知，验证具有大嵌入存储器的设计通常通过抽象出（过近似）存储器来处理。 这样的抽象对于找到真实的错误是没有用的。 目前，基于SAT的BMC由于搜索空间复杂度的大幅增加，无法处理具有显式内存建模的设计。 有利的是，我们的方法不需要分析设计，也不保证不产生假阴性。

公开(公告)号：US20050149301A1

公开(公告)日：2005-07-07

申请号：US11053915

申请日：2005-02-10

Applicant: Aarti Gupta ,  Pranav Ashar ,  Sharad Malik

Inventor： Aarti Gupta ,  Pranav Ashar ,  Sharad Malik

IPC: G06F17/10 ,  G06F17/50

CPC classification number: G06F17/5031

Abstract: A method for derivation and abstraction of test models for validation of industrial designs using guided simulation is described. The method employs automatic abstractions for the test model which reduce its complexity while preserving the class of errors that can be detected by a transition tour. A method for design validation comprising generating a state-based test model of the design, abstracting said test model by retiming and latch removal; and applying validation technique on the abstracted test model. First, the number of internal (non-peripheral) latches in a design is minimized via retiming using a method of Maximal Peripheral Retiming (MPR). According to the MPR method, internal latches are retimed to the periphery of the circuit. Subsequently, all latches that can be retimed to the periphery are automatically abstracted in the test model. The validation technique may comprise of model checking, invariant checking or guided simulation using test sequences generated from the abstracted test model.

Abstract translation: 描述了使用引导模拟验证工业设计的测试模型的推导和抽象方法。 该方法对测试模型采用自动抽象，这降低了其复杂性，同时保留了过渡旅程可以检测到的错误类别。 一种用于设计验证的方法，包括生成设计的基于状态的测试模型，通过重新定时和锁定移除抽象所述测试模型; 并对抽象测试模型应用验证技术。 首先，使用最大外设重定时（MPR）的方法通过重新定时来最小化设计中的内部（非外围）锁存器的数量。 根据MPR方法，将内部锁存器重新定位到电路的周围。 随后，可以在测试模型中自动提取所有可重新定位到外围的锁存器。 验证技术可以包括模型检查，不变检查或使用从抽象测试模型生成的测试序列的引导模拟。

公开(公告)号：US06745160B1

公开(公告)日：2004-06-01

申请号：US09414815

申请日：1999-10-08

Applicant: Pranav Ashar ,  Anand Raghunathan ,  Subhrajit Bhattacharya ,  Aarti Gupta

Inventor： Pranav Ashar ,  Anand Raghunathan ,  Subhrajit Bhattacharya ,  Aarti Gupta

IPC: G06F1750

CPC classification number: G06F17/504

Abstract: A method of checking correctness of scheduling of a circuit where a schedule for the circuit is obtained from a behavioral description. The method comprising extracting loop invariants to determine a sufficient set of acyclic threads when loops are present, performing symbolic simulation to extract the above loop invariants, and proving equivalence of the acyclic threads. Systems, computer systems and computer program products that incorporate the techniques of verification and correctness checking according to the present invention have also been disclosed.

Abstract translation: 一种检查电路调度的正确性的方法，其中从行为描述获得电路的调度。 该方法包括提取循环不变量以在存在循环时确定足够的非循环线程集合，执行符号仿真以提取上述循环不变量，以及证明非循环线程的等价性。 还公开了结合根据本发明的验证和正确性检查技术的系统，计算机系统和计算机程序产品。

公开(公告)号：US06728665B1

公开(公告)日：2004-04-27

申请号：US09693979

申请日：2000-10-23

Applicant: Aarti Gupta ,  Zijiang Yang ,  Pranav Ashar

Inventor： Aarti Gupta ,  Zijiang Yang ,  Pranav Ashar

IPC: G06F710

CPC classification number: G06F17/504

Abstract: A method of performing image or pre-image computation for a system is disclosed. The method comprises representing the system by a finite state model; representing state sets using Binary Decision Diagrams (BDDs); performing a satisfiabilty checking (SAT) based backtrack search algorithm, wherein, the SAT decomposes the search over an entire solution space into multiple sub-problems, and wherein a BDD-based image computation is used to solve each sub-problem by enumerating multiple solutions from the solution space. Further, a method for pruning a search space in a SAT procedure is disclosed. The method comprises using BDD Bounding against an implicit disjunction or conjunction of a given set of BDDs; continuing search if a partial assignment of variables satisfies the implicit disjunction or conjunction, and backtracking if a partial assignment of variables does not satisfy the implicit disjunction or conjunction.

Abstract translation: 公开了一种用于系统执行图像或预图像计算的方法。 该方法包括通过有限状态模型表示系统; 使用二进制决策图（BDD）表示状态集; 执行基于可靠性检查（SAT）的回溯搜索算法，其中，SAT将整个解空间的搜索分解成多个子问题，并且其中使用基于BDD的图像计算来通过枚举多个解决方案来解决每个子问题 从解决方案空间。 此外，公开了一种在SAT过程中修剪搜索空间的方法。 该方法包括使用BDD边界抵抗一组给定的BDD的隐式分离或连接; 如果变量的部分分配满足隐式分离或连接，并且如果变量的部分分配不满足隐式分离或连接，则继续搜索。

公开(公告)号：US06662323B1

公开(公告)日：2003-12-09

申请号：US09425886

申请日：1999-10-25

Applicant: Pranav Ashar ,  Aarti Gupta

Inventor： Pranav Ashar ,  Aarti Gupta

IPC: G01R3128

CPC classification number: G01R31/31835 ,  G01R31/31707 ,  G01R31/318502

Abstract: A fast error diagnosis system and process for combinational verification is described. The system and process localizes error sites in a combinational circuit implementation that has been shown to be inequivalent to its specification. In the typical case, it is not possible to identify the error location exactly. The invention uses a diagnosis strategy of gradually increasing the level of detail in the analysis algorithm to ultimately derive a small list of potential error sites in a short time. The invention combines the use of simulation, Binary Decision Diagrams, and Boolean satisfiability in a novel way to achieve the goal. The previous approaches have been limited in that they have either been constrained to a specific error model unlike the present invention, or they are inefficient in comparison to the present invention. The present invention allows for the final set of error sites derived to be small, where that set contains the actual error sites, and is derived in a reasonable amount of time.

Abstract translation: 描述了用于组合验证的快速错误诊断系统和过程。 系统和过程将组合电路实现中的错误位置定位，这已被证明与其规范不符。 在典型情况下，不可能准确地识别错误位置。 本发明采用逐步提高分析算法细节水平的诊断策略，最终在短时间内得到潜在的误差点列表。 本发明以一种新颖的方式结合了仿真，二进制决策图和布尔可满足性的使用来实现目标。 以前的方法受到限制，因为它们已经被限制到与本发明不同的特定误差模型，或者它们与本发明相比是低效的。 本发明允许导出的最终的错误站点集合很小，其中该集合包含实际的错误站点，并且在合理的时间量内导出。

公开(公告)号：US06415430B1

公开(公告)日：2002-07-02

申请号：US09456506

申请日：1999-12-08

Applicant: Pranav Ashar ,  Peixin Zhong ,  Margaret Martonosi

Inventor： Pranav Ashar ,  Peixin Zhong ,  Margaret Martonosi

IPC: G06F1750

CPC classification number: G06F17/504 ,  G06F17/5054

Abstract: A method and apparatus for implementing communication between literals and clauses of a Boolean SAT problem through use of a time-multiplexed pipelined bus architecture rather than hardwiring it using on-FPGA routing resources. This technique allows the circuits for different instances of the Boolean SAT problem to be identical except for small local differences. Incremental synthesis and place-and-route effort required for each instance of the Boolean SAT problem becomes negligible compared to the time to actually solve the SAT problem. The time-multiplexing feature allows dynamic addition of clauses into the SAT solver algorithm. The pipeline architecture is highly pipelined with very few long wires and no wires crossing FPGA boundaries, thereby providing high clock speeds.

Abstract translation: 一种用于通过使用时间多路复用流水线总线架构而不是使用FPGA路由资源硬连线来实现文本和布尔SAT问题的子句之间的通信的方法和装置。 这种技术允许布尔SAT问题的不同实例的电路相同，除了小的局部差异。 与实际解决SAT问题的时间相比，布尔SAT问题的每个实例所需的增量合成和布局和布线工作变得可以忽略不计。 时间复用功能允许在SAT求解器算法中动态添加子句。 流水线架构具有很高的流水线配置，极少的长导线，没有电线穿过FPGA边界，从而提供高的时钟速度。

公开(公告)号：US06324673B1

公开(公告)日：2001-11-27

申请号：US09321591

申请日：1999-05-28

Applicant: Zhen Luo ,  Margaret Martonosi ,  Pranav Ashar

Inventor： Zhen Luo ,  Margaret Martonosi ,  Pranav Ashar

IPC: G06F1750

CPC classification number: G06F17/5081

Abstract: The method and apparatus for performing design rule checking on Manhattan structures in VLSI circuit layouts. The method and apparatus provides an edge-endpoint-based technique for checking the geometry and spacing of the VLSI circuit layout. The edge-endpoint-based technique uses a scanline algorithm that detects errors between adjacent structures that do not simultaneously intersect the scanline. The method also provides efficient error compilation. The apparatus allows for the design rules to be changed as the VLSI circuit layout evolves. The apparatus can process the VLSI circuit layout with a single processor, and the apparatus provides for multiple processors to process slices of the VLSI circuit layout, thereby enhancing the speed of the design rule checking over traditional software-only techniques.

Abstract translation: 在VLSI电路布局中对曼哈顿结构执行设计规则检查的方法和装置。 该方法和装置提供用于检查VLSI电路布局的几何形状和间距的基于边缘端点的技术。 基于边缘端点的技术使用扫描线算法来检测不同时与扫描线相交的相邻结构之间的错误。 该方法还提供了有效的错误编译。 该设备允许随着VLSI电路布局的发展而改变设计规则。 该设备可以使用单个处理器来处理VLSI电路布局，并且该设备提供多个处理器来处理VLSI电路布局的片段，从而提高设计规则检查传统的仅软件技术的速度。

公开(公告)号：US6163876A

公开(公告)日：2000-12-19

申请号：US187927

申请日：1998-11-06

Applicant: Pranav Ashar ,  Subhrajit Bhattacharya ,  Anand Raghunathan ,  Akira Mukaiyama

Inventor： Pranav Ashar ,  Subhrajit Bhattacharya ,  Anand Raghunathan ,  Akira Mukaiyama

IPC: G06F17/50

CPC classification number: G06F17/504

Abstract: A complete procedure for verifying register-transfer logic against its scheduled behavior in a high-level synthesis environment is provided. A new method that is both complete and practical for verification is provided. Hardware verification is known to be a hard problem and the proposed verification technique leverages off the fact that high-level synthesis--performed manually or by means of high-level synthesis software--proceeds from the algorithmic description of the design to structural RTL through a sequence of very well defined steps, each limited in its scope. Equivalence checking task is partitioned into two simpler subtasks, verifying the validity of register sharing, and verifying correct synthesis of the RYL interconnect and control. While state space traversal is unavoidable for verifying validity of the register sharing, irrelevant portions of the design are automatically abstracted out, significantly simplifying the task that must be performed by a back-end model checker.

Abstract translation: 提供了一种在高级合成环境中验证寄存器传输逻辑与其调度行为的完整过程。 提供了一种完整和实用的验证方法。 已知硬件验证是一个困难的问题，并且所提出的验证技术利用了手动或通过高级合成软件执行的高级合成 - 从设计的算法描述到结构化RTL的顺序 非常明确的步骤，每个都限于其范围。 等效检查任务分为两个简单的子任务，验证寄存器共享的有效性，验证RYL互连和控制的正确合成。 虽然状态空间遍历对于验证寄存器共享的有效性是不可避免的，但是设计的不相关部分被自动抽出，从而显着简化了后端模型检查器必须执行的任务。