In DDF, a run-time scheduler detects which stars are runnable and fires them one by one until no star is runnable (the system is deadlocked), or until a specified stopping condition has been reached. A star is runnable if it has enough data on its inputs to satisfy its requirements. Thus, the only constraint on DDF stars is that they must specify on each firing how much data they require on each input to be fired again later.
In practice, stars in the DDF domain are written in a slightly simpler way. They are either SDF stars, in which case the number of particles required at each input is a constant, or they are dynamic, in which case they always alert the scheduler before finishing a firing that to be refired they expect some specific number of particles on one particular input. The input that a star is waiting for data on is called the waitPort.
Since the DDF domain is a superset of the SDF domain, all SDF stars can be used in the DDF domain. Similarly for BDF stars. Besides the SDF stars, the DDF domain has some DDF-specific stars that will be described in this chapter. The DDF-specific stars overcome the main modeling limitation of the SDF domain in that they can model dynamic constructs such as conditionals, data-dependent iteration, and recursion. All of these except recursion are also supported by the BDF domain. It is even possible, in principle, to dynamically modify a DDF graph as it executes (the implementation of recursion does exactly this). The lower run-time efficiency of dynamic scheduling is the cost that we have to pay for the enhanced modeling power.
Run-time scheduling is expensive. In figure
ptrimexecutable (on August 26, 1995). The default schedulers in the SDF and DDF domains were used. Note that both schedulers took approximately 13ms at startup, and then exhibited a close to linear increase in execution time. For the SDF scheduler, the slope is approximately 650 µs per iteration, while for the DDF scheduler, it is approximately 1,370 µs per iteration. With 17 stars, this comes to about 38 µs per firing for SDF and 81 µs per firing for DDF. For multirate systems, both of these schedulers will perform poorly compared to the loop scheduler in SDF. Note that for this simple system, DDF is more than twice as expensive as SDF. For systems that require DDF, Ptolemy allows us to regain much of this efficiency by grouping SDF stars in a wormhole that contains an SDF domain. For critical systems that are executed for many iterations, this can provide for considerably faster execution.
There are some subtleties, however, in DDF scheduling. Due to these subtleties, there have been three DDF schedulers implemented, all accessible by setting appropriate target parameters. In the next section, we explain these schedulers.