Top Up Prev Next Bottom Contents Index Search

12.2 The DE target and its schedulers

The DE domain, at this time, has only one target. This target has three parameters:

timeScale (FLOAT) Default = 1.0
A scaling factor relating local simulated time to the time of other domains that might be communicating with DE.
syncMode (INT) Default = YES
An experimental optimization explained below, again aimed at mixed-domain systems.
calendar queue scheduler?
(INT) Default = YES
A Boolean indicating whether or not to use the faster "calendar queue" scheduler, explained below.
The DE schedulers in Ptolemy determine the order of execution of the blocks. There are two schedulers that have been implemented which are distributed with the domain. They expect particular behavior (operational semantics) on the part of the stars. In this section, we describe the semantics.

12.2.1 Events and chronology

A DE star models part of a system response to a change in the system state. The change of state, which is called an event, is signaled by a particle in the DE domain. Each particle is assigned a time stamp indicating when (in simulated time) it is to be processed. Since events are irregularly spaced in time and system responses are generally very dynamic, all scheduling actions are performed at run-time. At run-time, the DE scheduler processes the events in chronological order until simulated time reaches a global "stop time."

Each scheduler maintains a global event queue where particles currently in the system are sorted in accordance with their time stamps; the earliest event in simulated time being at the head of the queue. The difference between the two schedulers is primarily in the management of this event queue. Anindo Banerjea and Ed Knightly wrote the default DE Scheduler, which is based on the "calendar queue" mechanism developed by Randy Brown [Bro88]. (This was based on code written by Hui Zhang.) This mechanism handles large event queues much more efficiently than the alternative, a more direct DE scheduler, which uses a single sorted list with linear searching. The alternative scheduler can be selected by changing a parameter in the default DE target.

Each scheduler fetches the event at the head of the event queue and sends it to the input ports of its destination block. A DE star is executed (fired) whenever there is a new event on any of its input portholes. Before executing the star, the scheduler searches the event queue to find out whether there are any simultaneous events at the other input portholes of the same star, and fetches those events. Thus, for each firing, a star can consume all simultaneous events for its input portholes. After a block is executed it may generate some output events on its output ports. These events are put into the global event queue. Then the scheduler fetches another event and repeats its action until the given stopping condition is met.

It is worth noting that the particle movement is not through Geodesics, as in most other domains, but through the global queue in the DE domain. Since the geodesic is a FIFO queue, we cannot implement the incoming events which do not arrive in chronological order if we put the particles into geodesics. Instead, the particles are managed globally in the event queue.

12.2.2 Event generators

Some DE stars are event generators that do not consume any events, and hence cannot be triggered by input events. They are first triggered by system-generated particles that are placed in the event queue before the system is started. Subsequent firings are requested by the star itself, which gives the time at which it wishes to be refired. All such stars are derived from the base class RepeatStar.

RepeatStar is also used by stars that do have input portholes, but also need to schedule themselves to execute at particular future times whether or not any outside event will arrive then. An example is PSServer.

In a RepeatStar, a special hidden pair of input and output ports is created and connected together. This allows the star to schedule itself to execute at any desired future time(s), by emitting events with appropriate time stamps on the feedback loop port. The hidden ports are in every way identical to normal ports, except that they are not visible in the graphical user interface. The programmer of a derived star sometimes needs to be aware that these ports are present. For example, the star must not be declared to be a delay star (meaning that no input port can trigger a zero-delay output event) unless the condition also holds for the feedback port (meaning that refire events don't trigger immediate outputs either). See the Programmer's Manual for more information on using RepeatStar.

12.2.3 Simultaneous events

A special effort has been made to handle simultaneous events in a rational way. As noted above, all available simultaneous events at all input ports are made available to a star when it is fired. In addition, if two distinct stars can be fired because they both have events at their inputs with identical time stamps, some choice must be made as to which one to fire. A common strategy is to choose one arbitrarily. This scheme has the simplest implementation, but can lead to unexpected and counter-intuitive results from a simulation.

The choice of which to fire is made in Ptolemy by statically assigning priorities to the stars according to a topological sort. Thus, if one of two enabled stars could produce events with zero delay that would affect the other, as shown in figure

12-1, then that star will be fired first. The topological sort is actually even more sophisticated than we have indicated. It follows triggering relationships between input and output portholes selectively, according to assertions made in the star definition. Thus, the priorities are actually assigned to individual portholes, rather than to entire stars. See the Programmer's Manual for further details.

There is a pitfall in managing time stamps. Two time stamps are not considered equal unless they are exactly equal, to the limit of double-precision floating-point arithmetic. If two time stamps were computed by two separate paths, they are likely to differ in the least significant bits, unless all values in the computation can be represented exactly in a binary representation. If simultaneity is critical in a given application, then exact integral values should be used for time stamps. This will work reliably as long as the integers are small enough to be represented exactly as double-precision values. Note that the DE domain does not enforce integer timestamps --- it is up to the stars being used to generate only integer-valued event timestamps, perhaps by rounding off their calculated output event times.

12.2.4 Delay-free loops

Many stars in the DE domain produce events with the same time stamps as their input events. These zero-delay stars can create some subtleties in a simulation. An event-path consists of the physical arcs between output portholes and input portholes plus zero-delay paths inside the stars, through which an input event instantaneously triggers an output event. If an event-path forms a loop, we call it a delay-free loop. While a delay-free loop in the SDF domain results in a deadlock of the system, a delay-free loop in the DE domain potentially causes unbounded computation. Therefore, it is advisable to detect the delay-free loop at compile-time. If a delay-free loop is detected, an error is signaled.

Detecting delay-free loops reliably is difficult. Some stars, such as Server and Delay, take a parameter that specifies the amount of delay. If this is set to zero, it will fool the scheduler. It is the user's responsibility to avoid this pathological case. This is a special case of a more general problem, in which stars conditionally produce zero-delay events. Without requiring the scheduler to know a great deal about such stars, we cannot reliably detect zero-delay loops. What appears to be a delay-free path can be safe under conditions understood by the programmer. In such situations, the programmer can avoid the error message placing a delay element on some arc of the loop. The delay element is the small green diamond found at the top of every star palette in Pigi. It does not actually produce any time delay in simulated time. Instead, it declares to the scheduler that the arc with the delay element should be treated as if it had a delay, even though it does not. A delay element on a directed loop thus suppresses the detection of a delay-free loop.

Another way to think about a delay marker in the DE domain is that it tells the scheduler that it's OK for a particle crossing that arc to be processed in the "next" simulated instant, even if the particle is emitted with timestamp equal to current time. Particles with identical timestamps are normally processed in an order that gives dataflow-like behavior within a simulated instant. This is ensured by assigning suitable firing priorities to the stars. A delay marker causes its arc to be ignored while determining the dataflow-based priority of star firing; so a particle crossing that arc triggers a new round of dataflow-like evaluation.

12.2.5 Wormholes

"Time" in the DE domain means simulated time. The DE domain may be used in combination with other domains in Ptolemy, even if the other domains do not have a notion of simulated time. A given simulation, therefore, may involve several schedulers, some of which use a notion of simulated time, and some of which do not. There may also be more than one DE scheduler active in one simulation. The notion of time in the separate schedulers needs to be coordinated. This coordination is specific to the inner and outer domains of the wormhole. Important cases are described below.

SDF within DE

A common combination of domains pairs the SDF domain with the DE domain. There are two possible scenarios. If the SDF domain is inside the DE domain, as shown in figure
12-2, then the SDF subsystem appears to the DE system as a zero-delay block. Suppose, for example, that an event with time stamp
is available at the input to the SDF subsystem. Then when the DE scheduler reaches this time, it fires the SDF subsystem. The SDF subsystem runs the SDF scheduler through one iteration, consuming the input event. In response, it will typically produce one output event, and this output event will be given the time stamp
.

If the SDF subsystem in figure 12-2 is a multirate system, the effects are somewhat more subtle. First, a single event at the input may not be sufficient to cycle through one iteration of the SDF schedule. In this case, the SDF subsystem will simply return, having produced no output events. Only when enough input events have accumulated at the input will any output events be produced. Second, when output events are produced, more than one event may be produced. In the current implementation, all of the output events that are produced have the same time stamp. This may change in future implementations.

More care has to be taken when one wants an SDF subsystem to serve as a source star in a discrete-event domain. Recall that source stars in the DE domain have to schedule themselves. One solution is to create an SDF "source" subsystem that takes an input, and then connect a DE source to the input of the SDF wormhole. We are considering modifying the wormhole interface to support mixing sources from different domains automatically.

DE within SDF

The reverse scenario is where a DE subsystem is included within an SDF system. The key requirement, in this case, is that when the DE subsystem is fired, it must produce output events, since these will be expected by the SDF subsystem. A very simple example is shown in figure
12-3. The DE subsystem in the figure routes input events through a time delay. The events at the output of the time delay, however, will be events in the future. The Sampler star, therefore, is introduced to produce an output event at the current simulation time. This output event, therefore, is produced before the DE scheduler returns control to the output SDF scheduler.

The behavior shown in figure 12-3 may not be the desired behavior. The Sampler star, given an event on its control input (the bottom input), copies the most recent event from its data input (the left input) to the output. If there has been no input data event, then a zero-valued event is produced. There are many alternative ways to ensure that an output event is produced. For this reason, the mechanism for ensuring that this output event is produced is not built in. The user must understand the semantics of the interacting domains, and act accordingly.

Timed domains within timed domains

The DE domain is a timed domain. Suppose it contains another timed domain in a DE wormhole. In this case, the inner domain may need to be activated at a given point in simulated time even if there are no new events on its input portholes. Suppose, for instance, that the inner domain contains a clock that internally generates events at regular intervals. Then these events need to be processed at the appropriate time regardless of whether the inner system has any new external stimulus.

The mechanism for handling this situation is simple. When the internal domain is initialized or fired, it can, before returning, place itself on the event queue of the outer domain, much the same way that an event generator star would. This ensures that the inner event will be processed at the appropriate time in the overall chronology. Thus, when a timed domain sits within a timed domain wormhole, before returning control to the scheduler of the outer domain, it requests rescheduling at the time corresponding to the oldest time stamp on its event queue, if there is such an event.

When an internal timed domain is invoked by another time domain, it is told to run until a given "stop time," usually the time of the events at the inputs to the internal domain that triggered the invocation. This "stop time" is the current time of the outer scheduler. Since the inner scheduler is requested to not exceed that time, it can only produce events with time stamp equal to that time. Thus, a timed domain wormhole, when fired, will always either produce no output events, or produce output events with time stamp equal to the simulated time at which it was fired.

To get a time delay through such a wormhole, two firings are required. Suppose the first firing is triggered by an input event at time

, then the inside system generates an internal event at a future time
. Before returning control to the outer scheduler, the inner scheduler requests that it be reinvoked at time
. When the "current time" of the outer scheduler reaches
, it reinvokes the inner scheduler, which then produces an output event at time
.

With this conservative style of timed interaction, we say that the DE domain operates in the synchronized mode. Synchronized mode operation suffers significant overhead at run time, since the wormhole is called at every time increment in the inner timed domain. Sometimes, however, this approach is too conservative.

In some applications, when an input event arrives, we can safely execute the wormhole into the future until either (a) we reach the time of the next event on the event queue of the outer domain, or (b) there are no more events to process in the inner domain. In other words, in certain situations, we can safely ignore the request from the output domain that we execute only up until the time of the input event. As an experimental facility to improve run-time efficiency, an option avoids synchronized operation. Then, we say that the DE domain operates in the optimized mode. We specify this mode by setting the target parameter syncMode to FALSE (zero). This should only be done by knowledgeable users who understand the DE model of computation very well. The default value of the syncMode parameter is TRUE (one), which means synchronized operation.

12.2.6 DE Performance Issues

DE Performance can be an issue with large, long-running universes. Below we discuss a few potential solutions.

The calendar queue scheduler is not always the one to use. It works well as long as the "density" of events in simulated time is fairly uniform. But if events are very irregularly spaced, you may get better performance with the simpler scheduler, because it makes no assumptions about timestamp values. For example, Tom Lane reported that the CQ scheduler did not behave well in a simulation that had a few events at time zero and then the bulk of the events between times 800000000 and 810000000 --- most of the events ended up in a single CQ "bucket", so that performance was worse than the simple scheduler.

Tom Lane also pointed out that both the CQ and simple schedulers ultimately depend on simple linear lists of events. If your application usually has large numbers of events pending, it might be worth trying to replace these lists with genuine priority queues (i.e., heaps, with O(log N) rather than O(N) performance). But you ought to profile first to see if that's really a time sink.

Another thing to keep in mind that the overhead for selecting a next event and firing a star is fairly large compared to other domains such as SDF. It helps if your stars do a reasonable amount of useful work per firing; that is, DE encourages "heavyweight" stars. One way to get around this is to put purely computational subsystems inside SDF wormholes. As discussedpreviously, an SDF-in-DE wormhole acts as a zero-delay star.

If you are running a long simulation, you should be sure that your machine is not paging or worse yet swapping; you should have plenty of memory. Usually 64Mb is enough, though 128Mb can help (gdb takes up a great deal of memory when you use it, too.). Depending on what platform you are on, you may be able to use the program top (ftp://eecs.nwu.edu/pub/top). You might also find it useful to use iostat to see if you are paging or swapping.

One way to gain a slight amount of speed is to avoid the GUI interface entirely by using ptcl, which does not have Tk stars. See "Some hints on advanced uses of ptcl with pigi" on page 3-19 for details.


Top Up Prev Next Bottom Contents Index Search

Copyright © 1990-1997, University of California. All rights reserved.