Method and Apparatus for Analyzing Finite State Machines

1. Field of Invention

The present invention relates to the field of hardware design verification. In particular, the present invention describes a method and apparatus for analyzing and verifying finite state machines (FSM).

2. Description of Related Art

Many electronic circuits, like microprocessors and microcontrollers, are designed with high level hardware description languages like Verilog, and VHDL. See "The Verilog HDL Language Reference Manual," Open Verilog International, 1992, and "IEEE 1076-1987 Standard VHDL Language Reference Manual", March 1988, for further information on these languages. To save time and money, designers prefer to verify their designs prior to fabricating their circuits. One aspect of the verification process includes verifying the finite state machines (FSM) incorporated in a hardware description. This process includes simulating the FSM's operation with a number of test vectors. Test vectors, or driver data, are stimuli for the simulator and are well known.

A finite state machine is a description of a physical process that includes states. That is, an FSM provides a solution to a sequential physical problem. The sequential physical problem requires that before some output is allowed, a specific set of inputs must have been received in a sequential manner. The FSM generates outputs according to past information and present inputs. Microcontrollers and microprocessors work in this manner.

Each FSM includes a number of states and a number of arcs between the states. The arcs define the transitions between the states. A particular arc is taken from a particular state, depending upon the inputs to the finite state machine. Finite state machines are described in, W. I. Fletcher, "An Engineering Approach to Digital Design," 1980 (Prentice-Hall: Englewood Cliffs, N.J.).

To verify FSMs, prior art analyzers have depended on post processing to determine the test coverage of a set of test vectors. That is, for a given FSM design, and a given set of test vectors, a large dump file is generated. This dump file contains information about the state of numerous signals in the hardware description. The post processing extracts statistical information from the dump file and generates a summary of the coverage of the test vectors. Typically, the summary includes the arcs traversed, the arcs missed, the states accessed, states missed, etc. This summary provides an indication of how well the test vectors covered all the states and arcs in the FSM (the sufficiency of the test coverage). The best test coverage will include the accessing of all the states and the traversing of all the arcs.

These prior art systems have a number of drawbacks. The dump files are very large. Creating, and then reading, these files takes a considerable amount of time. For example, a typical regression of 50000 cycles for a FSM with seven states and five inputs will require the time to create a dump file of 100 Mbytes. This example is for a relatively small FSM; there can be hundreds of larger FSMs in a large design. This takes time away from a designer's ability to experiment with the hardware description. Therefore, it is desired that FSM analysis occur without the need for post processing, and in particular, without the need for post processing a large simulation dump file.

Another prior art analyzer requires the designer to generate a separate file defining valid state transitions in a state table format. This state information defines the FSM. This requires additional work on the designer's part. For example, the MEG analyzer, available from University of California, Berkeley, requires the further definition of the FSM using state tables or the like. See Hamachi, G. "Designing Finite State Machines with PEG." in: 1986 VLSI Tools: Still More Works by the Original Artists (EECS, University of California, Berkeley, 1985, Report No. UCB/CSD 86/272), and the "Berkeley CAD Tools User's Manual", Ibid., for further information on MEG. The user must input the state table to the analyzer. Ideally, a designer should not be burdened with having to define such state table information. The designer should be allowed to define the hardware description and have the FSM verified without also having to define the FSM state table information. Therefore, it is preferred that the state table be automatically generated.

Further, the prior art systems, like MEG, use programming language interface (PLI) routines. These routines are used to enhance the capabilities of Verilog by defining a designer's own functions. However, often PLI routines are not compiled; therefore, analyzers using these routines execute substantially slower than analyzers not using these routines. Therefore, it is desired that an analyzing tool be implemented using Verilog compiled code rather than PLI routines.

Therefore, what is desired is an improved method and apparatus for analyzing finite state machines (FSM).

A method and apparatus for analyzing finite state machines (FSM) is described. The present invention removes the need to generate a large dump file in response to simulating a hardware description with test vectors. One embodiment includes a computer system for generating a summary of test coverage for a hardware description. The hardware description corresponds to a finite state machine (FSM). This embodiment requires at least one test vector. The computer system comprises a memory and a processor. The memory is for storing the hardware description and the test vector. The processor, coupled to the memory, uses the hardware description and generates state information corresponding to the FSM. The processor, using the state information, further generates a first description. The first description includes a description for monitoring states and signals in the hardware description. The processor, using the test vector, the hardware description and the first description, further generates the test coverage summary.

In another embodiment, the hardware description is written in Verilog code and the processor executes a design compiler to extract the state information. The processor uses a hardware simulator to generate the summary information. Thus, this embodiment has the advantage of integrating well with presently available systems.

In another embodiment, the processor is further for accessing a second summary, and the processor is further for generating a third summary corresponding to the summary, and the second summary. The second summary corresponds to at least one other test vector. Thus, the third summary corresponds to a summary of the coverage of at least the first test vector and the second test vector.

The present invention is illustrated by way of example, and not limitation, in the figures. Like references indicate similar elements.

FIG. 1 illustrates a computer system upon which the present invention may be implemented.

FIG. 2 illustrates an example of a finite state machine (FSM).

FIG. 3 is a flow diagram showing a method of analyzing a FSM to generate a result file.

FIG. 4 is a flow diagram showing a method of performing post processing on a number of result files to generate a summary file.

FIG. 5a and FIG. 5b are a flowchart of a method of generating a monitor file.

A method and apparatus for analyzing finite state machines (FSM) is described. In the following description, numerous specific details are set forth such as monitor file content, etc., in order to provide a thorough understanding of the present invention. It will be obvious, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known hardware description language constructs, circuits, structures and techniques have not been shown in detail in order not to unnecessarily obscure the present invention.

Referring to FIG. 1, a computer system upon which an embodiment of the present invention can be implemented is shown as 100. Computer system 100 comprises a bus 101, or other communications hardware and software, for communicating information, and a processor 109 coupled with bus 101 for processing information. System 100 further comprises a random access memory (RAM) or other dynamic storage device 104 (referred to as main memory), coupled to bus 101 for storing information and instructions to be executed by processor 109. Main memory 104 also may be used for storing temporary variables or other intermediate information during execution of instructions by processor 109. Computer system 100 also comprises a read only memory (ROM) 106, and/or other static storage device, coupled to bus 101 for storing static information and instructions for processor 109. Data storage device 107 is coupled to bus 101 for storing information and instructions.

Furthermore, a data storage device 107, such as a magnetic disk or optical disk, and its corresponding disk drive, can be coupled to computer system 100. Computer system 100 can also be coupled via bus 101 to a display device 121 for displaying information to a computer user. Display device 121 can include a frame buffer, specialized graphics rendering devices, a cathode ray tube (CRT), and/or a flat panel display. An alphanumeric input device 122, including alphanumeric and other keys, is typically coupled to bus 101 for communicating information and command selections to processor 109. Another type of user input device is cursor control 123, such as a mouse, a trackball, a pen, a touch screen, or cursor direction keys for communicating direction information and command selections to processor 109, and for controlling cursor movement on display 121. This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), which allows the device to specify positions in a plane. However, this invention should not be limited to input devices with only two degrees of freedom.

Another device which may be coupled to bus 101 is a hard copy device 124 which may be used for printing instructions, data, or other information on a medium such as paper, film, or similar types of media. Additionally, computer system 100 can be coupled to a device for sound recording, and/or playback 125, such as an audio digitizer coupled to a microphone for recording information. Further, the device may include a speaker which is coupled to a digital to analog (D/A) converter for playing back the digitized sounds.

Also, computer system 100 can be a terminal in a computer network (e.g., a LAN). Computer system 100 would then be a computer subsystem of a computer system including a number of networked devices.

An example of a finite state machine is shown in FIG. 2. For the purpose of this example, assume the state machine of FIG. 2 represents a discrete logic circuit for turning a light on for a set period of time and then off. Note that this figure illustrates a Mealy model of an FSM, however the present invention should not be restricted to only Mealy models of FSMs. The FIG. 2 state machine includes three states: Set0 210, Hold0 220 and Set 1 230. Set0 210 is connected to Hold0 by arc 215. Hold0 220 is connected to Set1 230 by arc 222. Set1 230 is connected to Set0 210 by arc 235. Hold0 220 has another arc, arc 227, connected back to Hold0 220.

At initialization, the circuit will begin at state Set0 210. No matter what the value of the input, X, the output Z will be set to 0 (the light is off). The next state will always be Hold0 220, arc 215.

At state Hold0 220, the next state depends on the value of the input, X. If X=1, then arc 227 is traversed, and the next state is Hold0 220. Returning to the light example, assume that Z=0 means the light is off. If at state Hold0 220, X=1, then the Z remains at 0, and the discrete logic circuit will keep the light off. If X=0, then arc 222 is traversed to state Set1 230. Traversing arc 222 causes Z=0.

At state Set1 230, the next state is not dependent upon the input X. That is, the next state will always be Set0 210, arc 235. However, traversing arc 235 represents the discrete logic circuit turning the light on, Z=1. The next state is Set0 210. Traversing arc 215, sets Z=0, and turns the light off again. Thus, the light is turned on in response to a stimulus (X=0 at state Hold0 22), and then turned off again.

Further for the purposes of example, assume that a designer has written a hardware description of the discrete logic circuit. Typically, the hardware description includes a language description of an electronic circuit and/or an FSM for a physical process. To test whether the description, and therefore the hardware, will cause the light to turn on and turn off at the correct times, the designer will write a set of test vectors that will test the function of the hardware. That is, test vectors and the hardware description are used as input to a simulator.

To verify that the state machine of the hardware description works as desired, the test vectors should access all three states, and should traverse all four arcs. For small systems like the hardware required to implement the FSM of FIG. 2, this can be relatively simple. However, for large systems like microprocessors, thousands of states and arcs may be represented in the hardware description. The present invention streamlines the process of testing FSMs.

FIG. 3 is a flow diagram showing a method of analyzing a FSM to generate a result file. This flow diagram represents one embodiment of the present invention for streamlining the process of testing FSMs. In one embodiment, this flow diagram represents the processes executed by processor 109 and the data stored in at least one of the memory units, main memory 104, static storage device 106, or data storage device 107. In FIG. 3, square comer rectangles indicate processes, rounded comer rectangles indicate data. The hardware description file 310, the design compiler 330, the state table 340, the test vector file 370, and the analysis 380 are elements that are used in other systems for designing and testing FSMs, and, therefore are well known to persons skilled in the art.

The process begins with a hardware description file 310. This file typically contains a register transfer language (RTL) description of one or more FSMs. One of ordinary skill in the art would understand how to generate an RTL description of an FSM given the discussion herein. Appendix A includes an example Verilog-XL.TM. (Verilog-XL.TM. is a trademark of Cadence Design Systems Inc.) hardware description of the FSM of FIG. 2. In one embodiment, the Verilog-XL.TM. description language, version 1.6, from Cadence Design Systems Inc. of San Jose, Calif., is used. Note, in another embodiment of the present invention, VHDL is used to describe the FSM.

A compiler script file 320 can optionally be provided. The script automates the process of generating a state table file 340. This script uses Unix shell commands and one of ordinary skill in the art would understand how to generate such a script file given the description herein. If a script is not provided, then the designer must manually enter the commands to extract the state information. The design compiler 330 uses the hardware description file 310 to extract a state table representing the corresponding FSM. A suitable design compiler 330 which may be utilized is the Synopsys.TM. design compiler, available from Synopsys Inc. of Mountain View, Calif. See the "Synopsys Design Compiler Reference Manual, Version 2.2." Mountain View, Calif., Synopsys Inc., December 1991. The design compiler generates the state table file 340. The state table file 340 is one representation of the FSM defined in the hardware description file 310. The description of the format of a typical state table can be found in the Synopsys.TM. Design Compiler Reference Manual, Appendix E. Other representations of FSMs are supported directly. That is, state table file 340 may be replaced by another representation of an FSM. In another embodiment, other FSM representations are first translated into the Synopsys.TM. state table format before being accessed by FSM monitor generator 350.

The state table, describing the FSM, is automatically generated by design compiler 330. This is a significant improvement over the prior art in that a designer does not have to separately define a state table describing the FSM. Appendix B includes an example state table generated using a Synopsys.TM. design compiler, version 2.2b. This example state table corresponds to the FSM of FIG. 2.

The FSM monitor generator 350 accepts, as input, the state table file 340. First, FSM monitor generator 350 parses the necessary FSM information from state table 340. Typically, this information includes the number of states, the arcs between the states, and the input and output values for each arc. In one embodiment, a Unix yacc grammar file is used in the parsing of the state table file 340. One of ordinary skill in the art will understand how to write such a parser given the description contained herein. Further, the technique of creating a suitable Unix yacc grammar file should be well known to a person of ordinary skill in the art.

Next, FSM monitor generator 350 produces the data structures needed to represent the FSM. These data structures include the parsed FSM information. These data structures hold a representation of the FSM which is then used to create the monitor file 360. Data structures used include: a table of all arcs, represented by a two dimensional array; a valid arc lookup table; a current arc structure; and a listing of all the arcs. In Verilog, the two dimensional arrays are modeled as memories. The valid arc lookup table includes three sets of two dimensional arrays: present state names array; next state names array; and present input names array. The current arc structure is modeled as having the following fields: state width for indicating the number of bits in a state; input width for indicating the number of inputs in an arc; present state for holding the previous value of the state register; next state for holding the current value of the state register; present inputs for holding the number of current inputs; and traversed value for specifying how many times an arc has been traversed. The listing of arcs is modeled as a 2-dimensional array. Each register (row) has an arc represented as a concatenation of the present inputs, the present state, and the next state. Each state is modeled as having: state value for indicating the number of bits which make up a state; begin index for indicating the begin index of all the arcs in the list of arcs which have this state as a current state; and end index for indicating the ending index of all the arcs in the list of arcs which have this state as the current state.

Using these data structures, FSM monitor generator 350 generates a file containing user-created tasks, monitor file 360. Monitor file 360 contains Verilog hardware description language code, however, in other embodiments of this invention, monitor file 360 can contain any code capable of executing during a simulation of the hardware description file 310. These tasks are later used to monitor states and signals in the hardware description file 310 during a simulation. That is, FSM monitor generator 350 generates a part of a program, monitor file 360. This part of a program executes during a simulation of the hardware description file 310, causing the FSM test coverage information to be extracted during the simulation process. What is particularly important about the above steps is that the monitor file 360 is automatically generated and can be used to track information about an FSM. Monitor file 360 is relatively small compared to a dump file. This reduces the overall time required to verify an FSM. Further discussion of the creation of this file is found below.

Once the monitor file 360 has been generated, the monitor file 360, the hardware description file 310, and a test vector file 370, are provided for analysis 380 (simulation). Analysis 380 is a simulator, executing on processor 109, available from Cadence Design Systems Inc. of San Jose, Calif. (Verilog-XL.TM. simulator, version 1.7). However, in another embodiment, analysis 380 is any simulator capable of simulating the information in the hardware description file 310. The test vector file 370 (or driver file), typically contains test vectors for a simulator. In one embodiment, test vector file 370 is the test vector file of prior art systems. That is, in prior art systems, test vector file 370 is used as stimulus to create a large dump file, which is then used in the post processing FSM verification.

Analysis 380 includes the process of simulating the hardware described in the hardware description file 310. The analysis 380 generates a result file 390 during the simulation process. Note, a large dump file and then post processing the dump file are not needed. Also, generating the results during the simulation greatly reduces the time required to determine test coverage and allows the designer to more quickly test an FSM design.

The result file 390 typically includes: states accessed; states not accessed; arcs traversed; the number of times an arc has been traversed, and arcs missed. In another embodiment of the present invention, three files are produced: the result file as described above; an error file containing information on the traversal of illegal arcs, and a log file containing a log of the simulation.

Of particular importance, in the above described process, is that only a small FSM monitor file 360 and a small result file 390 need be generated. Further, if a designer wishes to simulate the hardware with a second set of test vectors, then the designer can simply reuse the monitor file 360. That is, a designer need only repeat the analysis 380 with a different test vector file 370.

In the above embodiments, specific compilers, simulators, and description languages have been described; however, the present invention is not limited to such specific requirements. Further, although these embodiments indicate that files are used as inputs and outputs, other data holding and communicating devices can be used.

FIG. 4 is a flow diagram showing a method of performing post processing on a number of result files to generate a summary file.

In one embodiment of the present invention, a post processor is used to generate a summary of a number of result files. These result files are based on the same format as result file 390.

A number of result files, 410a-410c, are used as input to post processor 420. Post processor 420 extracts the information from the result files 410a-410c to generate a summary file 430. Each of the result files 410a-410c represents a result file 390 for a given test vector file. Typically, a designer will generate multiple test vector files 370 and will execute analysis 380 for each of these files. Thus, separate result files will be generated. Each of these result files represents the test coverage for the corresponding test vector 370. Post processor 420 then provides a summary of the test coverage for the combination of the test vector files. Because each result file 410a-410c is in the format of result file 390, these files are relatively small compared to the large dump files created in prior art systems. Thus, this form of processing provides test coverage summaries of a number of test vector files quickly and efficiently.

In another embodiment of the present invention, the summary file 430 can be used as an input to post processor 420. This allows the creation of summaries of summaries.

Note that although three files have been used as input to the post processor 420, the post processing can be performed on two or more files.

FIG. 5a and FIG. 5b illustrate a method of generating a monitor file. In one embodiment, the file contains code to cause a subsequent simulation of the hardware description to generate the required FSM statistics. This process can be thought of as a program, the FSM monitor generator 350, generating another program, the monitor file 360.

The following method of generating the monitor file 360 does not necessarily require the use of PLIs. This allows the monitor file to execute more quickly. Also, as many vendors' simulators do not fully support PLIs, this embodiment can use more vendors' simulators.

At 510, the state table information is accessed and parsed, as described above. At 520, the internal data structures are generated and an internal database consistency check is performed to determine: whether all the arcs have correct start and end indices; what are the maximum name lengths for the state and input names; and what are the state widths in bits. At 530, declarations are generated in a new monitor file 360. These declaration typically include the number of states and arcs in the FSM. At 540, an initialization block is written to the monitor file 360. At 545, an always block is generated. The always block is a Verilog construct used to execute statements continuously.

Next, a number of tasks are defined. Each task causes some action during the analysis 380. These tasks are used to extract the test coverage information during the simulation. At 547, a state encoding task is generated. This tasks causes the simulator to indicate the encoding of each of the states in the FSM. At 550, the input names tasks is generated. This causes the simulator to write out the input signal names. The initialization states task, at 552, is generated. This task initializes each of the states in the FSM. At 554, the arc counts reset task is generated. This resets the arc counts value to 0 for each of the arcs in the FSM. At 556, the initialize arcs task is generated. This allows the simulator to define the arcs in the FSM. Next, at step 558, the search invalidate task is generated. This task determines whether the current traversed arc is among the list of valid arcs. At 559, the exclusivity search task is generated. This task checks for non-mutually exclusive arcs in the list of valid arcs.

At 560, the FSM statistics task is generated. This task determines which statistics the designer wishes to display in the result file 390, and causes those statistics to be displayed accordingly. At 562, the arcs traversed task is generated. The arcs traversed task causes the simulator to calculate the number of times an arc has been traversed during the simulation, given the test vector file 370. At 564, the arcs not traversed task is generated. This task causes a simulator to count the number of arcs not traversed.

At step 570, the arc template module is generated. This template is used by the simulator to provide a representation of an arc. At 575, the state template module is generated. This provides the simulator with a template of a state. Finally, at 577, the arc memory module is generated. The arc memory module provides the lookup table with the list of all arcs.

Appendix C includes an example of a monitor generator file 360, generated from the state table of Appendix B.

A method and apparatus for analyzing finite state machines (FSM) has been described. ##SPC1##