Top Up Prev Next Bottom Contents Index Search

5.4 Targets

As is typical of simulation domains, the SDF domain does not have many targets. To choose one of these targets, with your mouse cursor in a schematic window, execute the edit-target command under the Edit vem menu choice (or just type "T"). You will get a list of the available Targets in the SDF domain. The "default-SDF" target is normally selected by default. When you click OK, dialog box appears with the parameters of the target. You can edit these, or accept the defaults. The next time you run the schematic, the selected target will be used. For more information, see "Summary of Uniprocessor schedulers" on page 4-11.

5.4.1 Default SDF target

The default SDF target has a simple set of options:

logFile (STRING) Default =
The name of a file into which the scheduler will write the final schedule. The initial default is the empty string.
loopScheduler (STRING) Default = DEF
A String specifying whether to attempt to compact the schedule for forming looping structure (see below). Choices are DEF, CLUST, ACYLOOP. The case does not matter: DEF, def, Def are all the same. For backward compatibility, "0" or "NO", and "1" or "YES" are also recognized, with "0" or "NO" being DEF, and "1" or "YES" being CLUST.
schedulePeriod (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.
The SDF scheduler determines the order of execution of stars in a system at start time. It performs most of its computation during its setup() phase. If the loopScheduler target parameter is DEF, then we get a scheduler that exactly implements the method described in [Lee87a] 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 star 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 (3 A)(2 B), corresponding to the firing sequence AAABB, is a single appearance schedule, whereas the schedule AB(2 A)B is not.

By setting the loopScheduler target parameter to CLUST, 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.

Setting the loopScheduler target parameter to ACYLOOP results in another loop scheduler being selected, this one developed by Praveen Murthy and Shuvra `Bhattacharyya [Mur96][Bha96]. This scheduler only tackles acyclic SDF graphs, and if it finds that the universe is not acyclic, it automatically resets the loopScheduler target parameter to CLUST. 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 universe during its computations; hence, scripted runs that depend on the universe remaining in the original state, cannot be used with this scheduler. Since the universe reverts to its original state after a run sequence, the ACYLOOP scheduler will work fine in normal usage.

5.4.2 The loop-SDF target

An exact looping algorithm, available in an alternative target called the loop-SDF target, was developed by adding postprocessing steps to the CLUST loop scheduling algorithm. For lack of a better name, we call this technique "SJS scheduling", for the first initials of the designers (Shuvra Bhattacharyya, Joe Buck, and Soonhoi Ha). In the postprocessing, we attempt to decompose the graph into a hierarchy of acyclic graphs [Bha93b], 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 [Bha94a] and extensions to these techniques developed by Soonhoi Ha. This scheduling option is selected when the loopTarget is chosen instead of the default SDF target. The target options are:

They have the same interpretation as for the default target, but in the loop-SDF target, schedulePeriod has an initial default of 10000.0.

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 [Bha93c]. 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 as described above, 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. Refer to the Code Generation domain documentation for a detailed discussion to the section on "Schedulers" on page 13-6.

5.4.3 Compile-SDF target

A third target in the SDF domain, called compile-SDF. Instead of executing a simulation by invoking the go() methods of stars from within the Ptolemy process, it generates a C++ program that implements the universe, links it with appropriate parts of the Ptolemy kernel, and then invokes that system. The schedule is constructed statically, so the generated program has no scheduler linked in. Instead, the generated code directly invokes the go() methods of the stars. The target parameters are:

The directory into which to place the generated code.
LoopingLevel (STRING) Default = ACYLOOP
The choices are DEF, CLUST, SJS, or ACYLOOP. Case does not matter; ACYLOOP is the same as AcyLoOP. If the value is DEF, no attempt will be made to construct a looped schedule. This can result in very large programs for multirate systems, since inline code generation is used, where a codeblock is inserted for each appearance of an actor in the schedule. Setting the level to CLUST invokes a quick and simple loop scheduler that may not always give single appearance schedules. Setting it to SJS invokes the more sophisticated SJS loop scheduler, which can take more time to execute, but is guaranteed to find single appearance schedules whenever they exist. Setting it to ACYLOOP invokes a scheduler that generates single appearance schedules optimized for buffer memory usage, as long as the graph is acyclic. If the graph is not acyclic, and ACYLOOP has been chosen, then the target automatically reverts to the SJS scheduler. For backward compatibility, "0" or "NO", "1", and "2" or "YES" are also recognized, with "0" or "NO" being DEF, "1" being CLUST, and "2" or "YES" being SJS.
writeSchedule? (INT) Default = NO
If the value is YES, then the schedule is written out to a file named.sched in the directory named by the directory target parameter.
If you wish to try this SDF target, open any of the basic SDF demos in figure 5-22, edit the target to change it to the compile-SDF target (in vem, hit T), and run the system. You can then examine the source code and makefile that are placed in the specified directory. An executable with the same name as the name of the demo will also be placed in that directory. This is a standalone executable that does not require any part of the Ptolemy system to run (except for the Ptolemy Tcl/Tk startup scripts in $PTOLEMY/lib/tcl). For example, if you choose the butterfly demo in figure 5-22, your destination directory will contain the following files:

The first of these is executable. Try executing it. You can modify the number of sample points generated using a command-line argument. For example, to generate 1,000 points instead of 10,000, type

butterfly 1000
The compile-SDF target is an example of a code-generation Target within the SDF domain. So, in a very fundamental way, a Target defines the way a system is executed. The default target is essentially an interpreter. The compile-SDF target synthesizes a standalone program and then executes it on the native workstation. It should be viewed merely as an example of the kinds of extensions users can build. More elaborate targets parallelize the code and execute the resulting programs on remote hardware. Targets can be defined by users and can make use of existing Ptolemy schedulers. Knowledgeable users can also define their own schedulers.

The compile-SDF target first creates the C++ source code for the current universe in a file of the same name of the universe followed by .cc. Then, it copies the C++ code into and builds the makefile to compile using the make template file CompileMake.template in the $PTOLEMY/lib directory. Next, the compile-SDF target runs the makefile to compile into an executable called code. The compile-SDF target then renames code to the name of the Ptolemy universe. If there is an error reported by make, then it is likely that one of make configuration variables is incorrect. The makefile includes the configuration makefile for the workstation you are using. The configuration makefiles are in the $PTOLEMY/mk directory.

The compile-SDF target has a number of known problems:

We would welcome any assistance in fixing these problems.

5.4.4 SDF to PTCL target

The SDF-to-PTCL target was introduced in Ptolemy 0.6. This target is substantially incomplete, we give a rough outline below. We hope to complete work on the SDF-to-PTCL target in a later release. The SDF-to-PTCL target uses CGMultiInOut stars to generate abstract ptcl graphs which capture the SDF semantics of a simulation SDF universe. These abstract graphs can then be used to test SDF schedulers.

The ptcl output filename will use the universe name as a prefix, and append .pt to the name (e.g., the ptcl output for the butterfly demo would be in Currently the directory that will contain the ptcl output is hardwired to ~/PTOLEMY_SYSTEMS/ptcl/. You may need to create this directory by hand.

The most interesting aspect about the target is that it collects statistics on the execution time of each star. This is valuable for seeing the relative runtimes of the various stars which can be used in code generation. It collects statistics by running the scheduled universe, accumulating elapsed CPU time totals for each star. This new target does not call the wrapup methods of the stars, so you will not see XGraph outputs.

Top Up Prev Next Bottom Contents Index Search

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