International Business Machines Corporation

Robert Lowell Kanzelman

Jason Raymond Baumgartner

Hari Mony

Viresh Paruthi

Michael L Case

Wolfgang Roesner

Alexander Ivrii

Pradeep Kumar Nalla

Raj Kumar Gajavelly

Geert Janssen

Mark A Williams

Scott Henry Mack

Anthony DeGroff Drumm

Brian C Wilson

Mihir Choudhury

Ayesha Akhter

Jason Raymond Baumgarter

Lance Gordon Thompson

Ali S El-Zein

Bruce George Rudolph

Victor A Acuña

Robert F Damiano

Kenneth Michael Caron

Dheeraj Baby

Rohit Dureja

Kathy M McCarthy

Michael K Edwards

An example system includes a processor to receive a high-level design representation of a system architecture. The processor can synthesize a logic design and generate an associated synthesis history based on the high-level hardware design representation. The processor can then execute an equivalence check between the high-level design and the synthesized logic design based on the generated synthesis history.

Equivalence checking of synthesized logic designs using generated synthesis history

In an approach for optimization of integer arithmetic expressions implemented as a Boolean logic circuit, a processor converts arithmetic operators in an arithmetic expression into adders. A processor identifies a topological order of the adders. A processor merges the adders based on the topological order into a multi-operand adder. A processor converts the multi-operand adder to a compressor tree and a two-operand adder. A processor performs the arithmetic expression based on the converted multi-operand adder.

Optimization of arithmetic expressions

Embodiments of the invention are directed to a computer-implemented method of logic verification. The method includes obtaining a netlist of a circuit comprising a plurality of observable gates. A first observable gate is grouped together with a second observable gate based on a portion of a fan-in logic of the first observable gate being equal to a portion of a fan-in logic of the second observable gate. The group is expanded by including a third observable gate, based on a first strongly connected component (SCC) in the group having a similarity greater than a first threshold to a second SCC in the fan-in logic of the third observable gate. The group is further expanded by including a fourth observable gate, based on the distance of a portion of the fan-in logic of the fourth observable gate from a fan-in logic of at least one observable gate in the group of observable gates.

Grouping and partitioning of properties for logic verification

A computing system determines a first set of registers having constant next-state functions in the netlist. The computing system identifies an observable gate in fan-out of a register in the first set, wherein an observable gate is a gate that is critical to a verification or synthesis context. The computing system identifies a second set of reducible registers in the fan-in of the observable gate. The computing system modifies at least one of an initial value and a next-state function of at least one reducible register of the second set to reflect an observable value of the at least one reducible register observed at the observable gate. The computing system simplifies one or more logic gates implementing the observable gate and the fan-in of the observable gate by eliminating a reference to a constant next-state function register in the first set of registers.

Initial-state and next-state value folding

Embodiments of the present invention provides methods, computer program products, and a system for processing hierarchical references for a formal equivalence check. In certain embodiments, hierarchical references of a first design are identified as functionally equivalent to hierarchical references of a second design. Value outputs of the first design can be compared to the value outputs of the second design to determine whether the value outputs of the respective designs match.

Equivalency verification for hierarchical references

A logic verification program, method and system provide an efficient behavior when verifying large logic designs. The logic is partitioned by cut-nodes that dominate two or more RANDOMS and a check is performed for a given cut-node to determine whether any of the dominated RANDOMS can be merged to a constant by performing satisfiability checks with each RANDOM merged to a constant, to determine whether a range of output values for the given cut-node has been reduced by merging the RANDOM. If the range is not reduced, the RANDOM can be added to the set of merge-able RANDOMS along with the corresponding constant value. If the range has been reduced, the opposite constant value is tried for a node and if the range is reduced for both constants, then the cut-node is abandoned for merging that dominated RANDOM and the next dominated RANDOM is tried.

Verification complexity reduction via range-preserving input-to-constant conversion

Liveness verification of a logic design is performed using various shadow abstraction refinement techniques. An initial subset of state elements are included in the shadow abstraction, and verification is performed (liveness-to-safety conversion) using this initial subset. If a liveness counterexample is detected, the shadow abstraction is refined by designating a second subset of the state elements different from the initial subset for inclusion in a refined abstraction. The initial subset can be designated by choosing all registers in a combinational fan-in of a liveness property of the design. High-performance algorithms for abstract liveness-to-safety conversion can be based upon simulation and counterexample refinement, bounded model checking and counterexample refinement, bounded model checking and proof-based refinement, proofs obtained during bounded model checking of a precise liveness checking problem, a hybrid of counterexample-based refinement and proof analysis, and proofs obtained.

Method for scalable liveness verification via abstraction refinement

System and program product for scalable liveness verification via abstraction refinement

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.

Efficiently determining Boolean satisfiability with lazy constraints

Leveraging existing Binary Decision Diagrams (BDDs) to enhance circuit reductions in a system model representing a state machine as a netlist. The netlist is evaluated to determine the regions with the greatest potential reductions. BDD sweeping is performed to identify redundancies in the netlist. BDD rewriting implements the circuit reductions by replacing gates of the original netlist with more efficient equivalent logic.

Optimizing a netlist circuit representation by leveraging binary decision diagrams to perform rewriting

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.

Constructing inductive counterexamples in a multi-algorithm verification framework

Efficiently determining boolean satisfiability with lazy constraints

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.

Method and system for optimal diameter bounding of designs with complex feed-forward components

A computer-implemented method includes receiving an input containing a candidate netlist, a target, and a number, K, of cycles of interest, where K represents a number of cycles required to be analyzed for the proof-based abstraction. In response to receiving the inputs, a computing device builds an inductively unrolled netlist, utilizing random, symbolic initial values, for K cycles and provides the unrolled netlist with a first initial value constraint to a satisfiability (SAT) solver, with the first initial value constraint empty. The method includes determining whether a result of the SAT solver is satisfiable, and in response to the result not being satisfiable, performing an abstraction on the netlist and outputting the abstraction. However, in response to the result being satisfiable, the method includes performing one of: (a) outputting a valid counterexample of the original netlist; and (b) lazily adding initial value constraints to avoid spurious counterexamples.

Method and system for optimal counterexample-guided proof-based abstraction

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.

Growing community of inventors

Rochester, MN, United States of America

Robert Lowell Kanzelman