The loop-SDF target

An exact looping algorithm, available in an alternative target called the loop-SDF target, was developed by adding post-processing steps to the Cluster loop scheduling algorithm. For lack of a better name, this technique is called "SJS scheduling", for the first initials of the designers (Shuvra Bhattacharyya, Joe Buck, and Soonhoi Ha).

In the post-processing, the attempt was to decompose the graph into a hierarchy of acyclic graphs [B13], for which a compact looped schedule can easily be constructed. Cyclic subgraphs that cannot be decomposed by this method, called tightly interdependent subgraphs, are expanded to acyclic precedence graphs in which looping structures are extracted by the techniques developed in [B15] and extensions to these techniques developed by Soonhoi Ha. This scheduling option is selected when the loop SDF target is chosen instead of the default SDF target. The target options are:

The name of a file into which the scheduler will write the final schedule. The initial default is an empty string.
(FLOAT) Default = 10000.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.

When there are sample rate changes in the program graph, the default SDF scheduler may be much slower than the loop schedulers, and in code generation, the resulting schedules may lead to unacceptably large code size. Buck's scheduler provides a fast way to get compact looped schedules for many program graphs, although there are no guarantees of optimality. The somewhat slower SJS scheduler is guaranteed to find a single appearance schedule whenever one exists [B14]. Furthermore, a schedule generated by the SJS scheduler contains only one instance of each actor that is not contained in a tightly interdependent subgraph. However, neither the SJS scheduler nor Buck's scheduler will attempt to optimize for buffer memory usage; this need is met by the Acyloop Scheduler chosen through the default-SDF target, for acyclic graphs. Algorithms for generating single appearance schedules optimized for buffer memory systematically for graphs that may contain cycles have not yet been implemented.

The looped result can be seen by setting the logFile target parameter. That file will contain all the intermediate procedures of looping and the final scheduling result. The loop scheduling algorithms are usually used in code generation domains, not in the simulation SDF domain.