next up previous contents
Next: Distributed Event Queues Up: An Alternative Approach Towards Previous: An Alternative Approach Towards

The Concept of Local Time

The notion of local time is contrary to the aforementioned traditional approaches in which all components are kept at the same point along the time line during the entire course of the simulation. Synchronization of all the components in such a simulator is enforced by a global queue that must invade the autonomy of all the components being simulated. By assigning the components the ability to manage their own local time, the components are not subject to the whims of an overburdened global event queue. As will be shown later, the concept of local time makes it possible to cleanly represent and simulate a circuit hierarchically.

The idea of local time is also exploited by the Chandy-Misra algorithm [5] as a means of achieving asynchronous distributed simulation in a parallel environment. Their motivation for employing a local time mechanism is justified by their need to eliminate the potential bottleneck introduced by a global entity which synchronizes all the simulation components:

``We do not wish to use any global variables nor do we want to use a single process to drive the simulation because it will prove to be a bottleneck. Our approach is totally asynchronous; every process maintains its own local clock and there is no global synchronization mechanism such as a global clock.'' [5]

In some respects, the simulation algorithm described by this section is similar to the Chandy-Misra algorithm; however, the algorithm has been adapted to run in a uniprocessor, sequential instruction environment.

One of the ramifications of the concept of local time is that during the course of the simulation, some components will be further advanced along the time line than other components. Indeed, it is even possible that some components may complete their contribution to the simulation before other components have even received any input at all. This fact creates an opportunity for memory recovery during the course of the simulation. For example, consider the case where a relatively large subcomponent has consumed all of its inputs and has successfully generated all of its outputs. At this point, the subcomponent is only wasting memory since it can no longer affect the outcome of the simulation, hence it can safely be destroyed. New subcomponents can subsequently be created and attached to the circuit. Through careful implementation, it may be possible to take advantage of this fact to simulate circuits which are too large to fit into memory all at once. Although the current implementation of the simulator engine does not support this strategy, it still seems theoretically plausible.


next up previous contents
Next: Distributed Event Queues Up: An Alternative Approach Towards Previous: An Alternative Approach Towards

Donald Craig
Mon Jul 8 12:05:35 NDT 1996