Events and chronology

A DE primitive 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 timestamp 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 timestamps; the earliest event in simulated time being at the head of the queue. The difference between the schedulers is primarily in the management of this event queue.

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 primitive is executed (fired) whenever there is a new event on any of its input portholes. Before executing the primitive, the scheduler searches the event queue to find out whether there are any simultaneous events at the other input portholes of the same primitive, and fetches those events. Thus, for each firing, a primitive 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.

Event generators

Some DE primitives are event generators which 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 primitive itself, which gives the time at which it wishes to be refired. All such primitives are derived from the base class RepeatStar.

RepeatStar is also used by primitives 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 the PSServer primitive which can be found in the Queues library.

In a RepeatStar, a special hidden pair of input and output ports is created and connected together. This allows the primitive to schedule itself to execute at any desired future time(s), by emitting events with appropriate timestamps 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 primitive sometimes needs to be aware that these ports are present. For example, the primitive must not be declared to be a delay primitive (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 Programming Primitives in the DE Domain→Source Primitives for more information on using RepeatStar.

Simultaneous events

A special effort has been made to handle simultaneous events in a rational way. As noted earlier, all available simultaneous events at all input ports are made available to a primitive when it is fired. In addition, if two distinct primitives can be fired because they both have events at their inputs with identical timestamps, 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 MLDesigner by statically assigning priorities to the primitives according to a topological sort. Thus, if one of two enabled primitives could produce events with zero delay that would affect the other, as depicted below, then that primitive 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 primitive definition. Thus, the priorities are actually assigned to individual portholes, rather than to entire primitives. See Programming Primitives in the DE Domain→Simultaneous Events for further details.

When DE primitives are enabled by simultaneous events, the choice of which to fire is determined by priorities based on a topological sort. Thus if B and C both have events with identical timestamps, B will take priority over C. The delay on the path from C to A serves to break the topological sort.

There is a pitfall in managing timestamps. Two timestamps are not considered equal unless they are exactly equal, to the limit of double-precision floating-point arithmetic. If two timestamps 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 timestamps. 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 primitives being used to generate only integer-valued event timestamps, perhaps by rounding off their calculated output event times.

Delay-free loops

Many primitives in the DE domain produce events with the same timestamps as their input events. These zero-delay primitives 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 primitives, 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 primitives, 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 primitives conditionally produce zero-delay events. Without requiring the scheduler to know a great deal about such primitives, 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. 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 data-flow-like behavior within a simulated instant. This is ensured by assigning suitable firing priorities to the primitives. A delay marker causes its arc to be ignored while determining the data-flow-based priority of primitive firing; so a particle crossing that arc triggers a new round of data-flow-like evaluation.