Synchronous Dataflow Networks

Synchronous Dataflow Networks (SDF) is a special case of Dataflow Networks in which the number of tokens consumed and produced by an actor is known before the execution begins. The same behavior repeats in a particular actor every time it is fired. Arcs can have initial tokens. Every initial token represents an offset between the token produced and the token consumed at the other end. It is a unit delay and is represented by a diamond in the middle of the arc. Figure 1.6 illustrates a Synchronous Dataflow Network.

Schedule can be performed statically. As the execution of the graph is going to be repeated the compiler should just construct one ``complete cycle'' of the periodic schedule. A ``complete cycle'' is defined as the sequence of actor firings that returns the graph to its original state. From the static information of the network we can construct a ``topology matrix'' that contains relations between produced/consumed tokens in every arc. The element ij is defined as the number of tokens produced on the ith arc by the jth actor. Although it is only a partial info because there is no information on the number of initial tokens on each arc we can use the matrix to build the static schedule. For doing so we must find the smallest integer vector that satisfies the equation matrix*vector=0. It must be noted though that in complex networks these equations may not have a solution.

Figure 1.6: A Synchronous Dataflow Process Network