Mapping Multiple Independent Synchronous Dataflow Graphs

3 Model of computation

3.1 Synchronous dataflow

Figure 2 shows a simple SDF graph. In this graph, actor A produces two tokens and actor B consumes three tokens for each firing. In a valid SDF schedule, the number of tokens in the first-in/first-out (FIFO) buffers of each arc returns to the initial state after one schedule period. Balance equations are written for each arc and an integral repetitions vector is found that solves this system of equations [5]. In this simple example, the balance equation for the arc is: . Thus the repetition vector is: . One possible valid schedule for this graph is AABAB. So, given an SDF specification, we can find a schedule at compile-time that is iterated at run-time.

3.2 Multiple independent SDF graphs

In our model, we allow multiple independent dataflow graphs as shown in figure 3. Here we have two independent graphs communicating nondeterminately over the dotted arcs. These arcs do not add data dependencies. The actors A and B are the same as in the previous example, and actors C, D, and E each produce/consume one token on each arc per firing. The schedule for the first graph is 3(A)2(B); the schedule for the second graph is CDE. One can think of the independent graphs as separate communicating processes.

3.3 Introducing nondeterminism: peek and poke

For the dotted arcs in figure 3, we splice in peek and poke actors. This is done in much the same way as send and receive actors are spliced in for self-timed SDF multiprocessor implementations. The peek/poke actors are similar to the send/receive actors except they do not block on the state of their buffer (see figure 4). A send/receive pair has a blocking FIFO buffer between the actors. The send actor will block on a write if the FIFO is full, and the receive actor will block on a read if the FIFO is empty. This guarantees that there is no data loss and that old data is not be reused. In contrast, the peek actor will reuse old data if there is no new data available, and the poke actor will overwrite old data to make new data available. Thus a peek actor appears to be a data source and the poke actor appears to be a data sink to the independent SDF schedulers. Furthermore, unlike the SDF use of send/receive for interprocessor communication only, a peek/poke pair can be used for either inter- or intra-processor communication.

The various properties of peek/poke actor pairs that we have found useful allow us to:

• update the link at the implicit rate of the graphs or at a user-specified rate

• transfer single tokens

• transfer a block of consecutive tokens with a sliding window (see figure 5)

• transfer a block of consecutive tokens aligned to block boundaries (see figure 5)

The next properties of the peek/poke actors are the number and alignment of data transferred. Transferring multiple tokens per update gives the user a window into a signal. Because there is no synchronization, the window slides by an arbitrary amount. Some tokens could be skipped, or consecutive windows could overlap and tokens would be reused. The advantage of controlling the alignment is two fold: it enables the user to download multiple run-time parameters simultaneously; and it enables downloading of a signal (such as a computed FFT) where the alignment is crucial. Again, because there is no synchronization, some blocks could be skipped and others reused.

[Next] [Previous] [Top]