Hierarchical Static Scheduling of Dataflow Graphs onto Multiple Processors
The first clustering technique is by far the simplest: we allow the user to specify clusters that will be mapped onto a single processor. This clustering technique empowers the user with fundamental scheduling decisions. A potential problem is that the user can introduce artificial deadlock. However, this error is easily caught at compile time [14]. When we automatically cluster subgraphs, we must ensure that the constructed clusters do not introduce artificial deadlock. To do this we can apply the four cluster conditions listed in [13].
The next clustering technique takes into account resource constraints. When mapping SDF graphs onto heterogeneous processors, a group of connected actors may be required to be mapped onto a particular processor. Here, we are free to cluster these SDF subgraphs as long as we do not introduce artificial deadlock.
In the last two clustering techniques, we cluster chains of SDF actors. A chain structured SDF subgraph is one in which each actor is connected to at most two other actors. One source actor is connected to all the input arcs and one destination actor is connected to all the output arcs. Thus, when clustering chain structured SDF subgraphs, we do not group over branch or merge SDF actors (actors which have multiple sources or destinations), where functional parallelism is exposed.
The third clustering technique groups the actors in a homogeneous chain structured SDF subgraph where the actors do not have internal state (or equivalently, have self loop arcs). A homogeneous SDF subgraph is one in which the number of outputs produced on an arc is equal to the number of inputs consumed on that arc (see figure 3). This clustering does not hide any of the available parallelism that will be exposed in the final DAG. These clusters obey the linear clustering heuristic described in [11] for DAG multiprocessor scheduling.
Finally, the last clustering technique groups the actors in chain structured subgraphs made up of multirate actors having internal state. Internal state introduces dependencies between the various repetitions of an actor in a schedule period, thereby reducing the data parallelism available. For example, if the actors in the SDF graph shown in figure 1 had internal state, then the resultant DAG shown in figure 2 would have additional precedence arcs connecting A1-->A2-->A3 and B1-->B2. Unlike the previous three clustering heuristics, this technique can hide some of the available parallelism although in this case, it does not.