Hierarchical Static Scheduling of Dataflow Graphs onto Multiple Processors
In this section we detail a quadrature phase-shift keying(QPSK) acoustical model [15] which is scheduled onto two heterogeneous processors (RISC, DSP). The SDF specification is shown in figure 5. A pseudo-random bit stream is generated on the workstation and then packed into a DSP word stream(22 bits/word). The stream of words is sent to a DSP which unpacks each word to form a bit stream. These bits are then encoded into a symbol (2 bits/symbol). The DSP transmits and then receives the symbol stream over a speaker/microphone channel. The received symbols are then decoded, packed and sent back to the workstation, where the errors are displayed to the user. The user can control the alignment of the symbol period and examine the resultant constellation using the peek/poke mechanism described in [16]. All of the transmitter and receiver filters are polyphase FIR filters with interpolation and decimation factors of 32 samples respectively.
Note that the SDF graph shown in figure 5 is expressed hierarchically. There are a total of 38 SDF actors; the corresponding DAG has a total of 2100 nodes. Since we are able to use SDF uniprocessor schedulers on the SDF subgraph clusters, for this example, we are able to obtain a single appearance schedule which leads to very compact code. A single appearance schedule is an SDF schedule in which each actor only appears once [13]. To obtain the single appearance schedule, three uniprocessor schedulers and one multiprocessor scheduler were used by the hierarchical scheduling framework. By using the cluster hierarchy, the multiprocessor scheduler only had to schedule a DAG with 8 nodes. The multiprocessor schedule generated from the fully expanded DAG graph, has one function call (or inlined procedure) for each of its 2100 nodes as compared to the 38 function calls for the hierarchical schedule.
Finally, the makespans of the schedules generated using the hierarchical scheduler and traditional full DAG expansion varied by less than 4% (the hierarchical being longer). The difference is due to the fact that a cluster of SDF actors is treated as an atomic SDF actor by the outside scheduler. Hence all of the inputs must be available before the cluster fires. Furthermore, none of the outputs will be available until a cluster schedule iteration is completed. We are investigating cyclo-static dataflow [17] as a method to eliminate the variance in makespans. In cyclo-static dataflow, each actor firing has distinct phases. Each phase produces and consumes a fixed amount of data at each input and output. The cluster schedule could then be expressed in schedule phases, thereby allowing part of the cluster to fire as soon as some of the input was available (versus waiting for all of the input for all of the phases).