Nec Usa, Inc.

Nec Corporation

Nec Laboratories America, Inc.

Other

Nec Research Institute, Inc.

Real Intent, Inc.

Princeton University

Pranav N Ashar

Aarti Gupta

Sharad Malik

Zijiang Yang

Malay K Ganai

Margaret Martonosi

Anand Raghunathan

Subhrajit Bhattacharya

Peixin Zhong

Franjo Ivancic

Srihari Cadambi

Srimat T Chakradhar

Srinivas Devadas

Farzan Fallah

Sujit Dey

Albert E Casavant

Akira Mukaiyama

Ilya Shlyakhter

Sanjeev Mahajan

Vikas Sachdeva

Aleksandr Zaks

Lintao Zhang

Fabrice Baray

Ian Andrew Guyler

Joseph Kilian

Hari Mony

Yang Xia

Anubhav Gupta

Zhen Luo

Nikhil Rahagude

Chao Cheong

Methods and systems are described to efficiently identify the potential for failures in integrated circuits (ICs) caused by glitches. In an IC based on synchronous operation, the operation of the multiplicity of inputs, storage elements and observed outputs in said IC are synchronized to one or more clocks that determine the specific times at which inputs change, outputs are observed, and stored values are updated. Almost all ICs are based on synchronous operation. When input values to a logic circuit in an IC change, the effects of said changes propagate through paths in said logic circuit in a delayed manner such that each of said paths may have a different delay. Said different delays can cause a wire in a logic circuit to have transient values (termed 'glitch') before settling to a final value consistent with the input values being applied to said logic circuit. An IC is likely to function erroneously, referred to as having a 'glitch failure', when a glitch value is observed at an output or captured by a storage element. Glitch failures are difficult and expensive to diagnose in a manufactured IC. To raise the productivity of IC development, it is imperative that any potential glitch failure in an IC be detected prior to manufacture. Said detection is hard because a typical IC has a very large number of logic circuits to analyze for glitch failure. To be practical, said analysis must have high performance and high accuracy. Said high performance requiring that said analysis should complete in acceptable run time even for the largest ICs. Said high accuracy requires that said analysis should identify all potential for glitch failure (100% recall), and minimize the number of logic circuits erroneously reported as having glitch failure potential (high precision). Whereas the glitch phenomenon, the potential for glitch failure and methods for detecting glitch failures in pre-manufacture IC models are well known, achievement of high performance with high accuracy has not yet been addressed in prior art. Whereas conventional methods for glitch checking are inefficient and insufficiently accurate, the methods and systems described in the present invention achieve new levels of performance, scalability and accuracy in said detection of glitch failures in an IC. Said methods and systems are based on a novel dissection of glitch-checking requirements into a multiplicity of individual steps, which said steps executed in a systematic sequence deliver high performance and accuracy.

Methods and systems for efficient identification of glitch failures in integrated circuits

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.

Methods and systems for correcting X-pessimism in gate-level simulation or emulation

A system and method is disclosed for formal verification of software programs that advantageously bounds the ranges of values that a variable in the software can take during runtime.

Software verification using range analysis

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.

Iterative abstraction using SAT-based BMC with proof analysis

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.

Efficient approaches for bounded model checking

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.

Efficient modeling of embedded memories in bounded memory checking

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.

Verification of scheduling in the presence of loops using uninterpreted symbolic simulation

A system and method is disclosed for formal verification of software programs that advantageously translates the software, which can have bounded recursion, into a Boolean representation comprised of basic blocks and which applies SAT-based model checking to the Boolean representation.

System and method for modeling, abstraction, and analysis of software

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.

Efficient SAT-based unbounded symbolic model checking

There is provided a method of solving a SAT problem comprising partitioning SAT-formula clauses in the SAT problem into a plurality of partitions. Each of said plurality of partitions is solved as a separate process each, thereby constituting a plurality of processes where each of said process communicates only with a subset of the plurality of processes.

Efficient distributed SAT and SAT-based distributed bounded model checking

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.

Content-based information retrieval architecture

Simulation continues to be the primary technique for functional validation of designs. It is important that simulation vectors be effective in targeting the types of bugs designers expect to find rather than some generic coverage metrics. The focus of this work is to generate property-specific testbenches that are targeted either at proving the correctness of a property or at finding a bug. It is based on performing property-specific analysis on iteratively less abstract models of the design in order to obtain interesting paths in the form of a Witness Graph, which is then targeted during simulation of the entire design. This testbench generation framework will form an integral part of a comprehensive verification system currently being developed.

Property specific testbench generation framework for circuit design validation by guided simulation

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. The test model is abstracted by retiming and latch removal. Finally, a validation technique is applied 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 simulation using test sequences generated from the abstracted test model.

Method for design validation using retiming

A method of automatically generating vector sequences for an observability based coverage metric supports design validation. A design validation method for Register Transfer Level (RTL) circuits includes the generation of a tag list. Each tag in the tag list models an error at a location in HDL code at which a variable is assigned a value. Interacting linear and Boolean constraints are generated for the tag, and the set of constraints is solved using an HSAT solver to provide a vector that covers the tag. For each generated vector, tag simulation is performed to determine which others of the tags in the tag list are also covered by that vector. Vectors are generated until all tags have been covered, if possible within predetermined time constraints, thus automatically providing a set of vectors which will propagate errors in the HDL code to an observable output. Performance of the design validation method is enhanced through various heuristics involving path selection and tag magnitude maximization.

Simulation vector generation from HDL descriptions for observability-enhanced statement coverage

A design verification method for verifying hardware designs utilizing combinational loop logic. A design verification system is provided wherein a model checker receives both a mathematical representation of the functionality of a design and a set of properties against which the mathematical model is to be checked. If the design contains a combinational loop wherein the output directly depends on its own output and must be logically completed within a single bus cycle, then modifications to the model are undertaken. A minimal number of flip-flops are first added to the combinational loop in order to break up the combinational dependency. All of the states of a state machine model of the design are then supplemented with a twin state which is exactly the same as the original state. If the current state is an original state then the next cycle progresses the state machine to twin state of the particular original state. If the current state is a twin state, then the state machine progresses to the next new original state. Thus, by modifying the model in a generic straightforward manner, the design containing a combinational loop can be verified with currently available verification systems without requiring any modifications to the model checker itself.

Growing community of inventors

Princeton, NJ, United States of America

Pranav N Ashar