Synchronous data flow definition

May 31, 2007

In CLAM related papers we use to define the synchronous flow as a flow where messages get produced and consumed at predictable —if not fixed— rate. This definition relates very well with my intuitive idea of synchronicity. However, having seen examples of multi-rate data flows and having implemented dynamic schedules, I didn’t feel very comfortable with this definition. The main concern is that node’s firing does not necessarily need to be predictable.

Recently, reading some papers from Edward Lee and others I saw the light:

A synchronous data flow is a graph of synchronous nodes. Where a node is synchronous if we can specify a priori the number of input samples consumed on each input and the number of output samples produced on each output each time the node is fired.

This is a extremely simple property of the graph itself and it is independent of its scheduling strategy. But the point is that it is not so intuitively related with the synchronicity idea. This great paper from Lee and Messerschmitt shows (very formally) how to know if an iterative scheduling exists or not. The condition is simple: the rank of the graph’s incidence matrix must be the number of nodes minus one. Also, if such scheduling exist, there is an algorithm that finds it. The algorithm itself is simple to understand but not so to implement since it involves linear equations solving and exponential search.

To make it clear, an scheduling is a list of executions that gets repeated —being for one or many processors—, and necessarily needs to be iterative since an infinite stream is assumed. Of course, an iteration is a list that may include some or all the nodes many times.


One Response to “Synchronous data flow definition”

  1. sgarealestates is the best website who offers you best deal of property in chandigarh, property in panchkula, property in zirakpur and property in mohali on reasonable rates.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: