Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-01-31
2004-02-03
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C703S015000
Reexamination Certificate
active
06687882
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of circuit design. More specifically, the invention relates to the design of integrated circuits which may be modified or optimized during a design process.
BACKGROUND OF THE INVENTION
For the design of digital circuits on the scale of VLSI (Very Large Scale Integration) technology, designers often employ computer-aided techniques. Standard languages such as hardware description languages (HDLs) have been developed to describe digital circuits to aid in the design and simulation of complex digital circuits. Several hardware description languages, such as VHDL and Verilog, have evolved as industry standards. VHDL and Verilog are general-purpose hardware description languages that allow definition of a hardware model at the gate level, the register transfer level (RTL), or the behavioral level using abstract data types. As device technology and design technology continues to advance, various product design tools have been developed to adapt HDLs for use with newer devices and design styles and to also allow for the optimization of a design after the compilation of an HDL code which describes a particular circuit.
FIG. 1
illustrates an example in the prior art in which a circuit is initially designed and then optimized in the design process. The optimized design typically must be compared with the original design to verify that the optimized design is equivalent to the initial or original design. This is often required because the optimization process may result in a change to the design which causes the second design (e.g. an optimized design) to not be an equivalent circuit such that the optimized design does not produce the same result for a given input as the initial design.
The process of
FIG. 1
starts at block
100
. At block
110
, an HDL code is prepared for a particular circuit. This code is typically compiled in an HDL compiler to generate a first RTL netlist, as shown in block
120
. Then at block
140
, the first RTL netlist is processed in order to optimize the design which results in a technology map. The optimization process may include, for example, redundancy removal, state machine re-encoding, flip-flop replication, retiming, pipelining, half-cycle scheduling, and conversions between clock gating and enables.
At block
160
, a verification tool, such as a commercially available verification software product, is used to check for equivalence between the first RTL netlist and the technology map. At block
170
, the use of this tool results in a test to determine whether the two netlists are equivalent. If these two netlists are not equivalent, this results in an error message being displayed to the designer by the verification tool, as shown in
180
. On the other hand, if the verification tool can verify that the two netlists are equivalent, then an indication of this equivalence is displayed to the designer and the process may proceed to block
190
in which place and route tools are used to create an integrated circuit from the technology map. The process stops at block
200
.
Typically in the prior art, the equivalence checking of the first RTL representation and the mapped representation performed in block
160
requires an exhaustive simulation of the circuits by going through all possible input vectors.
FIG. 2A
illustrates an example of a circuit used to test for non-equivalence. The circuit
200
includes five (5) inputs
210
-
214
and one output
215
.
FIG. 2B
is a truth table illustrating the 32 input vectors for the circuit
200
. Equivalence checking tools that are commercially available include Formality from Synopsis, Mountain View, Calif., Crysalys from Avant!, Fremont, Calif., Formal Pro from Mentor Graphics, Wilsonville, Oreg., Conformal from Verplex, Milpitas, Calif., etc. When the circuit has a large number of input vectors, the testing of the circuit using all of the input vectors can require a lot of memory and be very time consuming.
SUMMARY OF THE INVENTION
According to one aspect of the present invention, an exemplary method for determining non-equivalence between two netlists is disclosed. Matched registers between the two netlists are determined. The matched registers become cut off points to generate primary inputs and outputs. When there are one or more unmatched registers between the first netlist and the second netlist, the unmatched registers are pushed to the primary inputs or outputs using retiming. The primary inputs of the resulting circuits after using retiming are then driven by a function of subspace variables. The circuits are then verified with all possible values of the subspace variable.
The present invention also discloses apparatuses, including software media which may be used to design integrated circuits. For example, the present invention includes digital processing systems which are capable of designing integrated circuits according to the present invention, and the invention also includes machine readable media, which when executed on a digital processing system such as a computer system, causes the digital processing system to execute a method for designing integrated circuits.
REFERENCES:
patent: 5452239 (1995-09-01), Dai et al.
patent: 5633813 (1997-05-01), Srinivasan
patent: 5638381 (1997-06-01), Cho et al.
patent: 5862149 (1999-01-01), Carpenter et al.
patent: 5875112 (1999-02-01), Lee
patent: 5949691 (1999-09-01), Kurosaka et al.
patent: 6002861 (1999-12-01), Butts et al.
patent: 6035107 (2000-03-01), Kuehlmann et al.
patent: 6134705 (2000-10-01), Pedersen et al.
patent: 6163876 (2000-12-01), Ashar et al.
patent: 6167561 (2000-12-01), Chen et al.
patent: 6188934 (2001-02-01), Emura
patent: 6247163 (2001-06-01), Burch et al.
patent: 6336206 (2002-01-01), Lockyear
patent: 6415430 (2002-07-01), Ashar et al.
patent: 6449750 (2002-09-01), Tsuchiya
patent: 6457162 (2002-09-01), Stanion
patent: 6484135 (2002-11-01), Chin et al.
patent: 6490717 (2002-12-01), Pedersen et al.
patent: 6496955 (2002-12-01), Chandra et al.
patent: 6523155 (2003-02-01), Ruedinger
patent: 6530072 (2003-03-01), Hagerman et al.
patent: 6536018 (2003-03-01), Chisholm et al.
patent: 6609234 (2003-08-01), Kurupati
patent: 2002/0138812 (2002-09-01), Johannsen
patent: 2003/0023942 (2003-01-01), Kurupati
Burch et al., “Robust latch mapping for combinational equivalent checking”, 1998 IEEE/ACM International Conference on Computer-Aided Design, Nov. 8, 1998, pp. 563-569.*
Wohl et al., “Using ATP for clock rules checking in complex Scan Designs”, 15th IEEE VLSI Test Symposium, Apr. 27, 1997, p 130-136.*
Berman et al., “Functional comparison of logic designs for VLSI circuits”, 1989 IEEE International Conference on Computer-Aided Design, Nov. 5, 1989, pp. 456-459.*
Ashar et al., “Verification of RTL generated from scheduled behavior in a high-level synthesis flow”, 1998 IEEE/ACM International Conference on Computer-Aided Design, Nov. 8, 1998, pp. 517-524.*
Agrawal, “Choice of tests for logic verification and equivalence checking and the use of fault simulation”, Thirteenth Internation Conference on VLSI Design, Jan. 3, 2000, pp. 306-311.*
Caporossi et al., “Rule checking at the register level”, IEEE Spectrum, vol. 33, No. 6, Jun. 1996, pp. 72-73.*
Cerny et al., “Tautology checking using cross-controllability and cross-observability relations”, 1990 IEEE International Conference on Computer-Aided Design, Nov. 11, 1990, pp. 34-37.*
Williams et al., “Equivalence checking of hierarchial combinational circuits”, Proceedings of the 6th IEEE International Conference on Electronics, Circuits and Systems, vol. 1, pp. 355-360.*
Ribas-Xirgo et al., “On the reuse of symbolic simulation results for incremental equivalence verification of switch-level circuits”, Proceedings of Design, Automation and Test in Europe, Feb. 23, 1998, pp. 624-629.*
Paruthi et al., “Equivlance checking combing a strutural SAT-solver, BDDs, and simulation”, Proceedings of 2000 International Conference on Computer Design, Sep. 17, 2000, pp. 459-464.*
Joshi et al., “Design of provably correct storage a
Mahajan Sanjeev
McElvain Kenneth S.
Blakely , Sokoloff, Taylor & Zafman LLP
Kik Phallaka
Smith Matthew
Synplicity, Inc.
LandOfFree
Methods and apparatuses for non-equivalence checking of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatuses for non-equivalence checking of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatuses for non-equivalence checking of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3292135