Default SDF target

The default SDF target has a simple set of options:

The name of a file into which the scheduler will write the final schedule. The initial default is an empty string.
(FLOAT) Default = 0.0
A floating-point number defining the time taken by one iteration through the schedule. This is not needed for pure SDF systems, but if SDF systems are mixed with timed domains, such as DE, then this will determine the amount of simulated time taken by one iteration.
(STRING) Default = Default Scheduler
A String specifying whether to attempt to compact the schedule for forming looping structure (see below). Choices are Default Scheduler, Cluster Scheduler and Acyloop Scheduler.

Default Scheduler

The SDF scheduler determines the order of execution of primitives in a system at start time. It performs most of its computation during its setup() phase. If the usedScheduler target parameter is set to Default Scheduler, then we get a scheduler that exactly implements the method described in [B1] for sequential schedules. If there are sample rate changes in a program graph, some parts of the graph are executed multiple times. This scheduler does not attempt to generate loops; it simply generates a linear list of blocks to be executed. For example, if primitive A is executed 100 times, the generated schedule includes 100 instances of A. A loop scheduler will include in its "looped" schedule (where possible) only one instance of A and indicate the repetition count of A, as in (100 A). For simulation, a long unstructured list might be tolerable, but not in code generation. (The SDF schedulers are also used in the code generation for a single processor target).

Neglecting the overhead due to each loop, an optimally compact looped schedule is one that contains only one instance of each actor, and we refer to such schedules as single appearance schedules. For example, the looped schedule \fs1(3A)(2B), corresponding to the firing sequence \fs1AAABB, is a single appearance schedule, whereas the schedule \fs1AB(2A)B is not.

Cluster Scheduler

By setting the usedScheduler target parameter to Cluster Scheduler, we select a scheduler developed by Joe Buck. Before applying the non-looping scheduling algorithm, this algorithm collects actors into a hierarchy of clusters. This clustering algorithm consists of alternating a merging step and a looping step until no further changes can be made. In the merging step, blocks connected together are merged into a cluster if there is no sample rate change between them and the merge will not introduce deadlock. In the looping step, a cluster is looped until it is possible to merge it with the neighbor blocks or clusters. Since this looping algorithm is conservative, some complicated looping possibilities are not always discovered. Hence, even if a graph has a single appearance schedule, this heuristic may not find it.

Acyloop Scheduler

Setting the usedScheduler target parameter to Acyloop Scheduler results in another loop scheduler being selected, this one developed by Praveen Murthy and Shuvra Bhattacharyya. This scheduler only tackles acyclic SDF graphs, and if it finds that the system is not acyclic, it automatically resets the usedScheduler target parameter to Cluster Scheduler.

This scheduler is optimized for program as well as buffer memory. Basically, for a given SDF graph, there could be many different single appearance schedules. These are all optimally compact in terms of schedule length (or program memory in inline code generation). However, they will, in general, require differing amounts of buffering memory; the difference in the buffer memory requirement of an arbitrary single appearance schedule versus a single appearance schedule optimized for buffer memory usage can be dramatic. Again, in simulation this does not make that much difference (unless really large SDF graphs with large rate changes are being simulated of-course), but in code generation it is very helpful.

Note that acyclic SDF graphs always have single appearance schedules; hence, this scheduler will always give single appearance schedules. If the logFile target parameter is set, then a summary of internal scheduling steps will be written to that file. Essentially, two different heuristics are used by the Acyloop Scheduler, called APGAN and RPMC, and the better one of the two is selected. The generated file will contain the schedule generated by each algorithm, the resulting buffer memory requirement, and a lower bound on the buffer memory requirement (called BMLB) over all possible single appearance schedules.

Note that the Acyloop Scheduler modifies the system during its computations; hence, scripted runs that depend on the system remaining in the original state, cannot be used with this scheduler. Since the system reverts to its original state after a run sequence, the Acyloop Scheduler will work fine in normal usage.