The Simulation Algorithm

 

In simplistic terms, the simulation algorithm amounts to nothing more than a depth first traversal of the aforementioned three-dimensional hierarchy of components, in which signals are propagated both horizontally across the same hierarchical level and vertically through different hierarchical levels. One of the primary differences between this approach and the classical event-driven approach is with respect to when events are propagated. In the global queue approach, events are entered into a sorted event list and are propagated later; whereas in the distributed queue approach, events are entered into an entity's output queue and are propagated immediately, if possible.

The algorithm itself is set in motion when the top-level component receives a simulate() message. The semantics of this message are fairly straightforward and can be summarized with the following pseudo-code:

 
Component::simulate()

/* Same for all components */ \+

	while (component inputs are ready at local time)
	do \+

		increment local time of component

		process inputs at local time - 1

	done

Note that it is important that the local time of the component be incremented before the process() method is called. If this is not done, then the local time will never be incremented in cases where feedback is present in the circuit description. This would result in a non-terminating simulation.

Because the process() method is virtual, the actions taken by the second line of the while loop depend upon whether the component overrides the process() method it inherited from the Component base class. Components which are composed of subcomponents do not typically provide their own process() method. Instead, they simply inherit the same method as defined in the Component base class. The behaviour of the process() method in this case is to traverse the input port list of the component and to send simulate() messages to all the embedded subcomponents, as demonstrated by the following pseudo-code:

 
Component::process(t)

/* For high-level components */ \+

	for each (input port of component) do \+

		for each (component in fan-out of port)
	do \+

			simulate component

		done

	done

Hence, the default behaviour of the process() method is to essentially descend the representation hierarchy, informing lower-level components to process their inputs. A component which contains no subcomponents and does not override the process() virtual function of the base Component class is effectively treated as a null component since it is not capable of producing output.

Consequently, components which are located at the lowest level of the hierarchy (that is, components that do not contain subcomponents) should provide their own process() method, thus overriding the process() method in the base class. In this case, the process() method will typically employ the method Port::get_signal() to obtain the input signals that occurred at the current local time of the component. The process() method then performs some logic or calculation based upon these inputs and then sends the new signals to the output ports of the component using the method Port::send_signal(). An example of such a sequence of operations is demonstrated by the following pseudo-code:

 
Component::process(t)

/* For low-level components */ \+

	get inputs from inputs ports at time t

	calculate outputs based upon inputs

	send outputs to output ports with timestamp
	t + delay

Note that when adding a new low-level component that requires its own process() method to an existing component library, there is no need to add a new case label to a lengthy switch statement to ensure that the correct process() function is invoked for the new type of component. The virtual function mechanism will invoke the correct process() method for the component at run-time.

The implementation of the simulator engine, is for the most part, independent of the GUI discussed in the previous chapter -- the simulator engine may be run without the GUI and vice versa. This feature results in loose coupling, and therefore makes both the GUI and the engine reusable as separate autonomous modules in their own right. Details concerning the integration of the GUI and the simulator engine are presented in the next chapter.