Synopsys, Inc.

James Herbert Kukula

Robert F Damiano

Per Mattias Bjesse

Yunshan Zhu

Thomas Robert Shiple

Carl Preston Pixley

Pei-Hsin Ho

Rajeev Kumar Ranjan

Bharat Kalyanpur

Joseph T Buck

Jerry R Burch

Yirng-An Chen

Brian Eugene Lockyear

A method for digital circuit design. The first step of the process is the step of providing a circuit design in the form of a hardware definition language. Then, the process produces a binary simulation of the design by setting out for each unit of time during execution of the hardware design the a control state and a program state of the design and assigns a symbol to each signal of the design. The process proceeds by executing a symbolic simulation of the design, concluding with identifying and capturing the combinational logic expression of the simulation output and the next state functions of the simulation.

Method for modeling an HDL design using symbolic simulation

One embodiment of the present invention provides a system that routes a set of pairs of points during the design of an integrated circuit (IC) chip. The system comprises a routing engine which is configured to search for a path to connect a current pair of points in the set of pairs of points, wherein the path comprises a set of rectangles and vertices. The routing engine uses a routing database, which keeps track of previously routed nets that can obstruct the routing of the current pair of points. The system further comprises a satisfiability (SAT) solver which is capable of solving a set of constraints, wherein the set of constraints are associated with the routability of the set of pairs of points. The SAT solver additionally comprises a SAT database which maintains the set of constraints and a current partial solution to the set of constraints. The SAT database is used to update the routing database if the current partial solution changes.

Integrating a boolean SAT solver into a router

A method for functional verification includes transforming an original multiphase circuit design into a phase-abstracted circuit design by identifying cyclical (repetitive) signals in the multiphase circuit design, determining a number of simulation phases for the multiphase circuit design, unwinding the multiphase circuit design by the number of phases to create an unwound design, and then applying logic reduction techniques to the unwound design using the clock-like signals to reduce (simplify) the logic in the unwound design by eliminating unused/unnecessary registers, inputs, outputs, and logic. The resulting phase-abstracted design can then be processed much more efficiently by functional verification engines than the original multiphase circuit design due to the reduced number of registers/inputs.

Phase abstraction for formal verification

An approach to solving combinational constraints, comprising compile and generate phases, is presented. The compile phase constructs successive sets of constraints, each with a solution generator, according to blocks of a partition of the constraints' random variables. Interleaving conjunction of the constraints, with existential quantification of the constraints, is attempted. The generate phase uses a reverse-order, block-by-block, process for solving constraints, where variables of each solution generator processed have been predetermined, by the processing of earlier blocks, except for the random variables of the current block. The present invention can be used in conjunction with image computation. Successive sets of reachable states of an FSM at successive time steps can be determined by successive applications of the compile phase, with each set of solution generators being saved. The sets of solution generators permit a backward sequence of states, from an error state back to a start state, to be determined.

Method and apparatus for solving constraints

A method for formal verification includes a latch remodeling process to reduce computational requirements for clock modeling. Latches that exhibit flip flop-like output behavior in a synthesized layout of sequential logic are identified and replaced with flip flops to generate a remodeled layout. This latch replacement can be performed using rules that filter out latches that do not exhibit flip flop-like output behavior. Clock modeling is then performed on the remodeled layout. Because the remodeled layout contains fewer latches than the original synthesized layout, the computational expense and time required for clock modeling (and hence, formal verification) on the remodeled layout can be significantly reduced over the requirements for clock modeling (and formal verification) on the original synthesized layout.

Latch modeling technique for formal verification

One embodiment of the present invention provides a system that verifies whether a trace can be produced by a generator. A generator is defined as a finite state machine with a set of input and output signals. A trace is defined as a sequence of assignments of non-parametric input and output signals of the generator. The generator may contain parametric inputs to model non-determinism. The trace does not contain assignments of the parametric inputs. During operation, the system builds a data structure to determine if there exists a sequence of parametric input assignments that can match the non-parametric inputs and outputs of the generator with the ones specified in the trace.

Method and apparatus for performing generator-based verification

A decomposition technique, for solving combinational constraint expressions, is presented. Decomposing a set of constraints can increase the opportunities for dividing them into independent sets that do not need to be conjoined in a constraint-solving process using a BDD representation. An AND decomposition, relying on a Theorem 1, is presented. An OR decomposition, relying on a corollary of Theorem 1, is presented. Theorem 1 provides an operation to test for, and create, a pair of sub-constraints G and H which are independent in any two variables xand x. A decomposition procedure is presented for separating as many variables as possible, of an input constraint, into disjoint sub-constraints. A merging procedure is presented, that can be used if a decomposition does not only contain constraints whose support sets are disjoint from each other. The decomposition procedure can also be used to identify hold constraints.

In a finite state machine (FSM) a set of goal states, to be searched for their reachability from a start state, is defined. An overapproximated path is found from a start state to a goal state by a forward approximation technique. The overapproximated path representation relies upon a partitioning of the state and input bits of FSM. A state matrix of the overapproximated path is organized by time-steps of FSMalong a first dimension and by partitions of FSMstate bits along a second dimension. An underapproximated path, along the path of the stepping stone matrix, is determined. Underapproximation is typically accomplished by simulation. A sequence of states to be output is updated with the underapproximated path. If a start to goal state sequence has been found, the procedure ends. Otherwise, the above steps of over and under approximation are repeated, using the results of the last underapproximation as a start state.

Method and apparatus for formally constraining random simulation

A method and system for an automata-based approach to state reachability of an interacting extended finite state machine. The present invention comprises a computer system having a processor, and a memory coupled to the processor via a bus, the memory containing computer readable instructions which when executed by the processor cause the processor to implement a process in accordance with the present invention. A digital system is modeled as an extended finite state machine. Automata operations are applied to the extended finite state machine to efficiently compute a set of reachable states from an initial state. The design of the system is verified by determining whether the set of reachable states includes an undesirable state.

Growing community of inventors

Hillsboro, OR, United States of America

James Herbert Kukula