Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system
Reexamination Certificate
1997-06-10
2001-01-09
Lintz, Paul R. (Department: 2768)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Reexamination Certificate
active
06173241
ABSTRACT:
FIELD OF THE INVENTION
This invention pertains to the field of computer-aided design, and more particularly to integrated circuit simulation.
BACKGROUND OF THE INVENTION
Verification tools such as simulators play a vital role in efficient integrated circuit design. A circuit designer may use a simulator to verify that a design actually performs a desired function before fabricating a physical representation of that design. With the increasing complexity and expense of designing integrated circuits comes an increasing need for design verification tools which accelerate and simplify the design process.
The event-driven simulator is such a tool. In an event-driven simulator, small procedures, or functions, model the behavior of circuit elements, or cells, such as simple logic gates or more sophisticated elements such as arithmetic logic units. These procedures set the values of variables to represent nodes, such as wires or connections, within the circuit. Each node carries a signal, a unit of information in the simulation. Simulation is accomplished by setting the values of signals on nodes at the appropriate times.
In an event-driven simulator, an event is scheduled for a future time in the simulation when the simulator determines that the value of a signal on a node is to change. The information comprising an event includes the node to be changed, the new value of the signal at the node and the time at which the change is to take place. Pending events for any particular time are sorted in a prioritized event queue. The event queue provides the key list of tasks for a simulation.
In a known method of event-driven simulation, a next event is taken from the event queue. The value of the node affected is then set and every function that takes the node as an input is then evaluated. The function evaluations generate more events which are then added to the event queue.
For example, an input to an AND gate changes at simulated time T=12 nanoseconds (ns). The AND gate is re-evaluated and its output should change 2 ns later, at T=14 ns. The simulator schedules an event for the node of the AND gate output, storing its new value and time T=14 ns. The output of the AND gate is not changed immediately, since other activity may occur at T=13 ns which will use the current (not yet changed) value of the AND gate output node.
The simulator takes events in sequence, perhaps evaluating more events at T=12 ns and T=13 ns until it reaches T=14 ns. It removes the event from its list of pending changes, makes the change to the AND gate output and evaluates all the destinations of that node (the node's fanout), possibly creating more events at future times. The event information is then discarded.
With events generated in this manner, each cycle of the simulator invokes only those functions that must be evaluated. Since very few of the functions are invoked for each event, the event-driven method has the advantage of avoiding scanning a list of functions by keeping with each node a list of the functions it drives. All functions common to simultaneous events are preferably evaluated simultaneously to avoid re-evaluating the same function when only one evaluation is needed. Since modern circuits can include over a million cells, this feature of event-driven simulators is especially significant due to the long processing time required to evaluate all cell functions. It is desirable to further limit the amount of function evaluation needed during the simulation process while generating accurate results.
To allow a user to control a simulation, event-driven simulators supply a user interface. In the user interface, the user is allowed to examine nodes, set node values and re-start simulation.
If desired, a simulation can be scheduled to run for a specific amount of time with periodic interruption for the user interface. Similarly, the user interface can be invoked when certain node conditions are met or when a simulation is complete. A user interface may also be invoked when an unexpected system failure occurs.
Prior Art Simulation System
It will be helpful to an understanding of the present invention to first describe a known simulation system and flow diagram.
In
FIG. 1
, two AND gates
10
and
20
are shown. The inputs to AND gate
10
are nodes
12
and
14
, and the inputs to AND gate
20
are nodes
16
and
24
. Output node
16
of gate
10
is one input of gate
20
. The output of gate
20
is node
26
. For purposes of discussion it is assumed that gate
10
has a delay of 20 time units (e.g., tenths of nanoseconds) and gate
20
a delay of 10 time units.
The algorithm set forth in flow diagram form in
FIG. 2
can be used to simulate circuits such as the circuit of FIG.
1
. Obviously, in practice, much more complicated circuits are simulated containing hundreds of thousands or even millions of gates.
In the prior art, before the simulation begins, the circuit which is to be simulated is first represented digitally as a collection of gates. In this representation, a fanout of each node is set forth. Each fanout describes all the destinations of a node. For instance, referring to
FIG. 1
, it would be noted that in the fanout record of node
16
that the output of gate
10
is connected to one input terminal of gate
20
. If there were other gates connected to this node, they would be set forth as well, as part of the node's fanout. Similarly, for nodes
24
,
26
,
12
, and
14
, other gates coupled to these nodes would be set forth in their respective fanout information.
A state array is used in the known simulator to store the current values of the circuit nodes throughout the simulation. Each time a node value changes, the state array is updated accordingly. If desired, state information may be stored with the other information that makes up a node, such as the list of gates in a node's fanout.
The circuit representation in the simulator also includes a full description of behavior characteristics of each of the logical components. For gate
10
, the stored characteristics would indicate that gate
10
has a delay of 20 time units and that the output of the gate goes high when both inputs are high. Similarly, for gate
20
the entry for this gate would indicate that its output goes high when both its inputs are high and that the gate has a delay of 10 time units. Such description may also be made in the form of a truth table for each logical device.
The following example refers to simulated time in time units. A typical time unit for the circuit of
FIG. 1
would be 0.1 nanoseconds (ns). We will assume the simulation is to run for 6 ns beginning at time 0 ns, so the target time for completing the simulation is 60 time units.
Typically, in a simulation, there are initial events, conditions or inputs to stimulate the system being analyzed. To begin, assume all nodes for the circuit of
FIG. 1
are initially zero. Assume further that at time 1 the potential at node
14
goes high (N14=1@1), at time 10 the potential at node
12
goes high (N12=1@10), and at time 40 the potential at node
24
goes high (N24=1@40). Corresponding events for these changes are placed in the event queue. A timing diagram of the nodes in the present example is provided in FIG.
4
.
Events in the known simulator are stored with the simulated time for which each event is scheduled. Events are inserted into the event queue in any order. Events are removed from the event queue in order of increasing time. Therefore, every time an event is processed, it is the next most recent event.
FIG. 3
provides a clear representation of an event queue implementation referred to as a time wheel. Each slot in the time wheel contains a list of all events at one time step in the simulation. The current time, t, progresses through all time slots.
At step
56
, the simulation begins. At step
60
three pending events are found in the event queue, so the simulation continues. If no events had been found, a user interface would be ente
Do Thuan
Lintz Paul R.
Tachner, Esq. Adam M.
Xilinx , Inc.
Young Edel M.
LandOfFree
Logic simulator which can maintain, store, and use... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Logic simulator which can maintain, store, and use..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logic simulator which can maintain, store, and use... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2555718