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

( )

firings of CSDF node A are merged into a single firing, an equivalent SDF
actor A' is obtained. Hence the equivalent SDF graph is obtained as shown in Fig. 8 b
where node B' is obtained by merging six firings of node B in the CSDF graph. We
denote this equivalence relation as B ≈

If p A

6 B . For an equivalent SDF node, the scalar
sample rate of a port should be determined. Let σ (

)

be the sum of elements in
vector v . The total number of samples produced or consumed on arc e of CSDF
node A per the corresponding SDF node execution is given by p

v

) σ ( prod ( e ))
dim

( A or

( prod ( e ))

) σ ( cons ( e ))
dim

. So, we can construct a topology matrix for the equivalent SDF
graph as follows:

p ( A

( cons ( e ))

⎧
⎨

) σ ( prod ( e ))
dim

p ( A

)) ,

if A = src ( e )

( prod ( e

) σ ( cons ( e ))
dim

Γ ( e , A )= (5)

− p ( A

)) ,

if A = snk ( e )

⎩

( cons ( e

0 , otherwise

We can check the sample rate consistency with this topology matrix. For the
graph in Fig. 8 b , the topology matrix and the repetition vector become:

⎛ ⎞

3 60

10

−

⎝ ⎠

Γ =

− 1

02 − 1

q G =(

, , )

2 1 2

is 2, the CSDF graph is sample rate consistent. Moreover, a valid
schedule includes two invocations of nodes A' and C, and one invocation of node
B'. This means that a valid CSDF schedule contains 6A, 6B and 2C since A ≈

Since rank of Γ

3 A

and B ≈

6 B . The deadlock detection algorithm for an SDF graph in Sect. 2.1 is
applicable for a CSDF graph, which is to construct a static schedule by simulating
the graph.

3.2 Static Scheduling and Buffer Size Reduction

One strategy of scheduling a CSDF graph is to schedule the equivalent SDF graph
and replace the execution of the equivalent node with the multiple invocations of
the original CSDF node. We can obtain the following schedule for the graph in
Fig. 8 : 2 A B 2 C 6 A 6 B 2 C . Then the minimum buffer requirement on arc AB

becomes 6. We can construct better schedules in terms of buffer requirements by
utilizing the phased operation of a CSDF node. For the case of CSDF graph of
Fig. 8 a , we can construct a better schedule as follows.

Σ 1 = =

1. Initially nodes A and B are fireable, so schedule nodes A and B: Σ 2=“AB”.

2. Since node A is the only fireable node, we schedule node A again: Σ 2=“ABA”