JPH07230484A - Limited-state machine-transition analyzer - Google Patents

Abstract

PURPOSE: To make the verification on the design and the performance of a finite state machine(FSM) advantageous. CONSTITUTION: A synthesis tool 28 adopts the formal details of a logic circuit where FSM is buried as input and generates the gate level details of the logic circuit. A state table script generator 30 adopts the same formal details of the logic circuit as input and generates a state table extraction instruction file for FSM. A state table extraction tool 32 adopts the gate level details of the logic circuit and the state table extraction instruction file for FSM as inputs and generates the state table for FSM. A simulation driver 34 adopts the state table for FSM, adopts the gate level details of the logic circuit and multiple function vectors as inputs in cooperation with a simulator, simulates the logic circuit, and generates a simulation result for FSM. Then, a mutual operation reporter 38 generates an analysis result.

Description

Detailed Description of the Invention

[0001]

This invention relates to the field of integrated circuit design,
In particular, it relates to verification of integrated circuit designs. The present invention relates to the analysis and verification of finite state machines embedded in the design of very large scale integrated circuits.

[0002]

BACKGROUND OF THE INVENTION Finite state machines (FSMs) are an integrated part of any logic circuit. A typical use of them is control logic, where
The output depends not only on the current input to the circuit, but on the cumulative result of all previous inputs.

Therefore, the FSM is a synchronous sequential
It can be thought of as an abstract model that describes a machine. In this model, the results of all previous inputs to outputs are described by the current state of the machine.

In other words, if I is the set of possible input pairs, then Z is the set of possible output couplings and Q
Is a set of possible states, output ZkeZ is generated each time IjeI is applied when the machine is in state QieQ, the machine is in state QmeQ and Zk and Qm are I
It is uniquely determined by j and Qj.

FSMs are typically used to implement complex decision sequences and therefore can be very difficult to validate. Especially after being embedded as part of a large scale integrated circuit design. There are two problems to be pointed out in the verification of finite state machines.

The first problem is design verification, and the second problem is implementation verification. Design verification refers to the issue of whether the system has been correctly identified. This can only be done through simulation of a model of the entire logic circuit. Typically, a high level design language (HDL) is used to model the logic circuit and
Develop diagnostic tests and design circuits using a simulator.

Thus, verifying the FSM design is not impossible at all, but is often difficult. Therefore, it is desirable to be able to analyze and verify FSMs even after they have been embedded as part of a very large integrated circuit. Fulfillment validation, on the other hand, attempts to compare the HDL description with its fulfillment.

[0008] With the progress of synthesis algorithms, performance verification is becoming less important because the synthesized performance is correct. Nevertheless, it is desirable to be able to verify FSM implementation. As we will disclose,
The present invention provides a state machine transition analyzer that advantageously allows verification of FSM design and implementation.

[0009]

The state machine transition analyzer of the present invention is a state machine synthesis tool, a state table / script generator, a state table extraction tool,
Includes simulation driver, simulator, and interaction reporter.

The synthesis tool takes the formal specification of the logic circuit in which the FSM is embedded as an input and generates the gate level specification of the logic circuit. The state table script generator takes as input the same formal description of its logic circuit to create a state table extract instruction file for the FSM. The state table extraction tool inputs the gate level specification of the logic circuit and the state table extraction instruction file for the FSM, and creates a state table for the FSM.

The simulation driver adopts the state table for the FSM, and in cooperation with the simulator, adopts the gate level specification of the logic circuit and a large number of function vectors as inputs, and uses the logic circuit as the simulator.
Generate simulation results for M.

Finally, the Interaction Reporter takes as input the FSM simulation results, the state table, and user instructions to produce analysis results that allow verification of the FSM design and execution.

In one embodiment, commercially available packages for synthesis tools, state table extraction tools, and simulators are used. These state table script generators, simulation drivers and monitors, and interaction reporters are user created.

The state table script generator reads the formal description of the logic circuit and creates an executable state table extraction instruction file for the logic circuit. simulation·
When the driver and monitor are started, first the FSM
Load the state table of. Next is the simulation
Drivers and monitors repeatedly drive the simulator, causing the simulator to simulate the processing of multiple function vectors by logic circuits.

At the same time, the simulation driver and monitor log all clocks, inputs, states, and FSM output changes. At the end of this simulation, the simulation driver and monitor
Output the data entered for SM.

The Interaction Reporter uses an instruction decoder, a loader, a database, and the FS that uses the dumped data.
It includes a set of functional routines that support a number of functions for achieving M design and performance verification. The interaction reporter responds to user commands with a state table and FS.
Load M simulation results.

In response to additional user instructions, the interaction reporter produces an analysis report containing the necessary information to verify the FSM design and implementation.

[0018]

DETAILED DESCRIPTION OF THE INVENTION In the following description, for purposes of explanation, specific numbers, materials and constructions are set forth in order to provide a thorough understanding of the present invention. However, it will be apparent to one skilled in the art that the present invention may be practiced without the details specified therein.

In another example, well known systems are shown in block diagrams in order not to unnecessarily obscure the present invention. Referring now to FIG. 1, an example of a computer system in accordance with the teachings of the present invention is shown.

The computer system 10 illustrated is a C
PU 12, memory 14, I / O circuit 16, input device 1
8 and mass storage 20. This memory 1
4 and I / O circuit 16 are coupled to CPUI2,
Input device 18 and mass storage 20 are coupled to I / O circuit 16.

These elements 12-20 are meant to represent a broad sense CPU, memory, etc. found in most computer systems. Their structure and function are well known and will not be described further.

Referring to FIG. 2, the contents of memory 14 of computer system 10 of FIG. 1 are shown in more detail. The figure shows an operating system 22, a number of programming language compilers, and a run-time library 2.
4 and the state machine transition analyzer 26 of the present invention is shown.

The state machine transition analyzer 26 is detailed below with reference to the remaining figures. Operating system 22 and compiler and run-time library 24 are meant to represent software in the broadest sense of these systems and subsystems. Their configurations and functions are well known and will not be described further.

In addition, based on the following description, it should be understood that the present invention can be implemented with other support system and subsystem software.

Referring now to FIG. 3, there is shown a block diagram illustrating the state machine transition analyzer of the present invention. The state machine transition analyzer 26 of the present invention includes a state machine synthesis tool 28 and a state table script generator 3.
0, state table extraction tool 32, simulation
It includes a driver 34, a simulator 36, and an interaction reporter 38.

Synthesis tool 28 takes a formal specification 40 of a logic circuit with an FSM embedded as an input and generates a gate level specification 44 for that logic circuit. The state table script creator 30 takes in the formal specification 40 of the same logic circuit as the input and creates a state table extraction command file 46 for the FSM.

The state table extraction tool 32 receives as inputs the gate level specification 44 of the logic circuit and the FS.
Take the M state table extraction file 46 and generate a state table 48 for the FSM. simulation·
The driver 34 takes as input the state table for the FSM, cooperates with the simulator 36 and takes as input the gate level description 44 of the logic circuit and a number of function vectors 43 to simulate the logic circuit, FS
Create a simulation result 50 for M.

Finally, the interaction reporter 38 takes the FSM simulation results 52 and the user instructions 42 as inputs and creates an analysis result 52 which allows verification of the FSM design and implementation.

The formal specification 40 of the logic circuit includes the encoding of the various states and the state register, ie the memory device containing the state values. This formal specification 40 also includes embedded comments with a predetermined syntax for identifying FSM register bits.

This logic circuit can be formally defined using a number of formal specification languages. Preferably, the formal language used is a formal language supported by commercially available synthesis tools and simulators. A specific example of such a formal language is VERILOG.

In one example, commercially available packages include synthesis tool 28, state table extraction tool 32,
And used for the simulator 34. A specific example of the simulator 34 is the VER made with the Hcadence Design System in San Diego, CA.
It is a simulation utility for the ILOG system.

A specific example of the synthesis tool 28 and state table extraction tool 32 is the SYNOPSYS system state table extraction utility, which is made at the Synapsys of Mountain View, California.

See the various product literature provided by the respective manufacturers to further explain these various utilities. However, the state table / script creator 30, the simulation driver and the monitor 3
4. The interaction reporter 38 is created by the user. These will be described in more detail below with reference to FIGS. 4-6.

Referring to FIGS. 8 and 9, there are shown block diagrams showing FSM state tables and FSM simulation results. As shown in FIG.
The SM state table 48 includes a number of state transition row entries, each having four fields describing an input value 74, a current state 76, a next state value 78, and an output value 80.

As shown in FIG. 9, the FSM simulation result 50 has a number of modified input fields, each describing a clock value 82, an input value 84, a state value 86, and an output value 88. It has four fields. In each change entry field, at least one of the four values 84-88 is different from the previous change row entry field.

Referring to FIG. 4, a block diagram illustrating the operational flow of the state table script generator is shown in more detail. This state table script generator 3
0 reads the detailed description of the logic circuit 40. In step 63, the state table script generator 30 uses the embedded comment having the predetermined syntax described above to perform FS.
Identify the M register bits.

The state table script generator 30 further identifies the state coding constants in step 65, and identifies the top design name including the FSM in step 67. Then, this state table script generator 30
Creates the state table extraction command file 46 based on these identified information. An example of the state table extraction command file 46 is shown in FIG.

Referring to FIG. 5, there is shown a block diagram illustrating a more detailed operational flow of the simulation driver and monitor. The simulation driver and monitor, when started, first loads the FSM state table at step 64.

Next, the simulation driver and monitor, at step 66, repeatedly drive the simulator to cause it to simulate the processing of multiple function vectors by the logic circuit. At the same time, the simulation driver and monitor monitors and writes in step 68 all clock, input, state, and output changes of the FSM.

At the end of this simulation, branching to NO at step 70, the simulation driver and monitor output the entry data for the FSM at step 72. SYNOPSYS and VERI
Commercial packages such as LOG are preferred for state table extractors and simulators, and because state table output formats and programming interfaces are well known, implementations of simulation drivers and monitors with the above operational flow are within the skill of those in the art. Within capability.

Referring to FIG. 6, there is shown a block diagram detailing the major functions of the interaction reporter. The interaction reporter 38 includes an instruction decoder 54, a loader 5
6, database 60, and a number of function routines that support a number of functions for performing FSM design and implementation verification using dumped data for the FSM.

The loader 56 is a "rea" for loading the FSM simulated results 50 and the state table 48.
Supporting the "d-stor-mon" instruction, database 60 preferably stores state table 48 and FSM simulation results 50 in a format suitable for fast query and retrieval.

In addition, it is preferable that the loading of FSM simulation results can be done incrementally.
For function routines 58, it is preferable to support those instructions.

Next [n] for tracing the state machine to the next output change, st for tracing the state machine to the next input / output change
ep [n], g to trace the state machine from start to end
o CONT to continue tracing from the current state CONT current state information and current transition range (transition range = number of transitions taken x 100 / total number of possible transitions) states such as where state name Report statistical information about the whatis state or state machine to show information rep
ort

The instruction decoder 54 decodes the user instructions 42 and calls the loader 56 and the appropriate function routine 58. Initially, interaction reporter 38 loads state table 48 and FSM simulation results 50 into database 60 in response to user instructions 42.

In response to the additional user command 42, the interaction reporter 38 prepares an analysis report for various verification information. In particular, with the preferred instruction set, the user can use the interaction reporter 38 to create an analysis report 52 that prepares the answers to:

A, the number of state transitions taken and the current state and input conditions b, state transitions not acted on by the function vector c, attempted illegal state transitions d, whether there is a state in which the FSM is unreachable e, Transition range f (incremental) prepared by function vector set (s), improved range for function vector set (s)

From these answers, the user can verify the FSM design and implementation. Instruction decoder 54, loader 56, database 60, and function routine 58 can be implemented in various ways, using the functions and features described above, all of which are within the ability of one of ordinary skill in the art.

Although the present invention has been described in terms of presently preferred alternative embodiments, those skilled in the art will recognize that the present invention is not limited to the described embodiments. The method and apparatus of the invention may be modified and practiced within the spirit and scope of the appended claims. This description is given as an explanation of the invention and is not intended to be limiting.

[0050]

According to the present invention, it is possible to provide a state machine transition analyzer that allows the verification of FSM design and implementation advantageously.

[Brief description of drawings]

FIG. 1 is a system block diagram of an example of a computer system according to the teachings of the present invention.

FIG. 2 is a block diagram showing the contents of a memory of the computer system shown in FIG. 1 in more detail.

FIG. 3 is a functional block diagram of the state machine transition analyzer of the present invention.

FIG. 4 is an operational flow diagram showing further details of a state table script generator.

FIG. 5 is an operational flow diagram of a state machine transition analyzer simulation driver and monitor.

FIG. 6 is a more detailed block diagram of an interaction reporter of a state machine transition analyzer.

FIG. 7 is a chart showing an example of a generated state table extraction command file.

FIG. 8 is a chart showing a state table for the FSM.

FIG. 9 is a chart showing FSM simulation results.

[Explanation of symbols]

 26 State Machine Transition Analyzer 28 Synthesis Tool 30 State Table Script Generator 32 State Table Extraction Tool 34 Simulation Driver 36 Simulator 38 Interaction Reporter

 ─────────────────────────────────────────────────── ─── Continued Front Page (72) Inventor Shaddle Kazi San Jose Cross Springs Court, California, USA 1077 (72) Inventor Jim Ye, Pleasanton Paseo Santa Maria, California, USA 6390

Claims (20)

[Claims] 1. At least one finite state machine (FS)
M) and a formal specification of a logic circuit having a function vector for simulating at least one set of logic circuits, a device for analyzing and verifying said at least one FSM design and implementation,
Said apparatus comprising: a) combining means for producing a gate level specification of said logic circuit in response to said official specification of said logic circuit; and b) said at least one FSM in response to said official specification of said logic circuit. State table creating means for creating a state table for each; and c) in response to the gate level specification of the logic circuit, the at least one state table for the at least one FSM, and the at least one set of function vectors. Simulation means for simulating at least one FSM and producing a simulation result thereof; and d) reporting means for producing an analysis report in response to the simulation result of the at least one FSM and user input. And computer system. 2. The apparatus according to claim 1, wherein the state table creating means comprises: b. 1) command script creating means for creating at least one state table extraction command script file for the at least one FSM in response to the formal specification of the logic circuit; b. 2) A computer including the gate level specification of the logic circuit and state table creating means for creating the at least one state table for the at least one FSM in response to the at least one state table extraction instruction script file. system. 3. The apparatus according to claim 2, wherein said instruction script creating means reads said formal specification of said logic circuit, FSM register bit, status encoding constant and FS.
A computer system that identifies each top design name, including M, and creates the at least one state table extraction instruction script file based on the identified information. 4. The apparatus according to claim 2, wherein the simulation means includes: c. 1) Driving and monitoring means for responsive to at least one state table for said at least one FSM to generate a simulation command to monitor simulated signal changes and to generate a simulation result for said at least one FSM. And c. 2) a simulator coupled to the driving and monitoring means for simulating the logic circuit in response to the simulation instructions, the gate level specification of the logic circuit and the at least one set of function vectors. Characteristic computer system. 5. The apparatus according to claim 4, wherein the driving and monitoring means loads at least one state table for the at least one FSM upon starting, the driving and monitoring means further comprising the simulator. Repeatedly generate simulation commands for each FSM
In contrast, the applicable signal generated by the simulator is recorded, and the driving and monitoring means further creates the simulation result for the at least one FSM based on the recorded applicable signal when the simulation is completed. A computer system characterized by: 6. The apparatus of claim 1, wherein the reporting means is d. 1) an instruction decoder for decoding user instructions, d. 2) a loader working with the instruction decoder for loading simulation results for the at least one state table and at least one FSM; d. 3) a database for accumulating the at least one state table and simulation results; d. 4) A plurality of functional routines cooperating with the instruction decoder and the database to achieve a plurality of reporting and related functions. 7. The computer system of claim 6, wherein a loader responsive to the user instructions loads the simulation results in an incremental manner. 8. The apparatus of claim 6, wherein the functional routine is d. 41) A first functional routine for following the operation of the FSM to its next output change, and d. 42) a second functional routine for following the operation of the FSM to its next input / output change. 9. The apparatus of claim 6, wherein the functional routine is d. 41) A first function routine for tracing the operation of the FSM from start to end, and d. 42) a second functional routine for restarting the tracing of the operation of the FSM from the current state. 10. The apparatus of claim 6, wherein the functional routine is d. 41) A first function routine for displaying FSM current state information and current transition range; d. 42) a second functional routine for displaying status information. 11. At least one finite state machine (F
SM) and a formal specification of a logic circuit having a function vector for simulating at least one set of logic circuits, a method of analyzing and verifying said at least one FSM design and implementation,
Said method comprising: a) creating a gate level specification of said logic circuit in response to said official specification of said logic circuit; and b) each of said at least one FSM in response to said official specification of said logic circuit. C) creating a state table for: c) the gate level specification of the logic circuit, the at least one state table for the at least one FSM, and the at least one FSM in response to the at least one set of function vectors. And creating an analysis report in response to the at least one FSM simulation result and user input. 12. The apparatus of claim 11, wherein step b) comprises b. 1) creating at least one state table extract instruction script file for the at least one FSM in response to the formal specification of the logic circuit; b. 2) creating the at least one state table for the at least one FSM in response to the gate level specification of the logic circuit and the at least one state table extraction instruction script file. 13. The method of claim 12, wherein the step b. 1) includes: (b.11) reading the formal specification of the logic circuit; (b.12) FSM register bits, state encoding constants,
And (b, 13) at least 1 based on the identified information, each top design name including
Creating one state table extract instruction script file. 14. The method of claim 12, wherein step (c) comprises: c. 1) generating a simulation command in response to at least one state table for said at least one FSM to monitor simulated signal changes and produce a simulation result for said at least one FSM; c. ． 2) simulating the logic circuit in response to the simulation instructions, the gate level specification of the logic circuit and the at least one set of function vectors. 15. The method of claim 14, wherein said step (c.1) comprises: c. 11) At the start, the at least one FS
Loading at least one state table for M; c. 12) repeatedly generating simulation instructions for the simulator and recording, for each FSM, the applicable signal generated by the simulator; c. 13) Upon completion of the simulation, based on the recorded applicable signal, the at least one FS
Further generating the simulation result for M. a computer system. 16. The method of claim 11, wherein said step (d) comprises d. 1) Decoding user instructions, d. 2) loading at least one state table and at least one simulation result for at least one FSM in response to the user command; d. 3) accumulating the loaded at least one state table and simulation results; d. 4) achieving a plurality of reporting and related functions responsive to the user instructions. 17. The method of claim 16 wherein the loading of the state table and simulation results in step (d.2) is accomplished in an incremental fashion. 18. The method of claim 6, wherein said step (d.4) comprises d. 41) tracing the operation of the FSM to its next output change; d. 42) tracing the operation of the FSM to its next input / output change. 19. The method of claim 16, wherein said step (d.4) comprises d. 41) tracing the operation of the FSM from start to end; d. 42) restarting from the current state of the trace of FSM operation. 20. The method of claim 16, wherein said step (d.4) comprises d. 41) displaying FSM current state information and current transition range; d. 42) displaying the status information.