Patent application number | Description | Published |
20080216029 | METHOD AND SYSTEM FOR PERFORMING TARGET ENLARGEMENT IN THE PRESENCE OF CONSTRAINTS - A method for performing verification is disclosed. The method includes receiving a design, including one or one or more targets, one or more constraints, one or more registers and one or more inputs. A first function of one of the one or more targets over the one or more registers and the one or more inputs is computed. A second function of one or more of the one or more constraints over the one or more registers and the one or more inputs is computed. The inputs of the first function and the second function are existentially quantified. A bounded analysis is performed to determine if the one of the one or more targets may be hit while adhering to the constraints. A preimage of the inputs of the first function and a preimage of the inputs of the second function is existentially quantified to create a synthesizable preimage. The synthesizable preimage is simplified and synthesized to create an enlarged target. Verification of the enlarged target is performed. | 09-04-2008 |
20080229263 | PERFORMING UTILIZATION OF TRACES FOR INCREMENTAL REFINEMENT IN COUPLING A STRUCTURAL OVERAPPROXIMATION ALGORITHM AND A SATISFIABILITY SOLVER - A method, system and computer program product for performing verification are disclosed. The method includes creating and designating as a current abstraction a first abstraction of an initial design netlist containing a first target and unfolding the current abstraction by a selectable depth. A composite target is verified, using a satisfiability solver and, in response to determining that the verifying step has hit the composite target, a counterexample is examined to identify one or more reasons for the first target to be asserted. One or more refinement pairs are built by examining the counterexample and a second abstraction is built by composing the refinement pairs. A new target is built over one or more cutpoints in the first abstraction that is asserted when the one or more cutpoints assume values in the counterexample, and the new target is verified with the satisfiability solver. | 09-18-2008 |
20080307372 | METHOD AND SYSTEM FOR PERFORMING MINIMIZATION OF INPUT COUNT DURING STRUCTURAL NETLIST OVERAPPROXIMATION - A method for performing verification is disclosed. The method includes selecting a set of gates to add to a first localization netlist and forming a refinement netlist. A min-cut is computed with sinks having one or more gates in the refinement netlist and sources comprising one or more inputs of an original netlist and one or more registers registers of the original netlist which are not part of the refinement netlist. A final localized netlist is obtained by adding one or more gates to the refinement netlist to grow the refinement netlist until reaching one or more cut-gates of the min-cut. | 12-11-2008 |
20090094563 | Method and System for Enhanced Verification By Closely Coupling a Structural Satisfiability Solver and Rewriting Algorithms - A method, system and computer program product are disclosed. The method includes initializing a first variable to limit a rewrite time for rewrite operations with respect to an initial design by a rewriting module, a second variable to limit a time for satisfiability solver operations with respect to said initial design by a satisfiability solver module and a third variable to limit a maximum number of rewrite iterations with respect to said initial design. A timer is called to track said rewrite time and a local logic rewriting operation is run on said initial design with said rewrite module. In response to determining that all of all targets for said initial design netlist are not solved, whether a rewrite time is expired is determined. In response to determining that said rewrite time is not expired, AND refactoring is run. In response to determining that said rewrite time is not expired, XOR refactoring is run. | 04-09-2009 |
20090125856 | METHODS AND APPARATUS FOR BOOLEAN EQUIVALENCY CHECKING IN THE PRESENCE OF VOTING LOGIC - In a first aspect, a first method of designing a circuit is provided. The first method includes the steps of (1) providing a model of an original circuit design including a latch; (2) providing a model of a modified version of the original circuit design, wherein the modified version of the original circuit design includes a set of latches associated with the latch of the original circuit design and voting logic having inputs coupled to respective outputs of latches in the latch set; and (3) during Boolean equivalency checking (BEC), injecting an error on at most a largest minority of the inputs of the voting logic to test the voting logic function. | 05-14-2009 |
20100199241 | Method and System for Automated Use of Uninterpreted Functions in Sequential Equivalence Checking - A method, system and computer program product for automated use of uninterpreted functions in sequential equivalence checking. A first netlist and a second netlist may be received and be included in an original model, and from the original model, logic to be abstracted may be determined. A condition for functional consistency may be determined, and an abstract model may be created by replacing the logic with abstracted logic using one or more uninterpreted functions. One or more functions may be performed on the abstract model. For example, the one or more functions may include one or more of a bounded model checking (BMC) algorithm, an interpolation algorithm, a Boolean satisfiability-based analysis algorithm, and a binary decision diagram (BDD) based reachability analysis algorithm, among others. | 08-05-2010 |
20100218148 | Method and System for Sequential Netlist Reduction Through Trace-Containment - Methods and systems are provided for sequential netlist reduction through trace-containment for a circuitry design netlist by first identifying a cut of the netlist and enumerating a set of mismatch traces. Perform time-bounded unfolding of a cofactored version of the cut to reflect the sequential cofactor for a specific input i and temporal uncorrelation constraints for the set of inputs ‘J’. Determine whether there is trace containment by performing equivalence checking with respect to the cut of the netlist under temporal uncorrelation constraints for the set of inputs ‘J’. In response to detecting trace containment, simplify the netlist by merging the input ‘i’ to a constant. | 08-26-2010 |
20100251197 | METHOD, SYSTEM AND APPLICATION FOR SEQUENTIAL COFACTOR-BASED ANALYSIS OF NETLISTS - Methods, systems and computer products are provided for reducing the design size of an integrated circuit while preserving the behavior of the design with respect to verification results. A multiplexer is inserted at the gate being analyzed, and the multiplexer selector is controlled to provide a predetermined output for one frame at the point being analyzed. It is then determined whether the circuit remains equivalent during application of the predetermined output in order to decide whether the gate being analyzed is a candidate for replacement. | 09-30-2010 |
20100269077 | Trace Containment Detection of Combinational Designs via Constraint-Based Uncorrelated Equivalence Checking - Methods and systems are provided for producing more efficient digital circuitry designs by identifying trace-containment for a sequential circuitry design netlist through the use of constraint-based uncorrelated equivalence checking. A set of candidate input netlist sets n | 10-21-2010 |
20100293513 | Method and System for Design Simplification Through Implication-Based Analysis - Methods and systems are provided for reducing an original circuit design into a simplified circuit design by merging gates that may not be equivalent but can be demonstrated to preserve target assertability with respect to the original circuitry design. A composite netlist is created from the simplified netlist and the original netlist. The composite netlist includes a number of targets that imply the existence of a target in the simplified netlist and a corresponding target in the original netlist. The implications are verified and then validated to ensure the simplied circuit design is a suitable replacement for the original circuit design. | 11-18-2010 |
20110093825 | TECHNIQUES FOR ANALYSIS OF LOGIC DESIGNS WITH TRANSIENT LOGIC - A technique for performing an analysis of a logic design includes detecting an initial transient behavior in a logic design embodied in a netlist. A duration of the initial transient behavior is also determined. Reduction information on the logic design is gathered based on the initial transient behavior. The netlist is then modified based on the reduction information. | 04-21-2011 |
20110270597 | Tracking Array Data Contents Across Three-Valued Read and Write Operations - A mechanism is provided in an integrated circuit simulator for tracking array data contents across three-value read and write operations. The mechanism accounts for write operations with data values and address values having X symbols. The mechanism performs writes to a tree data structure that is used to store the three-valued contents to the array. The simulator includes functionality for updating the array contents for a three-valued write and to read data for a three-valued read. The simulator also includes optimizations for dynamically reducing the size of the data structure when possible in order to save memory in the logic simulator. | 11-03-2011 |
20110271242 | Efficient Redundancy Identification, Redundancy Removal, and Sequential Equivalence Checking within Designs Including Memory Arrays - A mechanism is provided for efficient redundancy identification, redundancy removal, and sequential equivalence checking with designs including memory arrays. The mechanism includes an array merging component to optimally merge an array output such that if the address is out-of-bounds or the port is not asserted, the array output is converted to a random output. The mechanism also includes a component for determining the equivalence of enabled array outputs rather than the array outputs directly and creating an enabled array output. The mechanism also includes a component that precludes potentially-redundant array cells from participating in the sequential redundancy removal determination. This component first checks for compatibility of the corresponding arrays, then the corresponding read port enables and addresses, then the corresponding initial values, and finally checking that writes to the corresponding columns yield a compatible set of values. | 11-03-2011 |
20110271244 | Enhanced Analysis of Array-Based Netlists via Reparameterization - A mechanism is provided for increasing the scalability of formal verification solutions through enabling the use of input reparameterization on logic models that include memory arrays. A pre-processing mechanism enables the selection of a cut-based design partition which enables optimal reductions though input reparameterization given a netlist with constraints. A post-processing mechanism next prevents input reparameterization from creating topologically inconsistent models in the presence of arrays. Additionally, this technique may be used to rectify inconsistent topologies that may arise when reparameterizing even netlists without arrays, namely false sequential dependencies across initialization constructs. Furthermore, a mechanism is provided to undo the effects of memory array based input reparameterization on verification results. | 11-03-2011 |
20110276930 | Minimizing Memory Array Representations for Enhanced Synthesis and Verification - Mechanisms are provided in a design environment for minimizing memory array representations for enhanced synthesis and verification. The design environment comprises one mechanism to compress the width of arrays using disconnected pin information. The design environment comprises another mechanism to simplify the enable conditions of array ports using “don't care” computations. The design environment comprises yet another mechanism to reduce address pins from an array through analysis of limitations of readable addresses. | 11-10-2011 |
20110276931 | Eliminating, Coalescing, or Bypassing Ports in Memory Array Representations - Mechanisms are provided in a design environment for eliminating, coalescing, or bypassing ports. The design environment comprises one mechanism to eliminate unnecessary ports in arrays using disabled and disconnected pin information. The design environment may comprise another mechanism to combine and reduce the number of array ports using address comparisons. The design environment may comprise another mechanism to combine and reduce the number of array ports using disjoint enable comparisons. The design environment may comprise one mechanism to combine and reduce the number of array ports using “don't care” computations. The design environment may comprise another mechanism to reduce the number of array ports through bypassing write-to-read paths around arrays. | 11-10-2011 |
20110276932 | Array Concatenation in an Integrated Circuit Design - Mechanisms are provided in a design environment for array concatenation. The design environment comprises one mechanism to concatenate arrays with enable- and address-compatible ports, thereby reducing the number of arrays in a netlist. The design environment comprises another mechanism to migrate read ports from one array to another based upon compatible enable-, address-, and data-compatible write ports, thereby reducing the number of arrays in a netlist. The design environment comprises yet another mechanism to eliminate unnecessary arrays. | 11-10-2011 |
20120271786 | Efficiently Determining Boolean Satisfiability with Lazy Constraints - A mechanism is provided for efficiently determining Boolean satisfiability (SAT) using lazy constraints. A determination is made as to whether a SAT problem is satisfied without constraints in a list of constraints. Responsive to the SAT problem being satisfied without constraints, a set of variable assignments that are determined in satisfying the SAT problem without constraints are fixed. For each constraint in the list of constraints, a determination is made as to whether the SAT problem with the constraint results in the set of variable assignments remaining constant. Responsive to the SAT problem with the constraint resulting in the set of variable assignments remaining constant, the constraint is added to a list of non-affecting constraints and a satisfied result is returned. | 10-25-2012 |
20120271792 | Efficiently Determining Boolean Satisfiability with Lazy Constraints - A mechanism is provided for efficiently determining Boolean satisfiability (SAT) using lazy constraints. A determination is made as to whether a SAT problem is satisfied without constraints in a list of constraints. Responsive to the SAT problem being satisfied without constraints, a set of variable assignments that arc determined in satisfying the SAT problem without constraints are fixed. For each constraint in the list of constraints, a determination is made as to whether the SAT problem with the constraint results in the set of variable assignments remaining constant. Responsive to the SAT problem with the constraint resulting in the set of variable assignments remaining constant, the constraint is added to a list of non-affecting constraints and a satisfied result is returned. | 10-25-2012 |
20120272197 | Enhancing Redundancy Removal with Early Merging - A mechanism is provided for simplifying a netlist before computational resources are exceeded. For each of a set of suspected equivalences in a proof graph of a netlist, a determination is made as to whether equivalence holds for at least one of an equivalence or an equivalence class by identifying whether the equivalence or equivalence class is either affecting or non-affecting. Responsive to the equivalence or equivalence class being affecting, a proof dependency is recorded as an edge in a proof graph. For each node in the proof graph, a determination is made as to whether the node has a falsified dependency. Responsive to the node failing to have a falsified dependency, identification is made that all dependencies are satisfied and that the equivalences represented by the node in the proof graph are sequential equivalences. The netlist is then simplified by consuming the sequential equivalences. | 10-25-2012 |
20120272198 | Enhancing Redundancy Removal with Early Merging - A mechanism is provided for simplifying a netlist before computational resources are exceeded. For each of a set of suspected equivalences in a proof graph of a netlist, a determination is made as to whether equivalence holds for at least one of an equivalence or an equivalence class by identifying whether the equivalence or equivalence class is either affecting or non-affecting. Responsive to the equivalence or equivalence class being affecting, a proof dependency is recorded as an edge in a proof graph. For each node in the proof graph, a determination is made as to whether the node has a falsified dependency. Responsive to the node failing to have a falsified dependency, identification is made that all dependencies are satisfied and that the equivalences represented by the node in the proof graph are sequential equivalences. The netlist is then simplified by consuming the sequential equivalences. | 10-25-2012 |
20120290282 | REACHABILITY ANALYSIS BY LOGICAL CIRCUIT SIMULATION FOR PROVIDING OUTPUT SETS CONTAINING SYMBOLIC VALUES - A logic simulation program, method and system for obtaining a set of reachable states for a logic design that can be used to provide input to other algorithms that simplify the netlist describing the logic design or perform other types of processing, provides an efficient, compact behavior when simulating large designs. Rather than simulating using ternary input and state value representations that are restricted to true, false and unknown, the techniques of the present invention use input symbolic values that are retained in the set of reachable states retained as the output. Behaviors such as oscillators, transient values, identical signals, dependent logical states and chicken-switch determined states can be detected in the simulation results and the netlist simplified using the results of the detection. | 11-15-2012 |
20120290992 | LOGICAL CIRCUIT NETLIST REDUCTION AND MODEL SIMPLIFICATION USING SIMULATION RESULTS CONTAINING SYMBOLIC VALUES - A logic synthesis program, method and system for simplifying and/or reducing a logic design receives output from a logic simulator that uses symbolic values for stimulus and contains symbolic values in the logic simulator output. Relationships between the nodes dependent on symbolic values can be used to merge nodes or otherwise simplify the logic design. Behaviors such as oscillators, transient values, identical signals, dependent logical states and chicken-switch determined states that depend on the symbolic values can be detected in the simulation results and the netlist simplified using the results of the detection. The netlist can be simplified by inserting registers to represent nodes that assume a symbolic value or combination based on symbolic values either statically or after an initial transient. Oscillating nodes can be replaced with equivalent oscillator circuits, and nodes having values dependent on chicken-switch operation can be detected and replaced with registers initialized from the chicken-switch input states. | 11-15-2012 |
20130290918 | CONSTRUCTING INDUCTIVE COUNTEREXAMPLES IN A MULTI-ALGORITHM VERIFICATION FRAMEWORK - A computer-implemented method simplifies a netlist, verifies the simplified netlist using induction, and remaps resulting inductive counterexamples via inductive trace lifting within a multi-algorithm verification framework. The method includes: a processor deriving a first unreachable state information that can be utilized to simplify the netlist; performing a simplification of the netlist utilizing the first unreachable state information; determining whether the first unreachable state information can be inductively proved on an original version of the netlist; and in response to the first unreachable state information not being inductively provable on the original netlist: projecting the first unreachable state information to a minimal subset; and adding the projected unreachable state information as an invariant to further constrain a child induction process. Adding the projected state information as an invariant ensures that any resulting induction counterexamples can be mapped to valid induction counterexamples on the original netlist before undergoing the simplification. | 10-31-2013 |
20130305197 | METHOD AND SYSTEM FOR OPTIMAL DIAMETER BOUNDING OF DESIGNS WITH COMPLEX FEED-FORWARD COMPONENTS - A computer-implemented method includes a processor identifying, within the netlist, at least one strongly connected components (SCCs) that has a reconvergent fanin input with at least two input paths from the reconvergent fanin input having a different propagation delay to the SCC. The method then computes an additive diameter for the netlist comprising at least one SCC, where the additive diameter includes a fanin additive diameter determined based on a propagation delay difference of the at least two input paths to a SCC and a number of complex feed-forward components within at least one input path. In response to the reconvergent fanin input to the SCC providing a binate function, the method computes a multiplicative diameter for the SCC utilizing a least common multiple (LCM) derived from one or more propagation delay differences across each reconvergent fanin input leading to the SCC. | 11-14-2013 |