专利快速检索-快速检索全球专利，免费商用专利数据库-IPRDB

1. 发明授权

US06324673B1 Method and apparatus for edge-endpoint-based VLSI design rule checking 有权
标题翻译：基于边缘端点的VLSI设计规则检查的方法和装置
公开(公告)号：US06324673B1
公开(公告)日：2001-11-27
申请号：US09321591
申请日：1999-05-28
申请人： Zhen Luo , Margaret Martonosi , Pranav Ashar
发明人： Zhen Luo , Margaret Martonosi , Pranav Ashar
IPC分类号： G06F1750
CPC分类号： G06F17/5081
摘要： 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.
摘要翻译：在VLSI电路布局中对曼哈顿结构执行设计规则检查的方法和装置。该方法和装置提供用于检查VLSI电路布局的几何形状和间距的基于边缘端点的技术。基于边缘端点的技术使用扫描线算法来检测不同时与扫描线相交的相邻结构之间的错误。该方法还提供了有效的错误编译。该设备允许随着VLSI电路布局的发展而改变设计规则。该设备可以使用单个处理器来处理VLSI电路布局，并且该设备提供多个处理器来处理VLSI电路布局的片段，从而提高设计规则检查传统的仅软件技术的速度。

2. 发明授权

US06247164B1 Configurable hardware system implementing Boolean Satisfiability and method thereof 失效
标题翻译：可配置硬件系统实现布尔满足度及其方法
公开(公告)号：US06247164B1
公开(公告)日：2001-06-12
申请号：US08919282
申请日：1997-08-28
申请人： Pranav Ashar , Sharad Malik , Margaret Martonosi , Peixin Zhong
发明人： Pranav Ashar , Sharad Malik , Margaret Martonosi , Peixin Zhong
IPC分类号： G06F1750
CPC分类号： G06F17/504
摘要： Disclosed is a configurable hardware system and method for implementing instance-specific (per-formula) SAT-solver circuits. A template design is provided for producing these circuits on a per-formula basis. The typical hardware requirements for implementing the invention makes the design amenable to current or next-generation FPGA implementation. Hardware simulations indicate that for many difficult SAT problems, the system according to the invention can offer one to three orders of magnitude speedup over prior art software implementations.
摘要翻译：公开了用于实现实例特定（每公式）SAT解算器电路的可配置硬件系统和方法。提供了一个模板设计，用于在每个公式的基础上产生这些电路。实现本发明的典型硬件要求使得设计适合当前或下一代FPGA实现。硬件模拟表明，对于许多困难的SAT问题，根据本发明的系统可以提供超过现有技术的软件实现一到三个数量级的加速。

3. 发明授权

US06415430B1 Method and apparatus for SAT solver architecture with very low synthesis and layout overhead 有权
标题翻译： SAT求解器架构的方法和设备具有非常低的综合和布局开销
公开(公告)号：US06415430B1
公开(公告)日：2002-07-02
申请号：US09456506
申请日：1999-12-08
申请人： Pranav Ashar , Peixin Zhong , Margaret Martonosi
发明人： Pranav Ashar , Peixin Zhong , Margaret Martonosi
IPC分类号： G06F1750
CPC分类号： G06F17/504 , G06F17/5054
摘要： 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.
摘要翻译：一种用于通过使用时间多路复用流水线总线架构而不是使用FPGA路由资源硬连线来实现文本和布尔SAT问题的子句之间的通信的方法和装置。这种技术允许布尔SAT问题的不同实例的电路相同，除了小的局部差异。与实际解决SAT问题的时间相比，布尔SAT问题的每个实例所需的增量合成和布局和布线工作变得可以忽略不计。时间复用功能允许在SAT求解器算法中动态添加子句。流水线架构具有很高的流水线配置，极少的长导线，没有电线穿过FPGA边界，从而提供高的时钟速度。

4. 发明授权

US6038392A Implementation of boolean satisfiability with non-chronological backtracking in reconfigurable hardware 失效
标题翻译：在可重配置硬件中实现具有非时序回溯的布尔可满足性
公开(公告)号：US6038392A
公开(公告)日：2000-03-14
申请号：US85646
申请日：1998-05-27
申请人： Pranav Ashar , Sharad Malik , Margaret Martonosi , Peixin Zhong
发明人： Pranav Ashar , Sharad Malik , Margaret Martonosi , Peixin Zhong
IPC分类号： G06F9/44 , G06F17/10 , G06F17/50 , G06N5/04
CPC分类号： G06F17/5054
摘要： A Boolean SAT solver uses reconfigurable hardware to solve a specific input problem. Each of the plurality of ordered variables has a corresponding one of a plurality of state machines. Each state machine has an implication circuit for its respective variable, and operates in parallel according to an identical state machine. One state machine implements the Davis-Putnam method in hardware and provides improved performance over software by virtue of the parallel checking of direct and transitive implications. Another state machine implements a novel non-chronological backtracking method that takes advantage of the parallel implication checking and avoids the need to maintain or to traverse a GRASP type implication graph in the event of backtracking. The novel non-chronological backtracking provides for setting a blocking variable as a leaf variable and for changing only the value of the leaf variable, but possibly changing both the value and identity of a backtracking variable.
摘要翻译：布尔SAT求解器使用可重构硬件来解决特定的输入问题。多个有序变量中的每一个具有多个状态机中的对应的一个。每个状态机具有用于其各自变量的含义电路，并且根据相同的状态机并行操作。一个状态机通过硬件实现Davis-Putnam方法，并通过并行检查直接和传递的影响，提高了软件性能。另一种状态机实现了一种新颖的非时间回溯方法，其利用并行含义检查的优点，并避免在回溯事件中维护或遍历GRASP类型含义图。新颖的非时间回溯提供将阻塞变量设置为叶变量，并且仅改变叶变量的值，但可能改变回溯变量的值和身份。

5. 发明授权

US07742907B2 Iterative abstraction using SAT-based BMC with proof analysis 失效
标题翻译：使用基于SAT的BMC进行迭代抽象与证明分析
公开(公告)号：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过程获得基于分辨率的不满足证明的方法，包括将约束表示为子句和互连门的组合。证明是作为条件，电路门和门连接约束的组合获得的，足以满足不满足性。

6. 发明授权

US07305637B2 Efficient SAT-based unbounded symbolic model checking 有权
标题翻译：高效的基于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的无界符号模型检查中的前图像和定点计算的性能。

7. 发明申请

US20050240885A1 Efficient SAT-based unbounded symbolic model checking 有权
标题翻译：高效的基于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的无界符号模型检查中的前图像和定点计算的性能。

8. 发明授权

US06223141B1 Speeding up levelized compiled code simulation using netlist transformations 失效
标题翻译：使用网表转换加快级别化的编译代码模拟
公开(公告)号：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.
摘要翻译：具有均衡编译代码模拟的同步数字电路的基于延迟的循环逻辑仿真具有显着提高的速度。扫描，消除和因素减少文字数量。使用配置，寄存器分配和溢出方案，逆变器最小化方案和重新定时进一步减少了二值和四值仿真的仿真时间。移位最小化方案减少了四值模拟中的时间。更快的模拟体现在方法，计算机系统和计算机程序产品中。

9. 发明申请

US20080065639A1 STRING MATCHING ENGINE 审中-公开
标题翻译： STRING匹配发动机
公开(公告)号：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个哈希位置的子集包括指向字符串字典中的字符串的指针，该字符串被提取并与第一个字符串，其中来自字符串字典的提取被交织在来自第一存储器的地址上。当第一个字符串匹配字典中存储的字符串中的至少一个字符串时，发出匹配信号。

10. 发明申请

US20080052644A1 STRING MATCHING ENGINE FOR ARBITRARY LENGTH STRINGS 审中-公开
标题翻译： STRING匹配发动机用于仲裁长度
公开(公告)号：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的方法 - 基于散列的查找方案，具有低平均情况带宽和功率需求，通过提供将锚定或未锚定输入流与线速度的长字符和任意长度字符串的大字典相匹配的能力来克服现有技术的限制。应当注意，在所描述的实施例的上下文中，字符串可以采取许多形式，诸如一组字符，位，数字或其任何组合。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式