## 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 priorithe 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.

February 26, 2011 at 7:48 am

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.