Data Flow Modeling and

Implementation
Introduction
• We will learn how to create data flow models, and how to implement those models in
hardware and software.
• Unlike C programs, data flow models are concurrent: they can express activities that
happen simultaneously.
• This property makes data flow well suited for a parallel hardware implementation as well
as a sequential software implementation.
• By nature, hardware is parallel and software is sequential.
• As a result, software models (C programs) are not very well suited to capture hardware
implementations, and vice versa, hardware models (RTL programs) are not a good
abstraction to describe software.
• However, designers frequently encounter situations in which they cannot predict if the
best solution for a design problem is a hardware implementation or a software
implementation.
• Trying to do both is not on option; it requires the designers to work twice as hard.
Introduction
• Signal processing domain experts are used to describe complex
systems, such as digital radios and radar processing units, using block
diagrams.
• A block diagram is a high‐level representation of the target system as
a collection of smaller functions.
• A block diagram does not specify if a component should be hardware
or software;
• We are specifically interested in digital signal processing systems.
• Such systems represent signals as streams of discrete samples rather
than continuous signal shapes.
Introduction
• Figure shows the block diagram for a simple digital signal processing system.
• It’s a pulse‐amplitude modulation (PAM) system, and it is used to transmit digital
information over bandwidth‐limited channels.
• A PAM signal is created from binary data in two steps.
• First, each word in the file needs to be mapped to PAM symbols, which are just pulses of
different heights.
Introduction
• An entire file of words will thus be converted to a stream of symbols or pulses.
• Next, the stream of pulses needs to be converted to a smooth shape using pulse‐shaping.
• Pulse‐shaping ensures that the bandwidth of the resulting PAM signal bandwidth does not exceed
the PAM symbol rate.
• The output of the pulse‐shaping unit produces many samples for each input symbol pulse, but it
is still a stream of discrete samples.
• A convolution‐based function is used to ensure the curve goes through the symbols while
providing a memory effect, which allows symbols to influence other symbols
• The final module in the block diagram is the digital‐to‐analog module, which will convert the
stream of discrete samples into a continuous signal.
Introduction
Here’s a high-level simulation model for PAM-4
Introduction
• Although this is a good model for simulation, it is not for an implementation C implicitly assumes
sequential execution
• If we observe block diagram carefully, we can see that the block diagram does not require a
sequential execution of the symbol mapping function and the pulse shaping function.
• The block diagram only specifies the flow of data in the system but not the execution order of the
functions.

• The lines between blocks represent data dependencies, and therefore, they force an ordering to
the sequence of operations
• However, unlike C, each block can execute simultaneously with other blocks.
• Another example of the difference between C and block diagrams is shown by the ‘fanout’ in the
following:
• Here, Block2 and Block3 are clearly parallel but C would execute them sequentially
Data Flow Models
• Note that, in general, it is easier to create a sequential implementation from a parallel
model than it is to create a parallel implementation from a sequential model.
• This argues in favor of Data Flow
• The following is a Data Flow model of PAM‐4:diagrams for modelling

• The bubbles, called actors, represent the functions in the block diagram
• Actors are linked together using directional lines, called queues
• The numbers on the lines represent the relative rates of communications between
modules, e.g., Map converts a 32‐bit word into 16 2‐bit symbols.
• Note that each actor works independently, i.e., it checks its input queue for the proper
number of elements and executes immediately when satisfied
Data Flow Models vs. C Programs
• Data Flow is a concurrent model (this is a major driver for their popularity), which means they can
easily be mapped to hardware or software implementations.
• Data Flow models are distributed, i.e., there is no centralized controller, i.e., each actor operates
autonomously.
• Data Flow models are modular, allowing libraries of components to be constructed and utilized in
a plug‐and‐play fashion
• Data Flow models can be analyzed,
• e.g., for deadlock conditions that can result in system lock‐up
• Deterministic, mathematical methods can be used to analyze Data Flow models, which is
generally not possible using C
• Data Flow models have been around since the early 1960s
• The 70’s and 80’s were active periods of research and development of Data Flow programming
languages and even Data Flow architectures
• NI’s Labview is a classic example of a Data Flow programming language
Tokens, Actors and Queues
• Here, we define the elements that make up a Data Flow model, and discuss a special class of Data
Flow models called Synchronous Data Flow (SDF) Graphs SDFs allow for the application of formal
analysis techniques
• A simple example:

A Data Flow model is made up of three elements:

• Actors: Contain the actual operations
• Actors have a precise beginning and end, i.e., they have bounded behavior, and they iterate that
behavior continuously
• Each iteration is called a firing, e.g., an addition is performed on each firing
Tokens, Actors and Queues
• Tokens: Carry information from one actor to another
• A token has a value, such ’1’ and ’4’ as shown below
• Queues: Unidirectional communication links that transport tokens between actors
• We assume Data Flow queues have an infinite amount of storage
• Data Flow queues are first‐in, first‐out (FIFO)
• In above example, token ’1’ is entered after token ’4’ so token ’4’ is processed first
• When a Data Flow model executes, actors read tokens from their input queues, apply an
operation and then write values to the output queue
• The execution of a Data Flow model is expressed as a sequence of concurrent actor firings
Tokens, Actors and Queues
• Data Flow models are untimed
• The firing of an actor happens instantaneously and therefore time is irrelevant
• Firings actually take non‐zero time in an actual implementation
• The execution of Data Flow models is guided only by the presence of data, i.e., an actor
can not fire until data becomes available on its inputs
• A Data Flow graph with tokens distributed across its queues is called a marking of a Data
Flow model
• A Data Flow graph goes through a series of marking when it is executed Each marking
corresponds to a different state of the system
• The distribution of tokens in the queues (marking) are the ONLY observable state in the
system (no state is maintained inside the actors)
Firing Rates, Firing Rules and Schedules

• A firing rule defines the conditions that enable an actor to fire

• In the above example, the firing rule checks that the actor’s input queues contain
at least one token
• Therefore, actors are able to check the number of tokens in each of its queues
Firing Rates, Firing Rules and Schedules
• The required number of tokens consumed and produced can be annotated on the actors inputs
and outputs, respectively

• Therefore, this information combined with a marking makes is easy to decide whether an actor
can fire.

• Data Flow actors can also consume more than one token per firing This is referred to as a multi‐
rate Data Flow graph
Synchronous Data Flow Graphs
• Synchronous Data Flow (SDF) graphs refer to systems where the number of tokens consumed and
produced per actor firing is fixed and constant
• The term synchronous refers to the fixed consumption and production rate of tokens.
• Note that SDF will not be able to handle control‐flow constructs, such as if‐then‐else statements
in C without adding special operators .
• Despite this significant limitation, SDFs are very powerful (and popular), and more importantly,
mathematical techniques can be used to verify certain properties
• The first of these properties is determinism
• The entire SDF is deterministic under the condition that all of its actors implement a deterministic
function
• Determinism guarantees that the same results will always be produced independent of the firing
order
Synchronous Data Flow Graphs
• Illustration of determinism:
Synchronous Data Flow Graphs
• As we start firing actors, tokens are transported through the graph.
• After the first firing, an interesting situation occurs: both the add actor as well as the
plus1 actor can fire.
• Going down at the left side, we assume that the plus1 actor fires first.
• Going down at the right side, we assume that the add actor fires first.
• However, regardless of this choice, the graph eventually converges to the situation
shown at the bottom.
• Why is this property so important?
• Assume for a moment that the add actor and the plus1 actor execute on two different
processors, a slow one and a fast one.
• This is the power of determinate property of SDF, it doesn’t matter which processor runs
on what actor: the results will be always the same.
• In other words, no matter what technology we are using to implement actors, the system
will work as specified as long as we implement the firing rules correctly.
Analyzing Synchronous Data Flow Graphs
• The second important property of SDF relates to an admissible schedule
• An admissible SDF is one that can run forever without deadlock (unbounded execution)
or without overflowing any of the communication queues (bounded buffer)
• Deadlock occurs when an SDF graph progresses to marking that prevents firings
• Overflow occurs when tokens are produced faster than they are consumed
• There is also a systematic method to determine whether a SDF graph is
admissible
• The method provides a closed form solution, i.e., no simulation is required
Analyzing Synchronous Data Flow Graphs
Lee proposed a method called Periodic Admissible Schedules (PASS), defined as:
• A schedule is the order in which the actors must fire
• An admissible schedule is a firing order that is deadlock‐free with bounded
buffers
• A periodic admissible schedule is a schedule that supports unbounded execution,
i.e., is periodic in the sense that the same markings will recur
• We also consider a special case called Periodic Admissible Sequential Schedules
(PASSs) that supports a microprocessor implementation with one actor firing at a
time
• There are four steps to creating a PASS for an SDF graph:
I. Create the topology matrix G of the SDF graph
II. Verify the rank of the matrix to be one less than the number of nodes in the graph
III. Determine a firing vector
IV. Try firing each actor in a round robin fashion, until the firing count given by the firing
vector is reached
Analyzing Synchronous Data Flow Graphs
Consider the following example:
• Step 1: Create a topology matrix for this graph:
• The topology matrix has as many rows as there are edges (FIFO queues) and as many columns
as there are nodes
• The entry (i, j) will be positive if the node j produces tokens onto the edge i and negative if it
consumes tokens
Analyzing Synchronous Data Flow Graphs
Step 2: The condition for a PASS to exist is that the rank of G has to be one less than the
number of nodes in the graph
• The rank of the matrix is the number of independent equations in G
• For our graph, the rank is 2 ‐‐ verify by multiplying the first column by ‐2 and the
second column by ‐1, and adding them to produce the third column

• Given that there are three nodes in the graph and the rank of the matrix is 2, a PASS is
possible
• This step effectively verifies that tokens can NOT accumulate on any edge of the graph
• The actual number of tokens can be determined by choosing a firing vector and
carrying out a matrix multiplication
Analyzing Synchronous Data Flow Graphs
• For example, the tokens produced/consumed by firing A twice and B and C zero times
is given by:

• This vector produces 4 tokens on edge(A,B) and 2 tokens on edge(A,C)

• Step 3: Determine a periodic firing vector
• The firing vector given above is not a good choice to obtain a PASS because it leaves
tokens in the system
• We are instead interested in a firing vector that leaves no tokens:

• Note that since the rank is less than the number of nodes, there are an infinite number
of solutions to the matrix equation
Analyzing Synchronous Data Flow Graphs
• Step 3: Determine a periodic firing vector (cont.)
• This is true b/c, intuitively, if firing vector (a, b, c) is a PASS, then so
should be firing vectors (2a, 2b, 2c), (3a, 3b, 3c), etc.
• Our task is to find the simplest one ‐‐ for this example, it is:

• Note that the existence of a PASS firing vector does not guarantee
that a PASS will also exist

• Here, we reversed the (A,C) edge We would find the same qPASS but
the resulting graph is deadlocked ‐‐ all nodes are waiting for each
other
Analyzing Synchronous Data Flow Graphs
Step 4: Construct a valid PASS.
• Here, we fire each node up to the number of times specified in qPASS
• Each node that is able to fire, i.e., has an adequate number of tokens, will fire
• If we find that we can fire NO more nodes, and the firing count is less than the number in
qPASS, the resulting graph is deadlocked
• Trying this out on our graph, we fire A once, and then B and C
Analyzing Synchronous Data Flow Graphs
Step 4: Construct a valid PASS.

• Try this out on the deadlocked graph ‐‐ it aborts immediately on the first iteration
because no node is able to fire successfully
• Note that the determinate property allows any ordering to be tried freely, e.g., B, C
and then A
• In some graphs (not ours), this may lead to additional PASS solutions
SDF Graphs: PAM‐4 Example
• Consider the digital pulse‐amplitude modulation system (PAM‐4) discussed earlier
• The SDF for this system consists of 4 actors, and is a multi‐rate Data Flow system:

• The first step is to construct the topology matrix G

• The queues correspond to the 3 rows and actors to the 4 columns
• The second step is to verify the rank is the number of actors minus 1
• It is easy to show that the 3 rows are independent, i.e., are not linear combinations of any other
rows
• This confirms that a PASS is possible
SDF Graphs: PAM‐4 Example
• The third step is to derive a feasible firing for the system
• The firing vector, qPASS, must yield a zero‐vector when multiplied by the topology matrix

• The fourth step is to derive a schedule ‐‐ there are two possibilities

• The first one is trivial, fire each actor in succession, from left to right Note that the queue (FIFO)
sizes are 16 and 2048
• Alternatively, we can fire FileSource and Map once and then repeat the following
• sequence: Fire PulseShape once and then fire DA 128 times
• The benefit here is the reduced queue sizes, i.e., the PulseShape input queue reduces
from 16 to 1 while the DA input queue reduces from 2048 to 128

• In general, deriving the optimal schedule is a difficult problem for complex systems
Euclid’s Algorithm as an SDF Graph
• The graph evaluates the greatest common divisor of
two numbers a and b.
• The sort actor reads two numbers, sorts them, and
copies them to the output.
• The diff actor subtracts the smallest number from the
largest one, as long as they are
• For example, assume (a0, b0)=(16,12)
• then we see the following sequence of token values.
(a1, b1)=(4,12), (a2, b2)=(8,4), (a3, b3)=(4,4),

𝑜𝑢𝑡1 𝑎 𝑏 ? 𝑎: 𝑏
Sort
𝑜𝑢𝑡2 𝑎 𝑏 ? 𝑏: 𝑎

diff 𝑜𝑢𝑡1 𝑎! 𝑏 ? 𝑎 𝑏: 𝑎;
𝑜𝑢𝑡2 𝑏;
Euclid’s Algorithm as an SDF Graph
Limitations of Data Flow Models
• SDF systems are distributed, data‐driven systems.
• They execute whenever there is data to process, and remain idle when there is nothing to do.
• However, SDF seems to have trouble to model control‐related aspects.
• Control appears in many different forms in system design, for example:
Stopping and Restarting. As we saw in the Euclid example an SDF model never terminates; it just
keeps running.
• Stopping and restarting is a control‐flow property that cannot be addressed well with SDF graphs.
Mode‐Switching. When a cell‐phone switches from one standard to the other, the processing
(which may be modeled as an SDF graph) needs to be reconfigured.
• However, the topology of an SDF graph is fixed and cannot be modified at runtime.
Exceptions. When catastrophic events happen, processing may suddenly need to be altered.
• SDF cannot model exceptions that affect the entire graph topology.
• For example, once a token enters a queue, the only way of removing it is to read the token out of
the queue.
• It is not possible to suddenly ‘empty’ the queue on a global, exceptional condition.
Limitations of Data Flow Models
• Run‐Time Conditions. A simple if‐then‐else statement (choice between two activities
depending on an external condition) is troublesome for SDF.
• An SDF node cannot simply ‘disappear’ or become inactive – it is always there.
• Moreover, we cannot generate conditional tokens, as this would violate SDF rules which
require fixed production/consumption rates.
• Thus, SDF cannot model conditional execution such as required for if‐then‐else
statements.
• There are two solutions to the problem of control flow modeling in SDF.
• The first one is to try using SDF anyhow,
• Next is emulate control flow at the cost of some modelling overhead.
Limitations of Data Flow Models
• There are two solutions to the problem of control flow modeling in SDFs
• Solution 1:
• emulate control flow on top of the SDF semantics Consider the
• stmt : if (c) then A else B

• The selector‐actor on the right routes either A or B to the output

• Note that this is not an exact match to the if‐then‐else in C because BOTH the if branch (A) and
the else (B) must execute and produce tokens
• However, it is a good match to hardware, which uses a multiplexer to select among one of several
input results
Limitations of Data Flow Models
• Solution 2: extend the SDF semantics using Boolean
Data Flow (BDF)
• BDFs ‘tune’ the production and consumption rate of a
actor according to the value of an external control token
• The condition token is distributed to two BDF
conditional fork and merge nodes, Fc and Sc
• Here, the conditional fork will fire when there is an input
token AND a condition token
• A token is produced on EITHER the upper or lower edge,
dependent on the condition token
• This is indicated by a dynamic variable p, which signifies
a conditional production rate
• The conditional merge works similarly, i.e., it fires when
there is a condition token and will consume a token on
EITHER the upper or lower edge.
DFG Performance Modelling and Transformations
• We indicated earlier that Data Flow graphs (DFGs) are untimed, i.e., our analysis did not model the
amount of time needed to complete a computation
• In this section, we describe how to use DFGs for performance analysis
• Performance estimation will be accomplished by modeling only two components: actors and queues
• Once our new modeling constructs are introduced, we then turn our attention to transformations
designed to enhance performance

• Input sample rate is the time interval between two adjacent input samples from a data stream
• For example, a digital sound system generates 44,100 samples per second
• Input sample rate defines a design constraint for the real‐time performance of the
• Data Flow system Similar constraints usually exists for output sample rate
Definitions
• We use two common metrics as measures of performance:
• Throughput: the number of samples processed per second (Note that input and output throughput may be
different)
• Latency: The time required to process a single token from input to output
DFG Performance Modelling and Transformations
The Data Flow Resource Model:

• We used the symbols on the left earlier to model DFGs

• For performance modelling, we
• Include a number within the actor symbol to model execution latency
• Replace FIFO queues with a communication channel, which includes delays
• Note that the number included in an actor represents the amount of time it takes (in clock cycles,
nanoseconds, etc) after it fires Time spent while waiting for input data is not counted
• Also note that the delay element (which replaces FIFO queues) can hold exactly one token
 DFG Performance Modelling and Transformations

• Think of delay elements as buffers with 1 unit of delay

• We can use a performance annotated DFG to evaluate its execution time
• In (a), (b) and (c) above, actor A introduces 5 units of latency while B introduces 3
units
 DFG Performance Modelling and Transformations

• The time stamp sequences on the left and right indicate when input
samples are read and when output samples are produced
• The time stamps for DFG (a) and (b) are different because of the position of
the delay element in the loop
• (a) requires the sum of execution times of A and B before producing a result
• (b) can produce a result at time stamp 3 because the delay element allows it to
execute immediately at system start time (we refer to this as transient behavior)
• In this case, the delay elements affect only the latency of the first sample
 DFG Performance Modelling and Transformations

• In contrast, (c) shows that delay elements can be positioned to enable parallelism, and
affect both latency and throughput
• Both actors can execute in parallel in (c), resulting in better performance than (a) and (b)
• The throughput of (a) and (b) is 1 sample per 8 time units, while (c) is 1 sample per 5
time units
• Similar to a pipelined system, the throughput in (c) is ultimately limited to the speed of
the slowest actor (A in this case ‐‐ B is forced to wait)
DFG Performance Modelling and Transformations
Limits on Throughput
• As indicated, the distribution of the delay elements in the loops impacts performance
• As an aid in analyzing performance, let’s define
• Loop bound as the round‐trip delay of a loop, divided by the number of delays in the loop
• Iteration bound as the largest loop bound in any loop of a DFG
• Iteration bound defines an upper limit on the best throughput of a DFG

• The loop bounds in this example are given as LBBC = 7 and LBABC = 4
• The iteration bound is 7 ‐‐ therefore, we need at least 7 time units per iteration
DFG Performance Modelling and Transformations
Limits on Throughput

• From the graph, it is clear that loop BC is the bottleneck

• Note that actors A and C have delay elements on their inputs so they can operate
in parallel
• On the other hand, actor B needs to wait for the result from C before it can fire
• The missing delay element forces actors B and C to run sequentially
• Note that linear graphs have implicit feedback loops that must be considered
DFG Performance Modelling and Transformations
Limits on Throughput
• Also note that the iteration bound is an upper limit on throughput, and in
reality, the DFG may not be able to achieve this throughput

• The DFG above (from an earlier slide) has an iteration bound (5 + 3)/2 = 4
time units, but the throughput is limited to the slowest actor at 1 sample
per 5 time units
• A nice way to think about actors and delays is to consider an actor as a
combinational circuit and a delay as a buffer or pipeline stage.
Transformations
Performance‐Enhancing Transformations
• Based on previous discussions, intuitively, it should be possible to ‘tune’ the DFG to
enhance performance, while maintaining the same functionality
• Enhancing performance either reduces latency or increases throughput or both The
following transformations will be considered:
• Multi‐rate Expansion: A transformation which converts a multi‐rate synchronous DFG to
a single‐rate synchronous DFG.
• Retiming: A transformation that redistributes the delay elements in the DFG Retiming
changes the throughput but does not change the latency or the transient behavior of the
DFG
• Pipelining: A transformation that introduces new delay elements in the DFG Pipelining
changes both the throughput and transient behavior of the DFG
• Unfolding: A transformation designed to increase parallelism by duplicating actors
Unfolding changes the throughput but not the transient behavior of the DFG
Transformations
Multi‐rate Transformation
• The following DFG shows actor A produces three tokens per firing, and actor B consumes
two tokens per firing

• After completing the steps above, we obtain the following DFG

• Here, the actors are duplicated according to their firing rates, and all multi‐rate I/O are
converted to single‐rate I/O
Transformations
Retiming Transformation
• Retiming redistributes delay elements in the DFG as a mechanism to increase
throughput
• Retiming does not introduce new delay elements
• Evaluation involves inspecting successive markings of the DFG and then selecting the one
with the best performance

• (a) has an iteration bound of 8

but produces data on intervals
of 16 because of the sequential
execution of actors A, B and C
Transformations
Retiming Transformation
• The next marking (b) is obtained by firing actor A, which consumes the delay elements
on its inputs, and produces a delay element at its output.
• This functionally equivalent configuration improves throughput to 1 sample every 11
time units by allowing actor A to run in parallel with B and C
• Firing B produces the next marking
in (c), which achieves an iteration
bound of 8 and represents the best
that can be obtained The last marking
which fires C creates a configuration
nearly equivalent to (a).
Transformations
Pipelining Transformation
• Pipelining increases the throughput at the cost of increased latency
• Pipelining augments retiming with adding delay elements

• (a) is extended with two pipeline delays in (b)

• Adding delay elements at the input increases the latency of (a) from 20 to 60
• Throughput is 20, i.e., 1 sample every 20 time units
Transformations
Pipelining Transformation

• Retiming of the pipelined graph yields (c) after firing A twice and B once,
which improves both throughput to 10 and latency to 20
• Again we see the slowest pipeline stage determines the best achievable
throughput.
Pipelining Transformation out[n]=c2×x[n−2]+c1×x[n−1]+c0×x[n]
Transformations
Unfolding Transformation
• Unfolding is very similar to the transformation carried out for multi‐rate expansion
• Here, actor A in the original DFG is replicated as needed, and interconnections and delay elements are
redistributed
• Note the original graph is single‐rate and goal is to increase sample consumption rate
• The text describes the sequence of steps that need to be applied to carry out unfolding
• (a) is unfolded two times in (b),
showing that the number of inputs
and outputs are doubled, allowing
twice as much data to be processed
per iteration
• Unfolding appears to slow it down, increasing
the size of the loop to include A0, B0,
• A1 and B1 while including only the single delay
Element
Hence, the iteration bound of a v‐unfolded graph
increases v times