DEDirector
ptolemy.domains.de.kernel.DEDirector

This director implements the discrete-event (DE) model of computation (MoC). It should be used as the local director of a CompositeActor that is to be executed according to the DE MoC. This director maintains a totally ordered set of events and processes these events in the order defined on their tags and depths.

An event is associated with a tag, which is a tuple of timestamp and microstep. A timestamp indicates the model time when this event occurs. It is an object of the ptolemy.actor.util.Time class. A microstep is an integer which represents the index of the sequence of execution phases when this director processes events with the same timestamp. Two tags are equal if they have the same timestamp and microstep. If two events have the same tag, they are called simultaneous events.

Microsteps can only be increased by calling the fireAt() method. For example, when an actor requests to be fired again at the current model time, a new event with the same timestamp but a bigger microstep (incremented by 1) will be generated.

An event is also associated with a depth reflecting its priority, based on which a DE director chooses the execution order for simultaneous events. A depth is an integer and a larger value of depth indicates a lower priority. The depth of an event is determined by topologically sorting all the ports of actors according to their data dependencies over which there is no time delay.

The order of events is defined as follows. An event A is said to be earlier than another event B if A's timestamp is smaller than B's; or if A's timestamp is the same as B's, and A's microstep is smaller than B's; or if A's tag is the same as B's, and A's depth is smaller than B's. By giving events this well-defined order, this director can handle simultaneous events in a deterministic way.

The bottleneck in a typical DE simulator is in the maintenance of the global event queue. This director uses the calendar queue as the global event queue. This is an efficient algorithm with O(1) time complexity in both enqueue and dequeue operations. Sorting in the ptolemy.actor.util.CalendarQueue class is done according to the order defined above.

The complexity of the calendar algorithm is sensitive to the length of the event queue. When the size of the event queue becomes too long or changes very often, the simulation performance suffers from the penalties of queuing and dequeuing events. A few mechanisms are implemented to reduce such penalties by keeping the event queue short. The first mechanism is to only store in the event queue pure events and the trigger events with the same timestamp and microstep as those of the director. See ptolemy.domains.de.kernel.DEEvent for explanation of these two types of events. What is more, no duplicate trigger events are allowed in the event queue. Another mechanism is that in a hierarchical model, each level keeps a local event queue. A lower level only reports the earliest event to its upper level to schedule a future firing. The last mechanism is to maintain a list which records all actors that are disabled. Any triggers sent to the actors in this list are discarded.

In the initialize() method, depths of actors and IO ports are statically analyzed and calculated. They are not calculated in the preinitialize() method because hierarchical models may change their structures during their preinitialize() method. For example, a modal model does not specify its initial state (and its refinement) until the end of its preinitialize() method. See ptolemy.domains.fsm.kernel.FSMActor. In order to support mutation, this director recalculates the depths at the beginning of its next iteration.

There are two types of depths: one is associated with IO ports, which reflects the order of trigger events; the other one is associated with actors, which is for pure events. The relationship between the depths of IO ports and actors is that the depth of an actor is the smallest of the depths of its IO ports. Pure events can only be produced by calling the fireAt() method, and trigger events can only be produced by actors that produce outputs. See put.

Directed loops of IO ports with no delay are not permitted because it is impossible to do a topological sort to assign depths. Such a loop can be broken by inserting some special actors, such as the TimedDelay actor. If zero delay in the loop is truly required, then set the delay parameter of those actors to zero. This zero-delay actor plays the same role as that of delta delay in VHDL. Note that the detection of directed loops are based on port connections rather than data dependencies between actors because port connections reflect the data dependencies more accurately. The information of port connections are stored in the nonpersistent attribute FunctionDependency.

An input port in a DE model contains an instance of DEReceiver. When a token is put into a DEReceiver, that receiver posts a trigger event to the director. This director sorts trigger events in a global event queue.

An iteration, in the DE domain, is defined as processing all the events whose tags are equal to the current tag of the director (also called the model tag). At the beginning of the fire() method, this director dequeues a subset of the earliest events (the ones with smallest timestamp, microstep, and depth) from the global event queue. These events have the same destination actor. Then, this director invokes that actor to iterate. This actor must consume tokens from its input port(s), and usually produces new events on its output port(s). These new events will be trigger the receiving actors to fire. It is important that the actor actually consumes tokens from its inputs, even if the tokens are solely used to trigger reactions. This is how polymorphic actors are used in the DE domain. The actor will be fired repeatedly until there are no more tokens in its input ports, or the actor returns false in its prefire() method. Then, this director keeps dequeuing and processing the earliest events from the event queue until no more events have the same tag as the model tag. After calling the postfire() method, this director finishes an iteration. This director is responsible to advance the model tag to perform another iteration.

A model starts from the time specified by startTime, which has default value 0.0. The stop time of the execution can be set using the stopTime parameter. The parameter has a default value Infinity, which means the execution runs forever.

Execution of a DE model ends when the timestamp of the earliest event exceeds the stop time. This stopping condition is checked inside the postfire() method of this director. By default, execution also ends when the global event queue becomes empty. Sometimes, the desired behaviour is for the director to wait on an empty queue until another thread makes new events available. For example, a DE actor may produce events when a user hits a button on the screen. To prevent ending the execution when there are no more events, set the stopWhenQueueIsEmpty parameter to false.

Parameters isCQAdaptive, minBinCount, and binCountFactor, are used to configure the calendar queue. Changes to these parameters are ignored when the model is running.

If the parameter synchronizeToRealTime is set to true, then the director will not process events until the real time elapsed since the model started matches the timestamp of the event. This ensures that the director does not get ahead of real time. However, of course, this does not ensure that the director keeps up with real time.

This director tolerates changes to the model during execution. The change should be queued with a component in the hierarchy using requestChange(). While invoking those changes, the method invalidateSchedule() is expected to be called, notifying the director that the topology it used to calculate the priorities of the actors is no longer valid. This will result in the priorities (depths of actors) being recalculated the next time prefire() is invoked.

Author(s): Lukito Muliadi, Edward A. Lee, Jie Liu, Haiyang Zheng
Version:$Id: DEDirector.java,v 1.295 2006/05/17 20:16:39 eal Exp $
Pt.Proposed Rating:Green (hyzheng)
Pt.Accepted Rating:Yellow (hyzheng)




binCountFactor
The factor when adjusting the bin number. This parameter must contain an IntToken. Changes to this parameter are ignored when the model is running. The value defaults to 2.

isCQAdaptive
Specify whether the calendar queue adjusts its bin number at run time. This parameter must contain a BooleanToken. If this parameter is true, the calendar queue will adapt its bin number with respect to the distribution of events. Changes to this parameter are ignored when the model is running. The value defaults to true.

minBinCount
The minimum (initial) number of bins in the calendar queue. This parameter must contain an IntToken. Changes to this parameter are ignored when the model is running. The value defaults to 2.

startTime
The start time of model. This parameter must contain a DoubleToken. The value defaults to 0.0.

stopTime
The stop time of the model. This parameter must contain a DoubleToken. The value defaults to Infinity.

stopWhenQueueIsEmpty
Specify whether the execution stops when the queue is empty. This parameter must contain a BooleanToken. If this parameter is true, the execution of the model will be stopped when the queue is empty. The value defaults to true.

synchronizeToRealTime
Specify whether the execution should synchronize to the real time. This parameter must contain a BooleanToken. If this parameter is true, then do not process events until the elapsed real time matches the time stamp of the events. The value defaults to false.