next up previous contents
Next: Distributed Event Queues Up: Circuit Simulation: Time and Previous: Circuit Simulation: Time and

The Global Event Queue

The traditional approach to simulating parallel devices is to treat all components as being at the same time with respect to a so-called global event queue [9]. This structure basically consists of a linked list of time nodes, with each node containing a pointer to a linked list of components, or events, which have to be processed at that time. All events which are linked to the same time node are essentially in parallel with one another. When a component produces an output, all the components which have an input that depends on the output are placed on the global event queue at the node representing the time that the output signal was produced. As the time nodes are traversed sequentially, the components connected to each of the nodes are simulated and more events are scheduled later in time, reflecting the output of these components. This continues until the end of the timing queue is reached or the time allotted for the simulation expires.

Even though many simulators are built based upon the concept of a global event queue [3],[10], [16]; there are some fundamental problems associated with these data structures and, in particular, how they are implemented using structured programming languages.

A global event queue is, by its very name, a global data structure. As such, it is accessible everywhere in the program. Since structured programming languages do not support abstract data types or data encapsulation, there is nothing to prevent a user from accidentally (or intentionally) corrupting this queue. Even though the designer of the queue may have written a clean interface consisting of functions which should be called in order to modify the queue, the user may still be permitted access to the implementation of the structure directly, thereby risking abuse. If the queue is corrupted, then every component in the simulation is affected and the simulation is rendered invalid.

Since the time queue is sequential in nature, once a time window is passed, it can be very cumbersome to go back. Going back in time may be necessary should it be discovered that an asynchronous signal entered the system at some time prior to the current time of the simulation. Even if it were possible to traverse the queue backwards, one has to realize that because this queue applies to every single component, all components go back in time as well. This could be very disconcerting if the asynchronous signal affected only a small portion of the circuit.

The concept of a global event queue is also somewhat unintuitive; it has no equivalent whatsoever in the actual hardware. This means that a global queue does not correspond to the way people normally think about hardware. It will be shown in the next section that the use of distributed event queues in the form of wires makes for a more intuitive approach to hardware simulation.


next up previous contents
Next: Distributed Event Queues Up: Circuit Simulation: Time and Previous: Circuit Simulation: Time and

Donald Craig
Sat Jul 13 16:02:11 NDT 1996