Dynamic Dataflow Graphs - Signal Processing Systems - page 913

1 %parameter EPS 0.005

2 w=0
3 ctrl_x_5 = (N+1,0)
4 for i = 1 to N,
5

y_1[i] = F1()

6 in_2 = y_1[i]

7 x_2[i] = F2( in_2 )

8 while (in_w =

σ x ( W , ( i , w ) )

>= EPS),

9 w=w+1

11 x_3[i,w] = F3()

11 for j = i+1 to N+1,

σ y ( S 4 , ( i , w , j ) )

1 &parameter EPS 0.005 12 in_4 =

13 y_4[i,w,j] = F4( in_4 )

σ x ( S 5 , ( i , w , j ) ) 2 fori=1toN,

3 y[i] = F1()
4 x = F2( y[i] )
5 while ( x >= EPS )
6 x = F3()
7 for j = i+1 to N+1,
8 y[j] = F4( y[j-1] )
9 x = F5( x, y[j] )
10 end
11 y[i] = F6( x )
12 end
13 out = F7( x )
14 end

14 in_5_x =

15 in_5_y = y_4[i,w,j]

16 x_5[i,w,j] = F5( in_5_x, in_5_y )

17 ctrl x 5 = (i,w)

18 end

19 in_6 =

σ x ( S 6 , ( i , w ) )

20 y_6[i,w] = F6( in_6 )

21 end

22 ctrl x 5 [i] = ctrl x 5

( a , b 23 ) = ctrl x 5 [i]

,,) )
25 out = F7( in_7 )
26 end

σ
x

( S 7 , ( i ab 24 in_7 =

An example of a WLAP program The corresponding final dSAC

Fig. 15 An example of a while-loop affine program and its corresponding dynamic single
assignment program

The iterator w is associated with the while loop and is initialized with value 0,
meaning that the while loop has never been executed. The parameter captures

the value of the for-loop iterator in the enclosing while-loop and is initialized to
N

α

+

1. The parameter β is the upper bound of the while-loop iterator w . Because

α ∈ [

.. N ]

β ≥

1, the above initializations satisfy the condition that their values
are never taken by the corresponding parameters. From line 23 at the right side
in Fig. 15 , it follows that the control variable ctrl x 5 is initialized to ctrl x 5
= (N+1,0) at line 3 at the right side in Fig. 15 . Where does the control variable
ctrl x 5 come from? It comes from the construction of the dSAC. The procedure
to derive the final dSAC is largely based on [ 18 ] and its extension in Sect. 7.2 .
The problem is again that the dSAC resulting from the FADA analysis is not a
proper dSAC because it violates the property that every variable is written at most
once . The relation between writing to and reading from the control variables must
be identified by performing a dataflow analysis for the control variables, where
the writings to them occur inside a while-loop. To that end, an additional control
variable ctrl x 5 is introduced right after the while-loop, see line 22 at the right
in Fig. 15 . The new control variable is written at every iteration of for -loop i and
takes the value either of control variable ctrl x 5 assigned on the last iteration of
the while-loop, or its initial value, if the while-loop is not executed. A static exact

1 and