Hierarchical Static Scheduling of Dataflow Graphs onto Multiple Processors
Generating a stand-alone application from a dataflow graph description consists of two phases: scheduling and synthesis [2]. In the scheduling phase, the dataflow graph is partitioned for parallel execution. We splice send and receive actors into the graph for interprocessor communication. These actors do the synchronization necessary for a self-timed implementation [3]. For each target processor, a sequence of actor firings is determined. In the synthesis phase, the code segments associated with each actor are stitched together, following the order specified by the scheduler. Commercial systems that use this "threading" technique include Comdisco's DPC [4] and CADIS's Descartes [5]. The techniques we describe here are complementary to those in DPC and Descartes, and could, in principle, be used in combination with them.
There are several forms of dataflow defined in Ptolemy. In synchronous dataflow (SDF) [6], the number of tokens produced or consumed in one firing of an actor is constant. This property makes it possible to determine execution order and memory requirements at compile time. Thus these systems do not have the overhead of run-time scheduling (in contrast to dynamic dataflow) and have very predictable run-time behavior. The production/consumption property on the arcs also provides a natural representation of multirate signal processing blocks [7]. In this paper, we will focus on scheduling SDF graphs onto multiple processors.
In the following sections, we will review scheduling of SDF graphs including uniprocessor scheduling and DAG construction. Then we will discuss the clustering techniques that make up the hierarchical scheduling framework. Finally, we look at extensions to current DAG schedulers that use declustering in order to break larger grain clusters to expose parallelism. In these circumstances we are able to delay (and possibly avoid) the expansion of SDF sub-graphs into the overall DAG.