公开(公告)号：US06745160B1

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

申请号：US09414815

申请日：1999-10-08

申请人： Pranav Ashar ,  Anand Raghunathan ,  Subhrajit Bhattacharya ,  Aarti Gupta

发明人： Pranav Ashar ,  Anand Raghunathan ,  Subhrajit Bhattacharya ,  Aarti Gupta

IPC分类号： G06F1750

CPC分类号： G06F17/504

摘要： 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.

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

公开(公告)号：US6163876A

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

申请号：US187927

申请日：1998-11-06

申请人： Pranav Ashar ,  Subhrajit Bhattacharya ,  Anand Raghunathan ,  Akira Mukaiyama

发明人： Pranav Ashar ,  Subhrajit Bhattacharya ,  Anand Raghunathan ,  Akira Mukaiyama

IPC分类号： G06F17/50

CPC分类号： G06F17/504

摘要： 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.

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

公开(公告)号：US07383166B2

公开(公告)日：2008-06-03

申请号：US10756303

申请日：2004-01-14

申请人： Pranav Ashar ,  Anand Raghunathan ,  Subhrajit Bhattacharya

发明人： Pranav Ashar ,  Anand Raghunathan ,  Subhrajit Bhattacharya

IPC分类号： G06F17/50

CPC分类号： G06F17/504

摘要： 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.

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

公开(公告)号：US07742907B2

公开(公告)日：2010-06-22

申请号：US10762499

申请日：2004-01-23

申请人： Aarti Gupta ,  Malay Ganai ,  Zijiang Yang ,  Pranav Ashar

发明人： Aarti Gupta ,  Malay Ganai ,  Zijiang Yang ,  Pranav Ashar

IPC分类号： G06F17/50 ,  G06F9/45

CPC分类号： G06F17/504

摘要： A method of obtaining a resolution-based proof of unsatisfiability using a SAT procedure for a hybrid Boolean constraint problem comprising representing constraints as a combination of clauses and interconnected gates. The proof is obtained as a combination of clauses, circuit gates and gate connectivity constraints sufficient for unsatisfiability.

摘要翻译： 使用针对混合布尔约束问题的SAT过程获得基于分辨率的不满足证明的方法，包括将约束表示为子句和互连门的组合。 证明是作为条件，电路门和门连接约束的组合获得的，足以满足不满足性。

公开(公告)号：US07305637B2

公开(公告)日：2007-12-04

申请号：US11087898

申请日：2005-03-23

申请人： Malay K. Ganai ,  Aarti Gupta ,  Pranav Ashar

发明人： Malay K. Ganai ,  Aarti Gupta ,  Pranav Ashar

IPC分类号： G06F17/50

CPC分类号： G06F17/504

摘要： An efficient approach for SAT-based quantifier elimination and pre-image computation using unrolled designs that significantly improves the performance of pre-image and fix-point computation in SAT-based unbounded symbolic model checking.

摘要翻译： 基于SAT的量化器消除和使用非滚动设计的前图像计算的有效方法，显着提高了基于SAT的无界符号模型检查中的前图像和定点计算的性能。

公开(公告)号：US20050240885A1

公开(公告)日：2005-10-27

申请号：US11087898

申请日：2005-03-23

申请人： Malay Ganai ,  Aarti Gupta ,  Pranav Ashar

发明人： Malay Ganai ,  Aarti Gupta ,  Pranav Ashar

IPC分类号： G06F7/60 ,  G06F17/50

CPC分类号： G06F17/504

摘要： An efficient approach for SAT-based quantifier elimination and pre-image computation using unrolled designs that significantly improves the performance of pre-image and fix-point computation in SAT-based unbounded symbolic model checking.

摘要翻译： 基于SAT的量化器消除和使用非滚动设计的前图像计算的有效方法，显着提高了基于SAT的无界符号模型检查中的前图像和定点计算的性能。

公开(公告)号：US06223141B1

公开(公告)日：2001-04-24

申请号：US09115668

申请日：1998-07-14

申请人： Pranav Ashar

发明人： Pranav Ashar

IPC分类号： G06F9455

CPC分类号： G06F17/5022

摘要： Delay-independent cycle-based logic simulation of synchronous digital circuits with levelized compiled code simulation has substantially increased speed. Sweep, eliminate, and factor reduce the number of literals. The use of cofactoring, a register allocation and spill scheme, an inverter minimization scheme, and retiming further reduce the simulation time for two and four valued simulation. A shift minimization scheme reduces time in four-valued simulation. The faster simulation is embodied in a method, a computer system, and a computer program product.

摘要翻译： 具有均衡编译代码模拟的同步数字电路的基于延迟的循环逻辑仿真具有显着提高的速度。 扫描，消除和因素减少文字数量。 使用配置，寄存器分配和溢出方案，逆变器最小化方案和重新定时进一步减少了二值和四值仿真的仿真时间。 移位最小化方案减少了四值模拟中的时间。 更快的模拟体现在方法，计算机系统和计算机程序产品中。

公开(公告)号：US20080065639A1

公开(公告)日：2008-03-13

申请号：US11550320

申请日：2006-10-17

申请人： Ashwini Choudhary ,  Pranav Ashar ,  Jitendra Kulkarni

发明人： Ashwini Choudhary ,  Pranav Ashar ,  Jitendra Kulkarni

IPC分类号： G06F7/00

CPC分类号： G06F7/02 ,  G06F2207/025

摘要： String matching a first string to a string stored in a string dictionary is performed by k-way hashing the first string and locating corresponding k hash locations in a first memory. When any of the k hash locations has a zero Bloom bit, the first string is deemed to not match any of the strings in the string dictionary. Otherwise, a sub-set of the k hash locations identified as those k hash locations having non-zero Bloom bits and a unique bit set to 1 each include a pointer that points to a string in the string dictionary that is fetched and compared to the first string wherein the fetches from the string dictionary are interleaved over the addresses from the first memory. A match signal is issued when the first string matches at least one of the strings stored in the dictionary.

摘要翻译： 将第一个字符串与存储在字符串字典中的字符串进行匹配的字符串通过k-way散列第一个字符串并在第一个存储器中定位相应的k个哈希位置来执行。 当k个哈希位置中的任何一个具有零布隆比特时，第一个字符串被认为与字符串字典中的任何字符串不匹配。 否则，被识别为具有非零布隆比特的k个哈希位置和设置为1的唯一比特的k个哈希位置的子集包括指向字符串字典中的字符串的指针，该字符串被提取并与 第一个字符串，其中来自字符串字典的提取被交织在来自第一存储器的地址上。 当第一个字符串匹配字典中存储的字符串中的至少一个字符串时，发出匹配信号。

公开(公告)号：US20080052644A1

公开(公告)日：2008-02-28

申请号：US11558061

申请日：2006-11-09

申请人： Pranav Ashar ,  Jitendra Kulkarni ,  Ashwini Choudhary

发明人： Pranav Ashar ,  Jitendra Kulkarni ,  Ashwini Choudhary

IPC分类号： G06F17/50

CPC分类号： G06F16/90344

摘要： An efficient finite state machine implementation of a string matching that relies upon a Content Addressable Memory (CAM) or a CAM-equivalent collision-free hash-based lookup architecture with zero false positives used as a method for implementing large FSMs in hardware using a collision-free hash-based look up scheme with low average case bandwidth and power requirements that overcomes prior art limitations by providing the ability to match an anchored or unanchored input stream against a large dictionary of long and arbitrary length strings at line speed. It should be noted that in the context of the described embodiments, a string could take many forms, such as a set of characters, bits, numbers or any combination thereof.

摘要翻译： 一个有效的有限状态机实现的字符串匹配依赖于内容可寻址内存（CAM）或CAM等效的无冲突的基于哈希的查找架构，零假想正用作在硬件中使用冲突实现大型FSM的方法 - 基于散列的查找方案，具有低平均情况带宽和功率需求，通过提供将锚定或未锚定输入流与线速度的长字符和任意长度字符串的大字典相匹配的能力来克服现有技术的限制。 应当注意，在所描述的实施例的上下文中，字符串可以采取许多形式，诸如一组字符，位，数字或其任何组合。

公开(公告)号：US07019674B2

公开(公告)日：2006-03-28

申请号：US10909907

申请日：2004-08-02

申请人： Srihari Cadambi ,  Joseph Kilian ,  Pranav Ashar ,  Srimat T. Chakradhar

发明人： Srihari Cadambi ,  Joseph Kilian ,  Pranav Ashar ,  Srimat T. Chakradhar

IPC分类号： H03M7/00

CPC分类号： G06F17/30949 ,  H04L45/00 ,  H04L45/745

摘要： A content-based information retrieval architecture is herein disclosed that can achieve correct and predictable high speed lookups while taking advantage of inexpensive conventional memory components. A content-based information retrieval architecture is herein disclosed that can achieve high speed lookups with a constant query time while taking advantage of inexpensive conventional memory components. In accordance with an embodiment of the invention, the architecture comprise a hashing module, a first table of encoded values, a second table of lookup values, and a third table of associated input values. The input value is hashed a number of times to generate a plurality of hashed values, the hashed values corresponding to locations of encoded values in the first table. The encoded values obtained from an input value encode an output value such that the output value cannot be recovered from any single encoded value.

摘要翻译： 本文公开了一种基于内容的信息检索架构，其可以在利用廉价的常规存储器组件的情况下实现正确和可预测的高速查找。 本文公开了一种基于内容的信息检索架构，其可以利用廉价的常规存储器组件来实现具有恒定查询时间的高速查找。 根据本发明的实施例，架构包括散列模块，编码值的第一表，查找值的第二表和相关联的输入值的第三表。 输入值被散列多次以产生多个散列值，该散列值对应于第一表中的编码值的位置。 从输入值获得的编码值对输出值进行编码，使得输出值不能从任何单个编码值恢复。