SDF Domain

Introduction

Synchronous Data Flow (SDF) is a data-driven, statically scheduled domain in MLDesigner. It is a direct implementation of the techniques given in [B1] and [B2].

Data-driven means that the availability of Particles at the inputs of a primitive enables it. Primitives without any inputs are always enabled (including disconnected Xgraphs).

Statically scheduled means that the firing order of the primitives is determined once during the start-up phase. The firing order will be periodic.

The SDF domain is one of the most mature in MLDesigner, having a large library of primitives and demo programs. It is a simulation domain, but the model of computation is the same as that used in most of the code generation domains. A number of different schedulers, including parallel schedulers, have been developed for this model of computation.

Basic data flow terminology

SDF is a special case of the data flow model introduced by Dennis [B24]. In the terminology of the data flow literature, primitives are called actors. An invocation of the go() method of a primitive is called a firing. Particles are called tokens. In a digital signal processing system, a sequence of tokens might represent a sequence of samples of a speech signal or a sequence of frames in a video sequence.

When an actor fires, it consumes a number of tokens from its input arcs, and produces a number of output tokens. In synchronous data flow, these numbers remain constant throughout the execution of the system. It is for this reason that this model of computation is suitable for synchronous signal processing systems, but not for asynchronous systems. The fact that the firing pattern is determined statically is both a strength and a weakness of this domain. It means that long runs can be very efficient, a fact that is heavily exploited in the code generation domains. But it also means that data-dependent flow of control is not allowed. This would require dynamically changing firing patterns. The Dynamic Data Flow (DDF) and Boolean Data Flow (BDF) domains were developed to support this.

Balancing production and consumption of tokens

Each porthole of each SDF primitive has an attribute that specifies the number of particles consumed (for input ports) or the number of particles produced (for output ports). When you connect two portholes with an arc, the number of particles produced on the arc by the source primitive may not be the same as the number of particles consumed from that arc by the destination primitive. To maintain a balanced system, the scheduler must fire the source and destination primitives with different frequency.

Consider a simple connection between three primitives. The symbols adjacent to the portholes, such as \fs1N, represent the number of particles consumed or produced by that porthole when the primitive fires. For many signal processing primitives, these numbers are simply one, indicating that only a single token is consumed or produced when the primitive fires. But there are three basic circumstances in which these numbers differ from one:

-
Vector processing in the SDF domain can be accomplished by consuming and producing multiple tokens on a single firing. For example, a primitive that computes a fast Fourier transform (FFT) will typically consume and produce \fs12M samples when it fires, where \fs1M is an integer. Examples of vector processing primitives that work this way are FFTCx, Burg, and LevinsonDurbin found in the MLD Libraries→SDF Domain→DSP library. This behavior is quite different from the matrix primitives, which operate on particles where each individual particle represents a matrix.
-
In multi-rate signal processing systems, a primitive may consume \fs1M samples and produce \fs1N, thus achieving a sampling rate conversion of \fs1\frac{N}{M}. For example, the FIRFloat and FIRCx primitives optionally perform such a sampling rate conversion, and with an appropriate choice of filter coefficients, can interpolate between samples. Other primitives that perform sample rate conversion include UpSample, DownSample, and Chop. They can be found in MLD Libraries→SDF Domain→Control.
-
Multiple signals can be merged using primitives such as Commutator or a single signal can be split into sub signals at a lower sample rate using the Distributor primitive. They can be found in MLD Libraries→SDF Domain→Control, too.

To be able to handle these circumstances, the scheduler first associates a simple balance equation with each connection in the graph. For the graph depicted above, the balance equations are

r_A N_{A1}=r_{C}N_{C1}

r_A N_{A2}=r_{B}N_{B1}

r_B N_{B2}=r_{C}N_{C2}

This is a set of three simultaneous equations in three unknowns. The unknowns, \fs1rA , \fs1rB and \fs1rC are the repetitions of each actor that are required to maintain balance on each arc. The first task of the scheduler is to find the smallest non-zero integer solution for these repetitions. It is proven in [B1] that such a solution exists and is unique for every SDF graph that is consistent, as defined below.

Iterations in SDF

When running an SDF system under the graphical user interface, you will have the opportunity to specify the Run Length. Since the SDF domain has no notion of time, this is not given in units of time. Instead, it is given in units of SDF iterations. At each SDF iteration, each primitive is fired the minimum number of times to satisfy the balance equations.

Create a system with the modeling domain set as SDF containing a Const.level primitive from the Sources Library, an FFTCx from the DSP Library and an XMgraph from the Sinks Library. Select the primitive FFTCx and make sure the parameter FFTLength is set to 128 and SamplesPerBlock is set to -1. It will consume 128 samples and produce 128 samples. The Const.level primitive produces exactly one sample on each output, and the XMgraph primitive consumes one sample from each input.

In summary,

N_{A1} = N_{A2} = N_{C1} = N_{C2} = 1

N_{B1} = N_{B2} = 128

The balance equations become

r_A = r_C

r_A = 128\cdot r_B

128\cdot r_B = r_C

The smallest integer solution is

r_A = r_C = 128

r_B = 1

 

Hence, each iteration of the system includes one firing of the FFTCx primitive and 128 firings each of primitives A and B.

System illustrating iterations in the SDF domain

Inconsistency

It is not always possible to solve the balance equations. Suppose that we have

N_{A1} = N_{A2} = N_{C1} = N_{C2} = N_{B1} = 1

N_{B2} = 2

In this case, the balance equations have no non-zero solution. The problem with this system is that there is no sequence of firings that can be repeated indefinitely with bounded memory. If we fire A,B,C in sequence, a single token will be left over on the arc between B and C. If we repeat this sequence, two tokens will be left over. Such a system is said to be inconsistent, and is flagged as an error. The SDF scheduler will refuse to run it. If you must run such a system, change the domain of your graph to the DDF domain.

Delays

Delays are indicated in MLDesigner by small green diamonds that are placed on an arc. Delays are created using the Add Delay toolbar button on the Modeling toolbar. Please refer to Modeling→Developing Models→Buses and Delays for more information.

The delay has a single parameter, the number of samples of delay to be introduced. In the SDF domain, a delay with parameter equal to one is simply an initial particle on an arc. This initial particle may enable a primitive, assuming that the destination primitive for the delay arc requires one particle in order to fire. To avoid deadlock, all feedback loops must have delays. The SDF scheduler will throw an error if it finds a loop with no delays.

For most particle types, the initial value of a delay will be zero. For particles which hold matrices, the initial value is an empty envelope, which must be checked for by primitives which work on matrix inputs. Initializable delays allow the user to give values to the initial particles placed in the buffer.

Targets

Primitives

Demos

A rather large number of SDF demonstrations have been developed. These can serve as valuable illustrations of the possibilities. Almost every primitive is illustrated in the demos. Because of the large number, the demos are organized into a set of libraries. Certain demos may appear in more than one library.