Process Oriented Logic Simulation Having Stability Checking

The present invention relates to the field of computer programs. Specifically, the present invention relates to logic simulation systems employing computer programs.

Typically the most common method by which combinatorial and sequential logic simulations occur are by traversal of logic networks as represented in a logic schematic. Such logic schematics include electrical circuit diagrams. The actual implementation of logic being simulated dictates how the simulator will traverse and schedule events during stabilization of signals in the logic network. This prior art method typically involves evaluation and conformation of sensitive and non-sensitive signals associated with logic in a given logic network. Sensitive signals are those that are dependent upon or affected by another signal. In many instances, the entire logic network or logic circuit must be evaluated even though some non-sensitive signals do not contribute to the signals of interest. The prior art method allows optimization to occur only in actual circuit implementation or internal algorithmic methods of the simulator's stabilizing mechanism. Neither of these options takes full advantage of the simulation environment.

The external information presented to a prior art logic simulator includes a definition of a circuit and the events causing propagation of signals through the defined circuit. This information may be provided as shown in the following example:

Signals:

Q, QBAR, S, R

Relationships:

Q:=(S'* QBAR')',

QBAR:=(R'* Q)'

In the above example, a functional sequential circuit is specified. As specified, the example logic circuit is sensitive to four signals: Q, QBAR, S, and R. Input signals `S` and `QBAR" will produce the product `Q`. Input signals `R` and `Q` will produce the product `QBAR`. Q and QBAR are generated by the prior art simulator whenever any of the sensitive factors or logic signals change state.

Given an instance where input signal `S` is the only signal changing state (for example toggling from a logic 0 state to logic 1 state), only the product `Q` needs to be computed by the simulator. Prior art systems, however group all four signals (Q, QBAR, S, and R) together. Thus, the prior art grouping of the sequential circuit contains unnecessary overhead.

To illustrate consider the following truth table:

The truth table indicates signal dependencies and the relationships that may be optimized. In the prior art, the actual sequential logic under simulation is traced out and evaluated. All signal dependencies are propagated to reach the final resulting signal values. Thus, the traditional method is not efficient in optimizing for signal relationships.

Additionally, another problem exists in prior art logic simulators when modeling zero delay logic circuits or other circuits where the timing of signal state changes is critical. This problem is illustrated in the following examples.

Given a clocked sequential circuit, SR flipflop, as described below:

Signals:

Q, S, QBAR, CLOCK

Relationships:

Q:=((S * CLOCK)'* QBAR)'

In the above example, if the input signals `S` and `CLOCK` are active at the same instant in time, the product `Q` will change state. This could possibly be valid in a real implementation as the input signal `CLOCK` may require a zero or negative setup and hold condition on input signal `S`. In that case, this level of precedence is still functionally valid without any constraints of a timing model imposed. However, if input signal `CLOCK` requires `S` to arrive before `CLOCK` is active, an incorrect behavior will be simulated in the above example, without any timing models or other solution imposed. Thus, prior art simulators are unable to properly and conveniently model time critical signal dependencies.

Thus, it is an object of the present invention to provide a logic simulation system including optimal configurability of combinatorial and sequential logic circuits in a behavioral form. It is a further object of the present invention to provide a logic simulation system allowing external definability of possible events which trigger combinatorial and sequential logic propagation. It is a further object of the present invention to provide a logic simulation system that eliminates unnecessary evaluations. It is a further object of the present invention to provide a logic simulation system that efficiently models time critical signal dependencies.

The present invention provides a means and method for optimal configurability of combinatorial and sequential logic circuits in a simulated behavioral form. The present invention allows optimization(s) or control of the performance by which combinatorial and sequential logic simulations occur. At least two techniques contribute to the high efficiency. First, the present invention contains process oriented functional blocks with event posting to eliminate unnecessary evaluations. Second, the present invention manages process to logic signal(s) and logic signal to process(s) sensitivity relationship(s) which reduces the traditional overhead of event scheduling and stabilization.

The present invention allows external definability of possible events which trigger combinatorial and sequential logic propagation. Additionally, by virtue of external definition of when propagation of the circuit will occur, the present invention contains a process which manages event scheduling during stabilization of the circuit. All combinatorial internal logic of a process is evaluated in sequential order.

To manage the definition of process to sensitive signals and sensitive signal to processes, the present invention incorporates a process and data relations to maintain the expressed correspondence. The present invention stores the data in a form similar to a tree in representation where a base node or root is at the top of the tree.

The preferred embodiment of the present invention includes a computer system which comprises a bus for communicating information, a processor coupled to the bus for processing information, and a random access memory coupled to the bus for storing information and instructions for the processor. The processing logic of the preferred embodiment is operably disposed within the random access memory and, executed by the processor of the computer system. Within the processing logic of the preferred embodiment, several data structures are defined and used throughout the execution of the present invention. These data structures include a list of processes, a list of signals, and a list of process-to-signal relationships including a list of sensitive signals.

Upon activation of the present invention, the start state of all signals is initially set. Once the start state of all signals is set, a test is performed to determine if the logic network being simulated is in a stable condition. A stable network exists when either no signals are changing or when signals are changing in a predictable manner. If this is the case, then execution of the simulator may be terminated for this cycle at processing block 105. If the logic network is not stable, a loop is initiated for propagating signals and updating signal states throughout the logic network. Once the logic is propagated, the new state for all signals for which a state transition has occurred is set. Once the new states of signals have been set, a test is performed to determine if a new state has been encountered. A loop continues as long as signals transition to a new state. When a new state is not encountered, but the logic network has still not stabilized, a new state is forced and a new loop iteration is initiated. These loop iterations continue until the logic network stabilizes and simulation processing terminates.

FIG. 1 is an illustration of the typical prior art computer system bus architecture.

FIG. 2 is a flowchart showing the overall process flow of the logic simulator of the present invention.

FIGS. 3a and 3b are together a flowchart that shows the process flow of the logic simulator of the present invention in setting the first state of a signal.

FIGS. 4, 5, 6, and 7 are together a flowchart that shows the process flow of the logic simulator of the present invention in propagating the logic within a process.

FIG. 8 is a flowchart that shows the process flow of the logic simulator of the present invention in setting the old state of a signal.

FIGS. 9 and 10 are together of a flowchart that shows the process flow of the logic simulator of the present invention in setting the next state of a signal.

FIGS. 11 and 12 are together a flowchart that shows the process flow of the logic simulator of the present invention in setting the new state of a signal.

The present invention provides a means and method for optimal configurability of combinatorial and sequential logic circuits in a simulated behavioral form. In the following description, numerous specific details are set forth in order to provide a thorough understanding of the invention. However, it will be apparent to one with ordinary skill in the art that these specific details need not be used to practice the present invention. In other instances, well-known logic structures, data structures, and interfaces have not been shown in detail in order not to unnecessarily obscure the present invention.

The present invention was formulated to provide an external capability of optimization(s) or control of the performance by which combinatorial and sequential logic simulations occur. The present invention is a method providing optimal configurability of combinatorial and sequential logic circuits in a behavioral form. Two techniques contribute to the high efficiency. First, the present invention contains process oriented functional blocks with event posting to eliminate unnecessary evaluations. Second, the present invention manages a process to logic signal(s) and logic signal to process(s) sensitivity relationship(s) which reduces the traditional overhead of event scheduling and stabilization.

The present invention allows external definability of possible events which trigger combinatorial and sequential logic propagation. These events can be optimally partitioned into multiple process definitions. Additionally, by virtue of external definition of when propagation of the circuit will occur, present invention contains a control means which manages event scheduling during stabilization of the circuit. All combinatorial internal logic of a process is evaluated in sequential order.

Referring to the sample logic definition presented above:

Signals:

Q, QBAR, S, R

Relationships:

Q:=(S'* QBAR')'

QBAR:=(R'* Q)'

the present invention can be used to optimize the simulation of the logic. Given that the function of both products `Q` and `QBAR` are evaluated as provided above, a more optimized solution may be illustrated in the following form:

This form allows for a more optimal simulation. Since the computation of Q and QBAR has been partitioned into independent processes, a transition of S only produces a propagation of the product Q. Similarly, a transition of R only produces a propagation of the product QBAR. Thus, the present invention achieves a more efficient simulating time length.

Additionally, definition of process to sensitivity relationships allows a more directly controllable level of logic precedence as required in proper modeling of zero delay logic circuit simulations.

Given a clocked sequential circuit, SR flipflop, as described above:

Signals:

Q, S, QBAR, CLOCK

Relationships:

Q:=((S * CLOCK)'* QBAR)'

To allow a level of precedence to occur without introduction of a timing delay or setup and hold information, an additional process would be defined. This process is described as follows:

With the new definition of CLOCK, on the first round of the duty cycle in stabilization, if input signals `CLOCK` and `S` go active at the same instance, the product `Q` would not realize a change of state. This now allows for definition of a positive timing setup and hold requirement without introduction of a timing model. Thus, functionally the circuit operates in simulation as would be realized in implementation.

To manage the definition of processes and process-to-sensitive-signal and sensitive-signal-to-process relationships, the present invention incorporates process and data relation information to maintain the expressed correspondence. The present invention stores the data in a form similar to a tree in representation where a base node or root is at the top of the tree. This root of the tree then spans out on branches or pages, that end in leafs where the data is stored. Means for maintaining information in a tree data structure is a technique well known to those of ordinary skill in the art.

The preferred embodiment of the present invention is implemented on a Sun Microsystems, Inc. brand computer system. It will be apparent to those with ordinary skill in the art, however, that alternative computer systems may be employed. In general, such computer systems, as illustrated by FIG. 1, comprise a bus 100 for communicating information, a processor 101 coupled with the bus for processing information, and a random access memory 102 coupled with the bus 100 for storing information and instructions for the processor 101. Optionally, such a computer system may include a display device 105 coupled to the bus 100 for displaying information to a computer user, a read only memory 103 coupled with the bus 100 for storing static information and instructions for the processor 101, a data storage device 113 such as a magnetic disk and disk drive coupled with the bus 100 for storing information and instructions, and an alphanumeric input device 106 including alphanumeric and function keys coupled to the bus 100 for communicating information and command selections to the processor 101.

The processing logic of the preferred embodiment is operably disposed within random access memory 102 and, executed by processor 101 of the computer system described above. The processing logic of the present invention may equivalently be disposed in read-only memory 103 or other memory means accessible to processor 101 for execution. A means for loading and activating the processing logic of the present invention exists using techniques well known to those of ordinary skill in the art. Once activated, the processing logic of the present invention operates in the manner described below.

The flowcharts provided in FIGS. 2, 3a, 3b, and 4-12 are used to best describe the processing logic of the present invention. In order to implement the processing logic of the present invention, several data structures are defined and used throughout the processing performed by the preferred embodiment. These data structures include a list of processes, a list of signals, and a list of process-to-signal relationships including a list of sensitive signals. The list of processes includes the name and a definition of processes that make up a particular logic network. A process is a functional logic block, circuit or group of signals that produce a particular result. The list of signals contains a name and definition of signals that are input to and output from processes. Information pertaining to each signal is maintained by the present invention. Such signal information includes the current state of the signal, the last state held by the signal prior to transitioning to the current state and the next state of the signal to which the signal will transition from the current state. Other information maintained for each signal is a changed state notifier which identifies whether the state of the signal has changed from the last cycle. The third set of information maintained by the present invention is a list of process to signal relationships. This data includes a list of sensitive signals associated with a particular process.

Listing A, provided herein, presents the Baucus Naur description of the supporting data structures and relationships used in the present invention. Refer to Listing B provided herein for the source code of the processing logic of the preferred embodiment of the present invention as coded in the C programming language. It will be apparent to those skilled in the art that alternative programming languages may be used. Both Listing A and Listing B are provided at the end of this detailed description, but before the claims.

Referring now to the first flowchart of the processing logic of the present invention illustrated in FIG. 2, an overall flowchart of the logic simulator of the present invention is illustrated. Upon activation of the present invention, processing control passes to processing block 100 illustrated in FIG. 2. First, the start state of all signals is initialized in processing block 102. It is assumed that the network is initially unstable. The logic contained within processing block 102 is more fully defined and illustrated in FIGS. 3a and 3b and described below. Once the start state of all signals is set, a test is performed to determine if the logic network being simulated is in a stable condition. A stable network exists when either no signals are changing or when signals are changing in a predictable manner. If this is the case, execution of the simulator may be terminated for this cycle at processing block 105. If the logic network is not stable, processing path 111 is taken to processing block 106 where a data item is set to indicate that a new logic state has occurred. It is assumed in processing the logic network under simulation that the network will eventually stabilize. Starting with decision block 107, a loop is initiated for propagating signals and updating signal states throughout the logic network. In processing block 109, the logic associated with each process defined in the system is propagated. A more detailed description of the processing logic within processing block 109 is illustrated in FIGS. 4-10 and described below. Once the logic is propagated (processing block 109), the new state for all signals for which a state transition has occurred is set in processing block 110. A more detailed description of the processing logic contained within processing block 110 is illustrated in the flowcharts presented in FIGS. 11 and 12 and described below. Once the new states of signals have been set (processing block 110), processing control returns to decision block 107 where a test is performed to determine if a new state has been encountered. The loop between decision block 107 and processing block 110 continues as long as signals transition to a new state. When a new state is not encountered, processing path 113 is taken back to decision block 103. If the logic network has still not stabilized (processing path 111), a new state condition is forced in processing block 106 and the loop between decision block 107 and processing block 110 is repeated. These loop iterations continue until the logic network stabilizes and simulation processing terminates at processing block 105 via processing path 112.

Referring now to FIG. 3a, a more detailed description of the processing logic contained within processing block 102 is depicted. For each signal defined in a particular logic network under simulation, the signal's last state is compared with its current value in decision block 201. If the signal's current state is equal to its last state, processing path 206 is taken to processing block 202 where the signal's old state is set to its current value. Similarly, the signal's next state is also set to its current value in processing block 203. A notify indication is then set to false in processing block 204 thereby indicating that no state change has occurred for a signal. Execution control is then transferred to processing block 214.

Referring again to decision block 201, if the current signal's last state is not equal to its current value (processing path 207) and the signal's last state is unknown (processing path 209), the signal's last state is set equal to a value not equal to its current value (processing block 205). In this way, the signal's last state is set to a known value but a value different from its current value. The signal's next state is set to its current value in processing block 211. A logic network stability indicator is set to a false value (processing block 212) and the notify indication for this signal is set to a true value (processing block 213) indicating that a signal has changed state. At this point, the state parameters associated with each signal have been initialized and the network stability indicator has been set to a value corresponding to state change information associated with each signal.

Starting at processing block 214, the list of process-to-signal relationships is traversed in order to properly set up the states of signals in relation to each other. A pointer to an initial position in the list of process-to-signal relationships is set in processing block 214. A loop is then initiated for each relationship in the list. If the relation currently being processed is nil or empty, processing for the set start state procedure terminates at processing block 220 via processing path 217. If, however, the relation currently being processed is not nil or empty, processing path 216 is taken to processing block 218 where the relation is retrieved from the list and an index for accessing sensitive signals associated with the process is initialized to zero in processing block 219. Execution control then transfers to the bubble labeled A illustrated in FIG. 3b.

Referring now to FIG. 3b at the bubble labeled A, a test is performed to determine if each of the sensitive signals associated with a process have been updated (decision block 303). If a sensitive signal remains to be updated, processing path 308 is taken to processing block 302 where the indexed process-to-signal relationship is retrieved from the list of same. If the fetched signal relation is matched to the signal for which a state change was detected in decision block 201, processing path 309 is taken to processing block 304 where the changed state notifier associated with the related signal is set to true. If the notify flag is also true (processing path 311), the current value of the related signal is saved in a saved state data item (processing block 306). Processing then continues at the bubble labeled B as illustrated in FIG. 3a where a loop pointer is updated to the next item to the list of process-to-signal relationships (processing block 221). The loop then repeats starting at decision block 215 for the next relation in the list. The looping continues until processing path 217 is taken after the entire list of process-to-signal relationships has been processed.

Referring now to FIGS. 4-10, the detailed propagation logic identified in processing block 109 is described. Referring now to FIG. 4, the propagate logic 400 of the present invention begins by initializing an evaluate indicator to false in processing block 401. The evaluate indicator is used to signal when propagation of signals through a logic network has not yet been completed. A pointer or index is then initialized to point to the start of the list of sensitive signals associated with a process (processing block 402). This list of sensitive signals is included in a list of process-to-signal relationships. As the processing logic of the present invention executes to completion, each process defined in the network and its associated sensitive signals are processed through the loop starting at decision block 403. For each of the sensitive signals associated with the process currently being evaluated, the sensitive signal is fetched (processing block 405) and the value associated with the signal is also retrieved (processing block 407). Processing then continues at the bubble labeled G illustrated in FIG. 5.

Referring now to FIG. 5, if the changed state notifier associated with the sensitive signal indicates that the sensitive signal has changed state (processing path 503), the evaluate indicator is set to true (processing block 504). If, however, the sensitive signal's state has not changed (processing path 501), the start state of the signal is set to its last state (processing block 502) and the sensitive signal's last state is set to its current value (processing block 508). Processing then continues at processing block 511 where a pointer or index is updated to point to the next sensitive signal in the list and processing loops back to the bubble labeled C illustrated in FIG. 4.

Referring still to FIG. 5, if the sensitive signal has changed state (processing path 503), the evaluate indicator is set to true (processing block 504). If the last state of the signal is unknown, the last state is set to the current value in processing block 507. If the last state of the signal is a known value (processing path 509), the last state is saved in a saved state data item in processing block 510. The pointer to the list of sensitive signals is updated to point to the next sensitive signal and execution control loops back to the bubble labeled C illustrated in FIG. 4 for a new iteration with the next sensitive signal. Once each sensitive signal of the current process is tested for a state change, processing control is transferred to the bubble labeled F as shown in FIG. 6.

Referring now to FIG. 6, if the evaluate indicator is true (processing path 606), a sensitive signal state change has occurred and thus, the process logic must be propagated. In this case, the old state of all signals of the process are set to their current value (processing block 607) and the process logic is propagated (processing block 608). The process logic is propagated by sequential evaluation of the processes combinatorial logic using a technique disclosed in a co-pending patent application entitled "Programmable Interpretive Virtual Machine" filed concurrently with the present patent application. Once the process logic has been propagated, the list of sensitive signals associated with the process is again checked for the occurrence of a state change for a sensitive signal. This processing loop begins by the initialization of a pointer or index into the list of sensitive signals associated with the process (processing block 609). A loop is then initiated at decision block 610 and iterated for each sensitive signal in the list of signals associated with the process. The currently indexed sensitive signal is fetched in processing block 613 and processing continues at the bubble labeled E as illustrated in FIG. 7.

Referring now to FIG. 7, if the indexed signal's state has changed (processing path 701), no further action in this loop is necessary. Thus, the index into the list of sensitive signals is updated to point to the next sensitive signal and processing continues at the bubble labeled D illustrated in FIG. 6 where processing for the next sensitive signal continues. If, however, the currently indexed sensitive signal has changed state (processing path 703), the notify indicator is set to false (processing block 704) and the signal's last state is set to a saved value (processing block 705). Execution then loops back to the bubble labeled D in FIG. 6 after the index or pointer to sensitive signals is updated to point to the next sensitive signal (processing block 702). This looping for sensitive signals continues until the list of sensitive signals associated with the current process is exhausted (processing path 611) as illustrated in FIG. 6. Referring again to FIG. 6, if the evaluate indicator is true (processing path 601), the signals associated with the process are set to their next state (processing block 602). A detailed description of the processing logic contained within processing block 602 is illustrated in flowchart form in FIGS. 9 and 10. Once the next state of all signals is set, process propagation terminates at termination box 604.

Referring now to FIG. 8, the logic for setting the old state of all signals is presented in detail. First, the current value of the signal is fetched in processing block 801. This current value is then stored into the old state associated with the signal in processing block 802. Set old state execution then terminates at termination box 803.

Referring now to FIG. 9, the processing associated with setting the next state of a signal is presented in detail. First, the signal's current state value is fetched in processing block 901. If the signal has not changed state (processing path 904), processing terminates at termination box 903. If, however, the signal's old value is not equal to its current value (processing path 906) and the signal's old state is a known value (processing path 909), the signal's next state is set to the value of its current state in processing block 910 and the value of the signal's current state is set to its old state value (processing block 911) . If the old state of the signal is unknown (processing path 908), the old state of the signal is set to a known value, but a value different than the signal's current value (processing block 907). The signal's next state is set to the value of its current state in processing block 913. A pointer or index is initialized to point to the first sensitive signal in the list of sensitive signals associated with the current process (processing block 912). Processing then continues at the bubble labeled J illustrated in FIG. 10.

Referring now to FIG. 10 at the bubble labeled J, a loop is started for scanning the list of sensitive signals associated with the current process. This scanning of the list of sensitive signals is similar to the loop shown and described in relation to FIGS. 3a and 3b starting at decision block 215. Referring to FIG. 10 at decision block 1009, if the currently indexed sensitive signal is equal to the signal for which a state change has occurred (processing path 1012), a stable indicator is set to false indicating that the logic network has not yet stabilized (processing block 1011). A notifier indicator is set to true in processing block 1013. The pointer or index to sensitive signals in the list of sensitive signals associated with the current process is updated in processing block 1014 to point to the next sensitive signal in the list and processing continues at decision block 1000. The loop starting at decision block 1000 continues until each of the sensitive signals associated with a process have been updated. Upon completion of the list, processing path 1001 is taken to the bubble labeled H as illustrated in FIG. 9 where processing for the set next state procedure is terminated at termination block 903.

Referring now to FIG. 11, the processing associated with setting the new state of a signal is illustrated. First, the current value of the signal is fetched in processing block 1101. If current value of the signal is equal to its next state value (processing path 1104), new state processing is terminated at termination block 1103. If, however, the current value of the signal is not equal to its next state value (processing path 1105), the last state of the signal is set to a known value other than the value of the signal's next state in processing block 1106. The current value of the signal is then set to the value of its next state in processing block 1107. At processing block 1108, an index or pointer is initialized to the start of the list of sensitive signals associated with the current process. Starting at decision block 1109, a loop is started for processing each of the sensitive signals associated with the current process. This loop is similar to that described and illustrated in FIGS. 3a and 3b starting at decision block 215.

Referring now to FIG. 12, the loop through the list of sensitive signals continues as illustrated. At decision block 1204, if a sensitive signal is equal to the signal for which a changed has been noted (processing path 1207), a stable indicator is set to false in processing block 1206 and a notify indication is set to true in processing block 1210. Processing then continues at the top of the loop (decision block 1109), illustrated in FIG. 11, for the next iteration with a new sensitive signal until each of the sensitive signals in the list have been processed. Upon completion of the list, processing path 1110 is taken to termination box 1103 where processing for the new state of the signal is terminated.

Thus, a logic simulation system providing optimal configurability of combinatorial and sequential logic circuits in a simulated behavioral form is disclosed.

Although this invention has been shown in relation to a particular embodiment, it should not be considered so limited. Rather, it is limited only by the appended claims. ##SPC1##