Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-05-12
2002-11-26
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06487704
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention relates generally to automatically testing circuit design descriptions generated in an Electronic Design Automation (EDA) environment, and more particularly to identifying finite state machines and verifying circuit designs in a Verilog or VHDL environment.
2. Background Art
Electronic Design Automation (EDA) is a process for using computer programs to design, simulate, and test electronic circuits before fabricating them in silicon. Verilog and VHDL are two languages commonly used to define circuits in the steps of design, simulation, and testing. Circuit designs are tested with the aid of various simulation/emulation software packages so that design flaws can be detected and corrected before any actual devices are fabricated. Testing a circuit design before it is fabricated saves design firms millions of dollars in non-recoverable engineering (NRE) costs; however, as the circuit design complexity increases, so too does the difficulty of testing. Since system designers are asked to design and test these increasingly complex circuits in ever smaller time frames, designers must choose between either taking more time to test the design, and thereby delaying product shipment, or only testing portions of the circuit, and thereby increasing the risk that many undiscovered bugs remain in the design.
Various simulation and test products on the market attempt to increase the efficiency of circuit design verification. One approach speeds up the design simulation programs. Native Code Simulators, Simulation Acceleration, and Chip Emulation Systems decrease the time it takes to simulate a design, and may decrease the time it takes to identify the next bug in a design. However, during early stages of the design process, design bugs are prevalent, and speeding up the simulation does little to help identify the bugs.
Another approach tests the circuit design randomly. Random testing involves generating randomly related unique test vectors and testing (or “exercising”) the design with these vectors. In this approach, as time allotted for random testing increases, more of the circuit design is tested. Random testing is time consuming and risky, since discovering bugs is hit or miss, and there usually is not sufficient time to fully test the circuit design. Running a random simulation ten or one hundred times longer may not significantly increase the verification density.
Other types of EDA testing tools, such as Automatic Test Pattern Generation (ATPG) tools, produce tests which only identify manufacturing defects in already-fabricated circuits. Testing is performed by successively applying known input values to the pins of the circuit, and then comparing actual output values with sets of expected output values. However, ATPG tools assume that the circuit design is fundamentally correct and that any anomalies discovered are due to physical defects such as wire breaks, introduced during manufacturing.
Other EDA testing tools, such as Verilint, developed by InterHDL of Los Altos, Calif.; Vericov, developed by Simulation Technology of Saint Paul, Minn.; Vera, developed by System Science of Palo Alto, Calif.; and Specman, developed by Verisity of Yehud, Israel are difficult to use, sell, and integrate into a test bench for verifying circuit designs.
Many circuit designs also include Finite State Machines (FSMs) which are complex and often a source of bugs. Thus, circuit designers are particularly interested in exercising the full range of behavior of an FSM as early in the testing process as possible. Existing test tools require designers to manually identify and define each of the states and transitions present in each FSM in the circuit before testing can commence.
What is needed is a system and method for identifying finite state machines and verifying circuit designs that increases the efficiency of circuit design testing.
SUMMARY OF THE INVENTION
The present invention provides a method and a system for identifying finite state machines and verifying circuit designs. The invention automatically identifies and tests input, output, and internal variables, finite state machines (FSMs), transitions elements, blocks, arcs, and paths of interest elements in a design description of a circuit.
The process of identifying elements first identifies a set of constructs in the design description. Next, a construct in the set of constructs and an object in the construct are identified. A first subset of constructs in the set of constructs, which can change, or control a change of a value of the object, are then identified. A second sub set of constructs in the set of constructs, whose values can be changed directly or indirectly by the object, are also identified. The identified construct, object, and first and second subsets of constructs are then stored in a relational database. The identifying and storing steps are then repeated for all objects in the construct and for all constructs in the set of constructs.
A finite state machine in the design description is identified by searching the relational database for a first object which controls changes of a value of a second object and whose value is also changed directly or indirectly by the second object. The first object is identified as an FSM state variable, if an occurrence of the first object precedes an occurrence of the second object. The second object is identified as an FSM state variable, if an occurrence of the second object precedes an occurrence of the first object. FSM state transition elements are identified as transitions from a first allowable state to a second allowable state in a set of allowable states of the FSM state variable.
Systems using the invention store a design description in a design database. A test generator identifies any finite state machine elements in the design description. Based on the design description retrieved from the design database a test bench then generates a simulated design. A coverage analysis tool monitors output data from the simulated design executing on the test bench and identifies which elements of the design remain to be tested. The test generator then generates test vectors, which are sent to the test bench, for exercising the untested elements.
Compared to the prior art the invention is advantageous because it automates a critical part of design verification which has been performed manually and sporadically due to time and resource requirements. The invention permits testing of input, output, and internal variables, finite state machines, transitions elements, blocks, arcs, and paths of interest elements in a design description, quickly, easily and comprehensively, in an integrated process. As a result, designers can proceed toward fabrication with confidence that the simulated design has been verified. A time savings of months is achieved, since any design flaws are discovered before the simulated design is fabricated.
These and other aspects of the invention will be recognized by those skilled in the art upon review of the accompanying drawings, detailed description and claims.
REFERENCES:
patent: 5469443 (1995-11-01), Saxena
patent: 5517432 (1996-05-01), Chandra et al.
patent: 5528553 (1996-06-01), Saxena
patent: 5539680 (1996-07-01), Palnitkar et al.
patent: 5555270 (1996-09-01), Sun et al.
patent: 5659555 (1997-08-01), Lee et al.
patent: 5680332 (1997-10-01), Raimi et al.
patent: 6041429 (2000-03-01), Koenemann
patent: 6141630 (2000-10-01), McNamara et al.
Chien Chiahon
Massey David Todd
McNamara Michael
Tan Chong Guan
Glenn Michael A.
Siek Vuthe
Verisity Design, Inc.
Wong Kirk D.
LandOfFree
System and method for identifying finite state machines and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for identifying finite state machines and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for identifying finite state machines and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2966492