Dynamic Dataflow Graphs - Signal Processing Systems - page 909

a

c

root

N2

p1 q2

for i = 1:1:N

for i = 1:1:N

(F2)

ED5(ctrl)

ED1(t_1)

p2 q1

if t_1(i) <= 0

F1 F2 F3

q2

p1

ED3(x_1) p2

p2

N1
(F1)

N3
(F3)

q1

STree Marking

root

for i = 1:1:N

for i = 1:1:N

b

if t_1(i) <= 0

N2
(F2)

F1 F2 F3

p1 q2

ED5(ctrl)

ED1(t_1)

p2 q1

STree Pruning

root
for i = 1:1:N

q2

p1

ED3(x_1) p2

for i = 1:1:N

q11

N1
(F1)

N3
(F3)

p3

q12

F3

F1

d C1( ED5 )

OG1 IG1 OG1

C2( ED4 )

P2

P1

C4( ED3 )

OG2 IG2

(N1&N3)

(N2)

IG1 OG2 IG3

C3( ED1&ED2 )

Fig. 11 Examples of ( a ) approximated dependence graph (ADG) model; ( b ) transformed ADG;
( c ) schedule tree and transformations; ( d ) process network model

The difference between the ADG in Fig. 11 a and the transformed ADG in
Fig. 11 b is that an ADG may have several input ports connected to a single output
port whilst in the transformed ADG every input port is connected to only one single
output port (in accordance with the Kahn Process Network semantics [ 35 ] ).
Parsing the STree in Fig. 11 c top-down from left to right generates a program
that gives a valid execution order (global schedule) among the functions F 1, F 2and
F 3 which is the original order given by the dSAC.
The process network in Fig. 11 d may be the result of a design space exploration,
and some optimizations. For example, process P 2 is constructed by grouping nodes
N 1and N 3intheADGinFig. 11 b . Because the behavior of process P 2 is sequential
(by default), it has to execute the functionality of nodes N 1and N 3 in sequential
order. This order is obtained from the STree in Fig. 11 c . See [ 60 ] for details.