Decidable Dataflow Models for Signal Processing: Synchronous Dataflow and Its Extensions - Signal Processing Systems - page 1080

1 1 1/3 1/2

A B C

1/3 1/2

Fig. 11 An FRDF graph in which sample types on arc BC and AC are a composite and a primitive
type respectively

×

sample is a macroblock-size data that represents a 16 16 array of pixel differences.

Node EN performs macroblock encoding by consuming one macroblock at a time
and produces one encoded macroblock as its output sample.
This SDF representation is not efficient in terms of buffer requirement and
performance. Since node ME produces 99 macroblock-size samples at once after
consuming a single frame size sample at each invocation, we need a 99-macroblock-
size buffer or a frame-size buffer (99

× × = ×

144) to store the samples on
the arc between nodes ME and EN. Moreover node EN cannot start execution before
node ME finishes motion estimation for the whole input frame. As this example
demonstrates, the SDF model has inherent difficulty of efficiently expressing
the mixture of a composite data type and its constituents: a video frame and
macroblocks in this example. A video frame is regarded as a unit of data sample in
integer rate dataflow graphs, and should be broken down into multiple macroblocks
explicitly by consuming extra memory space.
To overcome this difficulty, the fractional rate dataflow (FRDF) model in which a
fractional number of samples can be produced or consumed has been proposed [ 14 ] .
In FRDF, a fraction number can be used as a sample rate as shown in Fig. 10 b where
the input sample rates of node frME is set to 99 . The fractional number means that
the input data type of node frME is a macroblock and it corresponds to

16 16 176

1
99

of a frame

data.
Figure 11 shows an FRDF graph where the data type of arc BC is a composite
type as illustrated in the figure and the data type of arc AC is a primitive type such
as integer or float. A fractional sample rate has different meaning for a composite
data type from a primitive type. For a composite data type, the fractional sample rate
really indicates the partial production or consumption of the sample. In the example
graph, one firing of node B fills

1
3

of a sample on arc BC and node C reads the

first half of the sample at every -th firing and the second half at every 2 n -

th firing. Hence, if we consider the execution order of nodes B and C, a schedule
“BBCBC” is valid since

( 2 n + 1 )

2
3

of a sample is available after node B is fired twice and

node C becomes fireable.
For primitive types, partial production or consumption is not feasible. Then
statistical interpretation is applied for a fractional rate. In the example graph, the
output sample rate of node A is 1 3 on arc AC. This means that node A produces
a single sample every three executions. Similarly node C consumes one sample
every two executions. Note that a fractional rate does not imply at which firings
samples are produced. So node C becomes fireable only after node A is executed
three times. If we are concerned about the execution order of nodes A and C only,